Single Event Transient tolerant Count Min Sketches. (February 2022)

• Record Type: Journal Article
• Authors: Zhu, Jinhua; Jin, Jie; Gao, Zhen; Reviriego, Pedro
• Is Part Of: Microelectronics and reliability. Volume 129(2022)
• Publication Date: 2022-02
• Subjects: Count Min Sketch -- Fault tolerance -- Frequency estimation -- Single Event Transients; Electronic apparatus and appliances -- Reliability -- Periodicals; Miniature electronic equipment -- Periodicals; Appareils électroniques -- Fiabilité -- Périodiques; Équipement électronique miniaturisé -- Périodiques; Electronic apparatus and appliances -- Reliability; Miniature electronic equipment; Periodicals; 621.3815
• DOI: 10.1016/j.microrel.2022.114486
• Languages: English
• ISSNs: 0026-2714

Abstract

Abstract: Frequency estimation is a common operation in big data processing. In many big data applications, computing the exact data frequency is not practical as it requires a large computational effort. Instead, a reasonably accurate estimate is commonly used. The Count Min Sketch (CMS) is a popular method for frequency estimation due to its simple implementation and low memory requirements. However, Single Event Transients (SETs) can affect the logic functions of the CMS. Based on our previous research, nearly half of the SETs will lead to CMS estimation errors in the worst case. Moreover, the most frequent elements are more likely to be underestimated when SETs occur, which is not acceptable in practice. Therefore, this paper proposes several fault-tolerant schemes to protect the CMS against SETs, especially to avoid underestimation. In particular, space redundancy-based schemes and partial time redundancy-based schemes are proposed, and the probabilities for underestimation and overestimation are analyzed theoretically. Experiments are performed to compare the reliability of the CMS protected by different schemes and validate the theoretical predictions. Finally, the selection of the best CMS parameters for practical applications is discussed with a comprehensive analysis of the overhead and performance of the different protection schemes. Highlights: Innovative: proposing anti-single-event-transient schemes for Count Min Sketch Reliable: each scheme can completely eliminate the unacceptable fault Effective: compared with triple modular redundancy, our schemes need less overhead Optional: reasonable selection of schemes for time-limited or space-limited systems