Design and Implementation of Signatures for Transactional Memory Systems

TRANSACTIONAL MEMORY (TM) systems ease multithreaded application development by giving the programmer 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 access 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 of k parallel Bloom filters with one hash function each, and the same total state, can be implemented with inexpensive single-ported memories, being about 8x more area-efficient for typical signature designs. Furthermore, we show that true and parallel Bloom signatures perform ASYMPTOTICALLY the same in theory, and APPROXIMATELY the same in a practical setting with LogTM-SE under a variety of benchmarks. We perform a thorough evaluation of different Bloom signatures and find designs that achieve both higher performance than the previously recommended ones (reducing the execution time by a factor of two in some benchmarks), and are more robust, by exploiting the type of hash functions used.

Additionally, we describe, analyze and evaluate three novel signature designs. First, CUCKOO-BLOOM signatures adapt cuckoo hashing for hardware implementation and build an accurate hash-table based representation of small read/write sets (an important and common case), and morph dynamically into a Bloom filter as the sets get large, but do not support set intersection or union. Second, HASH-BLOOM signatures use a simpler hash-table based representation and morph into a Bloom filter more gradually than Cuckoo-Bloom signatures, outperforming similar Bloom signature designs for both small and large read/write sets. And third, ADAPTIVE BLOOM signatures, which use predictors to determine the optimal number of hash functions to use in a Bloom signature dynamically.

Download this report (PDF)

Return to tech report index