對(duì)于一個(gè)簡(jiǎn)單的計(jì)算機(jī)系統(tǒng)模型，我們可以將存儲(chǔ)器系統(tǒng)看做是一個(gè)線性的字節(jié)數(shù)組，而 CPU 能夠在一個(gè)常數(shù)時(shí)間內(nèi)訪問(wèn)每個(gè)存儲(chǔ)器的位置。實(shí)際上，存儲(chǔ)器系統(tǒng)（memory system）是一個(gè)具有不同容量、成本和訪問(wèn)時(shí)間的存儲(chǔ)設(shè)備的層次結(jié)構(gòu)。CPU 寄存器保存著最常用的數(shù)據(jù)。

靠近 CPU 的小、快速的高速緩存存儲(chǔ)器（cache memory）做為一部分存儲(chǔ)在相對(duì)慢速的主存儲(chǔ)器（main memory）中數(shù)據(jù)和指令的緩沖區(qū)域。主存緩存存儲(chǔ)在容量較大的、慢速磁盤上的數(shù)據(jù)，而磁盤常常作為存儲(chǔ)在通過(guò)網(wǎng)絡(luò)連接的其他機(jī)器的磁盤的緩存。

Cache 基本模型

問(wèn)題

CPU 通過(guò)總線從主存取指令和數(shù)據(jù)，完成計(jì)算之后再將結(jié)果寫回內(nèi)存。這個(gè)模型的瓶頸在于 CPU 的超級(jí)快的運(yùn)算速度和主存相對(duì)慢的多的運(yùn)算速度無(wú)法匹配，導(dǎo)致大量的時(shí)間都浪費(fèi)在內(nèi)存上。既然內(nèi)存比較慢那么就盡量減少 CPU 對(duì)內(nèi)存的訪問(wèn)，于是在 CPU 和 主存之間增加一層 Cache，如下圖所示。

cache

在計(jì)算機(jī)中，Cache 就是訪問(wèn)速度快的計(jì)算機(jī)內(nèi)存被用來(lái)保存頻繁訪問(wèn)或者最近訪問(wèn)的指令和內(nèi)存。通常 Cache 的造價(jià)比較高，所以相對(duì) Memory 來(lái)說(shuō)，容量比較小,保存的數(shù)據(jù)也有限?？偠灾捎?CPU 和內(nèi)存之間的指令和數(shù)據(jù)訪問(wèn)存在瓶頸，所以增加了一層 Cache，用來(lái)盡力消除 CPU 和內(nèi)存之間的瓶頸。這個(gè)模型如下圖所示。

Cache 模型

局部性原理

你可能會(huì)問(wèn)為什么在CPU 和內(nèi)存之間增加一層 Cache，就可以盡力消除 CPU 和內(nèi)存之間的瓶頸呢？

why cache work

如上圖所示，是局部性原理（principle of locality）讓 Cache 更好的工作。一個(gè)編寫良好的計(jì)算機(jī)程序通常都具有良好的局部性（locality）,程序傾向于引用鄰近于其他最近引用過(guò)的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng)，或者最近引用過(guò)的數(shù)據(jù)項(xiàng)本身，這種傾向性被稱作局部性原理。

局部性通常有 2 種不同的形式：時(shí)間局部性（temporal locality）和空間局部性 (spatial locality)。在一個(gè)具有良好時(shí)間局部性的程序中，被引用過(guò)一次的內(nèi)存地址很可能在不遠(yuǎn)的將來(lái)會(huì)再被多次引用。在一個(gè)具有良好空間局部性的程序中，如果一個(gè)內(nèi)存位置被引用了一次，那么程序很可能在不遠(yuǎn)的將來(lái)會(huì)引用附近的一個(gè)內(nèi)存位置。

程序是如何利用這個(gè)局部性原理呢？

Cache&locality

從數(shù)據(jù)方面來(lái)說(shuō)，

sum 變量在每次循環(huán)迭代的時(shí)候都會(huì)被訪問(wèn)，符合時(shí)間局部性。

采用步長(zhǎng)為 1 的方式訪問(wèn)數(shù)組 a ，符合空間局部性。

從指令方面來(lái)說(shuō)，

循環(huán)迭代，符合時(shí)間局部性

線性執(zhí)行指令，符合空間局部性

對(duì)于程序員來(lái)說(shuō)，編寫具有良好的局部性的程序是讓程序運(yùn)行更快的方法之一。

存儲(chǔ)器的層次結(jié)構(gòu)

存儲(chǔ)器層次結(jié)構(gòu)

上圖展示了一個(gè)典型的存儲(chǔ)器層次結(jié)構(gòu)。一般而言，從高層往底層走，存儲(chǔ)設(shè)備變得更慢、更便宜和更大。在最高層是少量快速的CPU 寄存器，CPU 可以再一個(gè)時(shí)鐘周期內(nèi)訪問(wèn)它們。接下來(lái)是一個(gè)或者多個(gè)小型到中型的基于 SRAM 的高速緩存存儲(chǔ)器，可以再幾個(gè) CPU 時(shí)鐘周期內(nèi)訪問(wèn)它們。

然后是一個(gè)大的基于 DRAM 的主存，可以在幾十或者幾百個(gè)時(shí)鐘周期內(nèi)訪問(wèn)它們。接下來(lái)是慢速但是容量很大的本地磁盤。最后有些系統(tǒng)甚至包括了一層附加的遠(yuǎn)程服務(wù)器上的磁盤，要通過(guò)網(wǎng)絡(luò)來(lái)訪問(wèn)它們，例如網(wǎng)絡(luò)文件系統(tǒng)（Network File System,NFS）這樣的分布式文件系統(tǒng)，允許程序訪問(wèn)存儲(chǔ)在遠(yuǎn)程的網(wǎng)絡(luò)服務(wù)器上的文件。

存儲(chǔ)器層次結(jié)構(gòu)的核心是，對(duì)于每個(gè) k , 位于 k 層的更快更小的存儲(chǔ)設(shè)備作為位于 k+1 層的更大更慢的存儲(chǔ)設(shè)備的緩存。也就是說(shuō)，層次結(jié)構(gòu)中的每一層都緩存來(lái)自較低一層的數(shù)據(jù)對(duì)象。例如，本地磁盤作為通過(guò)網(wǎng)絡(luò)從遠(yuǎn)程磁盤取出文件的緩存，以此類推知道 CPU 寄存器。

cache

上圖展示了存儲(chǔ)器層次結(jié)構(gòu)中緩存的一般性概念。第 k+1 層的存儲(chǔ)器被劃分成連續(xù)的數(shù)據(jù)對(duì)象組塊（chunk）,稱為塊（block）。每個(gè)塊都有一個(gè)唯一的名字或者地址以區(qū)別其他的塊。例如第 k+1 層存儲(chǔ)器被劃分成 16 個(gè)大小固定的塊，編號(hào)為 0 ~ 15。第 k 層的存儲(chǔ)器被劃分成較少的塊的集合，每個(gè)塊的大小與 k+1 層的塊的大小一樣。

在任何時(shí)刻，第 k 層的緩存包含了第 k+1 層塊的一個(gè)子集的副本。例如，第 k 層的緩存有 4 個(gè)塊的控件，當(dāng)前包含了 8，9，14，3 的副本。

數(shù)據(jù)總是以塊大小為傳輸單元在第 k 層 和 第 k+1 層之間來(lái)回復(fù)制的，雖然在層次結(jié)構(gòu)總?cè)魏我粚?duì)相鄰的層次之間塊大小是固定的，但是其他的層次對(duì)之間可以有不同的塊大小。

例如 L1 和 L2 之間的傳送通常使用的是幾十個(gè)個(gè)字大小的塊，而 L5 和 L4 之間的傳送用的是大小為幾百或者幾千字節(jié)的塊。一般而言，層次結(jié)構(gòu)中較低層（離 CPU 較遠(yuǎn)）的設(shè)備的訪問(wèn)時(shí)間較長(zhǎng)，因此為了補(bǔ)償這些較長(zhǎng)的訪問(wèn)時(shí)間，傾向于使用較大的塊。

cache hit

當(dāng)程序需要第 k+1 層的某個(gè)數(shù)據(jù)對(duì)象 d 時(shí)，它首先會(huì)在當(dāng)前存儲(chǔ)在第 k 層的一個(gè)塊中查找 d。如果 d 剛好緩存在第 k 層，那么就是緩存命中。該程序直接從第 k 層讀取 d，根據(jù)存儲(chǔ)器層次結(jié)構(gòu)的性質(zhì)，從 k 層讀取數(shù)據(jù)顯然比從 k+1 層讀取數(shù)據(jù)更快。如上圖所示，一個(gè)具有良好時(shí)間局部性的程序可以從塊 14 中讀出一個(gè)數(shù)據(jù)對(duì)象，得到一個(gè)對(duì) k 層的緩存命中 。

cache miss

如果第 k 層中沒有緩存數(shù)據(jù)對(duì)象 d，那么就是我們所說(shuō)的緩存不命中 （cache miss）。當(dāng)發(fā)生緩存不命中時(shí)，第 k 層的緩存從第 k+1 層緩存中取出包含 d 的那個(gè)塊，如果第 k 層的緩存已經(jīng)滿了，那么可能會(huì)覆蓋現(xiàn)存的一個(gè)塊。覆蓋一個(gè)現(xiàn)存的一個(gè)塊的過(guò)程稱為替換或者驅(qū)逐。被替換的塊有時(shí)也稱作犧牲塊。決定替換哪個(gè)塊是由緩存的替換策略來(lái)控制的，替換策略有隨機(jī)替換和最近最少被使用（LRU）替換策略。

高速緩存存儲(chǔ)器

早期的計(jì)算機(jī)系統(tǒng)的存儲(chǔ)器結(jié)構(gòu)只有三層：CPU 寄存器， DRAM 主存，磁盤。由于 CPU 和主存之間逐漸增大的速度差距，系統(tǒng)設(shè)計(jì)者在 CPU 和 主存之間插入了一個(gè)小的 SRAM 高速緩存存儲(chǔ)器，稱為 L1 高速緩存。隨著 CPU 和主存之間逐漸增大的速度差距，系統(tǒng)設(shè)計(jì)者在 L1 和 主存之間插入了一個(gè)更大的 SRAM 高速緩存存儲(chǔ)器，稱為 L2 高速緩存。

高速緩存存儲(chǔ)器的典型總線結(jié)構(gòu)

假設(shè)一個(gè)計(jì)算機(jī)系統(tǒng)，其中每個(gè)存儲(chǔ)器地址 m 位，形成 M = 2^m 個(gè)不同的地址。如下圖所示。一個(gè)機(jī)器的高速緩存被組織成一個(gè)有 S = 2^s 個(gè)高速緩存組（cache set）的數(shù)組。每個(gè)組包含 E 個(gè)高速緩存行（cache line）,每個(gè)行由一個(gè) B = 2^b 字節(jié)的數(shù)據(jù)塊組成，一個(gè)有效位（valid bit）指明這個(gè)行是否有效，t = m -（s+b）個(gè)標(biāo)記位（tab bit），他們唯一地標(biāo)識(shí)存儲(chǔ)在這個(gè)高速緩存行中的塊。

Cache Organization

根據(jù)每個(gè)組的高速緩存行數(shù) E，高速緩存可以被分為不同的類，每個(gè)組只有一行（E = 1）的高速緩存成為直接映射高速緩存。下面我們以直接映射高速緩存來(lái)講解。

E=1

假設(shè)有這么一個(gè)系統(tǒng)，它有一個(gè) CPU，一個(gè)寄存器文件，一個(gè) L1 高速緩存和一個(gè)主存。當(dāng) CPU 執(zhí)行一條讀內(nèi)存字 w 的指令，它向 L1 請(qǐng)求這個(gè)字，如果 L1 有 w 的副本，那么 L1 高速緩存命中，高速緩存取出 w，返回給 CPU。

若是不命中，當(dāng) L1 向主存請(qǐng)求包含 w 的塊的副本時(shí)，CPU 必須等待。當(dāng)被請(qǐng)求的塊從內(nèi)存到達(dá) L1 時(shí)，L1 將這個(gè)塊存放在它的一個(gè)高速緩存行里面，然后取出 w,返回給 CPU 。高速緩存上面的工作過(guò)程分為 3 個(gè)步驟：

組選擇

行匹配

字抽取

第一步，直接映射高速緩存的組選擇。高速緩存從 w 中取出 s 個(gè)組索引位。例子中的組索引位 00001 定位到組 1。

直接映射高速緩存的組選擇

第二步，直接映射高速緩存的行匹配。由于只有一個(gè)高速緩存行，而且有效位也設(shè)置了，所以這個(gè)行是有用的，從 w 中取出標(biāo)記位 t ，與高速緩存行中的標(biāo)記位相匹配，所以緩存命中。

直接映射高速緩存的行匹配

第三步，直接映射高速緩存的字選擇。一旦緩存命中，那么我們就知道 w 就在這個(gè)塊中的某個(gè)位置。我們把塊看成一個(gè)字節(jié)的數(shù)組，而字節(jié)偏移是到這個(gè)數(shù)組的索引。所以最后一步是確定所需要的字在塊中的偏移位置。例子中的塊偏移是 100，它說(shuō)明了 w 的副本是從塊中的字節(jié) 4 開始的（假設(shè)字長(zhǎng)為 4 字節(jié)）。

第四步，直接映射高速緩存不命中的行替換。如果緩存不命中，那么它需要從存儲(chǔ)器層次結(jié)構(gòu)中的下一層取出被請(qǐng)求的塊，然后將新的塊存儲(chǔ)在一個(gè)高速緩存行中。對(duì)于直接映射高速緩存來(lái)說(shuō)，每個(gè)組只要一個(gè)行，替換策略就是用新取出的行替換當(dāng)前的行。

編寫高速緩存友好的代碼

確保代碼高速緩存友好的基本方法有 2 種，

讓最常見的情況運(yùn)行的快。

盡量減少每個(gè)循環(huán)內(nèi)部的緩存不命中數(shù)量。

int?sumvec(int?v[n])
{
??int?i,?sum?=?0;
??for?(i?=?0;?i?

	首先對(duì)于局部變量 i 和 sum，循環(huán)體有良好的時(shí)間局部性。對(duì)數(shù)組 v 的步長(zhǎng)為 1 的引用，對(duì) v[0] 的引用會(huì)不命中，而對(duì)應(yīng)的 v[0] ~ v[3] 的塊會(huì)被從內(nèi)存加載到高速緩存中，因此接下來(lái)的三個(gè)引用都會(huì)命中，以此類推，四個(gè)引用中，三個(gè)會(huì)命中，這個(gè)是我們能做到的最好的情況了，具有良好的空間局部性。

	總結(jié)

	作為一個(gè)程序員需要理解存儲(chǔ)器的結(jié)構(gòu)層次，因?yàn)樗鼘?duì)應(yīng)用程序的性能有巨大的影響。如果你的程序需要的數(shù)據(jù)是存儲(chǔ)在 CPU 寄存器中的，那么在指令的執(zhí)行期間，在 0 個(gè)周期內(nèi)就可以訪問(wèn)到它們，如果在高速緩存中，需要 4 ~ 75 個(gè)周期。

	如果存儲(chǔ)在主存中，需要上百個(gè)周期，如果存儲(chǔ)在磁盤上，大約需要幾千萬(wàn)個(gè)周期。如果理解了系統(tǒng)是如何將數(shù)據(jù)再存儲(chǔ)器層次結(jié)構(gòu)中上上下下移動(dòng)的，那么就可以在編寫自己的應(yīng)用程序的時(shí)候使得他們的數(shù)據(jù)項(xiàng)存儲(chǔ)在結(jié)構(gòu)層次中較高的地方，以便 CPU 可以更快的訪問(wèn)到它們。

	編程時(shí)候可以注意以下幾點(diǎn)，讓程序性能更好！

	1.重復(fù)引用同一個(gè)變量的程序有良好的時(shí)間局部性；

	2.具有步調(diào)長(zhǎng)度為k的引用模式程序，步調(diào)越小，空間局部性越好;

	3.循環(huán)通常具有很好的空間局部性?&?時(shí)間局部性;

	4.數(shù)組通常具有很好的空間局部性;

	參考

	本文是華盛頓大學(xué)的公開課 《 The Hardware / Software Interface 》的課程筆記，該課程的參考書籍是大名鼎鼎的 CSAPP 也就是《 深入理解計(jì)算機(jī)系統(tǒng) 》這書。文章截圖來(lái)源于課程，文章的內(nèi)容也參考了 CSAPP 的書本內(nèi)容。

	審核編輯：黃飛

	?