詳解計(jì)算機(jī)緩存Cache以及Cache Line

1.計(jì)算機(jī)存儲(chǔ)體系簡介

存儲(chǔ)器是分層次的，離CPU越近的存儲(chǔ)器，速度越快，每字節(jié)的成本越高，同時(shí)容量也因此越小。寄存器速度最快，離CPU最近，成本最高，所以個(gè)數(shù)容量有限，其次是高速緩存（緩存也是分級(jí)，有L1，L2等緩存），再次是主存（普通內(nèi)存），再次是本地磁盤。

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

存儲(chǔ)器分級(jí)，利用的是局部性原理。我們可以以經(jīng)典的閱讀書籍為例。我在讀的書，捧在手里（寄存器），我最近頻繁閱讀的書，放在書桌上（緩存），隨時(shí)取來讀。當(dāng)然書桌上只能放有限幾本書。我更多的書在書架上（內(nèi)存）。如果書架上沒有的書，就去圖書館（磁盤）。我要讀的書如果手里沒有，那么去書桌上找，如果書桌上沒有，去書架上找，如果書架上沒有去圖書館去找。可以對(duì)應(yīng)寄存器沒有，則從緩存中取，緩存中沒有，則從內(nèi)存中取到緩存，如果內(nèi)存中沒有，則先從磁盤讀入內(nèi)存，再讀入緩存，再讀入寄存器。

2.計(jì)算機(jī)緩存 Cache

本系列的文章重點(diǎn)介紹緩存cache。了解如何獲取cache的參數(shù)，了解緩存的組織結(jié)構(gòu)。

2.1 Cache 概述

cache，中譯名高速緩沖存儲(chǔ)器，其作用是為了更好的利用局部性原理，減少CPU訪問主存的次數(shù)。簡單地說，CPU正在訪問的指令和數(shù)據(jù)，其可能會(huì)被以后多次訪問到，或者是該指令和數(shù)據(jù)附近的內(nèi)存區(qū)域，也可能會(huì)被多次訪問。因此，第一次訪問這一塊區(qū)域時(shí)，將其復(fù)制到cache中，以后訪問該區(qū)域的指令或者數(shù)據(jù)時(shí)，就不用再從主存中取出。

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

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

我們知道，cache的容量要遠(yuǎn)遠(yuǎn)小于主存，主存和cache肯定不是一一對(duì)應(yīng)的，那么主存中的地址和cache的映射關(guān)系是怎樣的呢？

拿到一個(gè)地址，首先是映射到一個(gè)組里面去。如何映射？取內(nèi)存地址的中間幾位來映射。

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

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

對(duì)于32位的內(nèi)存地址，每個(gè)line有2^6 = 64Byte，所以地址的【0，5】區(qū)分line中的那個(gè)字節(jié)。一共有64個(gè)組。我們?nèi)?nèi)存地址中間6為來hash查找地址屬于那個(gè)組。即內(nèi)存地址的【6，11】位來確定屬于64組的哪一個(gè)組。組確定了之后，【12，31】的內(nèi)存地址與組中8個(gè)line挨個(gè)比對(duì)，如果【12，31】為與某個(gè)line一致，并且這個(gè)line為有效，那么緩存命中。

OK，我們可以將cache分成三類，

直接映射高速緩存，這個(gè)簡單，即每個(gè)組只有一個(gè)line，選中組之后不需要和組中的每個(gè)line比對(duì)，因?yàn)橹挥幸粋€(gè)line。

組相聯(lián)高速緩存，這個(gè)就是我們前面介紹的cache。S個(gè)組，每個(gè)組E個(gè)line。

全相聯(lián)高速緩存，這個(gè)簡單，只有一個(gè)組，就是全相聯(lián)。不用hash來確定組，直接挨個(gè)比對(duì)高位地址，來確定是否命中?？梢韵胍娺@種方式不適合大的緩存。想想看，如果4M 的大緩存linesize為32Byte，采用全相聯(lián)的話，就意味著4*1024*1024/32 = 128K 個(gè)line挨個(gè)比較，來確定是否命中，這是多要命的事情。高速緩存立馬成了低速緩存了。

描述一個(gè)cache需要以下參數(shù)：

cache分級(jí)，L1 cache， L2 cache， L3 cache，級(jí)別越低，離CPU越近

cache的容量

cache的linesize

cache 每組的行個(gè)數(shù)。

2.2 Cache 結(jié)構(gòu)

假設(shè)內(nèi)存容量為M，內(nèi)存地址為m位：那么尋址范圍為000…00~FFF…F（m位）

倘若把內(nèi)存地址分為以下三個(gè)區(qū)間：

tag， set index， block offset三個(gè)區(qū)間有什么用呢？再來看看Cache的邏輯結(jié)構(gòu)吧：

參數(shù)如下：

B = 2^b

S = 2^s

現(xiàn)在來解釋一下各個(gè)參數(shù)的意義：

一個(gè)cache被分為S個(gè)組，每個(gè)組有E個(gè)cacheline，而一個(gè)cacheline中，有B個(gè)存儲(chǔ)單元，現(xiàn)代處理器中，這個(gè)存儲(chǔ)單元一般是以字節(jié)（通常8個(gè)位）為單位的，也是最小的尋址單元。因此，在一個(gè)內(nèi)存地址中，中間的s位決定了該單元被映射到哪一組，而最低的b位決定了該單元在cacheline中的偏移量。

valid通常是一位，代表該cacheline是否是有效的（當(dāng)該cacheline不存在內(nèi)存映射時(shí)，當(dāng)然是無效的）。tag就是內(nèi)存地址的高t位，因?yàn)榭赡軙?huì)有多個(gè)內(nèi)存地址映射到同一個(gè)cacheline中，所以該位是用來校驗(yàn)該cacheline是否是CPU要訪問的內(nèi)存單元。

當(dāng)tag和valid校驗(yàn)成功是，我們稱為cache命中，這時(shí)只要將cache中的單元取出，放入CPU寄存器中即可。

當(dāng)tag或valid校驗(yàn)失敗的時(shí)候，就說明要訪問的內(nèi)存單元（也可能是連續(xù)的一些單元，如int占4個(gè)字節(jié)，double占8個(gè)字節(jié)）并不在cache中，這時(shí)就需要去內(nèi)存中取了，這就是cache不命中的情況（cache miss）。當(dāng)不命中的情況發(fā)生時(shí)，系統(tǒng)就會(huì)從內(nèi)存中取得該單元，將其裝入cache中，與此同時(shí)也放入CPU寄存器中，等待下一步處理。注意，以下這一點(diǎn)對(duì)理解linux cache機(jī)制非常重要：

3.計(jì)算機(jī)緩存行 ChaceLine

高速緩存其實(shí)就是一組稱之為緩存行（cache line）的固定大小的數(shù)據(jù)塊，其大小是以突發(fā)讀或者突發(fā)寫周期的大小為基礎(chǔ)的。

每個(gè)高速緩存行完全是在一個(gè)突發(fā)讀操作周期中進(jìn)行填充或者下載的。即使處理器只存取一個(gè)字節(jié)的存儲(chǔ)器，高速緩存控制器也啟動(dòng)整個(gè)存取器訪問周期并請(qǐng)求整個(gè)數(shù)據(jù)塊。緩存行第一個(gè)字節(jié)的地址總是突發(fā)周期尺寸的倍數(shù)。緩存行的起始位置總是與突發(fā)周期的開頭保持一致。

當(dāng)從內(nèi)存中取單元到cache中時(shí)，會(huì)一次取一個(gè)cacheline大小的內(nèi)存區(qū)域到cache中，然后存進(jìn)相應(yīng)的cacheline中。

例如：我們要取地址 （t， s， b） 內(nèi)存單元，發(fā)生了cache miss，那么系統(tǒng)會(huì)取 （t， s， 00…000） 到 （t， s， FF…FFF）的內(nèi)存單元，將其放入相應(yīng)的cacheline中。

下面看看cache的映射機(jī)制：

當(dāng)E=1時(shí)， 每組只有一個(gè)cacheline。那么相隔2^（s+b）個(gè)單元的2個(gè)內(nèi)存單元，會(huì)被映射到同一個(gè)cacheline中。（好好想想為什么？）

當(dāng)1《E《C/B時(shí)，每組有E個(gè)cacheline，不同的地址，只要中間s位相同，那么就會(huì)被映射到同一組中，同一組中被映射到哪個(gè)cacheline中是依賴于替換算法的。

當(dāng)E=C/B，此時(shí)S=1，每個(gè)內(nèi)存單元都能映射到任意的cacheline。帶有這樣cache的處理器幾乎沒有，因?yàn)檫@種映射機(jī)制需要昂貴復(fù)雜的硬件來支持。

不管哪種映射，只要發(fā)生了cache miss，那么必定會(huì)有一個(gè)cacheline大小的內(nèi)存區(qū)域，被取到cache中相應(yīng)的cacheline。

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

下面來看看現(xiàn)實(shí)中cache的參數(shù)，以Intel Pentium處理器為例。

編輯：jq