Cache分類與替換算法

根據(jù)不同的分類標(biāo)準(zhǔn)可以按以下3種方法對(duì)Cache進(jìn)行分類。

?1）數(shù)據(jù)cache和指令cache

?● 指令cache：指令預(yù)取時(shí)使用的cache。

?● 數(shù)據(jù)cache：數(shù)據(jù)讀寫時(shí)使用的cache。

如果一個(gè)存儲(chǔ)系統(tǒng)中指令cache和數(shù)據(jù)cache是同一個(gè)cache，稱系統(tǒng)使用了統(tǒng)一的cache。反之，如果是分開(kāi)的，那么稱系統(tǒng)使用了獨(dú)立的cache；如果系統(tǒng)中只包含指令cache或者數(shù)據(jù)cache，那么在配制系統(tǒng)時(shí)可以作為獨(dú)立的cache使用了。

使用獨(dú)立的數(shù)據(jù)cache和指令cache，可以在同一個(gè)時(shí)鐘周期中讀取指令和數(shù)據(jù)，而不需要雙端口的cache，但這時(shí)候要注意保證指令和數(shù)據(jù)的一致性。

?2）寫通（write-through）cache和寫回（write-back）cache

?● 寫回cache CPU在執(zhí)行寫操作時(shí)，被寫的數(shù)據(jù)只寫入cache，不寫入主存，僅當(dāng)需要替換時(shí)，才把已經(jīng)修改的cache塊寫回到主存中，在采用這種更新算法的cache快表中，一般有一個(gè)修改位，當(dāng)一塊中的任何一個(gè)單元被修改時(shí)，這一塊的修改位被設(shè)置為1，否則這一塊的修改位仍保持為0；在需要替換這一塊時(shí)，如果對(duì)應(yīng)的修改位為1，則必須先把這一塊寫到主存中去之后，才能調(diào)入新的塊，否則，只要用新調(diào)入的塊覆蓋該塊即可。

?● 寫通cache CPU在執(zhí)行寫操作時(shí)，必須把數(shù)據(jù)同時(shí)寫入cache和主存，這樣，在cache的快表中就不需要“修改位”，
當(dāng)某一塊需要替換時(shí)，也不必把這一塊寫回到主存中，新調(diào)入的塊可以立即把這一塊覆蓋掉。

寫回cache和寫通cache的優(yōu)缺點(diǎn)比較如下表所示。

寫回cache與寫通cache比較

?3）讀時(shí)分配（read-allocate）cache和寫時(shí)分配（write-allocate）cache

?● 讀時(shí)分配cache當(dāng)進(jìn)行數(shù)據(jù)寫操作時(shí)，如果cache沒(méi)命中，只是簡(jiǎn)單地將數(shù)據(jù)寫入主存中，主要在數(shù)據(jù)讀取時(shí)，才進(jìn)行cache內(nèi)容預(yù)取。

?●寫時(shí)分配cache當(dāng)進(jìn)行數(shù)據(jù)寫操作時(shí)，如果cache未命中，cache系統(tǒng)將會(huì)進(jìn)行cache內(nèi)容預(yù)取，從主存中將相應(yīng)的塊讀取到cache中相應(yīng)的位置，并執(zhí)行寫操作，把數(shù)據(jù)寫入到cache中。對(duì)于寫通類型的cache，數(shù)據(jù)將會(huì)同時(shí)寫入到主存中，對(duì)于寫回類型的cache，數(shù)據(jù)將在合適的時(shí)候?qū)懟氐街鞔嬷小?/p>

由于寫操作分配cache增加了cache內(nèi)容預(yù)取的次數(shù)，增加了寫操作的開(kāi)銷，但同時(shí)可能提高cache的命中率，因此這種技術(shù)對(duì)于系統(tǒng)整體性能的影響與程序中讀操作和寫操作的數(shù)量有關(guān)。

Cache替換算法

隨機(jī)替換算法

通過(guò)一個(gè)偽隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)偽隨機(jī)數(shù)，用新塊編號(hào)為該偽隨機(jī)數(shù)的cache塊替換掉。這種算法很簡(jiǎn)單且容易實(shí)現(xiàn)，但沒(méi)有考慮程序的局部性特點(diǎn)，也沒(méi)有利用歷史上塊地址流的分布情況，因而效果較差，同時(shí)這種算法不易預(yù)測(cè)最壞情況下cache的性能。

輪轉(zhuǎn)替換算法

維護(hù)一個(gè)邏輯的計(jì)數(shù)器，利用該計(jì)數(shù)器依次選擇將要被替換出去的cache塊。這種算法容易預(yù)測(cè)在最壞情況下cache的性能。但在程序發(fā)生很小的變化時(shí)，可能造成cache平均性能的急劇變化，這是它的一個(gè)明顯缺點(diǎn)。