在多核心系統上之高效能雙層計數布隆過濾器

Abstract

在對稱式多核心系統中，基於廣播的窺探式協議被很廣泛地用於維持快取記憶體一致性。然而窺探式協議盲目地傳播整個系統的數據共享訊息，並且通常導致十分大量而不必要的資料傳輸及快取記憶體中的資料搜尋。本文提出了一種新的硬體架構：雙層計數布隆過濾器，並且使用該架構過濾在對稱式多核心系統中不必要的資料管理。透過階層式雜湊函數的設計，雙層計數布隆過濾器可以管理較大的檢索空間，並且有效地增加成功過濾的比例。相較於傳統的布隆過濾器，雙層計數布隆過濾器可以過濾掉 81.99% 更多的不必要的快取記憶體資料搜尋，並使用 18.75% 更少的記憶體。當應用於階層式共享匯流排時，雙層計數布隆過濾器可以較傳統布隆過濾器過濾 58% 更多的冗餘本地資料傳輸和 1.86 倍的冗餘遠距資料傳輸。

The broadcast-based snoopy protocol is a widely used scheme to maintain cache coherence in a SMP multicore system. However, the broadcasting snoopy protocol blindly disseminates the data sharing information across the system, and usually causes a significant amount of unnecessary data transfers on the interconnection and data searches on local caches. This paper proposes a novel architecture of Double Layer Counting Bloom Filter (DLCBF), and uses DLCBF to screen out the unnecessary data management in a SMP system. By using the two-layer hierarchical structure of the hash function, DLCBF can manage a larger query space and effectively increase the successful filter rates. When compared to conventional Bloom filters, the DLCBF can filter out 81.99% more unnecessary cache searches and use 18.75% less memory. When applied on a hierarchical shared bus in a SMP system, the DLCBF can filter out 58% more redundant local data transmissions and 1.86X remote data transmissions than conventional Bloom filters.