計(jì)算機(jī)硬件讀取高速緩存的過程

1. 什么是緩存

??緩存又叫高速緩存，是計(jì)算機(jī)存儲(chǔ)器中的一種，本質(zhì)上和硬盤是一樣的，都是用來存儲(chǔ)數(shù)據(jù)和指令的 。它們最大的區(qū)別在于讀取速度的不同。程序一般是放在內(nèi)存中的，當(dāng)CPU執(zhí)行程序的時(shí)候，執(zhí)行完一條指令需要從內(nèi)存中讀取下一條指令，讀取內(nèi)存中的指令要花費(fèi)100000個(gè)時(shí)鐘周期（緩存讀取速度為200個(gè)時(shí)鐘周期，相差500倍），如果每次都從內(nèi)存中取指令，CPU運(yùn)行時(shí)將花費(fèi)大量的時(shí)間在讀取指令上。這顯然是一種資源浪費(fèi)。

??如何解決這個(gè)問題呢？有人肯定會(huì)問，直接把程序存儲(chǔ)在緩存中不行嗎？

??答案是可以的。但是，緩存的造價(jià)太貴了。具體如下圖所示。以2015年的售價(jià)為例，1GB SRAM的價(jià)格大約為327680美元，而1GB 普通硬盤的價(jià)格僅僅為0.03美元。用緩存來存儲(chǔ)程序成本太高了，得不償失。

SRAM和DISK價(jià)格比較

??于是，有人就提出了這樣一種方法，在CPU和內(nèi)存之間添加一個(gè)高速內(nèi)存， 這個(gè)高速內(nèi)存容量小，只用來存儲(chǔ)CPU執(zhí)行時(shí)常用的指令。既保證了硬件成本，又提高了CPU的訪問速度。這個(gè)高速內(nèi)存就是緩存（高速緩存）。

2. 緩存的定義

??高速緩存是一個(gè)小而快速的存儲(chǔ)設(shè)備 ，它作為存儲(chǔ)在更大更慢的設(shè) 備中的數(shù)據(jù)對(duì)象的緩沖區(qū)域。使用高速緩存的過程稱為緩存 。

??具體如下圖所示，主存可以作為一個(gè)存儲(chǔ)設(shè)備，L3是主存的緩沖區(qū)域，從L3存取數(shù)據(jù)的過程就叫做緩存。

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

3. 計(jì)算機(jī)中的高速緩存

3.1 高速緩存相關(guān)名詞

??如下圖所示，數(shù)據(jù)總是以塊為單位 在高速緩存和主存之間來回復(fù)制。

緩存和內(nèi)存的數(shù)據(jù)交換

??如果我們的程序請(qǐng)求一個(gè)數(shù)據(jù)字，這個(gè)數(shù)據(jù)字存儲(chǔ)在編號(hào)為10的塊中。將分以下幾種情況考慮：

??1. 高速緩存行中為空，這叫做冷不命中 。

??2.高速緩存中有數(shù)據(jù)塊，但沒有數(shù)據(jù)塊10，這叫做緩存不命中 。接下來緩存請(qǐng)求主存將該塊復(fù)制到高速緩存，高速緩存接收到之后將替換一個(gè)現(xiàn)有的數(shù)據(jù)塊，從而存儲(chǔ)新的數(shù)據(jù)塊在高速緩存中。最后，高速緩存將數(shù)據(jù)塊10返回給CPU。

??3. 高速緩存中有數(shù)據(jù)，將內(nèi)存中的數(shù)據(jù)塊放置到高速緩存中時(shí)，發(fā)生了沖突，這叫做沖突不命中 。

放置策略中最常用的是：第k+1層的塊i必須放在第k層的塊（i mod 4）中。比如，第k+1層的0,4,8,12會(huì)映射到第k層的塊0。塊1,5,9,13會(huì)映射到塊1。

??4. 緩存中有數(shù)據(jù)塊10，則直接返回給CPU。這叫做緩存命中 。

3.2 計(jì)算機(jī)中的高速緩存存儲(chǔ)器模型

??高速緩存完全由硬件管理，硬件邏輯必須要知道，如何查找緩存中的塊，并確定是否包含特定塊。因此，必須以非常嚴(yán)格且簡單的方式去構(gòu)建高速緩存。在計(jì)算機(jī)中，高速緩存模型如下圖所示。

計(jì)算機(jī)中的高速緩存模型

??我們可以將高速緩存存儲(chǔ)器視為有個(gè)高速緩存組的數(shù)組 。每個(gè)組包含個(gè)高速緩存行 。每個(gè)行是由一個(gè)字節(jié)的數(shù)據(jù)塊組成的。

??一般而言，高速緩存的結(jié)構(gòu)可以用元組（S,E,B,m）來描述。高速緩存的大小（或容量）C指的是所有塊的大小的和。標(biāo)記位和有效位不包括在內(nèi) 。因此，C=S×E×B。

??每個(gè)高速緩存存儲(chǔ)器有m位，可以組成個(gè)不同的地址，。每個(gè)數(shù)據(jù)塊由以下三部分構(gòu)成。

??有效位：有效位為t位，t一般為1，指明這個(gè)行是否包含有效信息。

??標(biāo)記位：標(biāo)記位為s位。唯一的標(biāo)識(shí)了存儲(chǔ)在高速緩存中的塊（數(shù)組索引）。

??塊偏移：數(shù)據(jù)塊為字節(jié)。指明CPU請(qǐng)求的內(nèi)容在數(shù)據(jù)塊中的偏移。

地址和計(jì)算機(jī)緩存模型

??下面對(duì)以上內(nèi)容出現(xiàn)的參數(shù)做個(gè)總結(jié)：

3.3 計(jì)算機(jī)中有哪些緩存

?下表為現(xiàn)代計(jì)算機(jī)中用到的各種緩存。

3.4 硬件讀取高速緩存的過程

??當(dāng)一條加載指令指示CPU從主存地址A中讀取一個(gè)字w時(shí)，會(huì)將該主存地址A發(fā)送到高速緩存中，則高速緩存會(huì)根據(jù)以下步驟判斷地址A是否命中：

??組選擇：根據(jù)地址劃分，將中間的s位表示為無符號(hào)數(shù)作為組的索引 ，可得到該地址對(duì)應(yīng)的組。

??行匹配：根據(jù)地址劃分，可得到t位的標(biāo)志位，由于組內(nèi)的任意一行都可以包含任意映射到該組的數(shù)據(jù)塊，所以就要線性搜索組中的每一行，判斷是否有和標(biāo)志位匹配且設(shè)置了有效位的行 ，如果存在，則緩存命中，否則緩沖不命中。

??字抽取：如果找到了對(duì)應(yīng)的高速緩存行，則可以將b位表示為無符號(hào)數(shù)作為塊偏移量 ，得到對(duì)應(yīng)位置的字。

??當(dāng)高速緩存命中時(shí)，會(huì)很快抽取出字w，并將其返回給CPU。如果緩存不命中，CPU會(huì)進(jìn)行等待，高速緩存會(huì)向主存請(qǐng)求包含字w的數(shù)據(jù)塊，當(dāng)請(qǐng)求的塊從主存到達(dá)時(shí)，高速緩存會(huì)將這個(gè)塊保存到它的一個(gè)高速緩存行中，然后從被存儲(chǔ)的塊中抽取出字w，將其返回給CPU。

4. 直接映射高速緩存

??上面我們介紹了計(jì)算機(jī)中的高速緩存模型，我們可以根據(jù)每個(gè)組的高速緩存行數(shù)E，將高速緩存分成不同的類型。下面我們看下直接映射高速緩存（E=1）的具體例子。

4.1 組選擇

??組選擇示意圖如下所示。假設(shè)有 S 組，每組由一行組成，緩存塊為8字節(jié)。CPU發(fā)出地址要取數(shù)據(jù)字，高速緩存將該地址分解為三部分，對(duì)于圖中的地址來說，塊偏移量為4。組索引是 1 ，粉紅色的為t位標(biāo)記位。因此，高速緩存提取的組索引為 1，即圖中第二行。

直接映射高速緩存組選擇

4.2 行匹配

??然后，檢查地址中的標(biāo)記位與緩存行中的標(biāo)記位是否匹配。如果匹配，將進(jìn)行下一步字選擇。如果不匹配，則表示未命中。在未命中時(shí)，高速緩存必須從內(nèi)存中重新取數(shù)據(jù)塊， 在行中覆蓋此塊。

直接映射高速緩存行匹配

4.3 字選擇

??當(dāng)標(biāo)記位匹配時(shí)，表示命中，接著檢查地址中的塊偏移為4，即要從緩存行數(shù)據(jù)塊的第5位開始取值，并返回給CPU。

直接映射高速緩存字選擇

4.4 模擬直接映射緩存

??下面，我們模擬下直接映射高速緩存的過程，以便加深理解高速緩存是如何工作的。假設(shè)，內(nèi)存地址為4字節(jié)，S=4組，E=1行/組，B=2字節(jié)/塊。其結(jié)構(gòu)圖如下所示。

模擬直接映射高速緩存地址結(jié)構(gòu)圖

??我們模擬CPU要從高速緩存中讀取地址為0,1,7,8,0的數(shù)據(jù)。下面是具體的過程。

??1. 讀地址0的數(shù)據(jù)。標(biāo)記位為0，索引位為00，偏移位為0，塊號(hào)為0。緩存行中沒有數(shù)據(jù)，組0的有效位為0，地址的標(biāo)記位和組0的標(biāo)記位不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊0，塊1， 共2字節(jié)，并存儲(chǔ)在組0中。具體如下圖所示。

模擬直接映射高速緩存讀地址0的數(shù)據(jù)

??2. 讀地址1的數(shù)據(jù)。標(biāo)記位為0，索引位為00，偏移位為1，塊號(hào)1。緩存行中已有數(shù)據(jù)數(shù)據(jù)，組0的有效位為1，地址1的標(biāo)記位和組0的標(biāo)記位匹配，因此，命中。具體如下圖所示。

模擬直接映射高速緩存讀地址1的數(shù)據(jù)

??3. 讀地址7的數(shù)據(jù)。標(biāo)記位為0，索引位為11（3），偏移位為1，塊號(hào)為3。緩存行中有數(shù)據(jù)，組3的有效位為0，地址的標(biāo)記位和組0的標(biāo)記位不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊6，塊7， 共2字節(jié)，并存儲(chǔ)在組3中。具體如下圖所示。

模擬直接映射高速緩存讀地址7的數(shù)據(jù)

?? 4. 讀地址8的數(shù)據(jù)。標(biāo)記位為1，索引位為00，偏移位為0，塊號(hào)為4。緩存行中有數(shù)據(jù)，組0的有效位為1，地址的標(biāo)記位和組0的標(biāo)記位不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊8，塊9， 共2字節(jié)，并存儲(chǔ)在組0中。具體如下圖所示。

模擬直接映射高速緩存讀地址8的數(shù)據(jù)

?? 5. 讀地址0的數(shù)據(jù)。標(biāo)記位為0，索引位為00，偏移位為0，塊號(hào)為0。緩存行中有數(shù)據(jù)，組0的有效位為1，地址的標(biāo)記位和組0的標(biāo)記位不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊0，塊1， 共2字節(jié)，并存儲(chǔ)在組0中。具體如下圖所示。

模擬直接映射高速緩存再次讀地址0的數(shù)據(jù)

??最終結(jié)果如下：緩存命中率為20%。

注意：塊大小為2字節(jié)，所以從內(nèi)存中取數(shù)據(jù)總是以偶數(shù)倍開始的，所以會(huì)看到M[8-9],而不是M[7-8]。

??如果你看懂了上述高速緩存的整個(gè)過程，考慮下如何編程來模擬高速緩存呢？后面的文章我會(huì)詳細(xì)講解如何用C語言模擬高速緩存，歡迎關(guān)注我的公眾號(hào)【嵌入式與Linux那些事】，第一時(shí)間獲取更新。

4.5 直接映射高速緩存的缺陷

??觀察以上過程其實(shí)可以發(fā)現(xiàn)，在第5步，讀地址0的數(shù)據(jù)的時(shí)候，我們又得重新從內(nèi)存中取數(shù)據(jù)到緩存行中。在讀地址8的數(shù)據(jù)的時(shí)候，M[8-9]替換了緩存行中的M[0-1]。

??最主要的原因是每一個(gè)組中只允許存放一行緩存。假設(shè)，E = 2，每組中有2個(gè)緩存行，M[8-9]和M[0-1]就有很大可能同時(shí)存在于組0中。我們?cè)诘?步訪問時(shí)，就不需要重新從內(nèi)存中取數(shù)據(jù)了。因此，就有了E = 2的兩路相聯(lián)高速緩存。

5. 兩路相聯(lián)高速緩存

??直接映射高速緩存中沖突不命中造成的問題源于每個(gè)組只有一行這個(gè)限制。組相聯(lián)高速存放松了這條限制，所以每個(gè)組都保存有多于一個(gè)的高速緩存行。如下圖所示為兩路相聯(lián)的高速緩存。

5.1 組選擇

??它的組選擇與直接映射高速緩存的組選擇一樣，組索引位標(biāo)識(shí)組。具體如下圖所示，這里不再贅述。

兩路相聯(lián)高速緩存組選擇

5.2 行匹配

??組相聯(lián)高速緩存中的行匹配比直接映射高速緩存中的更復(fù)雜，因?yàn)樗仨毭看螜z查多個(gè)行 的標(biāo)記位和有效位，以確定所請(qǐng)求的字是否在集合中。具體如下圖所示。

兩路相聯(lián)高速緩存行匹配

5.3 字選擇

??字選擇的過程和直接映射高速緩存中的方式一樣，這里就不再贅述。

兩路相聯(lián)高速緩存字選擇

5.4 模擬兩路相聯(lián)高速緩存

??下面，我們模擬下兩路相聯(lián)高速緩存的過程，以便加深理解高速緩存是如何工作的。假設(shè)，內(nèi)存地址為4字節(jié)，S=2組，E=2行/組，B=2字節(jié)/塊。其結(jié)構(gòu)圖如下所示。

兩路相聯(lián)高速緩存地址結(jié)構(gòu)

??我們模擬CPU要從高速緩存中讀取地址為0,1,7,8,0的數(shù)據(jù)。下面是具體的過程。

??1. 讀地址0的數(shù)據(jù)。標(biāo)記位為00，索引位為0，偏移位為0，塊號(hào)為0。緩存行中沒有數(shù)據(jù)，組0的有效位為0，地址的標(biāo)記位和組0的第一行和第二行的標(biāo)記位都不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊0，塊1， 共2字節(jié)，并存儲(chǔ)在組0第一行中。具體如下圖所示。

模擬兩路相聯(lián)高速緩存讀地址0的數(shù)據(jù)

??2. 讀地址1的數(shù)據(jù)。標(biāo)記位為00，索引位為0，偏移位為1，塊號(hào)為1。緩存行中已有數(shù)據(jù)數(shù)據(jù)，組0的第一行有效位為1，地址1的標(biāo)記位和組0的第一行標(biāo)記位匹配，因此，命中。具體如下圖所示。

模擬兩路相聯(lián)高速緩存讀地址1的數(shù)據(jù)

??3. 讀地址7的數(shù)據(jù)。標(biāo)記位為01，索引位為1，偏移位為1，塊號(hào)為1。緩存行中有數(shù)據(jù)，組1的有效位為0，地址的標(biāo)記位和組1中的第一行和第二行的標(biāo)記位不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊6，塊7， 共2字節(jié)，并存儲(chǔ)在組1中。具體如下圖所示。

模擬兩路相聯(lián)高速緩存讀地址7的數(shù)據(jù)

?? 4. 讀地址8的數(shù)據(jù)。標(biāo)記位為10，索引位為0，偏移位為0，塊號(hào)為0。緩存行中有數(shù)據(jù)，組0的第一行有效位為1，第二行有效位為0，地址的標(biāo)記位和組0的第一行和第二行的標(biāo)記位不匹配，因此，未命中。然后，高速緩存從內(nèi)存中取出塊8，塊9， 共2字節(jié)，并存儲(chǔ)在組0的第二行中。具體如下圖所示。

模擬兩路相聯(lián)高速緩存讀地址8的數(shù)據(jù)

?? 5. 讀地址0的數(shù)據(jù)。標(biāo)記位為00，索引位為0，偏移位為0，塊號(hào)為0。緩存行中有數(shù)據(jù)，組0的第一行有效位為1，地址的標(biāo)記位和組0的第一行的標(biāo)記位匹配，因此，命中。具體如下圖所示。

模擬兩路相聯(lián)高速緩存再次讀地址0的數(shù)據(jù)

??兩路相聯(lián)高速緩存與直接映射高速緩存相比，在每組中增加了一行，緩存命中率提升了15%。避免了緩存頻繁從內(nèi)存中存取數(shù)據(jù)的情況，提高了程序運(yùn)行速度。

6. 全相聯(lián)高速緩存

??全相聯(lián)高速緩存中的行匹配和字選擇與組相聯(lián)高速緩存中的是一樣的，過程就不再贅述，其結(jié)構(gòu)圖如下所示。

全相聯(lián)高速緩存結(jié)構(gòu)示意圖

相聯(lián)度越高越好嗎？

答案是否定的。較高的相聯(lián)度會(huì)造成較高的成本。實(shí)現(xiàn)難度大，價(jià)格昂貴，而且很難使之速度變快。較高的相聯(lián)度會(huì)增加命中時(shí)間，因?yàn)閺?fù)雜性增加了，另外，還會(huì)增加不命中處罰，因?yàn)檫x擇犧牲行的復(fù)雜性也增加了。

相聯(lián)度的選擇最終變成了命中時(shí)間和不命中處罰之問的折中。一般來講，高性能系統(tǒng)會(huì)為L1高速緩存選擇較低的相聯(lián)度（這里的不命中處罰只是幾個(gè)周期），而在不命中處罰比較高的較低層上使用比較小的相聯(lián)度。例如， Intel Core i7系統(tǒng)中，L和L2高速緩存是8路組相聯(lián)的，而L3高速緩存是16路組相聯(lián)的。

7. 真實(shí)計(jì)算機(jī)系統(tǒng)中的緩存

??在此之前，我們一直假設(shè)高速緩存只保存數(shù)據(jù)。不過，實(shí)際上，高速緩存既保存數(shù)據(jù)，也保存指令。只保存指令的高速緩存稱為 i-cache 。只保存程序數(shù)據(jù)的高速緩存稱為 d-cache 。既保存指令又包括數(shù)據(jù)的高速緩存稱為 統(tǒng)一的高速緩存 。

??如下圖所示為 Intel Core i7處理器的高速緩存層次結(jié)構(gòu)。每個(gè)CPU芯片有四個(gè)核。每個(gè)核有自己的L1 i-cache， L1 d-cache和L2統(tǒng)一的高速緩存。所有的核共享片上L3統(tǒng)一的高速緩存。其具體參數(shù)如下表所示。

真實(shí)計(jì)算機(jī)的緩存模型

8. 緩存的評(píng)價(jià)指標(biāo)

??最后介紹下衡量高速緩存性能的一些指標(biāo)：

8.1 不命中率

??在一個(gè)程序執(zhí)行或程序的一部分執(zhí)行期間，內(nèi)存引用不命中的比率，它等于： 不命中數(shù)量/引用數(shù)量。

8.2 命中率

??命中的內(nèi)存引用比率。它等于： 1-不命中率。

8.3 命中時(shí)間

??從高速緩存?zhèn)魉鸵粋€(gè)字到CPU所需的時(shí)間，包括組選擇、行確認(rèn)和字選擇的時(shí)間。一般來講，L1緩存的命中時(shí)間為：4個(gè)時(shí)鐘。L2緩存的命中時(shí)間為：10個(gè)時(shí)鐘。

8.4 未命中懲罰

??未命中需要的額外時(shí)間。對(duì)于主存來說，一般為 50 ~ 200個(gè)時(shí)鐘周期。

舉個(gè)例子：

假設(shè)緩存命中時(shí)間為1個(gè)時(shí)鐘周期，緩存未命中懲罰為100個(gè)時(shí)鐘周期。

下面計(jì)算下97%緩存命中率和99%的緩存命中率的平均訪問時(shí)間為多少？計(jì)算公式為命中時(shí)間加上未命中處罰乘以百分系數(shù)。

97%的命中率：時(shí)鐘。

99%的命中率：時(shí)鐘。

結(jié)論：命中率增加2%，平均訪問時(shí)間減少了50%。

9. 總結(jié)

??計(jì)算機(jī)中存在著各種各樣的緩存，比如， 文件緩存 把一些需要高速存取的變量緩存在內(nèi)存中，每次訪問直接讀出即可。 瀏覽器緩存 根據(jù)一套與服務(wù)器約定的規(guī)則進(jìn)行工作，如果在瀏覽過程中前進(jìn)或后退時(shí)訪問到同一個(gè)圖片，這些圖片可以從瀏覽器緩存中調(diào)出而即時(shí)顯示。數(shù)據(jù)庫緩存 經(jīng)常需要從數(shù)據(jù)庫查詢的數(shù)據(jù)、或經(jīng)常更新的數(shù)據(jù)放入到緩存中，這樣下次查詢時(shí)，直接從緩存直接返回，減輕數(shù)據(jù)庫壓力。

??我們了解這么多基本概念有什么用呢？如果我們理解了計(jì)算機(jī)系統(tǒng)是如何將數(shù)據(jù)在內(nèi)存中組織和移動(dòng)的，那么在寫程序時(shí)就可以把數(shù)據(jù)項(xiàng)存儲(chǔ)在合適的位置，CPU能更快地訪問到它們，提高程序的執(zhí)行效率。

審核編輯：劉清