《現代體系結構上的UNIX系統：核心程式員的對稱多處理和緩存技術（修訂版）》——2.4 雙路組相聯高速緩存

本節書摘來自異步社群《現代體系結構上的unix系統：核心程式員的對稱多處理和緩存技術（修訂版）》一書中的第2章，第2.4節，作者：【美】curt schimmel著，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視

雙路組相聯高速緩存（two-way set associative cache）類似于直接映射高速緩存，不同之處在于散列函數算出的索引指向高速緩存中可能儲存資料的一組帶有兩行的高速緩存。在同一組内，每一行高速緩存都有它自己的标記，這意味着高速緩存可以同時儲存經雜湊演算法算出相同索引的兩個不同位址的資料。intel pentium的片上資料高速緩存就是雙路組相聯高速緩存。它總共儲存有8 kb的資料，每行32位元組。這意味着高速緩存中總共有256行（8192位元組÷32位元組/行），組成128組（256行÷2行/組）。圖2-16描繪出了這樣的一個高速緩存。

在查找操作期間，散列函數算出的索引指向一組兩行可以儲存資料的高速緩存。被索引的一組兩行高速緩存中的标記和位址同時進行比較，以檢視是否命中了兩行中的某一行（組内所有行的标記并行比較，進而不會因采用串行比較而降低高速緩存的通路速度）。雙路組相聯高速緩存的目的是，減少直接映射高速緩存中兩個不同位址經散列計算得出相同的索引值時發生的高速緩存颠簸。在雙路組相聯高速緩存中，這兩個不同的位址都儲存在高速緩存中。使用這種類型高速緩存的其他處理器還有intel i860 xr以及80486的外部高速緩存。

現在就很清楚為什麼直接映射高速緩存也稱為單路組相聯高速緩存了。“單路”和“雙路”的說法是指每一組中高速緩存行的數量（在高速緩存内所有的組都有相同數量的行）。“相聯”一詞則是指實際上這一組高速緩存就是以内容編址（content-addressable）的或者說相聯（associative）的一個存儲器，因為它是通過對照組内高速緩存行的位置（或者位址）來檢查标記的内容進而判斷出一次命中的。直接映射高速緩存是n路組相聯高速緩存的一種退化形式，因為每一個相聯組中隻有一行高速緩存。

配合雙路組相聯高速緩存的雜湊演算法和配合直接映射高速緩存的雜湊演算法相同，差別在于前者所需的位數更少，因為對于總量相同的高速緩存存儲器來說，雙路組相聯高速緩存中的組數隻有直接映射高速緩存的一半。是以用于圖2-16中高速緩存的雜湊演算法就隻使用“位<11..5>”來選擇組。和以前一樣，“位<4..0>”選擇高速緩存行内的位元組（因為一行有32位元組）。

替換政策稍微複雜一些。采用直接映射高速緩存時，在一次缺失操作期間，載入的高速緩存行必須放入将被索引的位置，進而可以在未來的查找操作期間找到。這一行就在雜湊演算法所索引的高速緩存行組内。但是采用雙路組相聯高速緩存時，現在組内有兩行都可以選擇用來替換。兩行中的任何一行都可以被替換，因為組内的兩行在查找操作期間都可以搜尋到。在理想情況下，最好替換在最長時間内不會被再次引用的行，因為這能提高高速緩存的整體命中率。遺憾的是，沒有辦法知道程式未來的引用模式。時間局部性表明，在組内宜采取lru替換的做法，是以大多數實作（如intel 80486 外部高速緩存）都利用了這種方法。這種做法不但易于實作，而且效果相當不錯。給每個組加上一個額外的位（稱為mru，代表“最近使用”）就可以實作這種方法。每次在一組内出現一次命中時，mru位就被更新，以反映該組内的哪一行産生了命中。當組内的一行必須被替換的時候，高速緩存首先檢查其中是否有一行被标記為無效。如果有，那麼就替換那一行。如果兩行都是有效的，那麼mru位就指出上次使用的是那一行，于是就選擇替換另一行。然後再更新mru位來指出被替換的行。

雙路組相聯高速緩存的總結

雙路組相聯高速緩存通過索引帶有兩行的一組可能儲存資料的高速緩存行，來嘗試獲得比直接映射高速緩存更好的高速緩存性能。雙路組相聯高速緩存實作起來要稍微複雜和昂貴一些，因為必須并行比較一組内兩行的标記，而且需要一種更複雜的替換政策。

它相對于直接映射高速緩存的優勢在于可以減少高速緩存颠簸的現象。如果在一個程序的局部引用中多個位址得出了同一個索引，那麼這兩個位址會同時被高速緩存，而直接映射高速緩存卻一定要替換該行。注意，雙路組相聯高速緩存的性能絕對不會低于行數相同的直接映射高速緩存。在最差的情況下，如果程式産生位址的順序是每個位址索引唯一一行，那麼雙路組相聯高速緩存的性能就和直接映射高速緩存一樣。另一方面，如果局部引用是由産生備援索引的多個位址所構成的，那麼雙路組相聯高速緩存的命中率會更高，因為它能同時緩存着産生相同索引的兩個不同位址的資料。