計算機緩存Cache以及Cache Line詳解

計算機緩存Cache以及Cache Line詳解

來自專欄現代計算機

1.計算機存儲體系簡介

存儲器是分層次的，離CPU越近的存儲器，速度越快，每位元組的成本越高，同時容量也因此越小。寄存器速度最快，離CPU最近，成本最高，所以個數容量有限，其次是高速緩存（緩存也是分級，有L1，L2等緩存），再次是主存（普通內存），再次是本地磁碟。

寄存器的速度最快，可以在一個時鐘周期內訪問，其次是高速緩存，可以在幾個時鐘周期內訪問，普通內存可以在幾十個或幾百個時鐘周期內訪問。

存儲器分級，利用的是局部性原理。我們可以以經典的閱讀書籍為例。我在讀的書，捧在手裡（寄存器），我最近頻繁閱讀的書，放在書桌上（緩存），隨時取來讀。當然書桌上只能放有限幾本書。我更多的書在書架上（內存）。如果書架上沒有的書，就去圖書館（磁碟）。我要讀的書如果手裡沒有，那麼去書桌上找，如果書桌上沒有，去書架上找，如果書架上沒有去圖書館去找。可以對應寄存器沒有，則從緩存中取，緩存中沒有，則從內存中取到緩存，如果內存中沒有，則先從磁碟讀入內存，再讀入緩存，再讀入寄存器。

2.計算機緩存 Cache

本系列的文章重點介紹緩存cache。了解如何獲取cache的參數，了解緩存的組織結構。

2.1 Cache 概述

cache，中譯名高速緩衝存儲器，其作用是為了更好的利用局部性原理，減少CPU訪問主存的次數。簡單地說，CPU正在訪問的指令和數據，其可能會被以後多次訪問到，或者是該指令和數據附近的內存區域，也可能會被多次訪問。因此，第一次訪問這一塊區域時，將其複製到cache中，以後訪問該區域的指令或者數據時，就不用再從主存中取出。

cache分成多個組，每個組分成多個行，linesize是cache的基本單位，從主存向cache遷移數據都是按照linesize為單位替換的。比如linesize為32Byte，那麼遷移必須一次遷移32Byte到cache。 這個linesize比較容易理解，想想我們前面書的例子，我們從書架往書桌搬書必須以書為單位，肯定不能把書撕了以頁為單位。書就是linesize。當然了現實生活中每本書頁數不同，但是同個cache的linesize總是相同的。

所謂8路組相連（ 8-way set associative）的含義是指，每個組裡面有8個行。

我們知道，cache的容量要遠遠小於主存，主存和cache肯定不是一一對應的，那麼主存中的地址和cache的映射關係是怎樣的呢？

拿到一個地址，首先是映射到一個組裡面去。如何映射？取內存地址的中間幾位來映射。

舉例來說，data cache: 32-KB, 8-way set associative, 64-byte line size

Cache總大小為32KB，8路組相連（每組有8個line），每個line的大小linesize為64Byte,OK，我們可以很輕易的算出一共有32K/8/64=64 個組。

對於32位的內存地址，每個line有2^6 = 64Byte，所以地址的【0，5】區分line中的那個位元組。一共有64個組。我們取內存地址中間6為來hash查找地址屬於那個組。即內存地址的【6，11】位來確定屬於64組的哪一個組。組確定了之後，【12，31】的內存地址與組中8個line挨個比對，如果【12，31】為與某個line一致，並且這個line為有效，那麼緩存命中。

OK，cache分成三類，

1 直接映射高速緩存，這個簡單，即每個組只有一個line，選中組之後不需要和組中的每個line比對，因為只有一個line。

2 組相聯高速緩存，這個就是我們前面介紹的cache。 S個組，每個組E個line。

3 全相聯高速緩存，這個簡單，只有一個組，就是全相聯。不用hash來確定組，直接挨個比對高位地址，來確定是否命中。可以想見這種方式不適合大的緩存。想想看，如果4M 的大緩存　linesize為32Byte，採用全相聯的話，就意味著4*1024*1024/32 = 128K 個line挨個比較，來確定是否命中，這是多要命的事情。高速緩存立馬成了低速緩存了。

　描述一個cache需要以下參數　：

1　cache分級，L1 cache, L2 cache, L3 cache,級別越低，離ｃｐｕ越近

2 cache的容量

3 cache的linesize

4 cache 每組的行個數.

2.2 Cache 結構

假設內存容量為M，內存地址為m位：那麼定址範圍為000…00~FFF…F(m位)

倘若把內存地址分為以下三個區間：

tag, set index, block offset三個區間有什麼用呢？再來看看Cache的邏輯結構吧：

將此圖與上圖做對比，可以得出各參數如下：

B = 2^b

S = 2^s

現在來解釋一下各個參數的意義：

一個cache被分為S個組，每個組有E個cacheline，而一個cacheline中，有B個存儲單元，現代處理器中，這個存儲單元一般是以位元組(通常8個位)為單位的，也是最小的定址單元。因此，在一個內存地址中，中間的s位決定了該單元被映射到哪一組，而最低的b位決定了該單元在cacheline中的偏移量。valid通常是一位，代表該cacheline是否是有效的(當該cacheline不存在內存映射時，當然是無效的)。tag就是內存地址的高t位，因為可能會有多個內存地址映射到同一個cacheline中，所以該位是用來校驗該cacheline是否是CPU要訪問的內存單元。

當tag和valid校驗成功是，我們稱為cache命中，這時只要將cache中的單元取出，放入CPU寄存器中即可。

當tag或valid校驗失敗的時候，就說明要訪問的內存單元(也可能是連續的一些單元，如int佔4個位元組，double佔8個位元組)並不在cache中，這時就需要去內存中取了，這就是cache不命中的情況(cache miss)。當不命中的情況發生時，系統就會從內存中取得該單元，將其裝入cache中，與此同時也放入CPU寄存器中，等待下一步處理。注意，以下這一點對理解linux cache機制非常重要：

3.計算機緩存行 ChaceLine

高速緩存其實就是一組稱之為緩存行(cache line)的固定大小的數據塊，其大小是以突發讀或者突發寫周期的大小為基礎的。

每個高速緩存行完全是在一個突發讀操作周期中進行填充或者下載的。即使處理器只存取一個位元組的存儲器，高速緩存控制器也啟動整個存取器訪問周期並請求整個數據塊。緩存行第一個位元組的地址總是突發周期尺寸的倍數。緩存行的起始位置總是與突發周期的開頭保持一致。

當從內存中取單元到cache中時，會一次取一個cacheline大小的內存區域到cache中，然後存進相應的cacheline中。

例如：我們要取地址 (t, s, b) 內存單元，發生了cache miss，那麼系統會取 (t, s, 00…000) 到 (t, s, FF…FFF)的內存單元，將其放入相應的cacheline中。

下面看看cache的映射機制：

當E=1時， 每組只有一個cacheline。那麼相隔2^(s+b)個單元的2個內存單元，會被映射到同一個cacheline中。(好好想想為什麼?)

當1<E<C/B時，每組有E個cacheline，不同的地址，只要中間s位相同，那麼就會被映射到同一組中，同一組中被映射到哪個cacheline中是依賴於替換演算法的。

當E=C/B，此時S=1，每個內存單元都能映射到任意的cacheline。帶有這樣cache的處理器幾乎沒有，因為這種映射機制需要昂貴複雜的硬體來支持。

不管哪種映射，只要發生了cache miss，那麼必定會有一個cacheline大小的內存區域，被取到cache中相應的cacheline。

現代處理器，一般將cache分為2~3級，L1, L2, L3。L1一般為CPU專有，不在多個CPU中共享。L2 cache一般是多個CPU共享的，也可能裝在主板上。L1 cache還可能分為instruction cache, data cache. 這樣CPU能同時取指令和數據。

推薦閱讀：