Reduce Data Coherence Cost with An Area Efficient Double Layer Counting Bloom Filter

Abstract

The snoopy protocol is a widely used scheme to maintain cache coherence. However, the protocol requires a broadcast scheme and forces substantial unnecessary data searches at the local cache. This paper proposes a novel Double Layer Counting Bloom Filter (DLCBF) to significantly reduce the redundant data searches and transmission. The DLCBF implements an extra layer of hash function and the counting feature at each filter entry. By using the hierarchical structure of the hash function, DLCBF can effectively increase the successful filter rates while requiring a smaller memory usage than the conventional Bloom filters. Experimental results show that the DLCBF can screen out 4.05X of unnecessary cache searches and use 18.75% less memory compared to conventional Bloom filters. The DLCBF is also used to filter out the redundant data transmission on a hierarchical shared bus. Simulation results show that the DLCBF outperforms conventional filters by 58% for local transmissions and 1.86X for remote transmissions.