Error detection and correction in content addressable memories by using bloom filters

Salvatore Pontarelli, Marco Ottavi

Research output: Contribution to journalArticle (Academic Journal)peer-review

20 Citations (Scopus)

Abstract

A content addressable memory (CAM) is an SRAM-based memory that can be accessed in parallel to search for a given search word, providing as a result the address of the matching data. Like conventional memories, a CAM can be affected by the occurrence of single event upsets (SEUs) that can alter the content of one of more memory cells causing different effects such as pseudo-HIT or pseudo-MISS events. It is well known that, because of the parallel search performed by a CAM during the query of a word, a standard error correction code could not defend it against SEU events. In this paper, we propose a method that does not require any modification to a CAM's internal structure and, therefore, can be easily applied at system level. Error detection is performed by using a probabilistic structure called 'Bloom filter, which can signal if a given data is present in the CAM. Bloom filters permit to efficiently store and query the presence of data in a set. But, while a CAM suffers from SEU induced errors, the probabilistic nature of Bloom filters has as a consequence the so called false-positive effect. This paper shows that, by combining the use of a Bloom filter with a CAM, the complementary limitations of these modules can be compensated. The combined use of a CAM and a Bloom filter is analyzed in different cases, showing that the proposed technique can be implemented with a low penalty in terms of area and power consumption.

Original languageEnglish
Article number6158642
Pages (from-to)1111-1126
Number of pages16
JournalIEEE Transactions on Computers
Volume62
Issue number6
DOIs
Publication statusPublished - 13 May 2013

Keywords

  • Bloom filter
  • content addressable memories
  • error detection and correction

Fingerprint

Dive into the research topics of 'Error detection and correction in content addressable memories by using bloom filters'. Together they form a unique fingerprint.

Cite this