原文標題：Cache: a place for concealment and safekeeping
原文地址：http://duartes.org/gustavo/blog/
[注：本人水平有限，只好挑一些國外高手的精彩文章翻譯一下。一來自己復(fù)習(xí)，二來與大家分享。]
本文簡要的展示了現(xiàn)代Intel處理器的CPU cache是如何組織的。有關(guān)cache的討論往往缺乏具體的實例，使得一些簡單的概念變得撲朔迷離。也許是我可愛的小腦瓜有點遲鈍吧，但不管怎樣，至少下面講述了故事的前一半，即Core 2的 L1 cache是如何被訪問的：
L1 cache – 32KB，8路組相聯(lián)，64字節(jié)緩存線
1. 由索引揀選緩存組（行）
在cache中的數(shù)據(jù)是以緩存線（line）為單位組織的，一條緩存線對應(yīng)于內(nèi)存中一個連續(xù)的字節(jié)塊。這個cache使用了64字節(jié)的緩存線。這些線被保存在cache bank中，也叫路（way）。每一路都有一個專門的目錄（directory）用來保存一些登記信息。你可以把每一路連同它的目錄想象成電子表格中的一列，而表的一行構(gòu)成了cache的一組（set）。列中的每一個單元（cell）都含有一條緩存線，由與之對應(yīng)的目錄單元跟蹤管理。圖中的cache有64 組、每組8路，因此有512個含有緩存線的單元，合計32KB的存儲空間。
在cache眼中，物理內(nèi)存被分割成了許多4KB大小的物理內(nèi)存頁（page）。每一頁都含有4KB / 64 bytes == 64條緩存線。在一個4KB的頁中，第0到63字節(jié)是第一條緩存線，第64到127字節(jié)是第二條緩存線，以此類推。每一頁都重復(fù)著這種劃分，所以第0頁第3條緩存線與第1頁第3條緩存線是不同的。
在全相聯(lián)緩存（fully associative cache）中，內(nèi)存中的任意一條緩存線都可以被存儲到任意的緩存單元中。這種存儲方式十分靈活，但也使得要訪問它們時，檢索緩存單元的工作變得復(fù)雜、昂貴。由于L1和L2 cache工作在很強的約束之下，包括功耗，芯片物理空間，存取速度等，所以在多數(shù)情況下，使用全相聯(lián)緩存并不是一個很好的折中。
取而代之的是圖中的組相聯(lián)緩存（set associative cache）。意思是，內(nèi)存中一條給定的緩存線只能被保存在一個特定的組（或行）中。所以，任意物理內(nèi)存頁的第0條緩存線（頁內(nèi)第0到63字節(jié)）必須存儲到第0組，第1條緩存線存儲到第1組，以此類推。每一組有8個單元可用于存儲它所關(guān)聯(lián)的緩存線（譯注：就是那些需要存儲到這一組的緩存線），從而形成一個8路關(guān)聯(lián)的組（8-way associative set）。當訪問一個內(nèi)存地址時，地址的第6到11位（譯注：組索引）指出了在4KB內(nèi)存頁中緩存線的編號，從而決定了即將使用的緩存組。舉例來說，物理地址0x800010a0的組索引是000010，所以此地址的內(nèi)容一定是在第2組中緩存的。
但是還有一個問題，就是要找出一組中哪個單元包含了想要的信息，如果有的話。這就到了緩存目錄登場的時刻。每一個緩存線都被其對應(yīng)的目錄單元做了標記（tag）；這個標記就是一個簡單的內(nèi)存頁編號，指出緩存線來自于哪一頁。由于處理器可以尋址64GB的物理RAM，所以總共有64GB / 4KB == 224個內(nèi)存頁，需要24位來保存標記。前例中的物理地址0x800010a0對應(yīng)的頁號為524,289。下面是故事的后一半：
在組中搜索匹配標記
由于我們只需要去查看某一組中的8路，所以查找匹配標記是非常迅速的；事實上，從電學(xué)角度講，所有的標記是同時進行比對的，我用箭頭來表示這一點。如果此時正好有一條具有匹配標簽的有效緩存線，我們就獲得一次緩存命中（cache hit）。否則，這個請求就會被轉(zhuǎn)發(fā)的L2 cache，如果還沒匹配上就再轉(zhuǎn)發(fā)給主系統(tǒng)內(nèi)存。通過應(yīng)用各種調(diào)節(jié)尺寸和容量的技術(shù)，Intel給CPU配置了較大的L2 cache，但其基本的設(shè)計都是相同的。比如，你可以將原先的緩存增加8路而獲得一個64KB的緩存；再將組數(shù)增加到4096，每路可以存儲256KB。經(jīng)過這兩次修改，就得到了一個4MB的L2 cache。在此情況下，需要18位來保存標記，12位保存組索引；緩存所使用的物理內(nèi)存頁的大小與其一路的大小相等。（譯注：有4096組，就需要lg(4096)==12位的組索引，緩存線依然是64字節(jié)，所以一路有4096*64B==256KB字節(jié)；在L2 cache眼中，內(nèi)存被分割為許多256KB的塊，所以需要lg(64GB/256KB)==18位來保存標記。）
如果有一組已經(jīng)被放滿了，那么在另一條緩存線被存儲進來之前，已有的某一條則必須被騰空（evict）。為了避免這種情況，對運算速度要求較高的程序就要嘗試仔細組織它的數(shù)據(jù)，使得內(nèi)存訪問均勻的分布在已有的緩存線上。舉例來說，假設(shè)程序中有一個數(shù)組，元素的大小是512字節(jié)，其中一些對象在內(nèi)存中相距4KB。這些對象的各個字段都落在同一緩存線上，并競爭同一緩存組。如果程序頻繁的訪問一個給定的字段（比如，通過虛函數(shù)表vtable調(diào)用虛函數(shù)），那么這個組看起來就好像一直是被填滿的，緩存開始變得毫無意義，因為緩存線一直在重復(fù)著騰空與重新載入的步驟。在我們的例子中，由于組數(shù)的限制，L1 cache僅能保存8個這類對象的虛函數(shù)表。這就是組相聯(lián)策略的折中所付出的代價：即使在整體緩存的使用率并不高的情況下，由于組沖突，我們還是會遇到緩存缺失的情況。然而，鑒于計算機中各個存儲層次的相對速度，不管怎么說，大部分的應(yīng)用程序并不必為此而擔心。
一個內(nèi)存訪問經(jīng)常由一個線性（或虛擬）地址發(fā)起，所以L1 cache需要依賴分頁單元（paging unit）來求出物理內(nèi)存頁的地址，以便用于緩存標記。與此相反，組索引來自于線性地址的低位，所以不需要轉(zhuǎn)換就可以使用了（在我們的例子中為第6到11位）。因此L1 cache是物理標記但虛擬索引的（physically tagged but virtually indexed），從而幫助CPU進行并行的查找操作。因為L1 cache的一路絕不會比MMU的一頁還大，所以可以保證一個給定的物理地址位置總是關(guān)聯(lián)到同一組，即使組索引是虛擬的。在另一方面L2 cache必須是物理標記和物理索引的，因為它的一路比MMU的一頁要大。但是，當一個請求到達L2 cache時，物理地址已經(jīng)被L1 cache準備（resolved）完畢了，所以L2 cache會工作得很好。
最后，目錄單元還存儲了對應(yīng)緩存線的狀態(tài)（state）。在L1代碼緩存中的一條緩存線要么是無效的（invalid）要么是共享的（shared，意思是有效的，真的J）。在L1數(shù)據(jù)緩存和L2緩存中，一條緩存線可以為4個MESI狀態(tài)之一：被修改的（modified），獨占的（exclusive），共享的（shared），無效的（invalid）。Intel緩存是包容式的（inclusive）：L1緩存的內(nèi)容會被復(fù)制到L2緩存中。在下一篇討論線程（threading），鎖定（locking）等內(nèi)容的文章中，這些緩存線狀態(tài)將發(fā)揮作用。下一次，我們將看看前端總線以及內(nèi)存訪問到底是怎么工作的。這將成為一個內(nèi)存研討周。
（在回復(fù)中Dave提到了直接映射緩存（direct-mapped cache）。它們基本上是一種特殊的組相聯(lián)緩存，只是只有一路而已。在各種折中方案中，它與全相聯(lián)緩存正好相反：訪問非?？旖?，但因組沖突而導(dǎo)致的緩存缺失也非常多。）
[譯者小結(jié)：
1. 內(nèi)存層次結(jié)構(gòu)的意義在于利用引用的空間局部性和時間局部性原理，將經(jīng)常被訪問的數(shù)據(jù)放到快速的存儲器中，而將不經(jīng)常訪問的數(shù)據(jù)留在較慢的存儲器中。
2. 一般情況下，除了寄存器和L1緩存可以操作指定字長的數(shù)據(jù)，下層的內(nèi)存子系統(tǒng)就不會再使用這么小的單位了，而是直接移動數(shù)據(jù)塊，比如以緩存線為單位訪問數(shù)據(jù)。
3. 對于組沖突，可以這么理解：與上文相似，假設(shè)一個緩存，由512條緩存線組成，每條線64字節(jié)，容量32KB。
a) 假如它是直接映射緩存，由于它往往使用地址的低位直接映射緩存線編號，所以所有的32K倍數(shù)的地址（32K，64K，96K等）都會映射到同一條線上（即第0線）。假如程序的內(nèi)存組織不當，交替的去訪問布置在這些地址的數(shù)據(jù)，則會導(dǎo)致沖突。從外表看來就好像緩存只有1條線了，盡管其他緩存線一直是空閑著的。
b) 如果是全相聯(lián)緩存，那么每條緩存線都是獨立的，可以對應(yīng)于內(nèi)存中的任意緩存線。只有當所有的512條緩存線都被占滿后才會出現(xiàn)沖突。
c) 組相聯(lián)是前兩者的折中，每一路中的緩存線采用直接映射方式，而在路與路之間，緩存控制器使用全相聯(lián)映射算法，決定選擇一組中的哪一條線。
d) 如果是2路組相聯(lián)緩存，那么這512條緩存線就被分為了2路，每路256條線，一路16KB。此時所有為16K整數(shù)倍的地址（16K，32K，48K等）都會映射到第0線，但由于2路是關(guān)聯(lián)的，所以可以同時有2個這種地址的內(nèi)容被緩存，不會發(fā)生沖突。當然了，如果要訪問第三個這種地址，還是要先騰空已有的一條才行。所以極端情況下，從外表看來就好像緩存只有2條線了，盡管其他緩存線一直是空閑著的。
e) 如果是8路組相聯(lián)緩存（與文中示例相同），那么這512條緩存線就被分為了8路，每路64條線，一路4KB。所以如果數(shù)組中元素地址是4K對齊的，并且程序交替的訪問這些元素，就會出現(xiàn)組沖突。從外表看來就好像緩存只有8條線了，盡管其他緩存線一直是空閑著的。
]
本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/drshenlei/archive/2009/06/17/4277959.aspx