5.3Support for Transactional Memory

Fine-grained inter-thread communication is the bane of irregular GPU code. Today’s options are grim: coarsen everything behind barriers (rewrite your algorithm) or hand-build fine-grained locks out of single-word atomics (too risky for shipping software — recall SIMT deadlock). Transactional memory offers a third way: mark a region atomic, let the hardware detect and resolve conflicts. The research question is whether TM can survive the GPU’s scale.

The GPU TM problem

Multicore TM juggles tens of largish transactions and leans on cache coherence to spot conflicts. A GPU flips every assumption: tens of thousands of tiny transactions, tracked at word granularity, on per-core caches shared by hundreds of threads — so coherence-based detection is nearly useless. New mechanisms required.

5.3.1 Kilo TM

Kilo TMKilo TMFirst GPU hardware TM: word-granularity, value-based conflict detection scaled to tens of thousands of small transactions.Glossary → (Fung et al.), the first GPU hardware TM, makes two moves:

• Value-based conflict detectionvalue-based conflict detectionValidate by re-reading a transaction's read-set from memory and comparing values — no global metadata, finest granularity.Glossary →. To validate, a transaction simply re-reads its read-set from global memory and checks the values — no global metadata, finest granularity, riding the parallel memory system. Conflicting transactions never touch each other.
• The recency bloom filterrecency bloom filterTime-ordered bloom filter compressing committing write-sets so hundreds of non-conflicting transactions commit in parallel (few kB, on-chip).Glossary →. Naive value-based detection forces serial commits; the recency bloom filter compresses committing transactions’ write-sets (using time and order) so each committer gets an approximate conflicting set — false positives allowed — enabling hundreds of non-conflicting transactions to commit in parallel. It stays a few kB, on-chip.

Aborts are a new kind of divergence

When a warp reaches tx_commit, some threads validate and some abort — the warp diverges after commit. Kilo TM handles this with a small, elegant extension to the SIMT stack: two new entry types, R (transaction Retry — records how to restart) and T (Transaction top — the current attempt), alongside ordinary N (Normal) entries. Step through one transaction where two of eight threads must retry (Fig 5.2):

Notice what the R/T mechanism buys: the winners commit once and move on, while only the losers loop back through the implicit abort edge — and ordinary branch divergence inside the transaction still uses plain N entries. The entire TM abstraction rides on the stack the GPU already had.

5.3.2 WarpTM and temporal conflict detection

Fung & Aamodt’s follow-up adds two efficiency wins:

• WarpTMWarpTMWarp-level transaction management: two-phase intra-warp conflict resolution enabling coalesced validation/commit memory accesses.Glossary → exploits the spatial locality of threads within a warp. A two-phase parallel intra-warp conflict resolution clears conflicts among a warp’s own transactions first; once resolved, their scalar validation/commit accesses coalesce into wide memory operations — finally feeding the vector-width memory system the way it wants to be fed.
• Temporal conflict detectiontemporal conflict detection (TCD)Implicitly synchronized on-chip timers timestamp reads so conflict-free read-only transactions commit without value checks.Glossary → (TCD) targets read-only transactions (common in data- structure traversals). Globally synchronized on-chip timers — each running locally, never communicating (the trait that distinguishes TCD from software timestamp schemes) — let Kilo TM infer read ordering and commit conflict-free read-only transactions without any value re-reads, slashing their memory-bandwidth cost.