Implementing Signatures for Transactional Memory

| Sorted by Date | Classified by Publication Type | Classified by Research Category |

Daniel Sanchez, Luke Yen, Mark D. Hill, and Karthikeyan Sankaralingam. Implementing Signatures for Transactional Memory. In Proceedings of the 40th Annual International Symposium on Microarchitecture, MICRO, December 2007.

Download

[PDF] [HTML]

Abstract

Transactional Memory (TM) systems must track the read and writesets---items read and written during a transaction---to detectconflicts among concurrent transactions. Several TMs use signatures,which summarize unbounded read/write sets in bounded hardware at aperformance cost of false positives (conflicts detected when noneexists).This paper examines different organizations to achievehardware-efficient and accurate TM signatures. First, we find thatimplementing each signature with a single $k$-hash-function Bloomfilter (True Bloom signature) is inefficient, as it requiresmulti-ported SRAMs. Instead, we advocate using $k$single-hash-function Bloom filters in parallel (Parallel Bloomsignature), using area-efficient single-ported SRAMs. Our formalanalysis shows that both organizations perform equally well in theoryand our simulation-based evaluation shows this to hold approximatelyin practice. We also show that by choosing high-quality hash functionswe can achieve signature designs noticeably more accurate than thepreviously proposed implementations. Finally, we adapt Pagh andRodler's cuckoo hashing to implement Cuckoo-Bloom signatures. Whilethis representation does not support set intersection, it mitigatesfalse positives for the common case of small read/write sets andperforms like a Bloom filter for large sets.

Additional Information

This is a test of the extra info broadcasting system.

BibTeX

 @inproceedings{micro2007:tmsig,
  author =       {Daniel Sanchez and Luke Yen and Mark D. Hill and Karthikeyan Sankaralingam},
  title =        "{Implementing Signatures for Transactional Memory}",
  booktitle =    "{Proceedings of the 40th Annual International Symposium on Microarchitecture, MICRO}",
  year =         2007,
  month =        {December},
  abstract = {
 Transactional Memory (TM) systems must track the read and write
 sets---items read and written during a transaction---to detect
 conflicts among concurrent transactions. Several TMs use signatures,
 which summarize unbounded read/write sets in bounded hardware at a
 performance cost of false positives (conflicts detected when none
 exists).
 This paper examines different organizations to achieve
 hardware-efficient and accurate TM signatures. First, we find that
 implementing each signature with a single $k$-hash-function Bloom
 filter (True Bloom signature) is inefficient, as it requires
 multi-ported SRAMs. Instead, we advocate using $k$
 single-hash-function Bloom filters in parallel (Parallel Bloom
 signature), using area-efficient single-ported SRAMs. Our formal
 analysis shows that both organizations perform equally well in theory
 and our simulation-based evaluation shows this to hold approximately
 in practice. We also show that by choosing high-quality hash functions
 we can achieve signature designs noticeably more accurate than the
 previously proposed implementations. Finally, we adapt Pagh and
 Rodler's cuckoo hashing to implement Cuckoo-Bloom signatures. While
 this representation does not support set intersection, it mitigates
 false positives for the common case of small read/write sets and
 performs like a Bloom filter for large sets.
 },
  bib_dl_pdf = {http://www.cs.wisc.edu/multifacet/papers/micro07_signatures.pdf},
  bib_dl = {http://www.cs.wisc.edu/multifacet/papers/by_topic#topic_transactional_memory},
  bib_pubtype = {Refereed Conference},
  bib_rescat = {Architecture}
  bib_extra_info = {This is a test of the extra info broadcasting system.}
 }

Generated by bib.pl (written by Patrick Riley ) on Thu Mar 04, 2021 10:09:29 time=1207019082