第五 章__存儲系統(tǒng)cache

1、5.3 并行(bngxng)主存儲器 所謂并行主存儲器，是指在一個(y )主存周期內(nèi)可以并行讀取多個數(shù)據(jù)字的主存儲器。通常采用單體多字和交叉存取方式。 尋址方式有單體多字尋址方式、多體存儲器的尋址方式和多體交叉尋址方式。下一頁上一頁共六十三頁 當(dāng)并行(bngxng)的存儲器共用一套地址寄存器和地址譯碼電路時稱為單體方式，其結(jié)構(gòu)原理圖如下。下一頁上一頁單體(dn t)多字尋址方式共六十三頁 多個并行存儲器與同一地址寄存器連接，所以同時被一個單元地址驅(qū)動，一次訪問讀出的是沿n個存儲器順序排列的n個字，故也稱單體多字方式。與單體單字結(jié)構(gòu)的存儲器相比，單體多字尋址方式在存取速度方面有明顯的優(yōu)點，因為，

2、單體單字存儲器的每一個主存周期只能讀出一條指令或一個數(shù)據(jù)，在取指和讀取數(shù)據(jù)的周期內(nèi)，CPU處于等待狀態(tài)(zhungti)，因此工作效率低。在本例所示的單體4字的尋址方式中，一次能讀出4個字長為w位的數(shù)據(jù)或指令，然后再以單字長的形式送給CPU執(zhí)行。當(dāng)然，若處理的數(shù)據(jù)不是連續(xù)地存放在主存中，或者在程序中經(jīng)常使用轉(zhuǎn)移指令，單體多字尋址方式的效果就不顯著了。下一頁上一頁共六十三頁下一頁上一頁多體存儲器的尋址方式(fngsh)下圖是多體存儲器原理圖共六十三頁下一頁上一頁 計算機(jī)系統(tǒng)中的大容量主存是由多個存儲體組成的，每個存儲體都有自己的讀寫線路、地址寄存器和數(shù)據(jù)寄存器，能以同等的方式與CPU交換信息，每

3、個存儲體容量相等，它們既能同時工作又獨(dú)立編址。圖中MAR為模塊地址寄存器，MDR為模塊數(shù)據(jù)寄存器，主存地址寄存器的高位表示模塊號，低位表示塊內(nèi)地址。這種結(jié)構(gòu)的尋址方式有利于并行處理，能夠?qū)崿F(xiàn)多個分體(fn t)的并行操作，一次訪問并行處理的n個字，不像單體方式那樣一定是沿存儲器順序排列的存儲單元內(nèi)容，而是分別由各分體的地址寄存器指示的存儲單元的內(nèi)容。因為各分體工作獨(dú)立，因此，只要進(jìn)行合理的調(diào)度，就能實現(xiàn)并行處理，兩個存儲體可以同時進(jìn)行不同的操作。例如一個存儲體被CPU訪問時，另一個存儲體可用來與外部設(shè)備進(jìn)行直接存儲器存取（DMA）操作。共六十三頁 多體交叉(jioch)是多體存儲器的另一種組織

4、形式，下面以一個四體交叉(jioch)存儲器的組織形式為例，來說明多體交叉(jioch)存儲器的工作原理。下圖是四體交叉(jioch)原理圖。下一頁上一頁多體交叉(jioch)尋址方式共六十三頁 多體交叉尋址方式與多體存儲器尋址方式不同(b tn)，多體存儲器是以高位地址作為模塊號，低位地址作為體內(nèi)地址，每個模塊體內(nèi)地址是連續(xù)的；多體交叉尋址方式是以低位地址作為模塊號，高位地址作為體內(nèi)地址，各模塊間地址編號采用交叉方式。上圖所示的4個模塊M0、M1、M2、M3的編址如下表所示?？騼?nèi)序號表示存儲單元的地址編號J=0，1，2。下一頁上一頁共六十三頁 地址連續(xù)的兩個單元分布在相鄰的兩個模塊中，地址按

5、模塊號方向(fngxing)順序編號。 同一模塊內(nèi)相鄰的兩個單元地址之差等于n。例如在四體交叉存儲器結(jié)構(gòu)方式下，兩個單元地址之差等于4。 任何一個存儲單元的二進(jìn)制地址編號的末2位正好指示該單元所屬模塊的編號，訪問主存時只要判斷這幾位就能決定訪問的是那個存儲模塊。在四體交叉存儲器結(jié)構(gòu)方式下，M0模塊的每個單元地址的二進(jìn)制編碼最后兩位都是00，M1模塊的每個單元地址最后兩位都是01，M2模塊的每個單元地址最后兩位都是02，M3模塊的每個單元地址最后兩位都是03。 同一模塊內(nèi)每個單元地址除去模塊號后的高位地址正好是模塊內(nèi)單元的順序號，由此就可決定訪問單元在模塊中的位置。下一頁上一頁n體交叉尋址方式(

6、fngsh)的規(guī)則滿足以下4點共六十三頁5.5 Cache存儲器5.5.1 多級存儲(cn ch)體系結(jié)構(gòu)5.5.2 Cache工作(gngzu)原理5.5.3 主存與Cache的地址映射和地址變換5.5.4 Cache的替換策略及寫操作策略共六十三頁中央處理器主存外存cacheCPUM1M2M3輔助硬件輔助軟硬件5.5.1 多級存儲(cn ch)體系結(jié)構(gòu)為解決存儲容量、存取速度和價格(jig)之間的矛盾,通常將各種不同存儲容量、不同存取速度的存儲器,按一定的體系結(jié)構(gòu)組織起來,形成一個統(tǒng)一整體.典型的三級存儲系統(tǒng):圖5.25 三級存儲系統(tǒng)示意圖共六十三頁 Cache-主存層次(cngc) Ca

7、che一般由SRAM構(gòu)成,容量小,存取速度快，依據(jù)程序局部性原理,存放的是主存中當(dāng)前最需要執(zhí)行的信息(xnx)副本. 目的：主存容量不足的問題. 利用輔助硬件和操作系統(tǒng)中的存儲管理軟件,將 主存和輔存構(gòu)成一個整體.目的：解決CPU和主存速度不匹配的問題. 主存-輔存層次 總體效果：存取速度接近Cache,而存儲容量接 近于輔存,整體價格也較合理.共六十三頁5.5 Cache存儲器5.5.1 多級存儲(cn ch)體系結(jié)構(gòu)5.5.2 Cache工作(gngzu)原理5.5.3 主存與Cache的地址映射和地址變換5.5.4 Cache的替換策略及寫操作策略共六十三頁1. 問題(wnt)的提出避免

8、(bmin) CPU “空等” 現(xiàn)象CPU 和主存（DRAM）的速度差異緩存CPU主存容量小速度高容量大速度低字塊共六十三頁主存塊 調(diào)入 緩存主存塊與緩存塊 建立 了對應(yīng)(duyng)關(guān)系標(biāo)記(bioj)記錄 與某緩存塊建立了對應(yīng)關(guān)系的 主存塊號命中未命中主存塊與緩存塊 未建立 對應(yīng)關(guān)系主存塊 未調(diào)入 緩存2. Cache的命中率共六十三頁命中率CPU 欲訪問的信息(xnx)在 Cache 中的 比率命中率 與 Cache 的 容量(rngling) 與 塊長 有關(guān) 共六十三頁命中率CPU 欲訪問(fngwn)的信息在 Cache 中的 比率命中率 與 Cache 的 容量(rngling)

9、與 塊長 有關(guān) 共六十三頁Cache 主存系統(tǒng)(xtng)的效率效率(xio l) e 與 命中率 有關(guān) 設(shè) Cache 命中率 為 h，訪問 Cache 的時間為 tc ， 訪問 主存 的時間為 tm 則 e = 100% tc h tc+ (1h) tm 訪問 Cache 的時間 平均訪問時間 e = 100%共六十三頁3. Cache 的 讀 操作(cozu) 訪問Cache取出信息送CPU 訪問主存取出信息送CPU將新的主存塊調(diào)入Cache中執(zhí)行替換算法 騰出空位 結(jié)束命中？Cache滿？CPU發(fā)出訪問地址 開始是否是否共六十三頁4. Cache 的基本(jbn)結(jié)構(gòu)Cache替換(t

10、 hun)機(jī)構(gòu)Cache存儲體主存Cache地址映像變換機(jī)構(gòu)由CPU完成共六十三頁 5.5.2 Cache工作(gngzu)原理Cache的工作(gngzu)機(jī)制 Cache工作是以程序訪問的局部性原理為基礎(chǔ)的,即, 一個程序的指令大都順序存放、順序執(zhí)行,與程序相關(guān)的數(shù)據(jù)在存儲器中也相對集中.所以程序運(yùn)行時,尤其有循環(huán)程序段和子程序段時,在較短時間區(qū)間內(nèi),常會對局部范圍的存儲器頻繁訪問,而此范圍之外的地址訪問甚少.這種現(xiàn)象稱為程序訪問的局部性.把局部范圍的主存內(nèi)容從主存放到一個高速小容量存儲器中,使CPU在這一段時間內(nèi)直接訪問它,以減少或不去訪問慢速的主存 ,程序運(yùn)行速度將明顯提高.共六十三頁

11、 2. Cache工作(gngzu)原理例:某機(jī)主存容量(rngling)為1MB, Cache容量為8KB,若以字節(jié)編址,每512B為一塊,則主存有2048塊, Cache有16塊.塊000000H 00001H. 001FFH塊2047FFE00HFFE01HFFFFFH主存塊00000H 0001H.01FFH塊151E00H1E01H1FFFH Cache 塊的概念一般將主存和Cache的存儲空間分塊,每塊大小相同,包括相同數(shù)量的存儲單元.共六十三頁 Cache構(gòu)成(guchng)及工作過程CPU主存主存地址(dzh)寄存器MAR主存Cache地址變換機(jī)構(gòu)(塊表)Cache存儲器Cac

12、he地址寄存器替換控制部件ABDB單字寬多字寬不命中命中(塊) Cache包括Cache存儲器及相應(yīng)控制部件,全部由硬件組成,速度快,對所有程序員均透明.CAR共六十三頁 Cache命中率 設(shè)Nc為Cache 完成(wn chng)存取的總次數(shù),Nm為主存完成存取的總次數(shù),h為命中率,則有: 設(shè)r=tm/tc表示主存慢于Cache的倍率,e表示訪問(fngwn)效率,則有: 高速緩存命中率:CPU訪存時,信息恰巧在Cache中的概率.h=Nc/(Nc+Nm) 若tc表示命中時的Cache訪問時間,tm表示未命中時的主存訪問時間,1-h表示未命中率,則Cache /主存系統(tǒng)的平均訪問時間ta為:

13、ta=htc+(1-h)tm e=tc/ta=tc/htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)h共六十三頁例：CPU執(zhí)行一段程序時,Cache完成(wn chng)存取的次數(shù)1900次,主存完成存取的次數(shù)為100次,已知Cache的存取周期為1ns,主存存取周期為5ns,求Cache/主存系統(tǒng)的效率和平均訪問時間.解：h=Nc/(Nc+Nm)=1900/(1900+100) =0.95 r=tm/tc=5ns/1ns=5 e=1/r+(1-r)h=1/5+(1-5)X0.95=83.3% ta=tc/e=1ns/0.833=1.2ns例:某計算機(jī)的存儲系統(tǒng)由Cache和主

14、存組成,某程序執(zhí)行過程中訪存1000次,其中(qzhng)訪問Cache缺失(未命中)50次,則Cache的命中率是( ). A.5% B.9.5% C.50% D.95%共六十三頁 影響 Cache命中率的因素 Cache的大小 容量相對較大的Cache,命中率也相應(yīng)提高(t go),但容量太大,成本會變得不合理. 程序的特點 遵循局部性原理的程序在運(yùn)行時Cache的命中率也會很高,相反,在程序中頻繁且無規(guī)則地使用Call或JMP命令,將嚴(yán)重影響基于Cache的系統(tǒng)性能. Cache的組織結(jié)構(gòu) Cache組織結(jié)構(gòu)的好壞,對命中率也會產(chǎn)生較大影響. Cache的組織結(jié)構(gòu)有三種類型:全相聯(lián)映射、

15、直接映射和組相聯(lián)映射. 共六十三頁5.5 Cache存儲器5.5.1 多級存儲(cn ch)體系結(jié)構(gòu)5.5.2 Cache工作(gngzu)原理5.5.3 主存與Cache的地址映射和地址變換5.5.4 Cache的替換策略及寫操作策略共六十三頁 5.5.3 主存與Cache的地址映射和地址變換1. 全相聯(lián)映射:允許主存中的每一個塊可以映射到Cache的任何一塊位置上.映射過程(guchng)如下圖所示: 一.全相聯(lián)映射(yngsh)及其地址變換 二者密切相關(guān)-地址變換由地址映射方式?jīng)Q定.主存-Cache地址變換:程序運(yùn)行時,根據(jù)地址映射把主存地址變換成Cache地址. 主存-Cache地址映

16、射(mapping):把存放在主存中的程序按某種規(guī)則裝入Cache中,并依此建立主存地址與Cache地址的對應(yīng)關(guān)系,即塊表. 塊表存放數(shù)據(jù)或指令在內(nèi)存中所在單元地址的存儲器,用于判斷Cache命中以及實現(xiàn)地址映射,其字?jǐn)?shù)等于Cache的塊數(shù).共六十三頁塊0 塊1塊15塊0塊1塊2047Cache主存全相聯(lián)映射(yngsh) 2.全相聯(lián)映射(yngsh)方式下的地址變換主存塊號塊內(nèi)地址 (1) 主存地址格式: (標(biāo)志字段)圖5.26 全相聯(lián)映射示意圖共六十三頁例:某機(jī)主存容量為1MB, Cache容量為8KB，若以字節(jié)編址，每512B為一塊(y kui),則主存有2048塊, Cache有16塊

17、。主存地址格式： 0000 0000 000 0 0000 0000 0000 0000 000 1 1 1 1 1 1 1 1 1塊號(0塊)塊內(nèi)存儲單元(cn ch dn yun)(0-511)塊號(1塊) 塊內(nèi)存儲單元( 0-511)0000 0000 001 0 0000 00000000 0000 001 1 1 1 1 1 1 1 1 1塊號(2047塊)塊內(nèi)存儲單元(0-511)1 1 1 1 1 1 1 1 111 0 0000 00001 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1共六十三頁Cache塊號塊內(nèi)地址(dzh) 主存塊號轉(zhuǎn)換(zhunh

18、un)為Cache塊號,塊內(nèi)地址不變(3) 地址變換(將主存地址轉(zhuǎn)換為Cache地址): (2) Cache地址格式:塊號(0塊)塊內(nèi)存儲單元(0-511)塊號(1塊) 塊內(nèi)存儲單元( 0-511) 0 00 1 0 0000 0000 0 00 1 1 1 1 1 1 1 1 1 1塊號(15塊)塊內(nèi)存儲單元(0-511) 1 1 1 1 0 0000 0000 1 1 1 1 1 1 1 1 1 1 1 1 1 0 00 0 0 0000 0000 0 00 0 1 1 1 1 1 1 1 1 1共六十三頁主存塊號B(標(biāo)志(biozh)字段)塊內(nèi)地址(dzh)WCache塊號b塊內(nèi)地址w主

19、存塊號BCache塊號bBb比較命中MARCAR 圖5.27 全相聯(lián)映射的地址變換塊表(塊表容量的計算：字?jǐn)?shù)等于高緩塊數(shù)，字長由主存塊數(shù)和高緩塊數(shù)決定)不命中則訪問主存注意:在全相聯(lián)映射中,主存塊號作為識別是否命中的標(biāo)志,標(biāo)志位的長度由主存塊數(shù)決定.共六十三頁字塊(z kui)0字塊(z kui)1字塊2C -1標(biāo)記標(biāo)記標(biāo)記設(shè)Cache有2C-1塊,主存有2m-1塊,即Cache塊地址有c位,主存塊地址有m位.字塊0字塊1字塊2C -1字塊2m -1主存地址格式：主存字塊標(biāo)記塊內(nèi)地址m位圖5.28 全相聯(lián)映射的另一種常見圖解共六十三頁 3.全相聯(lián)映射(yngsh)的優(yōu)缺點 i= j mod m

20、 (m為Cache中總塊數(shù)) 映射(yngsh)規(guī)則:主存中任何一組的第i塊只能放入Cache 的第i塊. 主存第j塊(大排塊數(shù))和Cache第i塊有如下函數(shù)關(guān)系:1.直接映射:首先,主存在分塊的基礎(chǔ)上分組,每組大小與Cache的大小相同。二. 直接映射及其地址變換 (2) 缺點:塊表的查找時間長,速度慢.(1) 優(yōu)點:塊沖突概率最低,只有當(dāng)Cache中全部裝滿后, 才有可能出現(xiàn)塊沖突,塊分配靈活；其中,商為主存第j塊所在主存的組數(shù),余數(shù)為在該組的塊數(shù).共六十三頁塊0塊1塊15Cache.0組1組127組塊 0 塊 1 塊15 塊16塊17 塊31 塊2047主存塊2032塊2033圖5.29

21、 直接(zhji)映射示意圖2.直接(zhji)聯(lián)映射方式下的地址變換 Cache塊號 組號塊內(nèi)地址Cache塊號塊內(nèi)地址組內(nèi)塊號 (2) Cache地址格式:(1) 主存地址格式:共六十三頁塊號(0塊)塊內(nèi)存儲單元(cn ch dn yun)(0-511)塊號(1塊) 塊內(nèi)存儲單元(cn ch dn yun)( 0-511)0000 0000 001 0 0000 00000000 0000 001 1 1 1 1 1 1 1 1 1塊號(2047塊)塊內(nèi)存儲單元(0-511)1 1 1 1 1 1 1 1 111 0 0000 00001 1 1 1 1 1 1 1 111 1 1 1 1

22、 1 1 1 1 1主存地址格式：0000 0000 000 0 0000 00000000 0000 000 1 1 1 1 1 1 1 1 1組號(0-127)組內(nèi)塊號(0-15)共六十三頁(3) 地址變換(將主存地址(dzh)轉(zhuǎn)換為Cache地址):Cache塊號b組號G(標(biāo)志(biozh)字段)MARCache塊號b塊內(nèi)地址w CAR命中不命中訪問主存塊內(nèi)地址W比較組號GCache地址根據(jù)CAR的內(nèi)容訪問Cache 主存地址中的“組內(nèi)塊號(Cache塊號)+塊內(nèi)地址”= Cache地址注意：在直接映射中,主存組號作為識別是否命中的標(biāo)志，標(biāo)志位的長度由主存組數(shù)決定.共六十三頁3.直接(z

23、hji)映射的優(yōu)缺點：塊內(nèi)地址(dzh)(9位) 組內(nèi)塊號(4位)組號(7位) Cache地址格式塊內(nèi)地址(9位) 塊號(4位)解:(1) 主存地址格式 (1) 分別寫出主存地址格式和Cache地址格式; (2) 畫出直接映射及地址變換圖; (3)主存地址為0022AH的單元在Cache中什么位置?例題:某機(jī)主存容量為1MB, Cache容量為8KB，每塊512B,如果采用直接映射,請回答:(2)缺點:Cache的空間利用率低,塊沖突較多,命中率也低.(1)優(yōu)點:硬件實現(xiàn)簡單,成本低.共六十三頁塊0塊1塊15Cache.0組1組塊 0 塊 1 塊15 塊16塊17 塊31 塊2047塊2032

24、塊2033 127組主存7位4位9位組號G組內(nèi)塊號b塊內(nèi)地址(dzh)主存地址(dzh)比較組號不命中,訪問主存Cache地址01b15(2) 直接映射及地址變換示意圖命中,MARCAR4位9位則根據(jù)CAR的內(nèi)容訪問Cache地址映射地址變換共六十三頁 (3) 主存地址為0022AH的單元在Cache中什么(shn me)位置組(0組)組內(nèi)塊號(1塊)塊內(nèi)地址(dzh)(42字)另外一種求法: 0022AH=(0000 0000 0010 0010 1010)2因為主存第j塊和Cache第i塊有如下函數(shù)關(guān)系: i= j mod m (m為Cache中總塊數(shù))這里,j=1,m=16,所以i=1

25、mod 16=1共六十三頁例:設(shè)一個(y )Cache中有8個塊,訪問主存進(jìn)行讀操作的塊地址序列為22、26、22、26、16、4、16、18,求每次訪問后Cache中的內(nèi)容.解：地址(dzh)命中與否地址轉(zhuǎn)換關(guān)系 不命中 22 MOD 8=6 不命中 26 MOD 8=2 22 命中 22 MOD 8=6 命中 26 MOD 8=216 不命中 16 MOD 8=04 不命中 4 MOD 8=4 16 命中 16 MOD 8=0 18 不命中 18 MOD 8=2 直接映象下Cache訪問情況共六十三頁 直接(zhji)映象的塊分配情況訪問順序 1 2 3 4 5 6 7 8地址(dzh)

26、22 26 22 26 16 4 16 18塊分配 情況 22操作狀態(tài)調(diào)進(jìn)2226調(diào)進(jìn)2226命中2226命中222616調(diào)進(jìn)2241626調(diào)進(jìn)2216264命中2216184替換共六十三頁練習(xí)1. 設(shè)有一個Cache的容量為2K字,每塊16字,在直接映象方式(fngsh)下,求:(1)該Cache可容納多少個塊?(2)如果主存的容量為256K字,則有多少個塊?(3)主存的地址格式? Cache的地址格式?(4) 主存中的第032AB單元映象到Cache中哪一塊?練習(xí)2. 設(shè)計算機(jī)的存儲器為64K16位,直接地址映射的Cache容量為1K字,每塊4字,問: (1) 主存中地址(dzh)的標(biāo)志字

27、段、塊號和塊內(nèi)地址(dzh)字段分別有多少位？ （2）Cache中可裝入多少塊數(shù)據(jù)？共六十三頁三. 組相聯(lián)映射(yngsh)及其地址變換n路組相聯(lián):每組中有n塊.有全相聯(lián)映射:主存第g組第i塊可映射到Cache第i組中任一塊(y kui)的位置. 有直接映射:主存第g組第i塊只能映射到Cache第i組. 1.組相聯(lián)映射:Cache分成大小相等的組,各組再分成大小相等的塊. 主存在分塊的基礎(chǔ)上分組,每組塊數(shù)等于Cache 組數(shù). 映射規(guī)則:Cahe分為m組,每組有n塊,則有以下關(guān)系: i=j mod m 其中,i為Cache組號,j為主存塊號(大排).商為主存第j塊所在組數(shù),余數(shù)為該組所在塊數(shù).

28、 共六十三頁塊0塊1塊2塊3塊14塊15 0組1組7組Cache主存塊0塊1塊2塊3塊7塊8塊15塊16塊17塊2047圖5.30 組相聯(lián)映射(yngsh)示意圖同上例,采用(ciyng)2路組相聯(lián) 塊90組1組共六十三頁 2.組相聯(lián)映射(yngsh)方式下的地址變換塊內(nèi)地址(dzh) (Cache組號)(1) 主存地址格式:(主存字塊標(biāo)記) (2) Cache地址格式:塊內(nèi)地址組號組內(nèi)塊號 組號組內(nèi)塊號共六十三頁(3) 地址變換(將主存地址(dzh)轉(zhuǎn)換為Cache地址):塊內(nèi)地址(dzh)組號組內(nèi)塊號塊內(nèi)地址 (Cache組號)(主存字塊標(biāo)記) 組號組內(nèi)塊號共六十三頁主存字塊(z kui)

29、標(biāo)記組號G塊內(nèi)地址(dzh)WMAR組號g組內(nèi)塊號b塊內(nèi)地址wCAR比較不命中訪問主存命中主存字塊標(biāo)記Cache組內(nèi)塊號b訪問Cache圖5.31 組相聯(lián)映射的地址變換示意圖塊表共六十三頁 例:某計算機(jī)的Cache共有16塊,采用2路組相聯(lián)(即每組2塊).每個主存塊大小為32字節(jié),按字節(jié)編址.主存129號單元(dnyun)所在主存應(yīng)裝入到得Cache組號是( ).A. 0 B.2 C.4 D.6 例:在下列因素中,與Cache的命中率無關(guān)的是( ). A. Cache塊的大小 B. Cache的容量 C. 主存的存取時間共六十三頁 例：假設(shè)主存容量為512K16位,Cache容量為409616

30、位,塊長為4個16位的字,訪存地址為字地址.(1)在直接映射方式下,設(shè)計(shj)主存地址格式.(2)在全相聯(lián)映射方式下,設(shè)計主存地址格式.(3)在2路組相聯(lián)映射方式下,設(shè)計主存地址格式. 解:(1)在直接映射方式下,Cache分4096/4=210塊,主存分219/4=217塊,主存分219/212=27組. 故主存地址格式:主存組數(shù)(7位)組內(nèi)塊數(shù)(10位)塊內(nèi)地址(dzh)(2位)共六十三頁(2)在全相聯(lián)方式(fngsh)下,Cache分4096/4=210塊,主存分219/4=217塊.故主存地址格式:主存塊數(shù)(17位)塊內(nèi)地址(dzh)(2位) (3)在組相聯(lián)映射方式下, Cache

31、分4096/4=210塊,2塊一組,Cache分210/2=29組;主存分219/4=217塊,每組分29塊,主存分217/29=28組.故主存地址格式:塊內(nèi)地址 (Cache組號)(主存字塊標(biāo)記)組號(8位)組內(nèi)塊號(9位) (2位)共六十三頁練習(xí)1. 設(shè)有一個Cache的容量為2K字,每塊16字,在直接映象方式下,求:(1)該Cache可容納多少個塊?(2)如果(rgu)主存的容量為256K字,則有多少個塊?(3)主存的地址格式? Cache的地址格式?(4) 主存中的第032ABH單元映象到Cache中哪一塊? 解:(1) Cache可容納(rngn)的塊數(shù)為:2K/16=27=128(

32、塊)(2) 主存的可容納的塊數(shù)為: 256K/16=214(塊) (3) 主存地址格式為:塊內(nèi)地址(4位) 組內(nèi)塊號(7位)組號(7位) Cache地址格式為:塊內(nèi)地址(4位) 組內(nèi)塊號(7位)共六十三頁(4) 主存中的032ABH單元(dnyun):032ABH=(0000 0011 0010 1010 1011)2 6組 42塊11字另外一種求法:因為主存第j塊和Cache第i塊有如下函數(shù)(hnsh)關(guān)系: i= j mod m (m為Cache中總塊數(shù))這里,j=29+28+25+23+21=810,m=128,所以i=1 mod m=810 mod 128=42 共六十三頁5.5 Ca

33、che存儲器5.5.1 多級存儲(cn ch)體系結(jié)構(gòu)5.5.2 Cache工作(gngzu)原理5.5.3 主存與Cache的地址映射和地址變換5.5.4 Cache的替換策略及寫操作策略共六十三頁5.5.4 Cache的替換(t hun)策略及寫操作策略LRU-Least Recently UsedFIFO-First In First OutRAND 常用(chn yn)替換算法: 注意:只有全相聯(lián)和組相聯(lián)的高速緩存中有替換策略問題. 替換策略(replacement policy): Cache地址變換中一旦發(fā)生不命中,需將主存中一個新塊調(diào)入Cache,如果此時發(fā)生塊沖突, 決定從Ca

34、che中選擇哪一個數(shù)據(jù)塊,并將其從Cache中移去,將新的數(shù)據(jù)塊寫入的方法. 一. Cache的替換策略共六十三頁 1. RAND算法(sun f) 特點:符合(fh)局部性原理,命中率較高. 方法:根據(jù)局部性原理選擇近期用的最少的數(shù)據(jù)塊作為替換的塊.具體做法:為每一塊設(shè)置一個計數(shù)器,當(dāng)某一塊命中時,其計數(shù)器清0,其它各塊的計數(shù)器增1,當(dāng)需要替換時,將計數(shù)值大的塊替換出.3. LRU算法 特點:較簡單,但沒有體現(xiàn)程序局部性規(guī)律,不能提高Cache命中率.方法:選擇最早調(diào)入Cache的塊進(jìn)行替換. 2. FIFO算法 方法:隨機(jī)地確定替換塊.特點:容易實現(xiàn),執(zhí)行速度快,但沒有體現(xiàn)程序局部性規(guī)律,

35、不能提高Cache命中率.共六十三頁二、Cache的寫操作(cozu)策略 Cache內(nèi)容是主存部分內(nèi)容的副本,在命中的情況下,如果CPU對Cache寫入,改變(gibin)了Cache (dirty block)的內(nèi)容,如何保證主存內(nèi)容與Cache內(nèi)容一致.缺點:當(dāng)CPU向主存寫操作時, Cache無高速緩沖功能,降低了Cache的功效. 優(yōu)點:寫主存與寫Cache同步. 1.直達(dá)法(write through)(通過式寫入):每次寫入Cache時同時寫入主存,使主存與Cache相關(guān)塊內(nèi)容始終保持一致.共六十三頁 2. 寫回法(write back)(標(biāo)志交換方式): Cache中每一塊各作一個標(biāo)記(清未修改過;濁修改(xigi)過),命中需將信息寫入主存時,暫只寫入 Cache, 并不寫入主存, 只有當(dāng)該塊需要從Cache中替換出來時,若其標(biāo)記為”濁”,再一次性寫入主存. 缺點:存在(cnzi)Cache與主存數(shù)據(jù)不一致的隱患.優(yōu)點:減少對主存的寫操作次數(shù), 工作速度較快.共六十三頁作業(yè)1:某一Cache-主存采用組相聯(lián)的方法進(jìn)行地址轉(zhuǎn)換. Cache容量為8KB,每組包括4個塊,塊大小為128W.