Address Order Violation Detection with Parallel Counting Bloom Filters

Naruki KURATA  Ryota SHIOYA  Masahiro GOSHIMA  Shuichi SAKAI  

Publication
IEICE TRANSACTIONS on Electronics   Vol.E98-C   No.7   pp.580-593
Publication Date: 2015/07/01
Online ISSN: 1745-1353
DOI: 10.1587/transele.E98.C.580
Type of Manuscript: Special Section PAPER (Special Section on Low-Power and High-Speed Chips)
Category: 
Keyword: 
processor architecture,  load-store queue,  bloom filter,  low-energy technologies,  

Full Text: PDF>>
Buy this Article




Summary: 
To eliminate CAMs from the load/store queues, several techniques to detect memory access order violation with hash filters composed of RAMs have been proposed. This paper proposes a technique with parallel counting Bloom filters (PCBF). A Bloom filter has extremely low false positive rates owing to multiple hash functions. Although some existing researches claim the use of Bloom filters, none of them make mention to multiple hash functions. This paper also addresses the problem relevant to the variety of access sizes of load/store instructions. The evaluation results show that our technique, with only 2720-bit Bloom filters, achieves a relative IPC of 99.0% while the area and power consumption are greatly reduced to 14.3% and 22.0% compared to a conventional model with CAMs. The filter is much smaller than usual branch predictors.