浅析x86架构中cache的组织结构
cache通常被翻譯為高速緩沖存儲器（以下簡稱“高速緩存”），雖然現在cache的含義已經不單單指CPU和主存儲器（也就是通常所謂的內存）之間的高速緩存了，但在本文中所謂的cache依舊特指CPU和主存儲器之間的高速緩存。
這篇文章誕生的源頭是我之前在stackoverflow看到的一個問題：
Why is transposing a matrix of 512×512 much slower than transposing a matrix of 513×513 ?
這個問題雖然國外的大神給出了完美的解釋，但是我當時看過之后還是一頭霧水。想必對x86架構上的cache沒有較深入了解過的童鞋看過之后也是一樣的感受吧。于是趁著寒假回家第一天還沒有過多外界干擾的時候，我們就來詳細的研究下x86架構下cache的組織方式吧。
我們就由這個問題開始討論吧。這個問題說為什么轉置一個512×512的矩陣反倒比513×513的矩陣要慢？（不知道什么是矩陣轉置的童鞋補習線性代數去）提問者給出了測試的代碼以及執行的時間。
不過我們不知道提問者測試機器的硬件架構，不過我的測試環境就是我這臺筆記本了，x86架構，處理器是Intel Core i3-2310M 2.10GHz。順便啰嗦一句，在linux下，直接用cat命令查看/proc/cpuinfo這個虛擬文件就可以查看到當前CPU的很多信息。
首先，我們將提問者給出的代碼修改為C語言版，然后編譯運行進行測試。提問者所給出的這段代碼有邏輯問題，但是這和我們的討論主題無關，所以請無視這些細節吧 :），代碼如下：
我的機器上得出了如下的測試結果：
Average for a matrix of 513 : 0.003879 s
Average for a matrix of 512 : 0.004570 s
512×512的矩陣轉置確實慢于513×513的矩陣，但是有意思的是我并沒有提問者那么懸殊的執行結果。不過在編譯命令行加上參數 -O2 優化后差異很明顯了：
Average for a matrix of 513 : 0.001442 s
Average for a matrix of 512 : 0.005469 s
也就是說512×512的矩陣居然比513×513的矩陣轉置平均慢了近4倍！
那么，是什么原因導致這個神奇的結果呢？
- 如果真是cache的緣故，那么cache又是如何影響代碼執行的效率呢？
- 如果是因為cache具體的組織方式帶來的特殊現象，那cache究竟是怎么組織的呢？
- 除此之外，僅僅是512×512的矩陣轉置慢嗎？其它的數字又會怎樣呢？
- 搞明白了cache的組織方式之后，能給我們平時寫代碼定義變量有怎樣的啟示呢？
好了，我們提出的問題足夠多了，現在我們來嘗試在探索中逐一解答這些問題，并嘗試分析一些現代CPU的特性對代碼執行造成的影響。
我們從cache的原理說起，cache存在的目的是在高速的CPU和較低速的主存儲器之間建立一個數據存儲的緩沖地帶，通常由SRAM制造，訪問速度略慢于CPU的寄存器，但是卻高于DRAM制造的主存儲器。因為制造成本過高，所以cache的容量一般都很小，一般只有幾MB甚至幾十到幾百KB而已。那你可能會說，這么小的cache怎么可能有大作用。有趣的是還真有大作用，由于程序的局部性原理的存在，小容量的cache在工作時能輕易達到90%以上的讀寫命中率。局部性原理分為時間局部性和空間局部性，這里不再詳述，有興趣的童鞋請參閱其他資料。
順便插一句嘴，不光金字塔型的存儲器體系結構和制造成本相關，甚至我覺得計算機體系結構很大程度受制于成本等因素的考量。假設主存儲器的存儲速率能和CPU寄存器比肩的話，cache肯定就會退出歷史的舞臺了。如果磁盤的讀寫速度能達到寄存器級別并且隨機存取，那恐怕內存也就沒有存在的必要的……
言歸正傳，我們如何查看自己機器上CPU的cache信息呢？/proc/cpuinfo這里是沒有的，我們需要使用lscpu命令查看，這條命令在我的機器上得到了如下的輸出結果：
可以看到，我的機器擁有L1d（L1數據cache）和L1i（L1指令cache）各32KB、L2 cache 256KB、L3 cache 3072KB（3MB）。
L1緩存居然分為數據緩存和指令緩存，這不是哈佛架構么？x86不是馮·諾伊曼架構么，怎么會在存儲區域區分指令和數據？其實，教科書中講述的都是完全理想化的模型，在實際的工程中，很難找到這種理想化的設計。就拿操作系統內核而言，盡管所謂的微內核組織結構更好，但是在目前所有知名的操作系統中是找不到完全符合學術意義上的微內核的例子。工程上某些時候就是一種折衷，選擇更“接地氣”的做法，而不是一味的契合理論模型。
既然cache容量很有限，那么如何組織數據便是重點了。接下來，我們談談cache和內存數據的映射方式。一般而言，有所謂的全相聯映射，直接相聯映射和組相聯映射三種方式。
CPU和cache是以字為單位進行數據交換的，而cache卻是以行（塊）（即Cache Block，或Cache Line）為單位進行數據交換的。在cache中劃分若干個字為一行，在內存中劃分若干個字為一塊，這里的行和塊是大小相等的。CPU要獲取某內存地址的數據時會先檢查該地址所在的塊是否在cache中，如果在稱之為cache命中，CPU很快就可以讀取到所需數據；反之稱為cache未命中，此時需要從內存讀取數據，同時會將該地址所在的整個內存塊復制到cache里存儲以備再次使用。
我們依次來看這三種映射方式，首先是全相聯映射，這種映射方式很簡單，內存中的任意一塊都可以放置到cache中的任意一行去。為了便于說明，我們給出以下的簡單模型來理解這個設計。
我們假設有一個4行的cache，每行4個字，每個字占4個字節，即64字節的容量。另外還有256字節（16塊，每塊4字，每字4字節）的一個RAM存儲器來和這個cache進行映射。映射結構如圖所示：
那么如何判斷cache是否命中呢？由于內存和cache是多對一的映射，所以必須在cache存儲一行數據的同時標示出這些數據在內存中的確切位置。簡單的說，在cache每一行中都有一個Index，這個Index記錄著該行數據來自內存的哪一塊（其實還有若干標志位，包括有效位（valid bit）、臟位（dirty bit）、使用位（use bit）等。這些位在保證正確性、排除沖突、優化性能等方面起著重要作用）。那么在進行一個地址的判斷時，采用全相聯方式的話，因為任意一行都有可能存在所需數據，所以需要比較每一行的索引值才能確定cache中是否存在所需數據。這樣的電路延遲較長，設計困難且復雜性高，所以一般只有在特殊場合，比如cache很小時才會使用。
然后是第二種方法：直接相連映射。這個方法固定了行和塊的對應關系，例如內存第0塊必須放在cache第0行，第一塊必須放在第一行，第二塊必須放在第二行……循環放置，即滿足公式：
內存塊放置行號 = 內存塊號 % cache總行數
映射如圖所示：
這樣做解決了比較起來困難的問題，由于每一塊固定到了某一行，只需要計算出目標內存所在的行號進行檢查即可判斷出cache是否命中。但是這么做的話因為一旦發生沖突就必須換出cache中的指定行，頻繁的更換緩存內容造成了大量延遲，而且未能有效利用程序運行期所具有的時間局部性。
綜上，最終的解決方案是最后的組相聯映射方式（Set Associativity），這個方案結合了以上兩種映射方式的優點。具體的方法是先將cache的行進行分組，然后內存塊按照組號求模來決定該內存塊放置到cache的哪一個組。但是具體放置在組內哪一行都可以，具體由cache替換算法決定。
我們依舊以上面的例子來說明，將cache里的4行分為兩組，然后采用內存里的塊號對組號求模的方式進行組號判斷，即內存0號塊第一組里，2號塊放置在第二組里，3號塊又放置在第一組，以此類推。這么做的話，在組內發生沖突的話，可以選擇換出組內一個不經常讀寫的內存塊，從而減少沖突，更好的利用了資源（具體的cache替換策略不在討論范圍內，有興趣的童鞋請自行研究）。同時因為組內行數不會很多，也避免了電路延遲和設計的復雜性。
x86中cache的組織方式采用的便是組相聯映射方式。
上面的闡述可能過于簡單，不過大家應該理解了組相聯映射方式是怎么回事了。那么我們接下來結合我的機器上具體的cache映射計算方法繼續分析。
我們剛說過組相聯映射方式的行號可以通過 塊號 % 分組個數 的公式來計算，那么直接給出一個內存地址的話如何計算呢？其實內存地址所在的塊號就是 內存地址值 / 分塊字節數，那么直接由一個內存地址計算出所在cache中的行分組的組號計算公式就是：
內存地址所在cache組號 = （內存地址值 / 分塊字節數） % 分組個數
很簡單吧？假定一個cache行（內存塊）有4個字，我們畫出一個32位地址拆分后的樣子：
因為字長32的話，每個字有4個字節，所以需要內存地址最低2位時字節偏移，同理每行（塊）有4個字，塊內偏移也是2位。這里的索引位數取決于cache里的行數，這個圖里我畫了8位，那就表示cache一共有256個分組（0～255）存在，每個分組有多少行呢？這個隨意了，這里的行數是N，cache就是N路組相聯映射。具體的判斷自然是取tag進行組內逐一匹配測試了，如果不幸沒有命中，那就需要按照cache替換算法換出組內的一行了。順帶畫出這個地址對應的cache結構圖：
標志位是有效位（valid bit）、臟位（dirty bit）、使用位（use bit）等，用于該cache行的寫回算法，替換算法使用。這里簡單期間我就畫了一個2路組相聯映射的例子出來。現在大家應該大致明白cache工作的流程了吧？首先由給出的內存地址計算出所在cache的組號（索引），再由判斷電路逐一比較標簽（tag）值來判斷是否命中，若命中則通過行（塊）內偏移返回所在字數據，否則由cache替換算法決定換出某一行（塊），同時由內存調出該行（塊）數據進行替換。
其實工作的流程就是這樣，至于cache寫回的策略（寫回法，寫一次法，全寫法）不在本文的討論范圍之內，就不細說了。
有了以上鋪墊，我們終于可以來解釋那個512×512的矩陣轉置問題了。很艱難的鋪墊，不是嗎？但我們距離勝利越來越近了。
512×512的矩陣，或者用C語言的說法稱之為512×512的整型二維數組，在內存中是按順序存儲的。
那么以我的機器為例，在上面的lscpu命令輸出的結果中，L1d（一級數據緩存）擁有32KB的容量。但是，有沒有更詳細的行大小和分組數量的信息？當然有，而且不需要多余的命令。在/sys/devices/system/cpu目錄下就可以看到各個CPU核的所有詳細信息，當然也包括cache的詳細信息，我們主要關注L1d緩存的信息，以核0為例，在/sys/devices/system/cpu/cpu0/cache目錄下有index0～index4這四個目錄，分別對應L1d，L1i，L2，L3的信息。我們以L1d（index0）為例查看詳細參數。
從圖中我們可以知道，這是L1數據緩存的相關信息：共有64個組，每組8行，每行16字（64字節），共有32KB的總容量。按照我們之前的分析，相信你很容易就能說出這個機器上L1d緩存的組織方式。沒錯，就是8路組相聯映射。
順帶貼出Intel的官方文檔證明我不是在信口開河：
此時32位內存地址的拆分如下：
對應的cache圖想必也難不倒大家吧？和上邊的cache結構不同的就是改變了分組數量、每組行數和每行大小。
我們繼續分析轉置問題。每個cache行（塊）擁有64個字節，正好是16個int變量的大小。一個n階矩陣的一個行正好填充n / 16個cache行。512階矩陣的話，每個矩陣的行就填充了32個組中的行，2個矩陣的行就覆蓋了64個組。之后的行若要使用，就必然牽扯到cache的替換了。如果此時二維數組的array[0][0]開始從cache第一行開始放置。那么當進入第二重for循環之后，由于內存地址計算出的cache組號相同，導致每一個組中的正在使用的cache行發生了替換，不斷發生的組內替換使得cache完全沒有發揮出效果，所以造成了512×512的矩陣在轉置的時候耗時較大的原因。具體的替換點大家可以自行去計算，另外513×513矩陣大家也可以試著去分析沒有過多cache失效的原因。不過這個問題是和CPU架構有關的，所以假如你的機器沒有產生同樣的效果，不妨自己研究研究自己機器的cache結構。
另外網上針對這個問題也有諸多大牛給出的解釋，大家不妨參照著理解吧。別人說過的我就不說了，大家可以參考著分析。
總結
以上是生活随笔為你收集整理的浅析x86架构中cache的组织结构的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java数据结构——有序链表
- 下一篇： 你能排第几？2016互联网行业薪酬数据分