An Effective Hybrid Transactional Memory System with Strong Isolation Guarantees

This paper proposes SigTM, a hybrid TM implementation that features lazy CD/CR as well as software maintained write sets. Hardware cache coherence and cache tags are not changed. The processor is extended with the capability of reading and writing RS and WS signatures. Incoming coherence requests are also tested with the signature to detect conflicts.

SigTM follows the STM methodology of instrumenting read and write instructions. Instead of providing fast and slow paths, as most hybird TM does, SigTM uses hardware to accelerate STM, and has only one mode of execution. The read set is maintained only on hardware as the read signature. The write set is maintained in both hardware signature, and in a software hash table. Transaction commit and abort are handled by software runtime. Conflict detection is performed on the hardware level using cache coherence protocol.

In the transactional load handler, SigTM first searches the store signature. If a hit is produced, then the load is fulfilled from the write set. Otherwise, the address is inserted into the read signature, and a load instruction is issued.

In the transactional store handler, SigTM inserts the store address into the store signature, and inserts the (addr., data) into the software hash table. No hardware store on the target address is issued.

On cache line invalidation, SigTM checks whether the address is in the read signature. If the result is positive, then the transaction aborts. The write signature is not checked (even not NACKed).

In the pre-commit handler, SigTM validates its write set while keeping an eye on the conflicting pre-commits and read phase transactions. Write set validation is standard FOCC: SigTM tries to obtain exclusive permission for every cache line in its write set. In the meantime, four events may possibly occur: (1) A read-exclusive request comes from another processor and hits the write signature. This implies another processor is also performing pre-commit. The current transaction tries to serialize after the former by restarting the validation. (2) A read-shared request comes from another processor and hits the write signature. This implies another reader transaction establishes a new dependency with the current transaction. In this case, the validating transaction also restarts validation. (3) The read-exclusive request times out because of NACK. This implies another transaction is undergoing write back phase. The current transaction can only serialize after it by either waiting for a while, or restarting the validation process. (4) A read-exclusive request comes from another processor and hits the read signature. This implies another processor is performing write validation, and the current transaction has a read dependency with its write back phase. In this case the current transaction can only abort. Note that no global commit lock is acquired during pre-commit. Although the paper mentions a global commit lock, it is in the base HTM design and does not appear in SigTM.

I am not sure whether (1) will cause livelock, because two validating transactions could repeatedly cause the other to restart validation without making any progress. The same may also be true for (2)(3) if a hot data item is repeatedly being read/written, but in (2) and (3) at least some progress is made. Maybe directly locking the write set and read set during pre-commit is better

Once pre-commit succeeds, the transaction becomes “invincible” in a sense that it can no longer abort. The write set is locked, such that all coherence requests will be NACKed. (The paper did not mention what if a read request is NACKed during the read phase). Then the commit handler performs write back for all write set items. Once finished, all signatures are cleared and coherence check for read/write sets are disabled.