自制一塊 CPU Cache！

象山公園??

理想情況下，我們希望擁有無限大的內存容量，這樣就可以立刻訪問任何一個特定的機器字，但我們不得不認識到有可能需要構建分層結構的存儲器，每一層次容量都要大于前一層次，但其訪問速度也要更慢一些。

早在計算機剛被發(fā)明出來的時候，那些計算科學界的先驅們就已經預測到之后的計算機結構。

他們覺得以后的程序員們肯定都會幻想著擁有無限容量甚至是無限數量的快速存儲器。

但是理想總是很豐滿，現實很骨感。在實際的計算機系統(tǒng)中，并不可能擁有程序員所幻想的那種存儲器。

所以一系列的計算機科學家們只能嘗試不斷提出更為經濟型的解決方案。從而，便有了所謂存儲器層級結構這樣的東西。?1??

事實上，存儲器層級結構的提出是存在重要背景的。計算機由于其使用者的特殊性，所以往往都會存在一些局域性原理。

局域性原理意味著大多數的計算機程序不會均衡的去訪問所有代碼和數據，計算機的執(zhí)行并不是一個等概率事件。

所以往往可以利用計算機程序的局域性原理去在性能和成本上對系統(tǒng)結構做出取舍和折中。

下圖是一個典型的存儲器層次結構，可以看出為了實現性能和成本上的折衷，存儲器層次結構會由不同速度、不同大小的存儲器組成。

這些不同的存儲器擁有不同的大小和速度，在存儲器系統(tǒng)中也位于不同的地位。

一般而言，存儲器級別離處理器越遠，速度越慢，容量越大。而越接近處理器，容量就越小，速度越快，每字節(jié)的成本也就越高。

科學家是想實現一種存儲器結構，能夠每字節(jié)的成本與最便宜的存儲器相當，而速度則與最快速的級別相當。這看起來的確是一個非常劃算和高性價比的買賣。

除此之外，一般這樣的存儲器結構中，還存在這樣一種特征。那就是低層次存儲器中的數據一般是上一級存儲器中數據的超集。

之所以這樣設計，是因為我們知道存儲器性能跟處理器性能之間存在巨大的差距。這也是程序員們渴求快速存儲器的原因。

當在緩存中找不到某一個字時，就需要從結構層次更低的存儲器中去尋找這個字。這樣一來，再結合空間局域性原理，我們就能夠很容易的通過對緩存塊的標記來快速的從存儲器中找到程序所需要的數據。

所以在設計存儲器的層次結構時，需要對緩存的安排做出重要的決策。

這些決策會決定哪些數據塊會可以放在緩存中。這就是計算機教材里常說的組相聯(lián)、全相聯(lián)的概念。

具體的描述可以看我這篇故事文：半夜，滴滴司機問我會LRU嗎？?放幾張精美圖幫助大家回憶回憶。

直接映像，主存單元中的區(qū)塊與緩存中內存塊的關系是固定的，主存中的內存塊只會存放在高速緩存存儲器中的相同塊號。

因此，只要主存地址中的主存區(qū)號與緩存中的主存區(qū)號相同，則表明訪問緩存命中。

全相聯(lián)與直接映像就是兩個極端，一個只能整個區(qū)塊進行對應，一個就允許任意主存的塊調入高速緩存存儲器中任意的塊。

組相連方式就是將主存和高速緩存存儲器中的塊再分成組，組之間采用直接映像方式，而組內的塊則采用全相聯(lián)映像方式。?2??

從原理上來看，要緩存一份只讀數據其實是一件很容易的事情，因為本身緩存和主存儲器中備份是一致的。

問題難就難在緩存的寫入。如何保證緩存和存儲器中的備份數據一致是一個難點。一般而言也會有緩存寫入的策略:

直寫緩存

它在更新緩存中數據的同時，會同步寫入主存儲器，更新雙方的數據

回寫緩存

它只更新緩存中的數據，但當緩存中的數據塊將要被替換時，再將其復制回主存儲器

當然了，由于緩存和主存儲器本身就會存在性能和速度的問題，所以在寫入的時候還需要依賴寫緩沖區(qū)。

需要寫入主存儲器的數據應該先被丟到緩沖區(qū)中，這樣就可以及時釋放緩存，而不需要等待主存儲器的寫入時間。

說到這，既然存在緩存和主存儲器同步的問題，那么其實就必然存在緩沖未命中的問題。

這就涉及到一個指標，缺失率。其實就是未命中率。也就是目標數據能夠在緩存中找到的概率。

一般而言，緩存未命中有一下三種場景：

• 強制缺失，意味著這是第一次對某個數據塊的訪問，這個數據塊開始不在緩存中，需要從主存中將該數據調入緩存。
• 容量缺失，顧名思義就是由于容量不足，導致某些在程序運行期間需要的數據塊無法一次性放入緩存，需要下一次被調用，從而就會導致容量缺失。
• 沖突缺失，當緩存置換策略不是全相聯(lián)策略時，那么當多個數據塊被映射到同一個塊，那么對不同數據塊多訪問就會混雜在一起。這個數據塊就有可能被放棄，下一次再被調入，這時候就會發(fā)生沖突缺失。

其實除了這三種場景之外，當存在多個處理器對應的多個緩存時，還會存在一致性缺失的問題。?3??

因此，為了解決不同場景下所帶來的緩存缺失問題，需要從幾個方面去優(yōu)化緩存結構，來獲得更高的命中率。

增大緩存塊以降低強制缺失

這應該是最容易優(yōu)化的一個點，由于數據塊可能第一次訪問時不在緩存中會導致強制缺失。

那么理論上增大緩存塊，在一個塊中存放更多的數據，由于空間局域性，就可以在一定程度上降低強制缺失。

但是若塊的大小過大，卻會增大容量缺失和沖突缺失的概率。所以選擇合適的塊大小是一個值得權衡的問題。

增大緩存以降低容量缺失

這同樣也是一個顯而易見的可以用來降低容量缺失的方法。但是緩存過大可能會影響數據的命中時間，同時也會造成成本的增加。

提高相聯(lián)程度以降低沖突缺失

很明顯，當緩存塊的映射策略不同時，相聯(lián)程度越低，所產生的沖突缺失也就越大。

因此可以通過采用相聯(lián)程度更高的策略來降低沖突缺失。

采用多級緩存以降低缺失代價

可以發(fā)現，存儲器層次結構的主要特點，其實就是在處理器與主存儲器之間存在多個速度不同大小不一的緩存。

這些多級緩存存在的目的就是為了在靠近處理器那頭能夠跟上處理器的高頻速度，在靠近主存儲器那頭獲得接近主存的容量。

原因就在于多級緩存能夠在不同級別的層次中分別降低不同類型的缺失。這樣使得總體的缺失率最低。

提高讀取缺失優(yōu)先級

我們在上面說到過，一般緩存向主存儲器寫入的時候，中間會使用一個寫緩存區(qū)。

當需要向主存儲器中寫入數據時，會先寫入緩存區(qū)，之后等待合適時機再將緩存區(qū)中的數據寫回主存儲器。

而在這個期間，可能某個數據剛寫入緩存區(qū)，還沒寫入到主存儲器，這時候又需要訪問該數據。

這個時候，若讀取優(yōu)先級低于寫入優(yōu)先級，那么此時會優(yōu)先執(zhí)行寫入邏輯，則需要等待緩沖區(qū)寫入主存，再進行數據的讀取。

這很明顯不是一件高效的事情。所以往往會設置讀取優(yōu)先級高于寫入優(yōu)先級。

這時，無論寫緩沖區(qū)是否正在執(zhí)行寫入邏輯，都會優(yōu)先處理讀取邏輯。

使用虛擬地址

虛擬地址是操作系統(tǒng)為每個進程所分配的存儲空間的地址，與實際的物理地址需要通過地址轉換和映射操作。

所以對于使用物理地址的緩存，則需要先將處理器給出的虛擬地址轉換成物理地址，然后再根據緩存中的物理地址來訪問數據。

這樣的實現需要對處理器虛擬地址到訪問存儲器物理地址之間的轉換，使得緩存命中時間變長，從而不利于缺失率的降低。

所以單從這點上來看，緩存若是使用虛擬地址，則可以節(jié)省地址轉換的時間。但是使用虛擬地址也并不是一件一勞永逸的事情。采用虛擬地址會導致一系列的問題。

比如由于每個進程都有自己的虛擬地址空間，所以在切換進程時，會出現不同的進程可能會有相同的虛擬地址，但這兩個相同的虛擬地址卻對應不同的物理地址。

因此在切換進程時，需要同步切換緩存，刷新緩存數據，在這個期間不可避免的也會產生大量缺失。

當然這樣的問題是可以解決的，可以將每個進程的pid與緩存塊綁定，在命中時檢查即可。

以上這六種方法只是最基本的幾種緩存優(yōu)化方法，主要是從缺失率和命中時間（其實還有缺失代價）這幾個方面去優(yōu)化。?4??

雖然這幾種方法不能給我們優(yōu)化出一個很完美的具備層次結構的存儲器，但是給予了我們優(yōu)化緩存的方向和思路。

事實上，若引入更多的優(yōu)化度量指標，比如緩存帶寬和功耗等。還可以引申出更多的優(yōu)化方法。

常見的還有10種高級的緩存優(yōu)化方法。這里就不一一細講，感興趣的可以深入理解一下。

一、 采用小而簡單的第一級緩存，用以縮短命中時間、降低功率
二、 采用路預測以縮短命中時間
三、 實現緩存訪問的流水化，以提高緩存帶寬
四、 采用無阻塞緩存，以提高緩存帶寬
五、 采用多種緩存分組以提高緩存帶寬
六、 關鍵字優(yōu)先和提前重啟動以降低缺失代價
七、 合并寫緩沖區(qū)以降低缺失代價
八、 采用編譯器優(yōu)化以降低缺失率
九、 對指令和數據進行硬件預取，以降低缺失代價或缺失率
十、 用編譯器控制預取，以降低缺失代價或缺失率

計算機科學家們老早就意識到存儲器沒辦法直接滿足程序的使用，所以在計算機出現的早期就已經研究出這種存儲器層次結構。

后來又逐漸引入了虛擬存儲器以及真正高性能的緩存，但是一直以來關于存儲器層次結構的基本概率和理論卻沒有本質的變化。

如果將計算機比作人類的大腦的話，那么存儲器就相當于是記憶細胞。

緩存技術一種能夠大幅度提升計算機性能的技術，在歷史上已經得到了充分的證明。

但是在真正研究出更強大的緩存之前，存儲器層次結構依然是解決問題最有效和性價比最高的方案。

今天的文章就到這，期待你的點贊、關注、轉發(fā)。