小編科普一下超標(biāo)量處理器中的Cache

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

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

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

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

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

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

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

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

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

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

在SoC中，主存和處理器之間通過總線SYSBUS連接起來。

?

圖1 處理器中的各種Cache

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

如果一個(gè)數(shù)據(jù)可以存儲在Cache的多個(gè)地方，這些被同一個(gè)地址找到的多個(gè)Cache line稱為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所示。

對于物理內(nèi)存(physical memory)中的一個(gè)數(shù)據(jù)來說，如果在Cache中只有一個(gè)地方可以容納它，它就是直接映射的Cache；如果Cache中有多個(gè)地方可以放置這個(gè)數(shù)據(jù)，它就是組相連的Cache；如果Cache中任何的地方都可以放置這個(gè)數(shù)據(jù)，那么它就是全相連的Cache?？梢钥闯?，直接映射和全相連映射這兩種結(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)的一種方式，處理器訪問存儲器的地址會被分為三部分：Tag、Index和Block Offset。

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

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

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

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

圖4 直接映射Cache

1.2 組相連

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

圖5 2路組相連映射Cache

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

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

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

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



圖6 并行訪問Cache中的Tag和Data部分

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

圖7 串行訪問Cache中的Tag部分和Data部分

1.3 全相連

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

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

圖8 全相連

2. Cache的寫入

2.1 寫通和寫回

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

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

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

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

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

2.2 Non-Write Allocate和Write Allocate

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

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

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

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

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

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

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



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

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



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

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

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

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

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

3. Cache的替換策略

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

3.1 近期最少使用法

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

圖11為LRU算法的工作流程。



圖11 LRU算法的工作流程

3.2 替換策略

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

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









審核編輯：劉清