2.1 Cache的一般設計

在超標量處理器中，有兩個部件直接影響著性能，他們是分支預測和Cache。縱觀每次Intel處理器升級，都會使分支預測的精度更高，Cache的命中率更高。

Cache之所以存在，是因為在處理器在計算機的世界中，存在如下兩個現象：

(1) 時間相關性(temporal locality)：如果一個數據現在被訪問了，那么在以后很有可能還會被訪問。

(2) 空間相關性(spatial locality)：如果一個數據現在被訪問了，那么它周圍的數據在以后有可能也會被訪問。

Cache的出現可以說是一種無奈的妥協，因為存儲器技術的發展比處理器技術的發展要慢。

尤其在超標量處理器中，考錄到每周期需要從Cache中同時讀取多條指令，同時每周期也可能有多條load/store指令會訪問Cache，因此需要實現多端口的Cache，這給芯片面積的速度帶來了不小的挑戰。

現代的超標量處理器都是哈佛結構，為了增加流水線的執行效率，L1 Cache一般都包括兩個物理的存在，指令Cache(I-Cache)和數據Cache(D-Cache)，本質來說，他們的原理都是一樣的，但是D-Cache不僅需要讀取，還需要考慮寫入的問題，而I-Cache只會被讀取，并不會被寫入，因此D-Cache更復雜一點。

L1 Cache更靠近處理器，它是流水線的一部分，需要和處理器保持近似的速度，這注定了它的容量不能夠很大。L1 Cache一般是SRAM來實現的，容量大的SRAM需要更長的時間來找到一個指定地址的內容，但是一旦不能和處理器保持速度上近似，L1 Cache就失去的了意義。對于L1 Cache而言，快就是硬道理。

L2 Cache則是為了求“全”。一般情況下，L2 Cache都是指令和數據共享，它和處理器的速度不必保持同樣的步調，可以容忍更慢一些，它的主要功能是為了盡量保存更多的內容。目前L2 Cache都是MB為單位的。在多核之間共享的L2 Cache就更復雜一點，現在處理器一般都是共享L3 Cache。L1 Cache依舊是每個核“私有”的。

在超標量處理器中，對于Cache有著特殊的要求。對于I-Cache來說，需要能夠每周期讀取多條指令，不過，它的延遲時間即使很大，在一般情況下也不會造成處理器性能的下降，仍舊可以實現每周期都可以讀取指令的效果。除非遇見預測跳轉的分支指令時，這些延遲才會對性能造成影響。

對于D-Cache來說，它需要支持在每周期內多條load/store指令的訪問，也就是需要多端口的設計。雖然在超標量處理器中，多端口的部件很多，例如發射隊列Issue Queue，Store Buffer，寄存器堆Register File和重排序緩存ROB等等，但是這些部件的容量本身就很小，所以即使采用多端口設計，也不會占用很大的空間。而D-Cache容量本身就很大，如果采用多端口設計，則占用的硅片面積就很難接受，也會導致更大的延遲，這個延遲會直接暴露給流水線中后續的指令。一般load處于相關性的頂端，所以這回對處理器的性能造成負面的影響。而對于L2 Cache而言，它的被訪問頻率不是很高(L1?Cache的命中率是比較高的)，所以它不需要多端口的設計，它的延遲也不是特別的重要。因為只有發生L1 Cache?miss的時候才會訪問它。但是L2 Cache需要比較高的命中率，因為在它發生缺失時候會去訪問物理內存DRAM，這個訪問時間會很長，因此盡量提高L2 Cache的命中率。

Cache主要由兩部分組成，Tag部分和Data部分。

Data部分就是用來保存一片連續地址的數據，而Tag部分則是存儲著這片連續數據的公共地址。

一個Tag和它對應的所有數據組成的一行稱為一個Cache?line。

而Cache?line中的數據部分稱為數據塊(Cache data block)。

如果一個數據可以存儲在Cache中的多個地方，這些被同一個地址找到的多個Cache?line稱為Cache Set。

?實際中，Cache有三種主要的實現方法，直接映射direct-mapped，組相連set-associative和fullt-associative Cache。

對于一個物理內存而言，如果在Cache中只有一個地方可以容納它，它就是直接映射的Cache；如果有多個地方都可以放置這個數據，它就是組相連的Cahce；如果Cache中任何地方都可以放置這個數據，那么它就是全相連的Cache。

直接相連和全相連實際是組相連Cache中的特殊情況。現代Cache一般屬于上述三種方式中的某一個，例如TLB和Victim Cache多采用全相連結構，而普通的I-Cache和D-Cache則采用組相連結構等。

Cache只能保存最近被處理器使用過的內容，由于它的容量有限，很多情況下，要找的指令或者數據并不在Cache中，這稱為Cache的缺失（Cache?miss）。在計算領域，影響Cache缺失的情況可以概括為：

（1）Compulsory，由于Cache只是緩存以前訪問過的內容，第一次被訪問的指令或數據肯定就不會在Cache中，當然可以采用預取prefetch的方法來盡量降低這種缺失發生的頻率。

（2）Capcacity，Cache容量越大，就可以緩存更多的內容，因此容量是影響Cache缺失發生頻率的一個關鍵因素。例如程序頻繁使用的5個數據屬于不同的Cache?set，而Cache的容量只有4個Cache Set時。

（3）Conflict，為了解決多個數據映射到Cache中同一個位置的情況，一般使用組相連結構的Cache，當然考慮到實際硅片面積的限制，相連度不可能很高。例如，在一個有著兩路結構（2-way）的Cahce中，如果程序頻繁使用的三個數據屬于同一個Cache?set，那么就肯定會發生缺失，此時可以使用Victim Cache來緩解這個問題。

盡管在超標量處理器中，可以采用預期prefetch和victim?cache這兩種方法，但是仍然無法從根本上消除Cache缺失，只能盡量減少它發生的頻率而已。

2.1.1 Cache的組成方式

1.?直接映射

直接映射（direct-mapped）結構的Cache是最容易實現的一種方式，處理器訪問存儲器的地址會被分為三部分，Tag、Index和Block Offset。使用Index來從Cahce中找到一個對應的Cache?lline，但是所有的Index相同的地址都會尋址到這個Cache?line，因此Cache?line中還有Tag部分，用來和地址中的Tag進行比較，只有它們是相等的，才表明這個Cache?line就是想要的那個。在一個Cache?line中有很多個數據，通過存儲器地址中的Block Offset部分可以找到真正想要的數據，它就可以定位到每個字節。在Cache?line中還有一個有效位valid，用來標記這個Cache?line是否保存著有效的數據，只有在之前被訪問過的存儲器地址，它的數據才會存在于對應的Cache?line中，相應的有效位也會被置為1了。

?對于所有Index相同的存儲器地址，都會尋址到同一個Cache?line中，這就會發生沖突，這也是直接映射結構Cache的一大缺點。如果兩個Index部分相同的存儲器地址交叉訪問Cache，就會一直導致Cache缺失，嚴重地降低了處理器的執行效率。、

下面通過一個實際的例子來說明存儲器地址的劃分對于Cache的影響，如圖所示一個32位存儲器地址，Block Offset有5位，所以Data?block的大小是2^5 = 32字節，Index是6位，表示Cache中共有2^6=64個Cache?line(在直接映射中，Cache?line和Cache Set是同義的)，存儲器地址中剩余的32-5-6=21位作為Tag值，因此這個Cache中可以存儲的數據大小為64*32=2048字節，即2KB；而Tag部分的大小是64*21=1344位，約為1.3Kb；有效位占用的大小為64*1=64位，一般情況下，都是以數據部分的大小來表示Cache的大小，因此這個Cache被稱為一個2KB直接映射結構的Cache，而實際它還額外占用多余1.3KB的存儲空間。

?直接映射結構的Cache在實現上是最簡單的，它都不需要替換算法，但是它的執行效率也是最低的，現代的處理器很少使用這種方式了。

2.組相連

組相連(set-associative)的方式是為了解決直接映射結構Cache的不足而提出的。存儲器中的一個數據不單單只能放在一個Cache?line中，而是可以放在多個Cache?line中，對于一個組相連結構的Cache來說，如果一個數據可以放在n個位置，則稱這個Cache是n路組相連(n-way)。

?這種結構依舊使用存儲器地址的Index部分對Cache進行尋址，此時可以得到兩個Cache?line，這兩個Cache?line稱為一個Cache?set，究竟哪個Cache?line才是最終需要的，是根據Tag比較的結果來確定的，當然，如果兩個Cache?line的Tag比較結果都不相等，那么發生了Cache缺失。

因為需要從多個Cache?line中選擇一個匹配的結果，這種Cache的實現方式較之直接映射結構的Cache，延遲會更大，有時候甚至需要將其進行流水線，以便減少對處理器周期時間cycle?time的影響，這樣會導致load指令的延遲增大，一定程度上影響了處理器的執行效率，但是這種方式的有點也很突出，它可以顯著減少Cache缺失發生的頻率，因此在現代處理器中得到了廣泛的應用。

上面提到的Tag和Data部分可以分開放置，稱為Tag SRAM和Data SRAM，可以同時訪問這兩個部分，稱為并行訪問；相反如果縣訪問Tag SRAM部分，根據Tag比較的結果再去訪問Data SRAM部分，稱為串行訪問。

對于并行訪問結構，當Tag部分的某個地址唄讀取的同時，這個地址在Data部分對應的所有數據也會被讀取出來，并送到一個多路選擇器上，這個多路選擇器受到Tag比較結果的控制，選出相應的餓Data?block，然后根據存儲器地址中的Block?offset的值，選擇出合適的字節，一般將選擇字節的這個過程稱為數據對齊data?alignment。

并行訪問Cache若在一個周期內完成，則在現實當中會占據很大延遲，要想使處理器運行在較高的頻率下，Cache的訪問就需要使用流水線，前面說過，對于指令Cache來說，流水線的結構不會有太大的影響，仍舊可以實現每周期讀取指令的效果；而對于數據Cache來說，使用流水線則會增大load指令的延遲，從而對處理器的性能造成負面影響。

流水線的地址計算Address Calculation階段可以計算得出存儲器的地址，接下來的Disambiguation階段對load/store指令之間存在的相關性進行檢查，然后在下個流水線階段Cache Access就可以直接并行地訪問Tag SRAM和Data SRAM，并使用Tag比較的結果對輸出的數據進行選擇，然后在下一個流水線階段Result Derive，使用存儲器地址中的block?offset值，從數據部分給出的data?block中選出最終需要的數據。將整個Cache的訪問放到幾個周期內完成，可以降低處理器的周期時間。

?而對于串行訪問方法來說，首先需要對Tag SRAM進行訪問，根據Tag比較的結果，就可以知道數據部分中，那一路是需要被訪問的，此時可以直接訪問這一路的數據，這樣就不需要上圖中的多路選擇器了而且，只需啊喲訪問數據部分指定的那個SRAM，其他的SRAM由于都不需要被訪問，可以將它們的使能信號置為無效，這樣可以節省很多功耗。

完全串行Tag SRAM和Data SRAM這兩部分的訪問，它的延遲會更大，仍舊需要使用流水線的方式來降低對處理器的周期時間的影響，用流水線降低了訪問Tag SRAM和Data RAM的延遲，因為此時已經不再需要多路選擇器，這對降低處理器的周期時間是有好處的，但是這樣設計的一個明顯的缺點就是Cache的訪問增加了一個周期，這也就增大了load指令的延遲，因為load指令處于相關性的頂端，會對處理器的執行效率造成一定的負面影響。

并行訪問的方式會有較低的時鐘頻率和較大的功耗，但是訪問Cache的時間周期縮短了一個周期，但是考慮到在亂序執行的超標量處理器來說，可以將訪問Cache的這段時間通過填充其他的指令而掩蓋起來，所以對于超標量處理器來說，當Cache的訪問處理器的關鍵路徑上時，可以采用串行訪問來提高處理器的時鐘頻率，同時并不會由于訪問Cache的時間增加了一個周期而引起性能的明顯降低；相反，對于普通的順序執行的處理器來說，由于無法對指令進行調度，訪問Cache如果增加了一個周期，就很有可能會引起處理器性能的降低，因此在這種處理器中使用并行訪問的方式就是一種比較合適的選擇。

3.全相連

在全相連full-associative的方式中，對于一個存儲器地址來說，它的地址可以放在任意一個Cache?line中。存儲器地址不在有Index部分，而是直接在整個Cache中進行Tag比較，找到比較結果相等的那個Cache?line，相當于直接使用存儲器的內容來尋址，從存儲器中找到匹配的項，這其實就是內容尋址的存儲器Content Address Memory，CAM。實際當中的處理器在使用全相連結構的Cache時，都是使用CAM來存儲Tag值，使用普通的SRAM來存儲數據。全相連結構Cache有著最大的靈活度，它的延遲也是最大的，因此一般這種結構的Cache不會有很大的容量，例如TLB就會使用這種全相連的方式來實現。

2.1.2 Cache的寫入

在一般的RISC處理器中，L1 Cache中的I-Cache都是不會被直接寫入內容的，即使有自修改的情況出現，也并不是直接寫入I-Cache，而是借助與D-Cache來實現，將要改寫的指令作為數據寫到D-Cache中，然后將D-Cache中的內容寫入到下級存儲器，例如L2 Cache。

對于D-Cache來說，它的寫操作和讀操作有所不同，當執行一跳store指令時，如果只是向D-Cache中寫入數據，而并不改變它的下級存儲器中的數據，這樣就會導致D-Cache和下級存儲器中，對于這一個地址有著不同的數據，這稱為不一致non-consistent。

要想保持一致性，最簡單的方式就是當數據在寫到D-Cache時，也寫到它的下級存儲器中，這種方式稱為write-through寫通。缺點是處理器執行效率不高。

如果在執行store指令時，數據被寫到D-Cache后，只是將被寫入的Cache?line做一個記號，并不將這個數據寫入到更下級的存儲器中，只有當Cache中這個被標記的line要被替換時，才將它寫到下級存儲器中，這種方式被稱為Write?back寫回，被標記的記號在計算機中術語為dirty狀態。優點可是減少寫慢速存儲器的頻率，缺點就是造成D-Cache和下級存儲器中有很多地址中的數據是不一致的，給存儲器的一致性管理帶來負擔，以及設計復雜度高一點。

以上是假設寫D-Cache時，要寫入的地址總是在D-Cache中，而實際當中，有可能發現這個地址并不在D-Cache中，這就發生了寫缺失write?miss，此時最簡單的處理方式就是將數據直接寫到下級存儲器中，而并不是寫到D-Cache中，這種方式稱為non-write?allocate。與之對應為write?allocate，如果寫Cache時發生了缺失，會首先將下級存儲器中將這個發生缺失的地址對應的數據塊data?block讀取出來，將要寫入到D-Cache中的數據合并到這個數據塊，然后將這個被修改過的數據塊寫到D-Cache。

此處的一個疑問，寫D-Cache而發生缺失時，為什么不直接將D-Cache中找到一個line，將要寫入的信息直接寫到這個line中，同時也將它寫到下級存儲器中呢？為什么還要先從下級存儲器中讀取相對應的數據塊并寫到D-Cache中？

這是因為在處理器中，對于寫D-Cache來說，最多也就是寫入一個字，而如果按照上面方式，直接從D-Cache中找到一個line來存儲這個需要寫入的數據，并將這個line標記為dirty，那么就會導致這個line中，數據塊的其他部分和下級存儲器中對應的地址的數據不一致，而且此時D-Cache中這些數據都是無效的，如果這個Cache?line由于被替換而寫回到下級存儲器時，就會使下級存儲器中的正確數據被篡改。

對于Write?allocate方法來說，就需要在發生寫缺失時，首先將缺失的地址對應的數據塊從下級存儲器中讀取出來，這個過程是必不可少的。

對于D-Cache來說，一般情況下，write?through是和non-write?allocate一起使用的，它們都是直接將數據更新到下級存儲器中。

1.write?through和non-write?allocate配合工作流程圖：

?write-back是和write?allocate配合使用的，不管是讀取還是寫入時發生缺失，都需要從D-Cache中找到一個line來存放新的數據，這個被替換掉的line如果是dirty，那么首先需要將其中的數據寫回到下級存儲器中，然后才能使用這個line存放缺失地址對應的數據塊。也就是說，當D-Cache中被替換的line是dirty，需要對下級存儲器進行兩次訪問。對于寫D-Cache的操作來說，還需要將寫入的數據也放到這個line中，并將其標記為dirty。

2.write-back與write?allocate工作流程圖：

在D-Cache中采用write?back方法時，不管是讀取還是寫入時發生缺失，都需要從D-Cache中找到一個line來存放新的數據，這個被替換的line如果此時是dirty，那么首先需要將其中的數據寫回到下級存儲器中，然后才能夠用這個line存放新的數據。

2.1.3 Cache的替換策略

不管是讀取還是寫入D-Cache時發生了缺失，都需要從有效的Cache?line中找到一個并替換之，這就是替換Cache replacement策略。

1.近期最少使用法

近期最少使用法Least Recently Used，LRU會選擇最近被使用次數最少的的Cahce?line，因此這個算法需要跟蹤每個Cache?libe的使用情況，為每個Cache?line都設置一個年齡age部分，每次當一個Cache?line被訪問時，它對應的年齡部分就會增加，或者減少其他Cache?line的年齡值，這樣當進行替換時，年齡值最小的那個Cache?line就是被使用次數最少了，會選擇它進行替換。但是隨著Cache相關聯度增加，要精確實現這種LRU方式就非常昂貴了。因此在way的個數很多的情況下，都是使用偽LRU的方法。

在下面8-way組相連Cache中，對所有way進行分組，共有三部分，分別介紹如下;

（1）首先將所有way分為兩組，每組有4個way；

（2）然后將每組中的way在分為兩組，也就是每組有2個way；

（3）繼續進行分組，此時每組只有一個way了

2.隨機替換

在處理器中，Cache的替換算法一般都是使用硬件來實現的，因此如果做得很復雜，會影響處理器的周期時間，于是就有了隨機替換Random?replacement的實現方法，此算法無需記錄每個way的年齡信息，而是隨機地選擇一個way進行替換，相比于LRU替換方法來說，這種方法發生缺失的頻率會更高一些，但是隨著Cache容量的增大，這個差距是越來越小的。實際設計很難做到嚴格的隨機，一般采用一種稱為時鐘算法clock?algorithm的方法來實現近似的隨機，工作原理本質上一個計算器，計數器的的寬度由Cache的相關度，也就是way的個數來決定，例如8way就需要三位，每次當Cache中的某個line需要被替換時，就會訪問這個計數器，使用計數器當前的值，從被選定的Cache?set找出要替換的line，這樣就近似地實現一種隨機的替換。理論上其性能不是最優，但是它的硬件復雜度比較低，也不會損失過多的性能。

?2.2 提高Cache的性能

在真實世界的處理器中，會采用更復雜的方法來提高Cache的性能，這些方法包括寫緩存write buffer、流水線pipeline cache、多級結構multilevel cache、victim cache和預期prefetch。除此之外，對于亂序執行的超標量處理器來說，根據它的特點，還有一些其他的方法來提高Cache的性能，例如非阻塞non-blocking cache、關鍵字優先critical word first和提前開始early restart等方法。

2.2.1 寫緩存

不管是load或者store指令，當D-Cache發生缺失時，需要從下一級存儲器中讀取數據，并寫到一個選定的Cache line中，如果這個line是dirty，那么首先需要將它寫到下級存儲器中，考慮一般的餓下級存儲器，例如L2 Cache或是物理內存，一般只有一個讀寫端口，這就要求上面的過程是串行完成的。先將dirty的Cache line的數據寫到下級存儲器中，然后才能讀取下級存儲器而得到缺失的數據，由于下級存儲器的訪問時間都比較長，這種串行的過程導致D-Cache發生缺失的處理時間變得很長，此時就可以采用write buffer寫緩存來解決這個問題，dirty的Cache line首先放到寫緩存中，等到下級存儲器有空閑的時候，才會將寫緩存中的數據寫到下級存儲器中。

對于write back類型的D-Cache來說，當一個dirty的Cache line被替換的時候，這個line中的數據會首先放到寫緩存中，然后就可以從下級存儲器中讀數據了。

對于write?through類型的D-Cache來說，采用寫緩存之后，每次當數據寫到D-Cache的同時，并不會同時寫到下級存儲器中，而是將其放到寫緩存中，這樣就減少了write?through類型的D-Cache在寫操作時需要的時間，從而提高了處理器的性能，以及write?through類型的Cache由于便于進行存儲器一致性的管理，所以在多核的處理器中，L1 Cache會經常采用這種結構。

加入寫緩存之后，會增加系統設計的復雜度，舉例來說，當讀取D-Cache發生缺失時，不僅需要從下級存儲器中查找這個數據，還需要在寫緩存中也進行查找。

寫緩存就相當于是L1 Cache到下級存儲器之間的一個緩沖，通過它，向下級存儲器中寫數據的動作會被隱藏，從而可以提升處理器的執行效率，尤其是對于write?through類型的D-Cache而言。

2.2.2?流水線

對于讀取D-Cache來說，由于Tag SRAM和Data SRAM可以在同時進行讀取，所以當處理器的周期時間要求不是很嚴格時，可以在一個周期內完成讀取的操作；而對于寫D-Cache來說，情況就比較特殊了，讀取Tag SRAM和寫Data SRAM的操作只能串行地完成。只有通過Tag比較，確認需要寫的地址在Cache中之后，才可以寫Data SRAM，在主頻比較高的處理器中，這些操作很難在一個周期內完成。這就需要對D-Cache的寫操作采用流水線的結構。比較典型的方式是將Tag SRAM的讀取和比較放在一個周期，寫D-Cache放在下一個周期。

需要注意當執行load指令時候，它想要的數據可能正好處于store指令的流水線寄存器中，而不是來自于Data SRAM，因此需要機制能檢測到這種情況，將load指令所攜帶的地址和store指令的流水線寄存器進行比較。

對寫D-Cache使用流水線之后，不僅增加了流水線本身的硬件，也帶來一些額外的硬件開銷。

2.2.3?多級結構

現代處理器很渴望有一種容量大，同時速度又很快的存儲器，但在硅工藝條件下，對存儲器來說，容量和速度是一對相互制約的因素，容量大必然速度慢。

為了使處理器看起來使用了一個容量大同時速度快的存儲器，可以使用多級結構的Cache：

?一般情況下，L1 Cache的容量很小，能夠和處理器保持在同樣速度等級上，L2 Cache的訪問通常需要消耗處理器的幾個時鐘周期，但是容量要更大一些，L1和L2 Cache都會和處理器放在同一芯片上，現在L3 Cache也放在片上。

一般在處理器中，L2 Cache會使用write?back方式，但是L1 Cache更傾向采用wirte?through，這樣可以簡化流水線設計，尤其在多核情況下，管理存儲器之間的一致性。

對于多級結構的Multilevel Cache，還需要了解兩個概念，Inclusive和Exclusive：

Inclusive：如果L2 Cache包括了L1 Cache的所有內容，則稱L2 Cache是Inclusive；

Exclusive：如果L2 Cache與L1 Cache的內容互不相同，則稱L2 Cache是Exclusive；

Inclusive類型的Cache是比較浪費硬件資源的，因為它將一份數據保存在兩個地方，優點則是可以直接將數據寫到L1 Cache中，雖然此時會將Cache?line中原來的數據覆蓋掉，但是在L2 Cache中存有這個數據的備份，所以這樣的覆蓋不會引起任何問題(當然，被覆蓋的line不能是dirty)，以及也簡化了一致性coherence的管理。

例如在多核的處理器中，執行store指令改變了存儲器中的一個地址的數據時，如果是Inclusive類型的Cache，那么只需檢查最低一級的Cache即可(L2 Cache)，避免打擾上級Cache(L1 Cache)和處理器流水線的影響；

如果是Exclusive類型的Cache，很顯然要檢查所有的Cache，而檢查L1 Cache也就意味著干擾了處理器的流水線。如果處理器要讀取的數據不在L1 Cache中，而在L2 Cache中，那么在將數據從L2 Cache放到L1 Cache的同時，也需要將L1 Cache中被覆蓋的數據寫到L2 Cache中，這樣數據交換很顯然會降低處理器的效率，但是Exclusive類型的Cache避免硬件的浪費，可以獲得更多可用的容量。

2.2.4 Victim Cache

Cache中被“踢出”的數據可能馬上又要被使用，因為Cache中存儲的是經常要使用的數據。例如對一個2-way組相連的D-Cache來說，如果個數據頻繁使用的3個數據恰好都位于同一個Cache?set中，那么就會導致一個way中的數據經常被“踢出”Cache，然后又經常地被寫回Cache。

這會導致Cache始終無法名字需要的數據，顯然降低了處理器的執行效率，如果為此增加Cache中的way個數，又會浪費大量的空間。Victim Cache正是要解決這樣的問題，它可以保存最近被踢出Cache的數據，因此所有的Cache?set都可以利用它來提高way的個數，通常Victim Cache采用全相連的方式，容量都比較小(一般存儲4~16個數據)。?

Victim?Cache本質上相當于增加了Cache中way的個數，能夠避免多個數據競爭Cache中有限的位置，從而降低了Cache的缺失率。一般情況下，Cache和Victim Cache存在互斥關系，也就是它們不包含想同樣的數據，處理器內核可以同時讀取它們。

同樣，Victim Cache的數據會被寫到Cache中，而Cache中被替換的數據會寫到Victim Cache中，這就相當于它們互換了數據。

還有一種更Victim Cache類似的設計思路，稱為Filter Cache，只不過使用在Cache之前，而Victim Cache使用在Cache之后，當一個數據第一次使用時，它并不會馬上放到Cache中，而是首先會被放到Filter Cache中，等到這個數據再次被使用時，它才會被搬移到Cache中，這樣做可以防止那些偶然使用的數據占據Cache。

?2.2.5?預取

影響Cache缺失率的3C中一項為Compulsory，當處理器第一次訪問一條指令或者一個數據時，這個指令或數據肯定不會在Cache中，這種情況引起的缺失似乎不可避免，但是實際上使用預取prefetch可以緩解這個問題。所謂預取，本質上也是一種預測技術，它猜測處理器在以后可能會使用什么指令或數據，然后提前將其放到Cache中，這個過程可以使用硬件或者軟件完成。

1.硬件預取

對于指令來說，猜測后續會執行什么指令相對比較容易，因為程序本身是串行執行的，雖然由于分支指令的存在，這種猜測有時候也會出錯，導致不會被使用的指令進入了I-Cache，這一方面降低了I-Cache實際可用的容量，一方面又占用了本來可能有用的指令，這稱為“Cache污染”，不僅浪費了時間，還會影響處理器的執行效率，為了避免這種情況，可用將預取的指令放到一個單獨的緩存中。

?當I-Cache發生缺失時，處理將需要的數據塊data?block從下級存儲器取出并放到I-Cache中，還會降下一個數據塊也讀取出來，只不過它不會放到I-Cache中，而是放到Stream Buffer的地方。在后續執行時，如果在I-Cache中發生了缺失，但是在Stream Buffer找到了想要的指令，那么除了使用Stream Buffer中讀取的指令之外，還會將其中對應的數據塊搬移到I-Cache中，同時繼續從下一級存儲器中讀取下一個數據塊放到Stream Buffer，當程序中沒有遇到分支指令時，這種方法會一直正確地工作，從而使I-Cache的缺失率得到降低。但是分支指令會導致Stream Buffer的指令編的無效，此時的預取相當于做了無用功，浪費了總線帶寬和功耗。預取是一把雙刃劍，它可能會減少Cache的缺失率，也可能由于錯誤的預取而浪費了功耗和性能。

不同于指令的預取，對于數據的預取來說，它的規律更難以進行捕捉。一般情況下，當訪問D-Cache發生缺失時，除了將所需要的數據塊從下級存儲器中取出來之外，還會將下一個數據塊也讀取出來。Intel Pentium 4和IBM Power5處理器中，采用了一種稱為Strided Prefetch方法，它能夠使用硬件來觀測程序中使用數據的規律。

2.?軟件預取

使用硬件進行數據的預取，很難得到滿意的結果，其實在程序的編譯階段，編譯器complier就可以對程序進行分析，進而知道哪些數據是需要進行預取的，如果在指令集中有預取指令prefetch?instruction，那么編譯器就可以可以直接控制程序進行預取。

應用軟件預取方法有一種前提，就是預取的時機。如果預取數據的時間太晚，那么當真正需要使用數據時，有可能還沒有被預取出來，這樣預取就失去的意義；如果預取的時間太早，那么就有可能踢掉D-Cache中一些本來有用的數據，造成Cache污染。

還需要注意，使用軟件預取的方法，當執行預取指令的時候，處理器需要能夠繼續執行，也就是能繼續從D-Cache中讀取數據，而不能讓預取指令阻礙了后面指令的執行，這要求D-Cache是non-blocking結構。

在實現虛擬存儲器Virtual?memory系統中，預取指令有可能會引起一些異常exception發生，例如Page?fault、虛擬地址錯誤virtual?address?fault或者保護違例Protection Violation。此時若對異常進行處理，就稱其為處理錯誤的預取指令Faulting Prefetch Instruction，反之，稱為不處理錯誤的預取指令nonfaulting?prefetch?instruction。

??2.3 多端口Cache

在超標量處理器中，為了提高性能，處理器需要能夠在每周期同時執行多條load/store指令，這需要一個多端口的D-Cache，以便支持多條load/stroe指令的同時訪問。

其實在超標量處理器中，有很多重要部件都是多端口結構的，比如寄存器堆register file、發射隊列issue queue和重排序緩存ROB等。由于這些部件本身容量不是很大，所以即使采用多端口結構，也不會對芯片的面積和速度產生太大的影響，但是D-Cache不同，它的容量本身就很大，如果采用多端口設計，會有很大負面影響，因此需要采用一些辦法來解決這個問題，本節重點介紹True Multi-port、Multi Cache Copies和Multi-banking。

2.3.1 True Multi-port

雖然在現實中，不可能對Cache直接采用多端口設計，但是本節還是看一下這種最原始的方法究竟有何缺點，這種方法使用一個多端口的SRAM來實現多端口的Cache，以一個雙端口的Cache為例，所有在Cache中的控制通路和數據通路都需要進行復制，這表示它有兩套地址解碼器address decoder，使兩個端口可以同時尋址Tag SRAM和Data SRAM；有兩個多路選擇器way mux，用來讀取兩個端口的數據；比較器的數量也需要增加一倍，用來判斷兩個端口的命中情況：同時還需要有兩個對其器aligner等。Tag SRAM和Data SRAM本身并不需要復制一份，但是它們當中的每個Cell都需要都是支持兩個并行的讀取操作，但是不需要兩個寫端口，因為無法對一個SRAM Cell同時寫兩次。

此種方法需要將很多電路進行復制，因此增大了面積，且SRAM Cell需要驅動多個讀端口，因此需要更長的訪問時間，功耗也隨之增大，所以一般不會直接采用這種方式來設計多端口Cache。

2.3.2 Multiple Cache Copies

將Tag SRAM和Data SRAM進行了復制，與2.3.1節類似，不過是將Cache進行復制，SRAM將不再需要使用多端口的結構，這樣可以基本上消除對處理器周期時間的影響。但是，這種方法浪費了很多面積，而且需要保持兩個Cache間的同步。例如store指令需要同時寫到兩個Cache中，當一個Cache?line被替換，也需要對另一個Cache進行同樣的操作，此設計顯然非常麻煩，不是一個很優化的方法，在現代處理器中很少被使用。

2.3.3 Multi-banking

此結構是在現實當中的處理器被廣泛使用的方法，它將Cache分為很多小個bank，每個bank都只有一個端口，如果在一個周期之內，Cache的多個端口上的訪問地址位于不同的bank之中，那樣就不會引起任何問題，只有當兩個或多個端口的地址位于同一個bank之中時，才會引起bank?conflict。

?使用這種方法，一個雙端口的Cache仍舊需要兩個地址解碼器、兩個多路選擇器、兩套比較器和兩個對齊器，而Data SRAM此時不需要多端口結構了，這樣就提高了速度，并在一定程度上減少了面積。但是由于需要判斷Cache的每個端口是否命中，所以對于Tag SRAM來說，仍舊需要提供多個端口同時讀取的功能，也就是采用多端口SRAM來實現。

影響這種多端口Cache性能的一個關鍵因素就是bank沖突，可以采用更多的bank來緩解這個問題，使bank沖突發生的概率盡可能降低，并且還可以提高bank的利用效率，避免有用的數據都集中在一個bank的情況發生，同時，由于每個端口都會訪問所有bank，這需要更多的布線資源，有可能對版圖設計造成一定的影響。

2.3.4?真實的例子AMD Opteron的多端口Cache

AMD的Opteron系列處理器是64位處理器，但是考慮到現實的需求，處理器的地址并沒有使用64位，它的虛擬地址virtual?address是48位，物理地址physical?address是40位，采用簡化地址從而減少硅片面積。

Opteron處理器的D-Cache是雙端口的，每個端口都是64位的位寬，雙端口以為這這個Cache能夠在一個周期內支持=兩條load/store指令同時進行訪問，它使用了multi-banking的機制來實現這個多端口的功能。

在AMD Opteron處理器的這個Cache中，data?block的大小是64字節，需要6位地址進行尋址，每個data?block被封為8個獨立的bank，每個bank都是64位的單端口SRAM。

整個Cache的大小是64KB，采用2-way組相連，因此每一路的大小是32KB；使用Virtually-index，physically-tag的實現方式，直接使用VA虛擬地址來尋址Cache。因為每一路是32KB大小，因此需要15位地址尋址，又因為每個data?block大小是64字節，因此尋址其中的每個字節需要使用VA[5:0]，剩下的VA[14:6]用來尋找每個Cache?set。

由于每個Cache?line中的data block被劃分為8個bank，每個bank是8字節寬的SRAM，所以很自然地使用VA[5:3]來找到某個bank，剩下的VA[2:0]用來從8字節中數據中找到某個字節，這種方式將兩個連續的8字節數據放到兩個相鄰的不同的bank中，利用空間局部性原理，使得對這兩個8字節數據訪問落在不同的bank中。

由于Cache的每個端口在訪問時候，都會同時訪問兩個way中的數據，然后根據Tag的比較結果來從兩個way中選擇命中的那個，所以Cache的一個端口在訪問的時候，會同時訪問到兩個bank，每個way各一個。

在支持虛擬存儲器的處理器中，最常見的頁面大小page為4KB，這需要VA[11:0]來尋找頁面內部，因此對于48位的虛擬地址來說，剩下的VA[47:12]就作為VPN（Virtual Page Number）來尋址TLB，得到物理地址中PFN（Physical Frame Number）[39:12]，它用來和Tag部分進行比較，判斷是否命中。

對于一個2-way組相連的Cache來說，相比于單端口的實現方式，兩個端口的實現方式所需要的控制邏輯電路基本上擴大了一倍，需要兩個TLB、兩個Tag比較器，還需要兩倍Tag存儲器，Opteron處理器采用將Tag SRAM復制一份來實現雙端口的SRAM，當然也可以采用真實的雙端口SRAM來實現這個功能，面積也不會減少多少，速度還會變慢。

除了Cache中存儲數據的Data SRAM沒有被復制之外，其他的電路基本上被復制一份，因此采用multi-banking方式來實現雙端口的Cache，面積會增大很度，但是它的好處是速度比較快，對處理器的周期時間有比較小的負面影響。

2.4 超標量處理器的取指令

如果一個超標量處理器在每周期可以同時解碼4條指令，這個處理器就稱為4-way的超標量處理器，此處理器每周期應該能夠從I-Cache中至少取得4條指令，才能喂飽后續的流水線，如果少于這個值，則會造成后面的流水線浪費。

對于一個n-way超標量處理器來說，它給出一個取指令的地址后，I-Cache應該能夠至少送出n條指令，稱這n條指令為一組(fetch group)。I-Cahce支持這個功能最簡單的方式就是使用data block的大小為n個字，每周期將其全部進行輸出如果處理器送出的取指令地址是n字對齊的，那么此時就可以實現每周期從I-Cache中讀取n條指令的功能，在數據塊data block部分需要n個32位的SRAM，當I-Cache命中時，這些SRAM會同時進行輸出。但是由于存在跳轉指令，處理器送出的取指令地址不可能總是n字對齊。

當取指令的地址不再是是字對齊時，一個組fetch group中的指令就可能落在兩個Cache line中，但是對于Cache來說，每周期只能訪問一個Cache line，這會導致在一個周期內無法取出4條指令，使得后續流水線無法得到充足的指令，使部分資源空置。

處理器每周期取出的指令多余它能夠解碼的指令個數，通過一個緩存來將多余的指令緩存起來，這樣就可以使后續的流水線得到充足的指令，避免了硬件資源的浪費，這些指令會存儲到一個稱為指令緩存Instruction Buffer，IB地方，后續的指令解碼器會從指令緩存中取指令。

即使當前周期送出的取指令地址不是四字對齊，只要以后的周期中不出現引起指令的執行順序改變的情況，例如分支指令和異常等情況，下個周期取指令的地址也會變成四字對齊，此時就可以在一個周期內取出四條指令了。

其實在現實世界中，分支指令出現的頻率還是比較高的，這一方面會導致取指令的地址無法四字對齊，另一方面還會在分支指令執行的時候導致過多的無用指令進入流水線，因此需要對分支指令進行預測。

即使取指令的地址不是四字對齊的，仍舊可以在一個周期內讀取4條指令，最簡單的實現方法是使數據塊data?block大小變大，例如其包含8個字，只要取指令的地址不是落在數據塊的最后三個字，就可以在每周期內讀取4條指令。這樣做的前提是增大了數據塊的容量，如果在Cache的總容量一定的情況下，意味著Cache?set的個數會減少，可能會增大Cache?miss的概率。

而且，如果Cache的每個數據塊是8個字，是不是也需要使用8個32位的SRAM來實現呢？?問題就是如果SRAM的個數過多，會導致保護電路也占用過多的面積，而且要從8個SRAM的輸出中選用4個字也是一件很浪費電路的事情。

若一個Cache?line中包含的8個字實際上占據了SRAM的兩行，因此共使用了4個32位的SRAM。其中需要一段重排序的邏輯電路，對4個SRAM的4條指令進行重排序，使它們滿足最原始的指令順序，這樣才能夠使后續的流水線得到正確的指令。此外，當取指令的地址指向了Cache?line中最后的三條指令的某一條時，此時本周期并不能輸出4條指令，因此在重排序邏輯電路中還需要假如指示每條指令是否有效的標志信號，這樣才能夠將有效的指令寫入到后續的指令緩存Instruction Buffer中。

為什么要實現分支預測呢？因此在超標量處理器中，并行度很高，流水線很深，一條指令從進入流水線直到結果被計算出來，中間會經歷很多段流水線，如果使用最簡單的靜態預測方法，那么一旦發現這條分支指令是需要執行的，就需要將流水線中，在分支指令之后進入流水線的所有指令都抹掉，也就是這段時間做了無用功。如果能夠提起知道在本周期取出的指令中，那條指令是分支指令，且可以預知這條分支指令的結果，那么就可以減少流水線被打斷的次數。

實現分支預測之后，從I-Cache中取指令的同時，已經可以知道當前指令組fetch?group中那條指令時分支指令，如果它被預測執行，那么指令組中位于它之后的指令就不應該進入到后續的流水線。

在實現虛擬存儲器VA的處理器中，處理器送出的取指令地址是虛擬地址，需要使用一定的方法將其轉換為物理地址，然后才能夠從存儲器中取指令，在這個轉換過程中可能發生很多事情，它們都可以打斷流水線的正常執行。

總結

以上是生活随笔為你收集整理的超标量处理器设计 姚永斌 第2章 Cache 摘录的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。