第六章層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)-3_24

1、第6章 層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)存儲(chǔ)器概述高速緩沖存儲(chǔ)器(cache)層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)層次結(jié)構(gòu)存儲(chǔ)系統(tǒng) 第一講：存儲(chǔ)器概述 第二講：高速緩沖存儲(chǔ)器(cache) - 程序訪問(wèn)的局部性、cache的基本工作原理 - cache行和主存塊之間的映射方式 - cache和程序性能 回顧：程序及指令的執(zhí)行過(guò)程回顧：程序及指令的執(zhí)行過(guò)程 在內(nèi)存存放的指令實(shí)際上是機(jī)器代碼（0/1序列） 08048394 : 1 8048394:55 push%ebp2 8048395:89 e5 mov%esp, %ebp3 8048397:8b 45 0c mov0 xc(%ebp), %eax4 804839a:03 45

2、08 add 0 x8(%ebp), %eax5 804839d:5d pop%ebp6 804839e:c3 ret 對(duì)于add函數(shù)的執(zhí)行，以下情況下都需要訪存：每條指令都需從主存單元取到CPU執(zhí)行PUSH指令需把寄存器內(nèi)容壓入棧中 POP指令則相反第3條mov指令需要從主存中取數(shù)后送到寄存器第4條add指令需要從主存取操作數(shù)到ALU中進(jìn)行運(yùn)算ret指令需要從棧中取出返回地址，以能正確回到調(diào)用程序執(zhí)行棧是主存中的一個(gè)區(qū)域！訪存是指令執(zhí)行過(guò)程中一個(gè)非常重要的環(huán)節(jié)！ 取指、取數(shù)、存數(shù)取指存數(shù)取數(shù)取數(shù)取數(shù)取數(shù)基本術(shù)語(yǔ)基本術(shù)語(yǔ) 記憶單元 （存儲(chǔ)基元 / 存儲(chǔ)元 / 位元） （Cell） 具有兩種穩(wěn)態(tài)

3、的能夠表示二進(jìn)制數(shù)碼0和1的物理器件 存儲(chǔ)單元 / 編址單位（Addressing Unit） 具有相同地址的位構(gòu)成一個(gè)存儲(chǔ)單元，也稱為一個(gè)編址單位 存儲(chǔ)體/ 存儲(chǔ)矩陣 / 存儲(chǔ)陣列（Bank） 所有存儲(chǔ)單元構(gòu)成一個(gè)存儲(chǔ)陣列 編址方式（Addressing Mode） -字節(jié)編址、按字編址 存儲(chǔ)器地址寄存器（Memory Address Register - MAR） 用于存放主存單元地址的寄存器 存儲(chǔ)器數(shù)據(jù)寄存器（ Memory Data Register-MDR (或MBR) ） 用于存放主存單元中的數(shù)據(jù)的寄存器存儲(chǔ)器分類存儲(chǔ)器分類（1）按工作性質(zhì)/存取方式分類 隨機(jī)存取存儲(chǔ)器 Rando

4、m Access Memory (RAM) -每個(gè)單元讀寫(xiě)時(shí)間一樣，且與各單元所在位置無(wú)關(guān)。如：內(nèi)存。（注：原意主要強(qiáng)調(diào)地址譯碼時(shí)間相同?，F(xiàn)在的DRAM芯片采用行緩沖，因而可能因?yàn)槲恢貌煌乖L問(wèn)時(shí)間有所差別。） 順序存取存儲(chǔ)器 Sequential Access Memory (SAM)-數(shù)據(jù)按順序從存儲(chǔ)載體的始端讀出或?qū)懭耄蚨嫒r(shí)間的長(zhǎng)短與信息所在位置有關(guān)。例如：磁帶。 直接存取存儲(chǔ)器 Direct Access Memory(DAM)-直接定位到讀寫(xiě)數(shù)據(jù)塊，在讀寫(xiě)數(shù)據(jù)塊時(shí)按順序進(jìn)行。如磁盤(pán)。 相聯(lián)存儲(chǔ)器 Associate Memory（AM） Content Addressed M

5、emory (CAM)-按內(nèi)容檢索到存儲(chǔ)位置進(jìn)行讀寫(xiě)。例如：快表。依據(jù)不同的特性有多種分類方法存儲(chǔ)器分類存儲(chǔ)器分類（2）按存儲(chǔ)介質(zhì)分類 半導(dǎo)體存儲(chǔ)器：雙極型，靜態(tài)MOS型，動(dòng)態(tài)MOS型 磁表面存儲(chǔ)器：磁盤(pán)（Disk）、磁帶 （Tape） 光存儲(chǔ)器：CD，CD-ROM，DVD（3）按信息的可更改性分類 讀寫(xiě)存儲(chǔ)器（Read / Write Memory)：可讀可寫(xiě) 只讀存儲(chǔ)器（Read Only Memory)：只能讀不能寫(xiě)（4）按斷電后信息的可保存性分類 非易失（不揮發(fā)）性存儲(chǔ)器(Nonvolatile Memory) 信息可一直保留， 不需電源維持。 （如 ：ROM、磁表面存儲(chǔ)器、光存儲(chǔ)器等

6、） 易失（揮發(fā)）性存儲(chǔ)器(Volatile Memory) 電源關(guān)閉時(shí)信息自動(dòng)丟失。（如：RAM、Cache等）存儲(chǔ)器分類存儲(chǔ)器分類（5）按功能/容量/速度/所在位置分類 寄存器(Register)-封裝在CPU內(nèi)，用于存放當(dāng)前正在執(zhí)行的指令和使用的數(shù)據(jù)-用觸發(fā)器實(shí)現(xiàn)，速度快，容量?。◣讕资畟€(gè)） 高速緩存(Cache)-位于CPU內(nèi)部或附近，用來(lái)存放當(dāng)前要執(zhí)行的局部程序段和數(shù)據(jù)-用SRAM實(shí)現(xiàn)，速度可與CPU匹配，容量?。◣譓B） 內(nèi)存儲(chǔ)器MM（主存儲(chǔ)器Main (Primary) Memory）-位于CPU之外，用來(lái)存放已被啟動(dòng)的程序及所用的數(shù)據(jù)-用DRAM實(shí)現(xiàn)，速度較快，容量較大（幾GB）

7、 外存儲(chǔ)器AM (輔助存儲(chǔ)器Auxiliary / Secondary Storage)-位于主機(jī)之外，用來(lái)存放暫不運(yùn)行的程序、數(shù)據(jù)或存檔文件-用磁表面或光存儲(chǔ)器實(shí)現(xiàn)，容量大而速度慢內(nèi)存與外存的關(guān)系及比較內(nèi)存與外存的關(guān)系及比較 內(nèi)存儲(chǔ)器（簡(jiǎn)稱內(nèi)存或主存） 存取速度快 成本高、容量相對(duì)較小 直接與CPU連接，CPU對(duì)內(nèi)存中可直接進(jìn)行讀、寫(xiě)操作 屬于易失性存儲(chǔ)器(volatile)，用于臨時(shí)存放正在運(yùn)行的程序和數(shù)據(jù)內(nèi)存儲(chǔ)器外存儲(chǔ)器外存儲(chǔ)器CPU指令指令1指令指令2指令指令k指令指令n程序數(shù)據(jù)數(shù)據(jù)1數(shù)據(jù)數(shù)據(jù)2數(shù)據(jù)數(shù)據(jù)m數(shù)據(jù)數(shù)據(jù)程序和數(shù)據(jù)從外存成批傳送到內(nèi)存CPU從內(nèi)存中逐條讀取指令及相關(guān)數(shù)據(jù)將指令處

8、理結(jié)果送回內(nèi)存保存將處理結(jié)果成批傳送到外存以長(zhǎng)久保存 逐 條 執(zhí)行 指 令 ，按 指 令 要求 完 成 對(duì)數(shù) 據(jù) 的 運(yùn)算和處理 外存儲(chǔ)器（簡(jiǎn)稱外存或輔存） 存取速度慢 成本低、容量很大 不與CPU直接連接，先傳送到內(nèi)存，然后才能被CPU使用。 屬于非易失性存儲(chǔ)器，用于長(zhǎng)久存放系統(tǒng)中幾乎所有的信息地址寄存器地址譯碼器讀寫(xiě)控制電路控制線讀/寫(xiě)控制信號(hào)記憶單元數(shù)據(jù)線讀/寫(xiě)的數(shù)據(jù)(64位位)主存地址地址線(36位位)0110100110101010存儲(chǔ)內(nèi)容00001000000001000011001001111011111存儲(chǔ)單元地址MDRMARCPUMM主存的結(jié)構(gòu)主存的結(jié)構(gòu)問(wèn)題：主存中存放的是什

9、么信息？CPU何時(shí)會(huì)訪問(wèn)主存？指令及其數(shù)據(jù)！CPU執(zhí)行指令時(shí)需要取指令、取數(shù)據(jù)、存數(shù)據(jù)！問(wèn)題：地址譯碼器的輸入是什么？輸出是什么？可尋址范圍多少？輸入是地址，輸出是地址驅(qū)動(dòng)信號(hào)（只有一根地址驅(qū)動(dòng)線被選中）。可尋址范圍為0236-1，即主存地址空間為64GB（按字節(jié)編址時(shí)）。內(nèi)存儲(chǔ)器的分類及應(yīng)用內(nèi)存儲(chǔ)器的分類及應(yīng)用 內(nèi)存由半導(dǎo)體存儲(chǔ)器芯片組成，芯片有多種類型：半導(dǎo)體存儲(chǔ)器只讀存儲(chǔ)器(ROM)隨機(jī)存取存儲(chǔ)器(RAM)靜態(tài)存儲(chǔ)器SRAM動(dòng)態(tài)存儲(chǔ)器DRAM 不可在線改寫(xiě)內(nèi)容的ROM閃存（Flash ROM）（用作（用作Cache） （用作主存儲(chǔ)器）（用作主存儲(chǔ)器） 每個(gè)存儲(chǔ)單元(cell)由6個(gè)晶體管

10、組成 只要加上電源，信息就能一直保持 對(duì)電器干擾相對(duì)不很敏感 比DRAM更快，也更貴 每個(gè)存儲(chǔ)單元由1個(gè)電容和1個(gè)晶體管組成 每隔一段時(shí)間必須刷新一次 對(duì)電器干擾比較敏感 比SRAM慢，但便宜（用作（用作BIOS）DRAM As Main Memory (*) Cell structureTo store a bit, the word line is set high, and the value to be stored is put on the bit line, and then the word line is set low. If the stored bit is a 1,

11、then a charge will be stored on capacitor Cbit. To read a bit, the bit line is set high, and then isolated leaving a charge on the line. The word line is set high then low. If the stored value was a 1, then the charge on the bit line and capacitor Cbit will be (more or less) equal, meaning the charg

12、e on the bit line will be basically unchanged. However, if the stored value was a 0, then a proportion of the charge on the bit line will charge up Cbit meaning there will be a small, and detectable, drop in the charge on the bit line. Specialized hardware (sense amplifiers) are needed to detect the

13、 change.層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)層次結(jié)構(gòu)存儲(chǔ)系統(tǒng) 第一講：存儲(chǔ)器概述 第二講：高速緩沖存儲(chǔ)器(cache) - 程序訪問(wèn)的局部性、cache的基本工作原理 - cache行和主存塊之間的映射方式 - cache和程序性能 希望的理想存儲(chǔ)器希望的理想存儲(chǔ)器到目前為止，已經(jīng)了解到有以下幾種存儲(chǔ)器：寄存器，SRAM，DRAM， 硬盤(pán)單獨(dú)用某一種存儲(chǔ)器，都不能滿足我們的需要！采用分層存儲(chǔ)結(jié)構(gòu)來(lái)構(gòu)建計(jì)算機(jī)的存儲(chǔ)體系！1ns2ns10ns10ms1KB1MB1GB1000GB100GB1ns問(wèn)題：你認(rèn)為哪一種最適合做計(jì)算機(jī)的存儲(chǔ)器呢？存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)cache主存主存(RAM和和ROM)

14、外存儲(chǔ)器（硬盤(pán)、光盤(pán)）外存儲(chǔ)器（硬盤(pán)、光盤(pán)）后備存儲(chǔ)器（磁帶庫(kù)、光盤(pán)庫(kù)）后備存儲(chǔ)器（磁帶庫(kù)、光盤(pán)庫(kù)）內(nèi)內(nèi)部部存存儲(chǔ)儲(chǔ)器器外部存儲(chǔ)器外部存儲(chǔ)器寄存器寄存器典型容量典型容量1KB1MB256MB1GB40GB200GB10TB100TB典型存取時(shí)間典型存取時(shí)間1ns(0.51cycles)2ns(13cycles)10ns(10100cycles)10ms(107108cycles)10s(脫機(jī)脫機(jī))列出的時(shí)間和容量會(huì)隨時(shí)間變化，但數(shù)量級(jí)相對(duì)關(guān)系不變。列出的時(shí)間和容量會(huì)隨時(shí)間變化，但數(shù)量級(jí)相對(duì)關(guān)系不變。層次化存儲(chǔ)器結(jié)構(gòu)（層次化存儲(chǔ)器結(jié)構(gòu)（Memory Hierarchy） 時(shí)間局部性（Tempor

15、al Locality） 含義：剛被訪問(wèn)過(guò)的單元很可能不久又被訪問(wèn)做法：讓最近被訪問(wèn)過(guò)的信息保留在靠近CPU的存儲(chǔ)器中 空間局部性 （Spatial Locality） 含義：剛被訪問(wèn)過(guò)的單元的鄰近單元很可能不久被訪問(wèn)做法：將剛被訪問(wèn)過(guò)的單元的鄰近單元調(diào)到靠近CPU的存儲(chǔ)器中 Lower LevelMemoryUpper LevelMemoryTo CPUFrom CPUBlock XBlock Y數(shù)據(jù)總是在相鄰兩層之間復(fù)制傳送 Upper Level: 上層更靠CPU Lower Level: 下層更遠(yuǎn)離CPUBlock: 最小傳送單位是定長(zhǎng)塊，互為副本問(wèn)題：為什么這種層次化結(jié)構(gòu)是有效的？相

16、當(dāng)于工廠中設(shè)置了多級(jí)倉(cāng)庫(kù)！相當(dāng)于工廠中設(shè)置了多級(jí)倉(cāng)庫(kù)！程序訪問(wèn)局部化特點(diǎn)！例如，寫(xiě)論文時(shí)圖書(shū)館借參考書(shū)：欲借書(shū)附近的書(shū)也是欲借書(shū)！加快訪存速度措施：引入加快訪存速度措施：引入Cache 大量典型程序的運(yùn)行情況分析結(jié)果表明 在較短時(shí)間間隔內(nèi)，程序產(chǎn)生的地址往往集中在一個(gè)很小范圍內(nèi)這種現(xiàn)象稱為程序訪問(wèn)的局部性：空間局部性、時(shí)間局部性 程序具有訪問(wèn)局部性特征的原因 指令：指令按序存放，地址連續(xù)，循環(huán)程序段或子程序段重復(fù)執(zhí)行 數(shù)據(jù)：連續(xù)存放，數(shù)組元素重復(fù)、按序訪問(wèn) 為什么引入Cache會(huì)加快訪存速度？ 在CPU和主存之間設(shè)置一個(gè)快速小容量的存儲(chǔ)器，其中總是存放最活躍（被頻繁訪問(wèn)）的程序和數(shù)據(jù)，由于程序

17、訪問(wèn)的局部性特征，大多數(shù)情況下，CPU能直接從這個(gè)高速緩存中取得指令和數(shù)據(jù)，而不必訪問(wèn)主存。這個(gè)高速緩存就是位于主存和這個(gè)高速緩存就是位于主存和CPU之間的之間的Cache！程序的局部性原理舉例程序的局部性原理舉例1sum = 0;for (i = 0; i n; i+)sum += ai;*v = sum;每條指令4個(gè)字節(jié)；每個(gè)數(shù)組元素4字節(jié)指令和數(shù)組元素在內(nèi)存中均連續(xù)存放sum, ap ,i, t 均為通用寄存器；A，V為內(nèi)存地址I0:sum - 0I1:ap - A A是數(shù)組是數(shù)組a的起始地址的起始地址I2:i = n) goto doneI4:loop: t - (ap) 數(shù)組元素?cái)?shù)組

18、元素ai的值的值 I5:sum - sum + t 累計(jì)在累計(jì)在sum中中I6:ap - ap + 4 計(jì)算下個(gè)數(shù)組元素地址計(jì)算下個(gè)數(shù)組元素地址I7:i - i + 1 I8:if (i n) goto loopI9:done: V - sum 累計(jì)結(jié)果保存至地址累計(jì)結(jié)果保存至地址vI1I2I3I4I5I60 x1000 x1040 x1080 x10C0 x1100 x114a0a1a2a3a4a50 x4000 x4040 x4080 x40C0 x4100 x414 0 x7A4 主存的布局主存的布局:I00 x0FC指指 令令 數(shù)數(shù) 據(jù)據(jù)AV高級(jí)語(yǔ)言源程序高級(jí)語(yǔ)言源程序?qū)?yīng)的匯編語(yǔ)言程

19、序?qū)?yīng)的匯編語(yǔ)言程序程序的局部性原理舉例程序的局部性原理舉例1sum = 0;for (i = 0; i n; i+)sum += ai;*v = sum;問(wèn)題：指令和數(shù)據(jù)的時(shí)間局部性和空間局部性 各自體現(xiàn)在哪里？指令：指令： 0 x0FC（I0） 0 x108（I3） 0 x10C（I4） 0 x11C（I8） 0 x120（I9） 數(shù)據(jù)：只有數(shù)組在主存中：數(shù)據(jù)：只有數(shù)組在主存中： 0 x4000 x4040 x408 0 x40C0 x7A4 I1I2I3I4I5I60 x1000 x1040 x1080 x10C0 x1100 x114a0a1a2a3a4a50 x4000 x4040

20、x4080 x40C0 x4100 x414 0 x7A4 主存的布局主存的布局: :I00 x0FC指指 令令 數(shù)數(shù) 據(jù)據(jù)AV若n足夠大，則在一段時(shí)間內(nèi)一直在局部區(qū)域內(nèi)執(zhí)行指令，故循環(huán)內(nèi)指令的時(shí)間局部性好；按順序執(zhí)行，故程序空間局部性好！數(shù)組元素按順序存放，按順序訪問(wèn)，故空間局部性好；每個(gè)數(shù)組元素都只被訪問(wèn)1次，故沒(méi)有時(shí)間局部性。循環(huán)循環(huán)n次次程序的局部性原理舉例程序的局部性原理舉例2 以下哪個(gè)對(duì)數(shù)組a引用的空間局部性更好？時(shí)間局部性呢？變量sum的空間局部性和時(shí)間局部性如何？對(duì)于指令來(lái)說(shuō)，for循環(huán)體的空間局部性和時(shí)間局部性如何？數(shù)組在存儲(chǔ)器中按行優(yōu)先順序存放程序段程序段B: int su

21、marraycols(int aMN) int i, j, sum=0; for (j=0; jN, j+) for (i=0; iM, i+) sum+=aij; return sum; 程序段程序段A: int sumarrayrows(int aMN) int i, j, sum=0; for (i=0; iM, i+)for (j=0; jN, j+) sum+=aij; return sum; M=N=2048時(shí)主存的布局時(shí)主存的布局:0 x1000 x17C0 x1800 x1840 x4000 x4040 xc000 xc040 x0FC指指 令令 數(shù)數(shù) 據(jù)據(jù)asumI34I35

22、a00a01 a02047a10a11 I1I2I33 for循環(huán)體程序的局部性原理舉例程序的局部性原理舉例2程序段A的時(shí)間局部性和空間局部性分析（1）數(shù)組a：訪問(wèn)順序?yàn)閍00, a01 , a02047; a10, a11, ,a12047; ，與存放順序一致，故空間局部性好！ 因?yàn)槊總€(gè)aij只被訪問(wèn)一次，故時(shí)間局部性差！ （2）變量sum：?jiǎn)蝹€(gè)變量不考慮空間局部性；每次循環(huán)都要訪問(wèn)sum，所以其時(shí)間局部性較好?。?） for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！ 循環(huán)體被連續(xù)重復(fù)執(zhí)行2048x2048次，所以時(shí)間局部性好！0 x1000 x17C0 x1800 x1840 x

23、4000 x4040 xc000 xc040 x0FC指指 令令 數(shù)數(shù) 據(jù)據(jù)asumI34I35a00a01 a02047a10a11 I1I2I33 for循環(huán)體循環(huán)體實(shí)際上 優(yōu)化的編譯器使循環(huán)中的sum分配在寄存器中，最后才寫(xiě)回存儲(chǔ)器！程序的局部性原理舉例程序的局部性原理舉例2程序段B的時(shí)間局部性和空間局部性分析（1）數(shù)組a：訪問(wèn)順序?yàn)閍00, a10 , a20470; a01, a11, ,a20471;，與存放順序不一致，每次跳過(guò)2048個(gè)單元，若交換單位小于2KB，則沒(méi)有空間局部性！ （時(shí)間局部性差，同程序A） （2）變量sum：（同程序A ）（3） for循環(huán)體：（同程序A）0

24、x1000 x17C0 x1800 x1840 x4000 x4040 xc000 xc040 x0FC指指 令令 數(shù)數(shù) 據(jù)據(jù)asumI34I35a00a01 a02047a10a11 I1I2I33 for循環(huán)體循環(huán)體實(shí)際運(yùn)行結(jié)果(2GHz Intel Pentium 4):程序A：59,393,288 時(shí)鐘周期程序B：1,277,877,876 時(shí)鐘周期程序A比程序B快21.5 倍!Cache(高速緩存高速緩存)是什么樣的？是什么樣的？ Cache是一種小容量高速緩沖存儲(chǔ)器，它由SRAM組成。 Cache直接制作在CPU芯片內(nèi)，速度幾乎與CPU一樣快。 程序運(yùn)行時(shí)，CPU使用的一部分?jǐn)?shù)據(jù)/

25、指令會(huì)預(yù)先成批拷貝在Cache中，Cache的內(nèi)容是主存儲(chǔ)器中部分內(nèi)容的映象。 當(dāng)CPU需要從內(nèi)存讀(寫(xiě))數(shù)據(jù)或指令時(shí)，先檢查Cache，若有，就直接從Cache中讀取，而不用訪問(wèn)主存儲(chǔ)器。012345678910111213141589143444101010主存中的信主存中的信息按息按“塊塊”送到送到Cache中中Cache存儲(chǔ)器存儲(chǔ)器主存儲(chǔ)器主存儲(chǔ)器數(shù)據(jù)訪問(wèn)過(guò)程：數(shù)據(jù)訪問(wèn)過(guò)程：塊（Block）Cache 的操作過(guò)程的操作過(guò)程若被訪問(wèn)信息不在cache中，稱為缺失或失靶(miss)若被訪問(wèn)信息在cache中，稱為命中(hit)問(wèn)題：什么情況下，CPU產(chǎn)生訪存要求？執(zhí)行指令時(shí)！Cache（高

26、速緩存）的實(shí)現(xiàn)（高速緩存）的實(shí)現(xiàn)問(wèn)題：要實(shí)現(xiàn)Cache機(jī)制需要解決哪些問(wèn)題？如何分塊？主存塊和Cache之間如何映射?Cache已滿時(shí)，怎么辦？寫(xiě)數(shù)據(jù)時(shí)怎樣保證Cache和MM的一致性？如何根據(jù)主存地址訪問(wèn)到cache中的數(shù)據(jù)？問(wèn)題：Cache對(duì)程序員(編譯器)是否透明？為什么？是透明的，程序員是透明的，程序員(編譯器編譯器)在編寫(xiě)在編寫(xiě)/生成高級(jí)或低級(jí)語(yǔ)言程序時(shí)無(wú)生成高級(jí)或低級(jí)語(yǔ)言程序時(shí)無(wú)需了解需了解Cache是否存在或如何設(shè)置，感覺(jué)不到是否存在或如何設(shè)置，感覺(jué)不到cache的存在。的存在。但是，對(duì)但是，對(duì)Cache深入了解有助于編寫(xiě)出高效的程序！深入了解有助于編寫(xiě)出高效的程序！主存被分成若

27、干大小相同的塊，稱為主存塊(Block)，Cache也被分成相同大小的塊，稱為Cache行（line）或槽（Slot）。Cache映射映射(Cache Mapping) 什么是Cache的映射功能？ 把訪問(wèn)的局部主存區(qū)域取到Cache中時(shí)，該放到Cache的何處？ Cache槽比主存塊少，多個(gè)主存塊映射到一個(gè)Cache槽中 如何進(jìn)行映射？ 把主存空間劃分成大小相等的主存塊（Block） Cache中存放一個(gè)主存塊的對(duì)應(yīng)單位稱為槽（Slot）或行（line） 有書(shū)中也稱之為塊（Block） 將主存塊和Cache行按照以下三種方式進(jìn)行映射-直接(Direct)：每個(gè)主存塊映射到Cache的固定行-

28、全相聯(lián)(Full Associate)：每個(gè)主存塊映射到Cache的任一行-組相聯(lián)(Set Associate)：每個(gè)主存塊映射到Cache固定組中任一行 The Simplest Cache: Direct Mapped Cache Direct Mapped Cache（直接映射Cache舉例) 把主存的每一塊映射到一個(gè)固定的Cache行（槽） 也稱模映射(Module Mapping) 映射關(guān)系為： Cache行號(hào)=主存塊號(hào) mod Cache行數(shù) 舉例：4=100 mod 16 （假定Cache共有16行） (說(shuō)明：主存第100塊應(yīng)映射到Cache的第4行中。)u特點(diǎn)： 容易實(shí)現(xiàn)，命中

29、時(shí)間短 但不夠靈活，Cache存儲(chǔ)空間得不到充分利用，命中率低 例如，需將主存第0塊與第16塊同時(shí)復(fù)制到Cache中時(shí)，由于它們都只能復(fù)制到Cache第0行，即使Cache其它行空閑，也有一個(gè)主存塊不能寫(xiě)入Cache。這樣就會(huì)產(chǎn)生頻繁的 Cache裝入。SKIP塊（行）都從塊（行）都從0開(kāi)始編號(hào)開(kāi)始編號(hào)直接映射直接映射Cache組織示意圖組織示意圖假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大小：213字=8K字=16行 x 512字/ 行 主存大?。?20字=1024K字=2048塊 x 512字/ 塊Cache標(biāo)記標(biāo)記(tag)指出對(duì)應(yīng)行取自指出對(duì)應(yīng)行取自哪個(gè)主存塊群哪個(gè)主

30、存塊群指出對(duì)應(yīng)地址位指出對(duì)應(yīng)地址位于哪個(gè)塊群于哪個(gè)塊群例：如何對(duì)例：如何對(duì)0220CH單元進(jìn)單元進(jìn)行訪問(wèn)？行訪問(wèn)？0220CH0000 0010 0010 0000 1100B 是第是第1塊群中的塊群中的0001塊塊（即第（即第17塊）中第塊）中第12個(gè)單元！個(gè)單元！0000001Cache索引索引有效位（有效位（Valid Bit） V為有效位，為1表示信息有效，為0表示信息無(wú)效 開(kāi)機(jī)或復(fù)位時(shí)，使所有行的有效位V=0 某行被替換后使其V=1 某行裝入新塊時(shí) 使其V=1為何要用有效位來(lái)為何要用有效位來(lái)區(qū)分是否有效？區(qū)分是否有效？64 KB Direct Mapped Cache with 16

31、B Blocks 主存和主存和Cache之間直接映射，塊大小為之間直接映射，塊大小為16B。Cache的數(shù)據(jù)區(qū)容量為的數(shù)據(jù)區(qū)容量為64KB，主存地址為主存地址為32位，按字節(jié)編址。要求：說(shuō)明主存地址如何劃分和訪存過(guò)程。位，按字節(jié)編址。要求：說(shuō)明主存地址如何劃分和訪存過(guò)程。 1612Byte offsetVtag163212832323223231 DataWord20ByteBlock offsetMemory AddressTagIndexMUX4Klines=Mux16dataHit 問(wèn)題：?jiǎn)栴}：Cache有多有多少行？容量多大？少行？容量多大？容量容量 4Kx(1+16)+64Kx8=5

32、80Kbits=72.5KB, 數(shù)據(jù)占數(shù)據(jù)占64KB / 72.5KB = 88.3% 64KB16B=4K行行如何計(jì)算如何計(jì)算Cache的容量？的容量？Consider a cache with 64 Lines and a block size of 16 bytes. What line number does byte address 1200 map to?地址地址1200對(duì)應(yīng)存放在第對(duì)應(yīng)存放在第11行。因?yàn)椋盒?。因?yàn)椋?1200/16=75 module 64 = 11實(shí)現(xiàn)以下實(shí)現(xiàn)以下cache需要多少位容量？需要多少位容量？Cache：直接映射：直接映射 、16K行數(shù)據(jù)、塊大小為

33、行數(shù)據(jù)、塊大小為1個(gè)字個(gè)字(4B)、32位主存地址位主存地址 答：答：Cache的存儲(chǔ)布局如下：的存儲(chǔ)布局如下：所以，所以，Cache的大小為：的大小為：214 (32 + (32-14-2)+1) = 21449 = 784 Kbits32 14 2 322141若塊大小為若塊大小為4 4個(gè)字呢？個(gè)字呢？ 214 (432 + (32-14-2-2)+1) = 214143 = 2288 KbitsCache共有共有16K x 4B= 64KB數(shù)據(jù)數(shù)據(jù)若塊大小為若塊大小為2m個(gè)字呢？個(gè)字呢？214 (2m32 + (32-14-2- m)+1) BACK1200 = 1024+128+32+

34、16 = 001 001011 0000 B 全相聯(lián)映射全相聯(lián)映射Cache組織示意圖組織示意圖Cache標(biāo)記（標(biāo)記（tag）指出）指出對(duì)應(yīng)行取自哪個(gè)主存塊對(duì)應(yīng)行取自哪個(gè)主存塊主存主存tag指出對(duì)應(yīng)地址位指出對(duì)應(yīng)地址位于哪個(gè)主存塊于哪個(gè)主存塊如何對(duì)如何對(duì)01E0CH單元單元進(jìn)行訪問(wèn)？進(jìn)行訪問(wèn)？0000 0001 1110 0000 1100B 是第是第15塊中的第塊中的第12個(gè)單元！個(gè)單元！每個(gè)主存塊可裝到每個(gè)主存塊可裝到Cache任一行中。任一行中。假定數(shù)據(jù)在主存假定數(shù)據(jù)在主存和和Cache間的傳間的傳送單位為送單位為512字。字。Cache大?。捍笮。?13字字=8K字字=16行行 x 5

35、12字字/ 行行 主存大?。褐鞔娲笮。?20字字=1024K字字=2048塊塊 x 512字字/ 塊塊0000 0001 111為何地址中沒(méi)有為何地址中沒(méi)有cache索引字段？索引字段？因?yàn)榭捎成涞饺我庖粋€(gè)因?yàn)榭捎成涞饺我庖粋€(gè)cache行中！行中！舉例：舉例：Fully Associative Example: 32bits memory address, 32 B blocks. 比較器位數(shù)多長(zhǎng)？比較器位數(shù)多長(zhǎng)？ we need N 27-bit comparators0431: Cache DataB 0:Cache Tag (27 bits long) V:B 1B 31:B 32B33B 63: Cache TagByte SelectEx: 0 x01=:問(wèn)題：需要多少個(gè)比較器？問(wèn)題：需要多少個(gè)比較器？每行一個(gè)比較器