RT Conference Proceedings
T1 Multiset Signatures for Transactional Memory
A1 Quislant-del-Barrio, Ricardo
A1 Gutiérrez-Carrasco, Eladio Damián
A1 Plata-González, Óscar Guillermo
A1 López-Zapata, Emilio
K1 Ordenadores - Memorias
AB Transactional Memory (TM) systems must record the memory locations read and written (read and write sets) by concurrent transactions in order to detect conflicts. Some TM implementations use signatures for this purpose, which summarize read and write sets in bounded hardware at the cost of false positives (detection of non-existing conflicts).Read/write signatures are usually implemented as two separate Bloom filters with the same size. In contrast, transactions usually exhibit read/write sets of uneven cardinality, where read sets use to be larger than write sets. Thus, the read filter populates earlier than the write one and, consequently the read signature false positive rate may be high while the write filter has still a low occupation.In this paper, a multiset signature design is proposed which records both the read and write sets in the same Bloom filter without adding significant hardware complexity. Several designs of multiset signatures are analyzed and evaluated. New problems arise related to hardware complexity and the existence of cross false positives, i.e. new false positives coming from the fact that both sets share the same filter. Additionally, multiset signatures are enhanced using locality-sensitive hashing, proposed by the authors in a previous work. Experimental results show that the multiset approach is able to reduce the false positive rate and improve the execution performance in most of the tested codes, without increasing the required hardware area in a noticeable amount.
PB ACM
YR 2011
FD 2011
LK https://hdl.handle.net/10630/33098
UL https://hdl.handle.net/10630/33098
LA eng
NO Ricardo Quislant; Gutierrez; Oscar Plata; Emilio Zapata. Multiset Signatures for Transactional Memory. En International Conference on Supercomputing (ICS'11), pp. 43 - 52. 2011.
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 22 ene 2026