1、cache存儲(chǔ)器,1、cache基本原理,一、功能 解決CPU和主存之間的速度不匹配問(wèn)題。一般采用高速的SRAM構(gòu)成。CPU和主存之間的速度差別很大采用兩級(jí)或多級(jí)Cache系統(tǒng)。早期的一級(jí)Cache在CPU內(nèi)，二級(jí)在主板上?，F(xiàn)在的CPU內(nèi)帶L1 Cahe和L2 Cahe。全由硬件調(diào)度，對(duì)用戶透明。,二、Cache基本原理 地址映射；替換策略；寫一致性；性能評(píng)價(jià)。,cache基本原理小結(jié)： Cache是介于CPU和主存M2之間的小容量存儲(chǔ)器，但存取速度比主存快。主存容量配置幾百M(fèi)B的情況下，cache的典型值是幾百KB。cache能高速地向CPU提供指令和數(shù)據(jù)，從而加快了程序的執(zhí)行速度。從功能上

2、看，它是主存的緩沖存儲(chǔ)器，由高速的SRAM組成。為追求高速，包括管理在內(nèi)的全部功能由硬件實(shí)現(xiàn)，因而對(duì)程序員是透明的。 Cache的設(shè)計(jì)依據(jù):CPU這次訪問(wèn)過(guò)的數(shù)據(jù)，下次有很大的可能也是訪問(wèn)附近的數(shù)據(jù)。 CPU與Cache之間的數(shù)據(jù)傳送是以字為單位 主存與Cache之間的數(shù)據(jù)傳送是以塊為單位 CPU讀主存時(shí)，便把地址同時(shí)送給Cache和主存，Cache控制邏輯依據(jù)地址判斷此字是否在Cache中，若在此字立即傳送給CPU ，否則，則用主存讀周期把此字從主存讀出送到CPU，與此同時(shí)，把含有這個(gè)字的整個(gè)數(shù)據(jù)塊從主存讀出送到cache中。,三、cache的命中率 增加cache的目的，就是在性能上使主存

3、的平均讀出時(shí)間盡可能接近c(diǎn)ache的讀出時(shí)間。因此,cache的命中率應(yīng)接近于1。由于程序訪問(wèn)的局部性 ，這是可能的。在一個(gè)程序執(zhí)行期間，設(shè)Nc表示cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，h定義為命中率，則有 h=Nc/(Nc+Nm) (3.4) 若tc表示命中時(shí)的cache訪問(wèn)時(shí)間，tm表示未命中時(shí)的主存訪問(wèn)時(shí)間，1-h表示未命中率，則cache/主存系統(tǒng)的平均訪問(wèn)時(shí)間ta為： ta=htc+(1-h)tm （3.5） 設(shè)r=tm/tc表示主存慢于cache的倍率,e表示訪問(wèn)效率，則有:,為提高訪問(wèn)效率，命中率h越接近1越好，r值以510為宜，不宜太大。命中率h與程序的行為

4、、cache的容量、組織方式、塊的大小有關(guān)。,【例5】CPU執(zhí)行一段程序時(shí)，cache完成存取的次數(shù)為1900次，主存完成存取的次數(shù)為100次，已知cache存取周期為50ns，主存存取周期為250ns，求cache/主存系統(tǒng)的效率和平均訪問(wèn)時(shí)間。 【解】 h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=250ns/50ns=5 e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3% ta=tc/e=50ns/0.833=60ns,無(wú)論選擇那種映射方式，都要把主存和cache劃分為同樣大小的“塊”。 選擇哪種映射方式，要考慮： 硬件是否容易

5、實(shí)現(xiàn) 地址變換的速度是否快 主存空間的利用率是否高 主存裝入一塊時(shí)，發(fā)生沖突的概率 以下我們介紹三種映射方法：,2、主存與cache的地址映射,一、全相聯(lián)的映射方式 映射方法（多對(duì)多） 主存內(nèi)容可以拷貝到任意行 地址變換 1、將地址分為兩部分（塊號(hào)和字），在內(nèi)存塊寫入Cache時(shí)，同時(shí)寫入塊號(hào)標(biāo)記；2、CPU給出訪問(wèn)地址后，也將地址分為兩部分（塊號(hào)和字），比較電路塊號(hào)與Cache 表中的標(biāo)記進(jìn)行比較，相同表示命中，訪問(wèn)相應(yīng)單元；如果沒(méi)有命中訪問(wèn)內(nèi)存，CPU 直接訪問(wèn)內(nèi)存，并將被訪問(wèn)內(nèi)存的相對(duì)應(yīng)塊寫入Cache。3、特點(diǎn)：優(yōu)點(diǎn)：沖突概率小，Cache的利用高。缺點(diǎn)：比較器難實(shí)現(xiàn)，需要一個(gè)訪問(wèn)速度

6、很快代價(jià)高的相聯(lián)存儲(chǔ)器4、應(yīng)用場(chǎng)合：適用于小容量的Cache,二、直接映射方式 1、映射方法（一對(duì)多）如： i= j mod m 主存第j塊內(nèi)容拷貝到Cache的i行 一般I和m都是2N級(jí) 例cache容量16字，主存容量256字，則地址2，18，34.242等都存放在cache的地址2內(nèi)，如果第一次2在cache中，下次訪問(wèn)34內(nèi)容，則不管cache其他位置的內(nèi)容訪問(wèn)情況，都會(huì)引起2塊內(nèi)容的替換,2、基本原理利用行號(hào)選擇相應(yīng)行；把行標(biāo)記與CPU訪問(wèn)地址進(jìn)行比較，相同表示命中，訪問(wèn)Cache；如果沒(méi)有命中，訪問(wèn)內(nèi) 存，并將相應(yīng)塊寫入Cache 3、特點(diǎn)優(yōu)點(diǎn)：比較電路少m倍線路，所以硬件實(shí)現(xiàn)簡(jiǎn)單

7、，Cache地址為主存地址的低幾位，不需變換。缺點(diǎn)：沖突概率高（抖動(dòng)）4、應(yīng)用場(chǎng)合適合大容量Cache,主存地址長(zhǎng)度(s+w)位尋址單元數(shù)2s+w個(gè)字或字節(jié)塊大小行大小2w個(gè)字或字節(jié)主存的塊數(shù)2scache的行數(shù)m2r標(biāo)記大小(s-r)位,三、組相聯(lián)映射方式 組相聯(lián)映射方式是前兩者的組合 Cache分組，組間采用直接映射方式，組內(nèi)采用全相聯(lián)的映射方式 Cache分組U，組內(nèi)容量V 映射方法（一對(duì)多） q= j mod u 主存第j塊內(nèi)容拷貝到Cache的q組中的某行 地址變換 設(shè)主存地址x，看是不是在cache中，先y= x mod u，則在y組中一次查找 分析：比全相聯(lián)容易實(shí)現(xiàn)，沖突低 v=

8、1，則為直接相聯(lián)映射方式 u=1，則為全相聯(lián)映射方式 v的取值一般比較小， 一般是2的冪，稱之為v路組相聯(lián)cache.,主存地址長(zhǎng)度(s+w)位尋址單元數(shù)2s+w個(gè)字或字節(jié)塊大小行大小2w個(gè)字或字節(jié)主存的塊數(shù)2s每組的行數(shù)k每組的v2dcache的行數(shù)kv標(biāo)記大小(s-d)位,cache工作原理要求它盡量保存最新數(shù)據(jù)，必然要產(chǎn)生替換。 對(duì)直接映射的cache來(lái)說(shuō)，只要把此特定位置上的原主存塊換出cache即可。 對(duì)全相聯(lián)和組相聯(lián)cache來(lái)說(shuō)， 就要從允許存放新主存塊的若干特定行中選取一行換出。,3、替換策略,最不經(jīng)常使用(LFU)算法 LFU算法將一段時(shí)間內(nèi)被訪問(wèn)次數(shù)最少的那行數(shù)據(jù)換出。每行

9、設(shè)置一個(gè)計(jì)數(shù)器。從0開始計(jì)數(shù)，每訪問(wèn)一次， 被訪行的計(jì)數(shù)器增1。當(dāng)需要替換時(shí)，將計(jì)數(shù)值最小的行換出，同時(shí)將這些行的計(jì)數(shù)器都清零。 這種算法將計(jì)數(shù)周期限定在對(duì)這些特定行兩次替換之間的間隔時(shí)間內(nèi)，不能嚴(yán)格反映近期訪問(wèn)情況。 近期最少使用(LRU)算法 LRU算法將近期內(nèi)長(zhǎng)久未被訪問(wèn)過(guò)的行換出。每行也設(shè)置一個(gè)計(jì)數(shù)器，cache每命中一次，命中行計(jì)數(shù)器清零，其它各行計(jì)數(shù)器增1。當(dāng)需要替換時(shí)，將計(jì)數(shù)值最大的行換出。 這種算法保護(hù)了剛拷貝到cache中的新數(shù)據(jù)行，有較高的命中率。 隨機(jī)替換 隨機(jī)替換策略從特定的行位置中隨機(jī)地選取一行換出。在硬件上容易實(shí)現(xiàn)，且速度也比前兩種策略快。缺點(diǎn)是降低了命中率和cache工作效率。,CPU對(duì)cache的寫入更改了cache的內(nèi)容?？蛇x用寫操作策略使cache內(nèi)容和主存內(nèi)容保持一致。,4、 cache的寫操作策略,寫回法 當(dāng)CPU寫cache命中時(shí)，只修 改cache的內(nèi)容，而不立即寫入主存；只有當(dāng)此行被換出時(shí)才寫回主存。這種方法減少了訪問(wèn)主存的次數(shù),但是存在不一致性的隱患。實(shí)現(xiàn)這種方法時(shí)，每個(gè)cache行必須配置一個(gè)修改位，以反映此行是否被CPU修改過(guò)。 全寫法 當(dāng)寫cache命中時(shí)，cache與主存同時(shí)發(fā)生寫修改，因而較好地維護(hù)了cache與主存