《3高速緩沖存儲器Cache.ppt》由會員分享，可在線閱讀，更多相關(guān)《3高速緩沖存儲器Cache.ppt（54頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、3 高速緩沖存儲器（Cache）n工作原理和基本結(jié)構(gòu) n地址映象與變換 nCache存儲器的LRU替換算法的硬件實(shí)現(xiàn) nCache存儲器的透明性及性能分析 1為什么要使用Cache?n用以彌補(bǔ)主存速度的不足。nCPU速度與主存速度相差很大（例如，一般的DRAM的工作速度比CPU慢100倍以上。nCache工作速度很高，可以將其集成到CPU內(nèi)。高性能CPU通常用兩級Cache,一級在CPU內(nèi)，其容量比較小，速度很快，第二級在主板上，容量比較大，速度比第一級低5倍左右。nCache全部用硬件調(diào)度對所有程序員都是透明的。nCache與主存儲器之間以塊為單位進(jìn)行數(shù)據(jù)交換。塊的大小通常以在主存儲器的一個

2、存儲周期內(nèi)可以訪問到的數(shù)據(jù)長度為限。2存儲系統(tǒng)兩級存儲器速度比Cache虛擬存儲器要達(dá)到的目標(biāo)提高速度擴(kuò)大容量實(shí)現(xiàn)方法全部硬件軟件為主硬件為輔310倍105倍頁(塊)大小116字1KB16KB等效存儲容量主存儲器虛擬存儲器透明性對系統(tǒng)和應(yīng)用程序員僅對應(yīng)用程序員不命中時處理方式 等待主存儲器任務(wù)切換Cache存儲系統(tǒng)與虛擬存儲系統(tǒng)比較3塊號塊內(nèi)地址主存-Cache地址映象變換機(jī)構(gòu)塊號塊內(nèi)地址Cache主存Cache替換策略來自處理機(jī)主存地址Cache地址訪主存替換Cache訪主存裝入Cache去處理機(jī)直接通路單字寬多字寬單字寬已裝不進(jìn)還可裝入不命中命中高速緩沖存儲器Cache4基本結(jié)構(gòu) n把主存

3、和Cache機(jī)械等分成相同大小的塊（行），塊比頁小得多；n訪問Cache的時間時訪問主存時間的1/4到1/10；nCache和CPU是同類型的半導(dǎo)體器件；nCache-主存間的地址映像和變換，以及替換、調(diào)度算法用硬件實(shí)現(xiàn)，對應(yīng)用程序員透明，也對系統(tǒng)程序員透明；5基本結(jié)構(gòu)（續(xù)）nCache在物理位置上靠近CPU，不在主存，減少傳輸延遲；n除Cache到處理機(jī)的通路外，還設(shè)有主存到處理機(jī)的通路，因此，Cache既是Cache-主存存儲層次中的一級，又是處理機(jī)和主存的一個旁視存儲器；n有Cache的主存系統(tǒng)都采用多體交叉存儲器；n應(yīng)盡量提高Cache的訪主存的優(yōu)先級；6地址映象與變換 n地址映象：是

4、將每個主存塊按某種規(guī)則（算法）裝入（定位于）Cache,并建立主存地址與Cache地址之間的對應(yīng)關(guān)系。n地址變換：是主存塊按照這種映象關(guān)系裝入Cache后,每次訪Cache，如何將主存地址變換成Cache地址。n在選取地址映象方法要考慮的主要因素：n地址變換的硬件容易實(shí)現(xiàn)；n地址變換的速度要快；n主存空間利用率要高；n發(fā)生塊沖突的概率要小7四種方式n全相聯(lián)映象與變換 n直接映象與變換 n組相聯(lián)映像與變換 n段相聯(lián)映象 8全相聯(lián)映象與變換n定義及規(guī)則n映象規(guī)則：主存中的任意一塊都可以映象到Cache中的任意一塊。n如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，映象關(guān)系共有：CbMb種。n用硬件實(shí)

5、現(xiàn)非常復(fù)雜n在虛擬存儲器中，全部用軟件實(shí)現(xiàn)9n相聯(lián)目錄表法n變換過程，如下圖。n特點(diǎn)：n沖突概率低n空間利用率高n地址變換復(fù)雜10塊0Cache塊1塊Cb-1塊0塊1塊i塊Mb-1主存儲器全相聯(lián)映象方式11有效位塊號B塊內(nèi)地址主存地址目錄表（由相聯(lián)存儲器組成，共Cb個字）主存塊號BB塊號b塊內(nèi)地址wCache塊號bb相聯(lián)比較命中Cache地址12直接映象與變換n定義及規(guī)則n映象規(guī)則：主存中一塊只能映象到Cache的一個特定的塊中。n計(jì)算公式：bB mod Cb，其中：b為Cache的塊號，B是主存的塊號，Cb是Cache的塊數(shù)。n整個Cache地址與主存地址的低位部分完全相同。13n變換過程，

6、如下圖。n特點(diǎn)：n硬件簡單n沖突概率高n出現(xiàn)大量空閑塊n很少使用。14塊0Cache塊1塊Cb-1塊0塊Cb-1主存儲器直接相聯(lián)映象方式塊Cb塊2Cb-1塊Mb-Cb塊Mb-1區(qū)0區(qū)1區(qū)Me-115n地址變換過程n用主存地址中的塊號B去訪問區(qū)號存儲器n把讀出來的區(qū)號與主存地址中的區(qū)號E進(jìn)行比較n比較結(jié)果相等,且有效位為1,則Cache命中n比較結(jié)果相等,有效位為0,表示Cache中的這一塊已經(jīng)作廢n比較結(jié)果不相等,有效位為0,表示Cache中的這一塊是空的n比較結(jié)果不相等,有效位為1,表示原來在Cache中的這一塊是有用的16有效位區(qū)號E塊內(nèi)地址w1主存地址區(qū)表存儲器區(qū)號E(按地址訪問)E塊號

7、b塊內(nèi)地址w命中Cache地址塊號B相等比較塊失效比較相等且有效位為1，訪問Cache17n提高Cache速度的一種方法：n把區(qū)號存儲器與Cache合并成一個存儲器n直接映象方法的主要優(yōu)點(diǎn)：n硬件實(shí)現(xiàn)很簡單,不需要相聯(lián)訪問存儲器訪問速度也比較快,實(shí)際上不做地址變換n直接映象方式的主要缺點(diǎn):n塊的沖突率較高18有效位區(qū)號E塊內(nèi)地址w1按地址訪問的Cache區(qū)號E塊號b塊內(nèi)地址w相等塊號B相等比較訪主存數(shù)據(jù)0D0數(shù)據(jù)1D1數(shù)據(jù)w-1Dw-11/w送CPU19組相聯(lián)映像與變換n定義及規(guī)則：各組之間是直接映象，組內(nèi)各塊間是全相聯(lián)映象。n變換過程，如下圖。n討論：nS=nv時，全相聯(lián)映像；nS=0時，直

8、接映像；n當(dāng)主存空間和Cache空間確定時，q+s已確定；ns值大，組內(nèi)頁數(shù)多，沖突概率小，變換復(fù)雜；ns值小，組內(nèi)頁數(shù)少，沖突概率大，變換簡單；20組內(nèi)塊號s區(qū)號nd塊內(nèi)地址W主存地址塊表nd區(qū)號，組內(nèi)塊號s相聯(lián)比較(s個塊)塊內(nèi)地址w相等Cache地址組內(nèi)塊號s相聯(lián)比較不等組號q組內(nèi)塊號s組號q21n組相聯(lián)映象方式的優(yōu)點(diǎn)：n塊的沖突概率比較低n塊的利用率大幅度提高n塊失效率明顯降低n組相聯(lián)映象方式的缺點(diǎn)：實(shí)現(xiàn)難度和造價要比直接映象方式高n地址變換過程：用主存地址的組號G按地址訪問塊表存儲器n把讀出來的一組區(qū)號和塊號與主存地址中的區(qū)號和塊號進(jìn)行相聯(lián)比較如果有相等的，表示Cache命中如果沒有

9、相等的，表示Cache沒有命中22段相聯(lián)映象 n減少相聯(lián)目錄表的容量，降低成本，提高地址變換速度。n組間全相聯(lián)，組內(nèi)直接映象。23替換算法的實(shí)現(xiàn)n常采用LRU算法，LRU算法是堆棧型算法n由于Cache的調(diào)塊時間是微秒級，不能采用程序換道n替換算法全部采用硬件途徑實(shí)現(xiàn)24堆棧法(塊號)(塊號)(塊號)(塊號)(塊號)近期最近訪問過的塊號近期最久沒有訪問的塊號需重新排序的塊號都下推一行被訪問的塊號（經(jīng)相聯(lián)比較找到）25比較對法n讓各個塊成對組合，用一個觸發(fā)器的狀態(tài)表示該比較對內(nèi)兩塊訪問的遠(yuǎn)近次序，再經(jīng)門電路就可找到LRU塊。n適用于組內(nèi)塊數(shù)較少的組相聯(lián)映像Cache。&TABTACTBC訪問B訪

10、問C訪問A00011126替換算法的設(shè)計(jì)要考慮的問題n如何對每次訪問進(jìn)行紀(jì)錄（適用位法、堆棧法、比較對法所用的記錄方法都不同）n如何根據(jù)所紀(jì)錄的信息來判定近期內(nèi)哪一塊是最久沒有被訪問過的nCache替換算法的主要特點(diǎn)：全部用硬件實(shí)現(xiàn)27Cache存儲器的透明性及性能分析 nCache的透明性 nCache的取算法 nCache存儲器性能分析 28Cache的透明性和一致性問題n由于Cache存儲器的地址變換和塊替換算法全由硬件實(shí)現(xiàn)，因此Cache-主存存儲層次對應(yīng)用程序員和系統(tǒng)程序員都是透明的。n本節(jié)討論的內(nèi)容僅限于單處理機(jī)、單存儲器n造成Cache與主存的不一致的原因：n由于CPU寫Cach

11、e，沒有立即寫主存n由于IO處理機(jī)或IO設(shè)備寫主存29CPUXI/OXCache主存儲器CPUXI/OXCache主存儲器(a)CPU寫Cache(b)I/O寫主存Cache與主存不一致的兩種情況30Cache的透明性n寫回法（抵觸修改法，WB）：是在CPU執(zhí)行寫操作時，信息只寫入Cache，僅當(dāng)需要被替換時，才將以被寫入過的Cache塊先送回主存，然后再調(diào)入新塊。n寫直達(dá)法（直達(dá)法，WT）：利用Cache主存存儲層次在處理機(jī)和主存之間的直接通路，每當(dāng)處理機(jī)寫入Cache的同時，也通過此通路直接寫入主存。31寫回法與寫直達(dá)法的優(yōu)缺點(diǎn)比較n可靠性，寫直達(dá)法優(yōu)于寫回法n與主存的通信量,寫回法少于寫

12、直達(dá)法n例如：寫操作占總訪存次數(shù)的20,Cache命中率為99%,每塊4個字。當(dāng)Cache發(fā)生塊替換時,有30%塊需要寫回主存,其余的因未被修改過而不必寫回主存。則對于WT法,寫主存次數(shù)占總訪存次數(shù)的20%。而WB法為(1-99%)*30%*4=1.2%。因此,WB法與主存的通信量要比WT法少10多倍。32寫回法與寫直達(dá)法的優(yōu)缺點(diǎn)比較n控制的復(fù)雜性：寫直達(dá)法比寫回法簡單n硬件實(shí)現(xiàn)的代價：寫回法要比寫直達(dá)法好n采用何種算法與適用場合有關(guān)n單處理機(jī)（節(jié)省成本）：寫回法n共享主存的多處理機(jī)（保證信息交換可靠）：寫直達(dá)法33n寫Cache的兩種方法：n不按寫分配法：在寫Cache不命中時，只把所要寫的

13、字寫入主存。n按寫分配法：在寫Cache不命中時，還把一個塊從主存讀入Cache。n目前，在寫回法中采用按寫分配法，在寫直達(dá)法中采用不按寫分配法。34Cache的取算法 n按需取進(jìn)法：出現(xiàn)Cache塊失效時，才將要訪問的字所在的塊（行）取進(jìn)。n預(yù)取法n恒預(yù)?。褐灰L問到主存第i塊的某個字，不論Cache是否命中，恒發(fā)預(yù)取命令。n不命中時預(yù)?。航?dāng)訪問第i塊不命中時，才預(yù)取命令。n采用預(yù)取法并非能提高命中率，其他因素n塊的大小n預(yù)取開銷35說明n采用緩沖器技術(shù)是減少預(yù)取干擾的好辦法n模擬結(jié)果表明n恒預(yù)取法使不命中率降低75%-80%n不命中率時預(yù)取法使不命中率降低30%-40%n但前者所引起的C

14、ache、主存間傳輸量的增加要比后者大得多。36Cache存儲器性能分析 n不命中率與Cache的容量、組的大小和快的大小的關(guān)系nCache-主存存儲層次的等效速度與命中率的關(guān)系推導(dǎo)nCache的容量對機(jī)器速度的關(guān)系37塊的大小、組的大小與Cache容量對Cache命中的影響不命中率1-HcCache容量組的大小一定塊的大小減小不命中率1-HcCache容量塊的大小一定組的大小減小塊的大小、組的大小及Cache容量增大時都能提高命中率38Cache-主存存儲層次的等效速度與命中率的關(guān)系推導(dǎo)設(shè)：tc 為Cache的訪問時間，tm為主存周期，Hc為訪Cache的命中率。則：Cache的等效存儲周期

15、 ta=Hc tc+(1-Hc)tm 因?yàn)椋褐鞔媾cCPU之間有直接通路，因此CPU對第二級的訪問時間就是tm。39（續(xù)）速度提高倍數(shù)是：因?yàn)镠c總小于1，可以令 40分析n由于 因此 n不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache-主存存儲層次后，速度能提高的最大值是有限的，不會超過41舉例nHc=0.5,=1 的最大值2nHc=0.75,=3 的最大值4nHc=1,Hc的期望值10.50.250.75124842舉例n由于Cache的命中率一般比0.9大的多，可達(dá)0.996，因此接近于所期望的tm/tcnHc受Cache容量的影響很大。n容量為4kb時，Hc

16、=0.93n容量為8kb時，Hc=0.9743舉例n因此在tm/tc=0.12時n4KB的Cache，速度的倍數(shù)是n8KB的Cache，速度的倍數(shù)是n增加4KB容量，帶來層次速度的提高：44Cache的容量對機(jī)器速度的關(guān)系n機(jī)器速度的單位是MIPS(每秒執(zhí)行百萬條指令)n主存采用多體交叉存取機(jī)器速度(MIPS)1020302004006008001000主存訪問時間(ns)無Cache 10ns4k 10ns64k 40ns16k 10ns64k 20ns64k 10nsCache CPU容量 拍寬45續(xù)n主存速度和CPU周期一定時，Cache容量變化，機(jī)器速度變化。nCache容量4KB，CPU拍寬10ns，主存周期1s，機(jī)器速度約為5MPISn同樣條件下，Cache容量增加到64KB，機(jī)器速度可能達(dá)15MPISn沒有Cache時，機(jī)器速度可能只有2MIPS46續(xù)nCache容量的增大，可以顯著降低對主存速度的要求n要達(dá)到機(jī)器速度為15MIPS，對于10ns的CPU拍寬、4KB容量的Cache，要求主存訪問周期為200nsnCache容量增達(dá)到64KB時，主存周期可以降低到1s474