對緩存的思考——提高命中率

開篇

編寫高效的程式并不隻在于算法的精巧，還應該考慮到計算機内部的組織結構，cpu微指令的執行，緩存的組織和工作原理等。

好的算法在實際中不見得有高效率，如果完全沒有考慮緩存、微指令實作的話。

前兩篇博文

建議先閱讀前兩篇博文，雖然他們之間聯系不大，在前面也有一些對本文的鋪墊。而且，這是一個系列的文章。旨在優化程式性能。

這篇博文主要介紹的是緩存的組織、工作原理。撥開迷霧，讓你更加清晰的認識緩存。

通用緩存結構

回顧

在這裡為了簡單起見，假設CPU寄存器和主存之間隻有一個L1緩存。

下圖是高速緩存存儲器的典型總線結構:

緩存結構

下圖清晰的說明了通用緩存的組織結構:

可以看到，緩存内部是以組的形式組織的。圖中的每一塊代表一組，每組由一到多行組成（當然圖中的是每組有多行）。

每一行包括

1 位标記位（valid bit）标明這行的資訊是否有可用

t 位的标記，标明它是屬于這一組的哪一行

剩下的空間是存儲資料的資料的空間

可以看出在下面的圖中把資料位址分為了三部分，左邊 t 位是标記行号的，中間的 s 位标明組号，最後的 b 位則是資料塊在行内的偏移量。

通常來說，緩存器可描述為(S; E; B; m)其中S為緩存中的組數，E為每組的行數，B為每行存儲的位元組數，m為緩存的位址位數。

是以緩存的容量為C=S*E*B。

從緩存中取資料

（這個過程在上一篇博文中就有簡單的介紹）當cpu需要從主存中取出位址為A的資料時，先把位址A發送給緩存，如果緩存中存有位址為A的資料，就從緩存中取出該資料傳給cpu。

那麼，緩存是如何知道自己是否存有位址為A的資料呢？這就和緩存的組織有關系了，上文中緩存把位址組分為了三部分，t 、s 、b。

是以，隻要簡單的檢查位址中的資料位，就能判斷該位址是否在緩存中，如果在的話，還能确定該資料的位置。

參數 s 、b 、m 把m個位址位分為三個字段。如下圖:

下面的詳細的尋址過程

位址A中的中間S 位标記了該位址在緩存中屬于哪一組，先通過s 确定這個位址在緩存中的哪一組。

通過上面一步确定了屬于的組後，位址A中的左邊 t 位标記了該位址在該組的哪一行。

最後由右邊的 b 指出位址A中的元素在該行的偏移位。也就是确定在這行的哪一個位置。

CPU從主存中讀資料的詳細過程

和上文中說的一樣，這裡假設計算機的存儲結構隻有：cpu寄存器，L1緩存，主存。

當cpu執行一條讀存儲器位址為A的指令，它向高速緩存請求該位址，如果緩存命中，緩存很快傳回資料。如果緩存不命中，L1緩存向主存請求該資料，在這期間cpu必須等待。當被請求塊從主存到達緩存L1時，L1緩存将資料放在他的一個高速緩存行裡，然後将資料從行中提取傳回給cpu。也就是說，如果緩存不命中，先要把資料存入緩存，再傳回給cpu。

概括的說，高速緩存确定一個請求是否命中有三個過程： 

1、組選擇

2、行比對

3、字抽取

下面将會結合具體情況說明這一過程。

直接映射高速緩存

現在已經知道，我們用(S; E; B; m) 來描述緩存，這裡就根據其中的E，也就是一組的行數， 把緩存分為不同的類别。

當E=1 時，也就是說每組隻有一行的緩存組織形式，我們稱為直接映射高速緩存。因為容易了解，先對它進行介紹。

（圖檔來源 《computer systems》）

正如上圖所示，直接映射高速緩存中每組隻有一行。

直接映射高速緩存中取資料

下面将以直接映射高速緩存為例，一步步說明cup從高速緩存中取資料的過程。

如上圖所示，緩存從位址A中抽取出中間的s 位，這 s 為的數值就标記了該位址所在的組。這裡可以把緩存當作是一維數組，其中每個元素是一個組，而位址中的 s 位則是這些組的索引。如圖中的組标記為 0001 對應組 set1。這要把位址中間的 s 為提取，就能得到該位址在緩存中對應的組。

2、 行選擇

選好組 i 之後，就是确定位址A在組 i 的哪一行。因為直接映射緩存的每一組隻有一個行。是以隻要看A位址中的行标記是否和緩存中的行标記位比對。比對則位址A中的資料在緩存中。

既然已知道了位址A中的資料在緩存中的位置，最後一步隻要更具位址A中表示偏移量的位，從緩存中取出資料即可。

如下圖所示：

直接映射高速緩存不命中

當緩存不命中的時候，就要從下一層存儲中取出資料，放入緩存的某個位置中，放入的位置就由請求位址A中的組索引确定所在緩存的組，行是以确定應該放置的行。如果組中的行都是有效緩存行了，就必須要驅逐現有的一個行。對于直接映射高速緩存，每組包含一個行，替換政策就變的很簡單，用新來的行替換目前行。

直接映射緩存尋址示例

通過上面的介紹，已經基本了解了緩存的組織形式以及如何從緩存中取出資料，但是上面都隻是理論上的闡述。

為了能更好的了解，這裡會有一個具體的示例。誠然，學習一種隻是最好的方式就是應用它。 如果你已經對上面的知識有所了解，那麼請繼續吧。下面的内容會讓你更清楚的了解到緩存工作的機制。

假設我們有一個直接映射的高速緩存，描述如下

(S; E; B; m)=(4;1;2;4)

也就是說:該緩存有4個組（s=4），每組有一行（E=1），每一塊有兩個位元組（B=2）存儲器的位址是4位的（m=4）

該狀态有圖描述如下:

其中最左邊的一列是位址，中間的三列是位址的二進制表示形式。最右邊的一列是虛拟存儲器的塊的标号。

和上文中說的一樣，緩存尋址時，把位址分為了三個部分。分别表示該位址在緩存中所在的組、行、以及偏移。和上圖所對應是四位的位址，

行：其中最高的一位标記所在的行，因為是直接映射高速緩存，每組隻有一行，是以一位就能表示。

組：中間的兩位表示位址所在的組。從圖中可以看出，擁有相同組的位址有四個，比如組号為00 的位址有四個，為0、2、8、9

偏移：偏移位由最右邊的一位表示。每行中有兩個資料塊，是以偏移位用一位也就能表示。

看這個表的時候有一點提示：中間的三列其實是第一列位址的二進制表示形式。

下面是對這個特定緩存的一點分析：

該緩存有四個組，每組一行。有圖中可知，要放入緩存的位址為16個。是以每組對應四個位址。在圖中的表現就是：四個相同的位址有相同的組索引。

每行有兩個資料塊，用位址最低位表示（0表示第一個，1為第二個）。

看組索引為00的位址，為0 、1 和 8 、9。0和1有相同的行标記0，8和9有相同的行标記1.是以位址為0、1的資料要麼都在組00中，要麼多不在。位址為8、9的也一樣。說明了0、1是一個整體，8、9也一樣。如果在，都在；不在，都不在。這兩個整體通過最高位（标記為）來标明。

下面是尋址執行個體

剛開始時，緩存是空的，也就是還沒有預熱，如下圖所示

1）讀位址0的字

位址0的為 0 00 0 對應緩存中第0組，行标記位為0的，偏移為0的位置。顯然，現在緩存還是空的（标志位 valid 都為0）。緩存不命中，是以緩存先從下一級的存儲中取出改行對應的所有位址的元素，放入緩存中。（也就是位址為0 和1 的元素）。然後再從緩存中取出資料m[0]，傳遞給cpu。

進過對位址0的讀操作後，緩存的組織情況如下所示

這也驗證了上文的說法，位址0 和1 是一體的，他們要麼都在，要麼都不在。因為他們有相同的組索引、行索引。

2）讀取位址1的字

位址1為0 00 1 對應緩存中的第0組，行标記為0，偏移為1。這次緩存命中，從緩存傳回m[1]

3)讀位址13的字

位址13為1 10 1 對應緩存中的第2組 行标記為1 偏移為1。同1）一樣，緩存不命中，從低一級存儲中取出 組索引為10 行為1 的資料放入緩存，然後傳回m[13]

對位址13進行操作後的緩存情況為

4）讀位址為8的字

位址8為 1 00 0 組索引為00 行标記為1 偏移為0 在看上圖的緩存組織情況，可判讀發生緩存不命中。于是從低一級存儲中取出組索引為00 行标記為1 的資料，也就是m[8]、m[9]放入第一行中，然後傳回m[8]

操作後的緩存組織為

通過上面的示例，應該對緩存的工作原理有一定了解了把。

其實就是吧位址分為不同的部分，劃分為表示組、行 和偏移。然後根據這些去判斷所需位址是否在緩存中。如果在，則傳回資料，不在則從低一級的存儲中取出資料放入緩存中（放入的位置由位址确定）。然後傳回位址。

組相聯高速緩存

 剛才讨論的直接映射高速緩存可以看作是緩存中的一個特例，因為每組隻有一行。這裡介紹一下更普遍的緩存結構：組相連高速緩存。

其實就是每一組有多行。如下圖是E =2 的緩存

同樣的，當要從緩存中取位址為A的資料時，

1）先确定位址A所在的組，如下圖所示

2）确定行

3）抽取字（偏移）

全聯高速緩存

 全聯高速緩存中的S =1 ，也就是說，全聯高速緩存隻有一個組。

全聯高速緩存中對資料的操作和之前讨論過的兩種情況大同小異，主要就是三部。這裡就不說了。

小結

這篇博文先介紹了緩存内部的組織形式，并介紹了從緩存中讀取資料的方式，主要包括1)組選擇2）行比對 3）字抽取

緩存可以用形如(S; E; B; m)的形式表述。其中S代表緩存中的組數，E為每組的行數，B為每個緩存塊的大小。

更具E的不同可将緩存分類。

這篇文章主要介紹的是緩存的工作機制。在以後的文章中會介紹如何寫出緩存友好的代碼

全文完。

參看資料：computer systems

一條魚、尹雁鈴@ 部落格園 2012-2-12

 E-mail：[email protected]