Implementing Signatures for Transactional Memory
Daniel Sánchez, Luke Yen, Mark D. Hill, Karthikeyan Sankaralingam · 2007
Transactional Memory (TM) systems ease multithreaded application development by giving the program-mer the ability to specify that some regions of code, called transactions, must be executed atomically. To achieve high efficiency, TM systems optimistically try to execute multiple transactions concurrently and either stall or abort some of them if a conflict occurs. A conflict happens if two or more transactions ac-cess to the same memory address, and at least one of the accesses is a write. TM systems must track the read and write sets —items read and written during a transaction — to detect possible conflicts. Several TMs, including Bulk, LogTM-SE, BulkSC, and SigTM, represent read and write sets with signatures, which allow unbounded read/write sets to be summarized in bounded hardware at a performance cost of false positives (conflicts detected when none actually existed). This study addresses the aspects of signature design and implementation for conflict detection in TM systems. We first cover the design of Bloom signatures (i.e. signatures implemented with Bloom filters), identifying their three design dimensions: size, number of hash functions, and type of hash functions. We find that true Bloom signatures, implemented with a k hash function Bloom filter, require k-ported SRAMs, which are not area efficient (for k ≥ 2). Instead, parallel Bloom signatures, which consist