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

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

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

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

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

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

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

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

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

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

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

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

12、he地址寄存器替換控制部件ABDB單字寬多字寬不命中命中(塊) Cache包括Cache存儲(chǔ)器及相應(yīng)控制部件,全部由硬件組成,速度快,對(duì)所有程序員均透明.CAR共六十三頁(yè) Cache命中率 設(shè)Nc為Cache 完成(wn chng)存取的總次數(shù),Nm為主存完成存取的總次數(shù),h為命中率,則有: 設(shè)r=tm/tc表示主存慢于Cache的倍率,e表示訪問(wèn)(fngwn)效率,則有: 高速緩存命中率:CPU訪存時(shí),信息恰巧在Cache中的概率.h=Nc/(Nc+Nm) 若tc表示命中時(shí)的Cache訪問(wèn)時(shí)間,tm表示未命中時(shí)的主存訪問(wèn)時(shí)間,1-h表示未命中率,則Cache /主存系統(tǒng)的平均訪問(wèn)時(shí)間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共六十三頁(yè)例：CPU執(zhí)行一段程序時(shí),Cache完成(wn chng)存取的次數(shù)1900次,主存完成存取的次數(shù)為100次,已知Cache的存取周期為1ns,主存存取周期為5ns,求Cache/主存系統(tǒng)的效率和平均訪問(wèn)時(shí)間.解：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ì)算機(jī)的存儲(chǔ)系統(tǒng)由Cache和主

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

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

16、射(mapping):把存放在主存中的程序按某種規(guī)則裝入Cache中,并依此建立主存地址與Cache地址的對(duì)應(yīng)關(guān)系,即塊表. 塊表存放數(shù)據(jù)或指令在內(nèi)存中所在單元地址的存儲(chǔ)器,用于判斷Cache命中以及實(shí)現(xiàn)地址映射,其字?jǐn)?shù)等于Cache的塊數(shù).共六十三頁(yè)塊0 塊1塊15塊0塊1塊2047Cache主存全相聯(lián)映射(yngsh) 2.全相聯(lián)映射(yngsh)方式下的地址變換主存塊號(hào)塊內(nèi)地址 (1) 主存地址格式: (標(biāo)志字段)圖5.26 全相聯(lián)映射示意圖共六十三頁(yè)例:某機(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塊號(hào)(0塊)塊內(nèi)存儲(chǔ)單元(cn ch dn yun)(0-511)塊號(hào)(1塊) 塊內(nèi)存儲(chǔ)單元( 0-511)0000 0000 001 0 0000 00000000 0000 001 1 1 1 1 1 1 1 1 1塊號(hào)(2047塊)塊內(nèi)存儲(chǔ)單元(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共六十三頁(yè)Cache塊號(hào)塊內(nèi)地址(dzh) 主存塊號(hào)轉(zhuǎn)換(zhunh

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

19、存塊號(hào)BCache塊號(hào)bBb比較命中MARCAR 圖5.27 全相聯(lián)映射的地址變換塊表(塊表容量的計(jì)算：字?jǐn)?shù)等于高緩塊數(shù)，字長(zhǎng)由主存塊數(shù)和高緩塊數(shù)決定)不命中則訪問(wèn)主存注意:在全相聯(lián)映射中,主存塊號(hào)作為識(shí)別是否命中的標(biāo)志,標(biāo)志位的長(zhǎng)度由主存塊數(shù)決定.共六十三頁(yè)字塊(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)映射的另一種常見(jiàn)圖解共六十三頁(yè) 3.全相聯(lián)映射(yngsh)的優(yōu)缺點(diǎn) i= j mod m

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

21、 直接(zhji)映射示意圖2.直接(zhji)聯(lián)映射方式下的地址變換 Cache塊號(hào) 組號(hào)塊內(nèi)地址Cache塊號(hào)塊內(nèi)地址組內(nèi)塊號(hào) (2) Cache地址格式:(1) 主存地址格式:共六十三頁(yè)塊號(hào)(0塊)塊內(nèi)存儲(chǔ)單元(cn ch dn yun)(0-511)塊號(hào)(1塊) 塊內(nèi)存儲(chǔ)單元(cn ch dn yun)( 0-511)0000 0000 001 0 0000 00000000 0000 001 1 1 1 1 1 1 1 1 1塊號(hào)(2047塊)塊內(nèi)存儲(chǔ)單元(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組號(hào)(0-127)組內(nèi)塊號(hào)(0-15)共六十三頁(yè)(3) 地址變換(將主存地址(dzh)轉(zhuǎn)換為Cache地址):Cache塊號(hào)b組號(hào)G(標(biāo)志(biozh)字段)MARCache塊號(hào)b塊內(nèi)地址w CAR命中不命中訪問(wèn)主存塊內(nèi)地址W比較組號(hào)GCache地址根據(jù)CAR的內(nèi)容訪問(wèn)Cache 主存地址中的“組內(nèi)塊號(hào)(Cache塊號(hào))+塊內(nèi)地址”= Cache地址注意：在直接映射中,主存組號(hào)作為識(shí)別是否命中的標(biāo)志，標(biāo)志位的長(zhǎng)度由主存組數(shù)決定.共六十三頁(yè)3.直接(z

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

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

25、mod 16=1共六十三頁(yè)例:設(shè)一個(gè)(y )Cache中有8個(gè)塊,訪問(wèn)主存進(jìn)行讀操作的塊地址序列為22、26、22、26、16、4、16、18,求每次訪問(wèn)后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訪問(wèn)情況共六十三頁(yè) 直接(zhji)映象的塊分配情況訪問(wèn)順序 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替換共六十三頁(yè)練習(xí)1. 設(shè)有一個(gè)Cache的容量為2K字,每塊16字,在直接映象方式(fngsh)下,求:(1)該Cache可容納多少個(gè)塊?(2)如果主存的容量為256K字,則有多少個(gè)塊?(3)主存的地址格式? Cache的地址格式?(4) 主存中的第032AB單元映象到Cache中哪一塊?練習(xí)2. 設(shè)計(jì)算機(jī)的存儲(chǔ)器為64K16位,直接地址映射的Cache容量為1K字,每塊4字,問(wèn): (1) 主存中地址(dzh)的標(biāo)志字

27、段、塊號(hào)和塊內(nèi)地址(dzh)字段分別有多少位？ （2）Cache中可裝入多少塊數(shù)據(jù)？共六十三頁(yè)三. 組相聯(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組號(hào),j為主存塊號(hào)(大排).商為主存第j塊所在組數(shù),余數(shù)為該組所在塊數(shù).

28、 共六十三頁(yè)塊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組共六十三頁(yè) 2.組相聯(lián)映射(yngsh)方式下的地址變換塊內(nèi)地址(dzh) (Cache組號(hào))(1) 主存地址格式:(主存字塊標(biāo)記) (2) Cache地址格式:塊內(nèi)地址組號(hào)組內(nèi)塊號(hào) 組號(hào)組內(nèi)塊號(hào)共六十三頁(yè)(3) 地址變換(將主存地址(dzh)轉(zhuǎn)換為Cache地址):塊內(nèi)地址(dzh)組號(hào)組內(nèi)塊號(hào)塊內(nèi)地址 (Cache組號(hào))(主存字塊標(biāo)記) 組號(hào)組內(nèi)塊號(hào)共六十三頁(yè)主存字塊(z kui)

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

30、位,塊長(zhǎng)為4個(gè)16位的字,訪存地址為字地址.(1)在直接映射方式下,設(shè)計(jì)(shj)主存地址格式.(2)在全相聯(lián)映射方式下,設(shè)計(jì)主存地址格式.(3)在2路組相聯(lián)映射方式下,設(shè)計(jì)主存地址格式. 解:(1)在直接映射方式下,Cache分4096/4=210塊,主存分219/4=217塊,主存分219/212=27組. 故主存地址格式:主存組數(shù)(7位)組內(nèi)塊數(shù)(10位)塊內(nèi)地址(dzh)(2位)共六十三頁(yè)(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組號(hào))(主存字塊標(biāo)記)組號(hào)(8位)組內(nèi)塊號(hào)(9位) (2位)共六十三頁(yè)練習(xí)1. 設(shè)有一個(gè)Cache的容量為2K字,每塊16字,在直接映象方式下,求:(1)該Cache可容納多少個(gè)塊?(2)如果(rgu)主存的容量為256K字,則有多少個(gè)塊?(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)塊號(hào)(7位)組號(hào)(7位) Cache地址格式為:塊內(nèi)地址(4位) 組內(nèi)塊號(hào)(7位)共六十三頁(yè)(4) 主存中的032ABH單元(dnyun):032ABH=(0000 0011 0010 1010 1011)2 6組 42塊11字另外一種求法:因?yàn)橹鞔娴趈塊和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 共六十三頁(yè)5.5 Ca

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

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

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