Implementing Signatures for Transactional Memory
| Sorted by Date | Classified by Publication Type | Classified by Project |
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
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 = {proj-opinion}
bib_extra_info = {This is a test of the extra info broadcasting system.}
}
Generated by bib.pl (written by Patrick Riley ) on Sun Sep 26, 2021 16:14:28 time=1207019082