從三個方面闡述Cache

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

映射方式

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

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

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

（1）directmapped

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

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

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

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

（2）fullyassociative

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

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

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

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

（3）setassociative

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

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

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

setassociative是折中方案，所以其特點就是集directmapped 和fully associative之所長。是一個平衡方案。

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

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

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

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

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

寫策略

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

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

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

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

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

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

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

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

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

替換策略

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

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

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

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

責(zé)任編輯：haq