CPU的高速緩存存儲器知識整理

基于緩存的存儲器層次結構

基于緩存的存儲器層次結構行之有效，是因為較慢的存儲設備比較快的存儲設備更便宜，還因為程序往往展示局部性：

時間局部性：被引用過一次的存儲器的位置很可能在不遠的將來被再次引用。

空間局部性：如果一個存儲器位置被引用了一次，那么程序很可能在不遠的將來引用附近的一個存儲器位置。

通用高速緩存存儲器結構

一個通用的高速緩存存儲器會有S = 2 ^ s個set（組）

每個set含有E個line（既通常所說的cache line）

每個line又包含1位vaild bit、 t位tag、B = 2 ^ b bytes cache block（真正存儲數據的地方）。

通常我們說的cache line 64位 32位，實際上是說的cache line中cache block是64位32位。

假設我們的存儲器地址有m位，共M = 2^m個不同的地址。我們看一下各個變量之間的關系。

cache緩存數據的大小C = (sizeof set * number of set) = (size of block * lines a set) * number of set = B * E * S

內存大小2^m Cache line大小2^b 內存的cache line個數2^(m-b)

2^(m-b)個cache line分到2^s個set里， 每個set會有2^(m - b –s)個cache line，這個數字不是E，是指會有2^(m – b –s)個cache line落到這個set 里面，那么就需要有m-b-s位tag，標記出當前是哪個cache line落到這個set里面了。也就是說t = m - b –s。

如上圖所示，m位地址的內存，需要s位做索引，選set，t位做tag，選cache line，然后b 位做偏移取具體地址的內存。

高速緩存的映射

高速緩存確定一個請求是否命中，然后抽取出被請求的字的過程，分為三步1）組選擇2）行匹配3）字抽取。

直接映射

直接映射每個組只有一行E=1

選組

地址中取s bits選組

選行

地址中取t bits與cache line中t bits tag匹配，匹配則命中，不匹配則cache miss

字抽取

地址中的b bits就是cache line中偏移，在命中的cache line中的取字。

?

直接映射不命中時，不需要什么策略，直接把索引的組中的cache line替換掉即可。

?

組相連映射

組相連映射中，一個組包括多個cache line，目前常見的有四路組相連映射，16路組相連映射，即一個set中有4個或16個cache line。對比直接映射，set 個數要比直接映射的少。因此s會小，相應的落到每個set中的cache line會多，因此t會大。

選組

組相連映射的組選擇與直接映射一致。

選行

cache line的選擇時，因為一個set中有多個cache line，因此需要搜索set中的每個cache line的tag，對比檢查是否命中。

字抽取

與直接映射一致

?

組相連映射對于一個index就會有多個行與之相對應，比較每行的tag是否與想要的地址相符合，這樣就會大大增加命中的幾率，避免了一小段程序中頻繁cache失效的問題。

組相連映射不命中時，由于索引到的組中會有多個cache line，因此會有多種算法選擇到底替換哪個cache line。

?

全相連映射

全相連映射就是組相連映射只有一個組的情況。

選組

全相連映射組選擇很簡單，只有一個組，不需要組索引，s = 0，地址只被劃分為一個標記tag，和一個偏移。

選行

全相連映射cache line選擇時，需要多緩存中的所有cache line進行搜索對比。

字抽取

與之前一致

?

全相連映射需要大量的搜索cache line進行對比，導致構造一個又大又快的全相連高速緩存很困難，而且很昂貴。因此全相連緩存只適合做小的高速緩存，比如TLB。

Core i7的高速緩存特性

?

以上內容來自《深入理解計算機系統》6.4

以下內容來自互聯網

?

幾種cache方式

Virtual index virtual tagged

邏輯cache，Virtual index virtual tagged是純粹用虛擬地址來尋址，邏輯地址索引邏輯地址tag，這種方式帶來了很多的問題，每一行數據在原有tag的基礎上都要將進程標識加上以區分多個進程之間的相同地址，而在 處理共享內存時也比較麻煩，共享內存在不同的進程中的虛擬地址不相同，如何同步是個問題。

Physical index physical tagged

物理cache，Physical index physical tagged，物理地址索引和物理地址tag，是一種最容易理解的操作方式，cache針對物理地址進行操作，簡單粗暴，而且不會有歧義。但是這種方式的缺陷也很明顯，在多進程操作系統 中，每個進程擁有自己獨立的地址空間，指令和代碼都是以虛擬地址的方式存在，cpu發出的memory access的指令都是以虛擬地址的方式發出，這樣的話，對于每一個memory access的操作，都要先等待MMU將虛擬地址翻譯為物理地址，這是一種串行的方式，效率較低。

virtual index physical tagged

現在比較多的是采用virtual index physical tagged的方式，virtual index的含義是當cpu發出一個地址請求之后，低位地址去和cache中的index匹配， physical tagged是指虛擬地址的高位地址去和mmu中的頁表匹配以拿到物理地址（index和取物理地址這兩個過程是并行的），然后用從mmu中取到的物理地 址作為tag（或者tag的一部分）去和cache line的tag位匹配，這樣既保證了同一地址在cache中的唯一性（有個例外，cache alias）又能將mmu和cache并行工作，提高了效率。

這種方式帶來的唯一問題就是cache alias，即一個物理地址緩存到兩個cache line中。當進程間通過共享內存方式通信，或者一個進程通過mmap的方式內核與應用層共享內存，就會出現同同一塊物理內存，以多個虛擬地址訪問的情況。就容易導致一塊物理內存緩存到兩個cache line中。

由于共享內存是頁對其的，因此多個進程空間的共享內存，或者內核態用戶態的共享內存，其物理地址不同，但其頁偏移是相同的。

假如頁大小為P = 2^p 字節，cache line為 C = 2^c 字節，那么共享內存的不同虛擬地址其低p位是一致的，假如地址0 -> c位用于block offset，c -> p 位用于set index，那么就可以避免cache alias的問題。

但如果set index 位數 > p -c ，那肯定會出現cache alias的問題，因為同一塊物理內存，不同的虛擬地址，其set index不同。

針對于cache alias問題，目前的方案是由操作系統來保證，對于同一物理地址在不同進程空間的虛擬地址，要保證他們index相同，落在同一個set，就需要保證他們虛擬地址的差值是cache大小的整數倍。同時已經有些cpu廠商在開發監視模塊，試圖在硬件層面解決類似的同步問題。