原文標題：Cache: a place for concealment and safekeeping

原文地址：http://duartes.org/gustavo/blog/

[注：本人水平有限，只好挑一些國外高手的精彩文章翻譯一下。一來自己復習，二來與大家分享。]

本文簡要的展示了現代Intel處理器的CPU cache是如何組織的。有關cache的討論往往缺乏具體的實例，使得一些簡單的概念變得撲朔迷離。也許是我可愛的小腦瓜有點遲鈍吧，但不管怎樣，至少下面講述了故事的前一半，即Core 2的 L1 cache是如何被訪問的：

L1 cache – 32KB，8路組相聯，64字節緩存線

1.       由索引揀選緩存組（行）

在cache中的數據是以緩存線（line）為單位組織的，一條緩存線對應于內存中一個連續的字節塊。這個cache使用了64字節的緩存線。這些線被保存在cache bank中，也叫路（way）。每一路都有一個專門的目錄（directory）用來保存一些登記信息。你可以把每一路連同它的目錄想象成電子表格中的一列，而表的一行構成了cache的一組（set）。列中的每一個單元（cell）都含有一條緩存線，由與之對應的目錄單元跟蹤管理。圖中的cache有64 組、每組8路，因此有512個含有緩存線的單元，合計32KB的存儲空間。

在cache眼中，物理內存被分割成了許多4KB大小的物理內存頁（page）。每一頁都含有4KB / 64 bytes == 64條緩存線。在一個4KB的頁中，第0到63字節是第一條緩存線，第64到127字節是第二條緩存線，以此類推。每一頁都重復著這種劃分，所以第0頁第3條緩存線與第1頁第3條緩存線是不同的。

在全相聯緩存（fully associative cache）中，內存中的任意一條緩存線都可以被存儲到任意的緩存單元中。這種存儲方式十分靈活，但也使得要訪問它們時，檢索緩存單元的工作變得復雜、昂貴。由于L1和L2 cache工作在很強的約束之下，包括功耗，芯片物理空間，存取速度等，所以在多數情況下，使用全相聯緩存并不是一個很好的折中。

取而代之的是圖中的組相聯緩存（set associative cache）。意思是，內存中一條給定的緩存線只能被保存在一個特定的組（或行）中。所以，任意物理內存頁的第0條緩存線（頁內第0到63字節）必須存儲到第0組，第1條緩存線存儲到第1組，以此類推。每一組有8個單元可用于存儲它所關聯的緩存線（譯注：就是那些需要存儲到這一組的緩存線），從而形成一個8路關聯的組（8-way associative set）。當訪問一個內存地址時，地址的第6到11位（譯注：組索引）指出了在4KB內存頁中緩存線的編號，從而決定了即將使用的緩存組。舉例來說，物理地址0x800010a0的組索引是000010，所以此地址的內容一定是在第2組中緩存的。

但是還有一個問題，就是要找出一組中哪個單元包含了想要的信息，如果有的話。這就到了緩存目錄登場的時刻。每一個緩存線都被其對應的目錄單元做了標記（tag）；這個標記就是一個簡單的內存頁編號，指出緩存線來自于哪一頁。由于處理器可以尋址64GB的物理RAM，所以總共有64GB / 4KB == 224個內存頁，需要24位來保存標記。前例中的物理地址0x800010a0對應的頁號為524,289。下面是故事的后一半：

在組中搜索匹配標記

由于我們只需要去查看某一組中的8路，所以查找匹配標記是非常迅速的；事實上，從電學角度講，所有的標記是同時進行比對的，我用箭頭來表示這一點。如果此時正好有一條具有匹配標簽的有效緩存線，我們就獲得一次緩存命中（cache hit）。否則，這個請求就會被轉發的L2 cache，如果還沒匹配上就再轉發給主系統內存。通過應用各種調節尺寸和容量的技術，Intel給CPU配置了較大的L2 cache，但其基本的設計都是相同的。比如，你可以將原先的緩存增加8路而獲得一個64KB的緩存；再將組數增加到4096，每路可以存儲256KB。經過這兩次修改，就得到了一個4MB的L2 cache。在此情況下，需要18位來保存標記，12位保存組索引；緩存所使用的物理內存頁的大小與其一路的大小相等。（譯注：有4096組，就需要lg(4096)==12位的組索引，緩存線依然是64字節，所以一路有4096*64B==256KB字節；在L2 cache眼中，內存被分割為許多256KB的塊，所以需要lg(64GB/256KB)==18位來保存標記。）

如果有一組已經被放滿了，那么在另一條緩存線被存儲進來之前，已有的某一條則必須被騰空（evict）。為了避免這種情況，對運算速度要求較高的程序就要嘗試仔細組織它的數據，使得內存訪問均勻的分布在已有的緩存線上。舉例來說，假設程序中有一個數組，元素的大小是512字節，其中一些對象在內存中相距4KB。這些對象的各個字段都落在同一緩存線上，并競爭同一緩存組。如果程序頻繁的訪問一個給定的字段（比如，通過虛函數表vtable調用虛函數），那么這個組看起來就好像一直是被填滿的，緩存開始變得毫無意義，因為緩存線一直在重復著騰空與重新載入的步驟。在我們的例子中，由于組數的限制，L1 cache僅能保存8個這類對象的虛函數表。這就是組相聯策略的折中所付出的代價：即使在整體緩存的使用率并不高的情況下，由于組沖突，我們還是會遇到緩存缺失的情況。然而，鑒于計算機中各個存儲層次的相對速度，不管怎么說，大部分的應用程序并不必為此而擔心。

一個內存訪問經常由一個線性（或虛擬）地址發起，所以L1 cache需要依賴分頁單元（paging unit）來求出物理內存頁的地址，以便用于緩存標記。與此相反，組索引來自于線性地址的低位，所以不需要轉換就可以使用了（在我們的例子中為第6到11位）。因此L1 cache是物理標記但虛擬索引的（physically tagged but virtually indexed），從而幫助CPU進行并行的查找操作。因為L1 cache的一路絕不會比MMU的一頁還大，所以可以保證一個給定的物理地址位置總是關聯到同一組，即使組索引是虛擬的。在另一方面L2 cache必須是物理標記和物理索引的，因為它的一路比MMU的一頁要大。但是，當一個請求到達L2 cache時，物理地址已經被L1 cache準備（resolved）完畢了，所以L2 cache會工作得很好。

最后，目錄單元還存儲了對應緩存線的狀態（state）。在L1代碼緩存中的一條緩存線要么是無效的（invalid）要么是共享的（shared，意思是有效的，真的J）。在L1數據緩存和L2緩存中，一條緩存線可以為4個MESI狀態之一：被修改的（modified），獨占的（exclusive），共享的（shared），無效的（invalid）。Intel緩存是包容式的（inclusive）：L1緩存的內容會被復制到L2緩存中。在下一篇討論線程（threading），鎖定（locking）等內容的文章中，這些緩存線狀態將發揮作用。下一次，我們將看看前端總線以及內存訪問到底是怎么工作的。這將成為一個內存研討周。

（在回復中Dave提到了直接映射緩存（direct-mapped cache）。它們基本上是一種特殊的組相聯緩存，只是只有一路而已。在各種折中方案中，它與全相聯緩存正好相反：訪問非常快捷，但因組沖突而導致的緩存缺失也非常多。）

[譯者小結：

1.         內存層次結構的意義在于利用引用的空間局部性和時間局部性原理，將經常被訪問的數據放到快速的存儲器中，而將不經常訪問的數據留在較慢的存儲器中。

2.         一般情況下，除了寄存器和L1緩存可以操作指定字長的數據，下層的內存子系統就不會再使用這么小的單位了，而是直接移動數據塊，比如以緩存線為單位訪問數據。

3.         對于組沖突，可以這么理解：與上文相似，假設一個緩存，由512條緩存線組成，每條線64字節，容量32KB。

a)         假如它是直接映射緩存，由于它往往使用地址的低位直接映射緩存線編號，所以所有的32K倍數的地址（32K，64K，96K等）都會映射到同一條線上（即第0線）。假如程序的內存組織不當，交替的去訪問布置在這些地址的數據，則會導致沖突。從外表看來就好像緩存只有1條線了，盡管其他緩存線一直是空閑著的。

b)        如果是全相聯緩存，那么每條緩存線都是獨立的，可以對應于內存中的任意緩存線。只有當所有的512條緩存線都被占滿后才會出現沖突。

c)        組相聯是前兩者的折中，每一路中的緩存線采用直接映射方式，而在路與路之間，緩存控制器使用全相聯映射算法，決定選擇一組中的哪一條線。

d)        如果是2路組相聯緩存，那么這512條緩存線就被分為了2路，每路256條線，一路16KB。此時所有為16K整數倍的地址（16K，32K，48K等）都會映射到第0線，但由于2路是關聯的，所以可以同時有2個這種地址的內容被緩存，不會發生沖突。當然了，如果要訪問第三個這種地址，還是要先騰空已有的一條才行。所以極端情況下，從外表看來就好像緩存只有2條線了，盡管其他緩存線一直是空閑著的。

e)         如果是8路組相聯緩存（與文中示例相同），那么這512條緩存線就被分為了8路，每路64條線，一路4KB。所以如果數組中元素地址是4K對齊的，并且程序交替的訪問這些元素，就會出現組沖突。從外表看來就好像緩存只有8條線了，盡管其他緩存線一直是空閑著的。

]

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/drshenlei/archive/2009/06/17/4277959.aspx