超標(biāo)量處理器中，Cache和分支預(yù)測(cè)會(huì)直接影響著性能，分支預(yù)測(cè)的內(nèi)容將在其它博文中介紹，本文重點(diǎn)關(guān)注超標(biāo)量處理器中的Cache。

Cache之所以存在，是因?yàn)榇鎯?chǔ)器的速度遠(yuǎn)遠(yuǎn)滯后于處理器的速度，人們觀察到在計(jì)算機(jī)的世界中，存在如下的兩個(gè)現(xiàn)象：

時(shí)間相關(guān)性（temporal locality）：如果一個(gè)數(shù)據(jù)現(xiàn)在被訪問(wèn)了，那么以后很有可能也會(huì)被訪問(wèn)；

空間相關(guān)性（spatial locally）：如果一個(gè)數(shù)據(jù)現(xiàn)在被訪問(wèn)了，那么它周?chē)臄?shù)據(jù)在以后可能也會(huì)被訪問(wèn)；

處理器中的各種cache示意如圖1所示，現(xiàn)代超標(biāo)量處理器都是哈佛結(jié)構(gòu)，為了增加流水線的執(zhí)行效率，L1 Cache一般都包括兩個(gè)物理的存在，指令Cache(I-Cache)和數(shù)據(jù)Cache(D-Cache)，本質(zhì)上兩者是一樣的，I-Cache只會(huì)發(fā)生讀情況，D-Cahce既可以讀也可以寫(xiě)，所以更復(fù)雜點(diǎn)，L1 Cach緊密耦合在處理器的流水線中，主打功能就是求快。

L2通常是指令和數(shù)據(jù)共享，它和處理器的速度不必保持同樣，可以容忍慢點(diǎn)，它存在的主要意義是盡量保存更多的內(nèi)容，即求全。

在L1 Cache miss的情況下，會(huì)去訪問(wèn)L2 Cache，加入L2 Cache在缺失時(shí)去訪問(wèn)物理內(nèi)存(一般是DRAM)，這個(gè)訪問(wèn)時(shí)間很長(zhǎng)，因此要盡可能地提高L2 Cache的命中率。

L1 Cache和L2 Cache是和處理器聯(lián)系最緊密的，通常采用SRAM實(shí)現(xiàn)。物理主存Main memory通常是采用DRAM實(shí)現(xiàn)的。

再往下就是硬盤(pán)(Disk)和閃存(Flash)。層層嵌套，CPU擁有存儲(chǔ)器相當(dāng)于硬盤(pán)的大小和SRAM的速度。

L1 Cache和L2 Cache通常和處理器是在一塊實(shí)現(xiàn)的。

在SoC中，主存和處理器之間通過(guò)總線SYSBUS連接起來(lái)。

?

圖1 處理器中的各種Cache

Cache主要由兩部分組成，Tag部分和Data部分。因?yàn)镃ache是利用了程序中的相關(guān)性，一個(gè)被訪問(wèn)的數(shù)據(jù)，它本身和它周?chē)臄?shù)據(jù)在最近都有可能被訪問(wèn)，因此Data部分就是用來(lái)保存一片連續(xù)地址的數(shù)據(jù)，而Tag部分則是存儲(chǔ)著這片連續(xù)地址的公共地址，一個(gè)Tag和它對(duì)應(yīng)的所有數(shù)據(jù)Data組成一行稱(chēng)為Cache line，而Cache line中的數(shù)據(jù)部分成為數(shù)據(jù)塊(Cache data block，也稱(chēng)做Cache block或Data block)。

如果一個(gè)數(shù)據(jù)可以存儲(chǔ)在Cache的多個(gè)地方，這些被同一個(gè)地址找到的多個(gè)Cache line稱(chēng)為Cache set。

以上關(guān)系如圖2所示。



圖2 Cache的結(jié)構(gòu)

圖2中只表示了一種可能的實(shí)現(xiàn)方式，在實(shí)際當(dāng)中，Cache有三種主要的實(shí)現(xiàn)方式，直接映射(direct-mapped)Cache，組相連(set-associative)Cache和全相連(full-associative)Cache，實(shí)現(xiàn)原理如圖3所示。

對(duì)于物理內(nèi)存(physical memory)中的一個(gè)數(shù)據(jù)來(lái)說(shuō)，如果在Cache中只有一個(gè)地方可以容納它，它就是直接映射的Cache；如果Cache中有多個(gè)地方可以放置這個(gè)數(shù)據(jù)，它就是組相連的Cache；如果Cache中任何的地方都可以放置這個(gè)數(shù)據(jù)，那么它就是全相連的Cache?？梢钥闯觯苯佑成浜腿噙B映射這兩種結(jié)構(gòu)的Cache實(shí)際上是組相連Cache的兩種特殊情況，現(xiàn)代處理器中的Cache一般屬于上述三種方式的一種，例如TLB和Victim Cache多采用全相連結(jié)構(gòu)，而普通的I-Cache和D-Cache則采用組相連結(jié)構(gòu)等。



圖3 Cache的三種實(shí)現(xiàn)方式

1. Cache的組成方式

1.1 直接映射

直接映射結(jié)構(gòu)的Cache是最容易實(shí)現(xiàn)的一種方式，處理器訪問(wèn)存儲(chǔ)器的地址會(huì)被分為三部分：Tag、Index和Block Offset。

如圖4所示，使用Index來(lái)從Cache中找到一個(gè)對(duì)應(yīng)的Cacheline，但是所有Index相同的地址都會(huì)尋址到這個(gè)Cacheline，因此在Cacheline中還有Tag部分，用來(lái)和地址中的Tag進(jìn)行比較，只有它們相等才表明這個(gè)Cacheline就是想要的那個(gè)。

在一個(gè)Cacheline中有很多數(shù)據(jù)，通過(guò)存儲(chǔ)器地址中的Block Offset部分可以找到真正想要的數(shù)據(jù)，它可以定位到每個(gè)字節(jié)。

在Cacheline中還有一個(gè)有效位(Valid)，用來(lái)標(biāo)記這個(gè)Cacheline是否保存著有效的數(shù)據(jù)，只有在之前被訪問(wèn)過(guò)的存儲(chǔ)器地址，它的數(shù)據(jù)才會(huì)存在于對(duì)應(yīng)的Cacheline中，相應(yīng)的有效位也會(huì)被置為1。

直接映射有個(gè)缺點(diǎn)，就是對(duì)于所有Index相同的存儲(chǔ)器地址，都會(huì)尋址到同一個(gè)Cacheline，如果兩個(gè)Index部分相同的存儲(chǔ)器地址交互地訪問(wèn)Cache，就會(huì)一直導(dǎo)致Cache缺失，嚴(yán)重地降低了處理器的執(zhí)行效率。

圖4 直接映射Cache

1.2 組相連

組相連的方式是為了解決直接映射結(jié)構(gòu)Cache的不足而提出的，存儲(chǔ)器中的一個(gè)數(shù)據(jù)不單單只能放在一個(gè)Cacheline中，而是可以放在多個(gè)Cacheline中，對(duì)于一個(gè)組相連結(jié)構(gòu)的Cache來(lái)說(shuō)，如果一個(gè)數(shù)據(jù)可以放在n個(gè)位置，則稱(chēng)這個(gè)Cache是n路組相連的Cache(n way set-associative Cache)，圖5為一個(gè)兩路組相連Cache的原理圖。

圖5 2路組相連映射Cache

這種結(jié)構(gòu)仍舊使用存儲(chǔ)器地址的Index部分對(duì)Cache進(jìn)行尋址，此時(shí)可以得到兩個(gè)Cacheline，這兩個(gè)Cacheline稱(chēng)為一個(gè)Cache set，究竟哪個(gè)Cacheline才是最終需要的，是根據(jù)Tag比較的結(jié)果來(lái)確定的，如果兩個(gè)Cacheline的Tag比較結(jié)果都不相等，那么就說(shuō)明這個(gè)存儲(chǔ)器地址對(duì)應(yīng)的數(shù)據(jù)不在Cache中，也就是發(fā)生了Cache缺失。

這種方式在實(shí)際處理器中應(yīng)用最為廣泛，上面提到的Tag部分和Data部分都是分開(kāi)放置的，稱(chēng)為T(mén)ag SRAM和Data SRAM，可以同時(shí)訪問(wèn)這兩部分。

圖5所示為并行訪問(wèn)，如果先訪問(wèn)Tag SRAM部分，根據(jù)Tag比較的結(jié)果再去訪問(wèn)Data SRAM部分，就稱(chēng)為串行訪問(wèn)。

圖6為并行訪問(wèn)方法的示意圖，對(duì)于并行訪問(wèn)的結(jié)構(gòu)，當(dāng)某個(gè)地址的Tag部分被讀取的同時(shí)，這個(gè)地址在Data部分對(duì)應(yīng)的所有數(shù)據(jù)也會(huì)被讀取出來(lái)，并送到一個(gè)多路選擇器，這個(gè)多路選擇器受到Tag部分比較結(jié)果的控制，選出對(duì)應(yīng)的Data block，然后根據(jù)存儲(chǔ)器地址中Block Offset的值，選擇出合適的字節(jié)，一般將選擇字節(jié)的這個(gè)過(guò)程稱(chēng)為數(shù)據(jù)對(duì)齊(Data Alignment)。



圖6 并行訪問(wèn)Cache中的Tag和Data部分

如圖7為串行訪問(wèn)實(shí)現(xiàn)方式，對(duì)于串行訪問(wèn)方法來(lái)說(shuō)，首先對(duì)Tag SRAM進(jìn)行訪問(wèn)，根據(jù)Tag比較的結(jié)果，就可以知道數(shù)據(jù)部分中，哪一路的數(shù)據(jù)時(shí)需要被訪問(wèn)的，此時(shí)可以直接訪問(wèn)這一路的數(shù)據(jù)，這樣就不在需要圖6中的多路選擇器，而且，只需要訪問(wèn)數(shù)據(jù)部分指定的那個(gè)SRAM，其它的SRAM由于都不需要被訪問(wèn)，可以將它們的使能信號(hào)置為無(wú)效，這樣可以節(jié)省很多功耗，當(dāng)然串行訪問(wèn)在延遲上會(huì)更大。

圖7 串行訪問(wèn)Cache中的Tag部分和Data部分

1.3 全相連

在全相連中，一個(gè)存儲(chǔ)器地址的數(shù)據(jù)可以放在任何一個(gè)cacheline中，如圖8所示，存儲(chǔ)器地址中將不再有Index部分，而是直接在整個(gè)的Cache中進(jìn)行Tag值比較，找到比較結(jié)果相等的那個(gè)Cache line，這種方式相當(dāng)于直接使用存儲(chǔ)器的內(nèi)容來(lái)尋址，從存儲(chǔ)器中找到匹配的項(xiàng)，這其實(shí)就是內(nèi)容尋址的存儲(chǔ)器( Content Address Memory, CAM)，實(shí)際當(dāng)中的處理器在使用全相連結(jié)構(gòu)的Cache時(shí)，都是使用CAM來(lái)存儲(chǔ)Tag值，使用普通的SRAM來(lái)存儲(chǔ)數(shù)據(jù)的。

當(dāng)CAM中的某一行被尋址到時(shí)，SRAM中對(duì)應(yīng)的行(一般稱(chēng)為word line)也將會(huì)被找到，從而SRAM可以直接輸出對(duì)應(yīng)的數(shù)據(jù)。

圖8 全相連

2. Cache的寫(xiě)入

2.1 寫(xiě)通和寫(xiě)回

對(duì)于D-Cache來(lái)說(shuō)，它的寫(xiě)操作和讀操作有所不同，當(dāng)執(zhí)行一條store指令時(shí)，如果只是向D-Cache中寫(xiě)入數(shù)據(jù)，而并不改變它的下級(jí)存儲(chǔ)器中的數(shù)據(jù)，這樣就會(huì)導(dǎo)致D-Cache和下級(jí)存儲(chǔ)器中，對(duì)于這一個(gè)地址有著不同的數(shù)據(jù)，這稱(chēng)作不一致(non-consistent)。

要想保持它們的一致性，最簡(jiǎn)單的方式就是當(dāng)數(shù)據(jù)在寫(xiě)到D-Cache的同時(shí)，也寫(xiě)到它的下級(jí)存儲(chǔ)器中，這種寫(xiě)入方式稱(chēng)為寫(xiě)通(Write Through)。

由于D-cache的下級(jí)存儲(chǔ)器需要的訪問(wèn)時(shí)間相對(duì)是比較長(zhǎng)的，而store指令在程序中出現(xiàn)的頻率又比較高，如果每次執(zhí)行store指令時(shí)，都向這樣的慢速存儲(chǔ)器中寫(xiě)入數(shù)據(jù)，處理器的執(zhí)行效率肯定不會(huì)很高了。

如果在執(zhí)行store指令時(shí)，數(shù)據(jù)被寫(xiě)到D-Cache后，只是將被寫(xiě)入的Cacheline做一個(gè)記號(hào)，并不將這個(gè)數(shù)據(jù)寫(xiě)到更下級(jí)的存儲(chǔ)器中，只有當(dāng)Cache中這個(gè)被標(biāo)記的line要被替換時(shí)，才將它寫(xiě)到下級(jí)存儲(chǔ)器中，這種方式就稱(chēng)為 寫(xiě)回(Write Back)，被標(biāo)記的記號(hào)在計(jì)算機(jī)術(shù)語(yǔ)中稱(chēng)為臟(dirty)狀態(tài)，很顯然，這種方式可以減少寫(xiě)慢速存儲(chǔ)器的頻率，從而獲得比較好的性能。

當(dāng)然，這種方式會(huì)造成D-Cache和下級(jí)存儲(chǔ)器中有很多地址中的數(shù)據(jù)是不一致的，這會(huì)給存儲(chǔ)器的一致性管理帶來(lái)一定的負(fù)擔(dān)。

2.2 Non-Write Allocate和Write Allocate

上面所講述的情況都是假設(shè)在寫(xiě)D-Cache時(shí)，要寫(xiě)入的地址總是D-Cache中存在的，而實(shí)際當(dāng)中，有可能發(fā)現(xiàn)這個(gè)地址并不在D-Cache中，這就發(fā)生了寫(xiě)缺失(write miss)，此時(shí)最簡(jiǎn)單的處理方法就是將數(shù)據(jù)直接寫(xiě)到下級(jí)存儲(chǔ)器中，而并不寫(xiě)到D-Cache中，這種方式稱(chēng)為Non-Write Allocate。

與之相對(duì)應(yīng)的方法就是Write Allocate，在這種方法中，如果寫(xiě)Cache時(shí)發(fā)生了缺失，會(huì)首先從下級(jí)存儲(chǔ)器中將這個(gè)發(fā)生缺失的地址對(duì)應(yīng)的整個(gè)數(shù)據(jù)塊(data block)取出來(lái)，將要寫(xiě)入到D-Cache中的數(shù)據(jù)合并到這個(gè)數(shù)據(jù)塊中，然后將這個(gè)被修改過(guò)的數(shù)據(jù)塊寫(xiě)到D-Cache中。

如果為了保持存儲(chǔ)器的一致性，將這個(gè)數(shù)據(jù)塊也寫(xiě)到下級(jí)存儲(chǔ)器中，這種方法就是上小節(jié)說(shuō)過(guò)的寫(xiě)通(Write Through)。

如果只是將D-Cache中對(duì)應(yīng)的line標(biāo)記為臟(Dirty)的狀態(tài)，只有等到這個(gè)line要被替換時(shí)，才將其寫(xiě)回到下級(jí)存儲(chǔ)器中，則這種方法就是前面提到的寫(xiě)回(Write Back)。

Write Allocate為什么在寫(xiě)缺失時(shí)，要先將缺失地址對(duì)應(yīng)的數(shù)據(jù)塊從下級(jí)存儲(chǔ)器中讀取出來(lái)，然后在合并后寫(xiě)到Cache中？

因?yàn)橥ǔ?duì)于寫(xiě)D-Cache來(lái)說(shuō)，最多也就是寫(xiě)入一個(gè)字，直接寫(xiě)入Cache的話，會(huì)造成數(shù)據(jù)塊中的其它部分和下級(jí)存儲(chǔ)器中對(duì)應(yīng)的數(shù)據(jù)不一致，且是無(wú)效的，如果這個(gè)cacheline由于被替換而寫(xiě)回到下級(jí)存儲(chǔ)器中時(shí)，就會(huì)使下級(jí)存儲(chǔ)器中的正確數(shù)據(jù)被篡改。

通過(guò)上面的描述可以看出，對(duì)于D-Cache來(lái)說(shuō)，一般情況下，寫(xiě)通(Write Through)總是配合Non-Write Allocate一起使用的，它們都是直接將數(shù)據(jù)更新到下級(jí)存儲(chǔ)器中，這兩種方法配合的工作流程如圖9所示。



圖9 Write Through和Non-Write Allocate兩種方法配合工作的流程圖

在D-Cache中，寫(xiě)回(Write back)的方法和Write Allocate也是配合在一起使用的，它的工作流程如圖10所示。



圖10 Write back和Write Allocate配合工作的流程圖

由圖10可以看出，在D-Cache中采用寫(xiě)回(Write back)的方法時(shí)，不管是讀取還是寫(xiě)入時(shí)發(fā)生缺失，都需要從D-Cache中找到一個(gè)line來(lái)存放新的數(shù)據(jù)，這個(gè)被替換的line如果此時(shí)是臟(dirty)狀態(tài)，那么首先需要將其中的數(shù)據(jù)寫(xiě)回到下級(jí)存儲(chǔ)器中，然后才能夠使用這個(gè)line存放新的數(shù)據(jù)。

也就是說(shuō)，當(dāng)D-Cache中被替換的line是臟的狀態(tài)時(shí)，需要對(duì)下級(jí)存儲(chǔ)器進(jìn)行兩次訪問(wèn)，首先需要將這個(gè)line中的數(shù)據(jù)寫(xiě)回到下級(jí)存儲(chǔ)器，然后需要從下級(jí)存儲(chǔ)器中讀取缺失的地址對(duì)應(yīng)的數(shù)據(jù)塊，并將其寫(xiě)到剛才找到的Cache line中。

對(duì)于D-Cache來(lái)說(shuō)，還需要將寫(xiě)入的數(shù)據(jù)也放到這個(gè)line中，并將其標(biāo)記為臟的狀態(tài)。

從圖9和圖10可以看出，采用寫(xiě)回和Write Allocate配合工作的方法，其設(shè)計(jì)復(fù)雜度要高于寫(xiě)通和Non-Write Allocate配合工作的方法，但是它可以減少寫(xiě)下級(jí)存儲(chǔ)器的頻率，從而使處理器獲得比較好的性能。

3. Cache的替換策略

在一個(gè)Cache Set內(nèi)的所有l(wèi)ine都已經(jīng)被占用的情況下，如果需要存放從下游存儲(chǔ)器中讀過(guò)來(lái)的其它地址的數(shù)據(jù)，那么就需要從其中替換一個(gè)，如何從這些有效的Cache line找到一個(gè)并替換之，這就是替換(Cache replacement)策略。本節(jié)主要介紹幾種最常用的替換算法。

3.1 近期最少使用法

近期最少使用法(Least Recently Used, LRU)會(huì)選擇最近被使用次數(shù)最少的Cache line，因此這個(gè)算法需要追蹤每個(gè)Cache line的使用情況，這需要為每個(gè)Cache line都設(shè)置一個(gè)年齡(age)部分，每次當(dāng)一個(gè)Cache line被訪問(wèn)時(shí)，它對(duì)應(yīng)的年齡部分就會(huì)增加，或者減少其它Cache line的年齡值，這樣當(dāng)進(jìn)行替換時(shí)，年齡值最小的那個(gè)Cacheline就是被使用次數(shù)最少的了，會(huì)選擇它進(jìn)行替換。

圖11為L(zhǎng)RU算法的工作流程。



圖11 LRU算法的工作流程

3.2 替換策略

在處理器中，Cache的替換算法一般都是使用硬件來(lái)實(shí)現(xiàn)的，因此如果做得很復(fù)雜，會(huì)影響處理器的周期時(shí)間，于是就有了隨機(jī)替換(Random Replacement)的實(shí)現(xiàn)方法，這種方法不再需要記錄每個(gè)way的年齡信息，而是隨機(jī)地選擇一個(gè)way進(jìn)行替換，相比于LRU替換方法來(lái)說(shuō)，這種方法確實(shí)的頻率會(huì)更高一些，但是隨著Cache容量的增大，這個(gè)差距是越來(lái)越小的。

當(dāng)然，在實(shí)際的設(shè)計(jì)中很難實(shí)現(xiàn)嚴(yán)格的隨機(jī)，一般采用一種稱(chēng)為時(shí)鐘算法(Clock algorithm)的方法來(lái)實(shí)現(xiàn)近似的隨機(jī)，它的工作原理本質(zhì)上就是一個(gè)計(jì)數(shù)器，這個(gè)計(jì)數(shù)器一直在運(yùn)轉(zhuǎn)，例如每周期加1，計(jì)數(shù)器的寬度由Cache的相關(guān)度，也就是way的個(gè)數(shù)來(lái)決定，例如一個(gè)八路組相連的結(jié)構(gòu)的Cache，則計(jì)數(shù)器的寬度需要三位，每次當(dāng)Cache中的某個(gè)line需要被替換時(shí)，就會(huì)訪問(wèn)這個(gè)計(jì)數(shù)器，使用計(jì)數(shù)器當(dāng)前的值，從被選定的Cache Set中找到要替換的line，這樣就近似地實(shí)現(xiàn)了一種隨機(jī)的替換，這種方法從理論上來(lái)說(shuō)，可能并不能獲得最優(yōu)化的結(jié)果，但是它的硬件復(fù)雜度比較低，也不會(huì)損失過(guò)多的性能，因此綜合來(lái)看是一種不錯(cuò)的折中方法。









審核編輯：劉清