從三個(gè)方面闡述Cache

關(guān)于cache，大概可以從三個(gè)方面進(jìn)行闡述：內(nèi)存到cache的映射方式，cache的寫(xiě)策略，cache的替換策略。

映射方式

內(nèi)存到cache的映射方式，大致可以分為三種，分別是：直接映射（directmapped），全相連（fullyassociative），組相連（setassociative）。

為了便于理解，現(xiàn)在假設(shè)一個(gè)例子，比如咱們的內(nèi)存只有16bytes，而cache只有4bytes（cacheline是1byte），那么對(duì)于分別采用三種不同的映射方式，會(huì)是什么情況呢？如下圖所示：

（direct mapped：直接映射 ; fully associative：全相連 ;set associative：組相連）

（1）directmapped

對(duì)于directmapped（直接映射），為了便于數(shù)據(jù)查找，一般規(guī)定內(nèi)存數(shù)據(jù)只能置于緩存的特定區(qū)域。對(duì)于直接匹配緩存，每一個(gè)內(nèi)存塊地址都可通過(guò)模運(yùn)算對(duì)應(yīng)到一個(gè)唯一緩存塊上。注意這是一個(gè)多對(duì)一匹配：多個(gè)內(nèi)存塊地址須共享一個(gè)緩存區(qū)域。

對(duì)于咱們這個(gè)例子來(lái)說(shuō)，內(nèi)存的0地址只能映射到cache的第0個(gè)（0%4=0）cacheline，內(nèi)存的1地址只能映射到cache的第1個(gè)（1%4=1）cacheline，內(nèi)存的2地址只能映射到cache的第2個(gè)（2%4=2）cacheline，內(nèi)存的3地址只能映射到cache的第3個(gè)（3%4=3）cacheline，內(nèi)存的4地址只能映射到cache的第0個(gè)（4%4=0）cacheline，。。。。。。如此循環(huán)下去。

所以如果采用directmapped的話(huà)，core在訪問(wèn)cache時(shí)，根據(jù)TLB處理之后的物理地址，進(jìn)行取模（%）運(yùn)算，就可以直接確定其cache的位置，由于一個(gè)cacheline可能對(duì)應(yīng)不同的內(nèi)存地址（具有相同模運(yùn)算結(jié)果的內(nèi)存），然后將物理地址的tag部分與cache的tag部分進(jìn)行一次比較，就可以確定是cache hit，還是cachemiss。

directmapped的特點(diǎn)是，邏輯簡(jiǎn)單，延遲短（只進(jìn)行一次比較），但命中率低。

（2）fullyassociative

對(duì)于fullyassociative（全相連），這種方式，內(nèi)存中的數(shù)據(jù)塊可以被放置到cache的任意區(qū)域。這種相聯(lián)完全免去了索引的使用，而直接通過(guò)在整個(gè)緩存空間上匹配標(biāo)簽進(jìn)行查找。

對(duì)于咱們的這個(gè)例子來(lái)說(shuō)，內(nèi)存的某個(gè)地址，可以映射到cache的任意個(gè)cacheline。內(nèi)存的0地址能映射到cache的第0個(gè)cacheline，也可以映射到第1個(gè)cacheline，也可以映射到第2個(gè)cache line，也可以映射到第3個(gè)cacheline。

所以如果采用fullyassociative的話(huà)，core在訪問(wèn)cache時(shí)，根據(jù)TLB處理之后的物理地址，要依次和所有的cacheline的tag進(jìn)行比較。

fullyassociative的特點(diǎn)是：控制復(fù)雜，查找造成的電路延遲最長(zhǎng)，因此僅在特殊場(chǎng)合，如緩存極小時(shí)，才會(huì)使用，命中率較高。

（3）setassociative

set associative（組相連）是directmapped 和fully associative兩種方式的一個(gè)折中。

對(duì)于咱們這個(gè)例子來(lái)說(shuō)，我們將4個(gè)cacheline分成了兩組，內(nèi)存的0地址只能映射到cache的第0個(gè)組（0%2=0），但是在組內(nèi)是任意的，既可以映射到組內(nèi)的第0個(gè)cacheline，也可以映射到第1個(gè)cacheline。內(nèi)存的1地址只能映射到cache的第1個(gè)組（1%2=1），但是在組內(nèi)也是任意的，既可以映射到組內(nèi)的第0個(gè)cacheline，也可以映射到第1個(gè)cacheline。內(nèi)存的2地址只能映射到cache的第0個(gè)組（2%2=0），但是在組內(nèi)也是任意的，既可以映射到組內(nèi)的第0個(gè)cacheline，也可以映射到第1個(gè)cacheline，。。。。。。。依次類(lèi)推。

所以，如果采用setassociative的話(huà)，core在訪問(wèn)cache時(shí)，根據(jù)TLB處理之后的物理地址，先將物理地址取模，得到其可能的cache的組，然后再依次與組內(nèi)的所有cacheline的tag進(jìn)行比較，確定是cache hit還是cachemiss。

setassociative是折中方案，所以其特點(diǎn)就是集directmapped 和fully associative之所長(zhǎng)。是一個(gè)平衡方案。

咱們這個(gè)例子是2 way setassociative，即兩路組相連，所謂的兩路，是指每個(gè)cache組內(nèi)的cacheline的數(shù)目，不是分組的數(shù)目。比如是4路組相連，指的是每個(gè)cache組內(nèi)有4個(gè)cacheline。

對(duì)于直接映射，由于緩存字節(jié)數(shù)和緩存塊數(shù)均為2的冪，上述運(yùn)算可以由硬件通過(guò)移位極快地完成。直接匹配緩存盡管在電路邏輯上十分簡(jiǎn)單，但是存在顯著的沖突問(wèn)題。由于多個(gè)不同的內(nèi)存塊僅共享一個(gè)緩存塊，一旦發(fā)生緩存失效就必須將緩存塊的當(dāng)前內(nèi)容清除出去。這種做法不但因?yàn)轭l繁的更換緩存內(nèi)容造成了大量延遲，而且未能有效利用程序運(yùn)行期所具有的時(shí)間局部性。

組相聯(lián)（SetAssociativity）是解決這一問(wèn)題的主要辦法。使用組相聯(lián)的緩存把存儲(chǔ)空間組織成多個(gè)組，每個(gè)組有若干數(shù)據(jù)塊。通過(guò)建立內(nèi)存數(shù)據(jù)和組索引的對(duì)應(yīng)關(guān)系，一個(gè)內(nèi)存塊可以被載入到對(duì)應(yīng)組內(nèi)的任一數(shù)據(jù)塊上。

直接映射可以認(rèn)為是單路組相聯(lián)。經(jīng)驗(yàn)規(guī)則表明，在緩存小于128KB時(shí)，欲達(dá)到相同失效率，一個(gè)雙路組相聯(lián)緩存僅需相當(dāng)于直接匹配緩存一半的存儲(chǔ)空間。

為了和下級(jí)存儲(chǔ)（如內(nèi)存）保持?jǐn)?shù)據(jù)一致性，就必須把數(shù)據(jù)更新適時(shí)傳播下去。這種傳播通過(guò)回寫(xiě)來(lái)完成。

寫(xiě)策略

一般有兩種回寫(xiě)策略：寫(xiě)回（Writeback）和寫(xiě)通（Writethrough）。

寫(xiě)回是指，僅當(dāng)一個(gè)緩存塊需要被替換回內(nèi)存時(shí)，才將其內(nèi)容寫(xiě)入內(nèi)存。如果緩存命中，則總是不用更新內(nèi)存。為了減少內(nèi)存寫(xiě)操作，緩存塊通常還設(shè)有一個(gè)臟位（dirtybit），用以標(biāo)識(shí)該塊在被載入之后是否發(fā)生過(guò)更新。如果一個(gè)緩存塊在被置換回內(nèi)存之前從未被寫(xiě)入過(guò)，則可以免去回寫(xiě)操作。

寫(xiě)回的優(yōu)點(diǎn)是節(jié)省了大量的寫(xiě)操作。這主要是因?yàn)?，?duì)一個(gè)數(shù)據(jù)塊內(nèi)不同單元的更新僅需一次寫(xiě)操作即可完成。這種內(nèi)存帶寬上的節(jié)省進(jìn)一步降低了能耗，因此頗適用于嵌入式系統(tǒng)。

寫(xiě)通是指，每當(dāng)緩存接收到寫(xiě)數(shù)據(jù)指令，都直接將數(shù)據(jù)寫(xiě)回到內(nèi)存。如果此數(shù)據(jù)地址也在緩存中，則必須同時(shí)更新緩存。由于這種設(shè)計(jì)會(huì)引發(fā)造成大量寫(xiě)內(nèi)存操作，有必要設(shè)置一個(gè)緩沖來(lái)減少硬件沖突。這個(gè)緩沖稱(chēng)作寫(xiě)緩沖器（Writebuffer），通常不超過(guò)4個(gè)緩存塊大小。不過(guò)，出于同樣的目的，寫(xiě)緩沖器也可以用于寫(xiě)回型緩存。

寫(xiě)通較寫(xiě)回易于實(shí)現(xiàn)，并且能更簡(jiǎn)單地維持?jǐn)?shù)據(jù)一致性。

當(dāng)發(fā)生寫(xiě)失效時(shí)，緩存可有兩種處理策略，分別稱(chēng)為分配寫(xiě)（Writeallocate）和非分配寫(xiě)（No-writeallocate）。

分配寫(xiě)是指，先如處理讀失效一樣，將所需數(shù)據(jù)讀入緩存，然后再將數(shù)據(jù)寫(xiě)到被讀入的單元。非分配寫(xiě)則總是直接將數(shù)據(jù)寫(xiě)回內(nèi)存。

設(shè)計(jì)緩存時(shí)可以使用回寫(xiě)策略和分配策略的任意組合。對(duì)于不同組合，發(fā)生數(shù)據(jù)寫(xiě)操作時(shí)的行為也有所不同。

對(duì)于組相聯(lián)緩存，當(dāng)一個(gè)組的全部緩存塊都被占滿(mǎn)后，如果再次發(fā)生緩存失效，就必須選擇一個(gè)緩存塊來(lái)替換掉。存在多種策略決定哪個(gè)塊被替換。

替換策略

顯然，最理想的替換塊應(yīng)當(dāng)是距下一次被訪問(wèn)最晚的那個(gè)。這種理想策略無(wú)法真正實(shí)現(xiàn)，但它為設(shè)計(jì)其他策略提供了方向。

先進(jìn)先出算法（FIFO）替換掉進(jìn)入組內(nèi)時(shí)間最長(zhǎng)的緩存塊。最久未使用算法（LRU）則跟蹤各個(gè)緩存塊的使用狀況，并根據(jù)統(tǒng)計(jì)比較出哪個(gè)塊已經(jīng)最長(zhǎng)時(shí)間未被訪問(wèn)。對(duì)于2路以上相聯(lián)，這個(gè)算法的時(shí)間代價(jià)會(huì)非常高。

對(duì)最久未使用算法的一個(gè)近似是非最近使用（NMRU）。這個(gè)算法僅記錄哪一個(gè)緩存塊是最近被使用的。在替換時(shí)，會(huì)隨機(jī)替換掉任何一個(gè)其他的塊。故稱(chēng)非最近使用。相比于LRU，這種算法僅需硬件為每一個(gè)緩存塊增加一個(gè)使用位（usebit）即可。

此外，也可使用純粹的隨機(jī)替換法。測(cè)試表明完全隨機(jī)替換的性能近似于LRU。

責(zé)任編輯：haq