計(jì)算機(jī)組成原理chap課件

1、第四章 存儲(chǔ)系統(tǒng)南京大學(xué)計(jì)算機(jī)系多媒體技術(shù)研究所袁春風(fēng)1第四章 內(nèi)部存儲(chǔ)器存儲(chǔ)器的基本概念半導(dǎo)體存儲(chǔ)器多模塊存儲(chǔ)器高速緩沖存儲(chǔ)器輔助(外部)存儲(chǔ)器虛擬存儲(chǔ)器2南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1 存儲(chǔ)器的基本概念基本術(shù)語(yǔ)主要性能指標(biāo)存儲(chǔ)器分類(lèi)存儲(chǔ)器分級(jí)體系結(jié)構(gòu)3南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1 .1 基本術(shù)語(yǔ)記憶單元（位元）：具有兩種穩(wěn)態(tài)的能夠表示二進(jìn)制數(shù)碼0和1的物理器件。存儲(chǔ)單元：主存中具有相同地址的那些位構(gòu)成一個(gè)存儲(chǔ)單元。存儲(chǔ)體：若干存儲(chǔ)單元構(gòu)成一個(gè)存儲(chǔ)體。編址方式：對(duì)存儲(chǔ)體中各存儲(chǔ)單元進(jìn)行編號(hào)的方式。按字節(jié)編址按字編址按半字編址存儲(chǔ)器地址寄存器（MAR）：用

2、于存放主存單元地址的寄存器。存儲(chǔ)器數(shù)據(jù)寄存器（MDR）：用于存放主存單元中的數(shù)據(jù)的寄存器。4南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1 .1 基本術(shù)語(yǔ)存儲(chǔ)字、編址單位和傳輸單位機(jī)器字長(zhǎng)：運(yùn)算器中參加運(yùn)算的寄存器的位數(shù)。存儲(chǔ)字：存儲(chǔ)器按機(jī)器字長(zhǎng)組織的一個(gè)“自然”單位。它的長(zhǎng)度一般應(yīng)等于一個(gè)數(shù)或指令的位數(shù)。但大多數(shù)機(jī)器并不是這樣。存儲(chǔ)芯片中的一個(gè)讀寫(xiě)單位。編址單位：一個(gè)存儲(chǔ)單元的位數(shù)。有的按字編址，有的按字節(jié)編址，等等。傳輸單位：對(duì)主存而言，指一次從存儲(chǔ)器讀出或?qū)懭氲臄?shù)的位數(shù)，它可以不等于存儲(chǔ)字的長(zhǎng)度，也可不等于編址單位。對(duì)外存而言，數(shù)據(jù)通常按塊傳輸。 （例如：386/486等，其編址單位為

3、字節(jié)、字長(zhǎng)為32位，單字位數(shù)為16位，但傳輸單位可以是8/16/24/32位。）5南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.2 主要性能指標(biāo)存儲(chǔ)容量 ：存儲(chǔ)器能夠容納的二進(jìn)制信息量。存儲(chǔ)器的存儲(chǔ)容量越大，能存儲(chǔ)的信息就越多。存儲(chǔ)容量常用存儲(chǔ)單元數(shù)與每個(gè)單元的位數(shù)的乘積表示，或用字節(jié)數(shù)表示。如PDP-11/23計(jì)算機(jī)主存容量為64K字，字長(zhǎng)為16位，則可表示為64K*16位，或128K字節(jié)，記為128KB（Byte）。現(xiàn)代計(jì)算機(jī)的主存容量要大得多，一般以字節(jié)為單位表示。如以Pentium為CPU的微型計(jì)算機(jī)，主存的配置一般為32256MB。 通常用2的整數(shù)冪來(lái)計(jì)算存儲(chǔ)容量，計(jì)量單位有K，

4、M，G，T等。這些計(jì)算單位之間的換算如下：1K=210=1024 1G=230=1024M 1M=220=1024K 1T=240=1024G6南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.2 主要性能指標(biāo)存取速度存取時(shí)間TA；存儲(chǔ)器接到讀/寫(xiě)命令后到被讀數(shù)據(jù)穩(wěn)定在MDR的輸出端或數(shù)據(jù)被寫(xiě)入某單元為止的時(shí)間間隔。也稱讀寫(xiě)時(shí)間。存儲(chǔ)周期TMC：連讀兩次訪問(wèn)存儲(chǔ)器所需的最小時(shí)間間隔，它應(yīng)等于存取時(shí)間加上下一存取開(kāi)始前所要求的附加時(shí)間（ 因?yàn)榇鎯?chǔ)器由于讀出放大器、驅(qū)動(dòng)電路等都有一段穩(wěn)定恢復(fù)時(shí)間，所以讀出后不能立即進(jìn)行下一次訪問(wèn)。 ）。因此，TMC比TA大。最大數(shù)據(jù)傳輸率R：連續(xù)訪問(wèn)時(shí)每秒鐘從存儲(chǔ)

5、器入出的信息量。單位： 位/秒(bps) 或 字節(jié)/秒(Bps) 。 RAM：R=W/ TMC （假定存儲(chǔ)周期是500ns，每次讀寫(xiě)一個(gè)字(16位),則最大數(shù)據(jù)傳輸率為：16b/500ns=32Mbps。) 磁表面： TN =TA+N/R (其中TN 為讀寫(xiě)N位的平均時(shí)間；TA為平均存取時(shí)間；N為位數(shù)) 速度計(jì)量單位：毫秒= 10-3秒(m s)，微秒=10-6秒( s)，納秒=10-9秒(ns)7南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.2 主要性能指標(biāo)價(jià)格（每位成本）存儲(chǔ)器的價(jià)格常用每位(bit)的價(jià)格來(lái)衡量。它不僅包含了存儲(chǔ)元件本身的價(jià)格，也包括為該存儲(chǔ)器操作服務(wù)的外圍電路的價(jià)格

6、。一般來(lái)說(shuō)，用來(lái)組成主存的存儲(chǔ)器價(jià)格較高，如半導(dǎo)體存儲(chǔ)器（雙極型和MOS型存儲(chǔ)器）。輔助存儲(chǔ)器（如磁盤(pán)、磁帶、光盤(pán)）的價(jià)格則低得多。速度很高的存儲(chǔ)器往往價(jià)格較貴，容量也不可能很大。因此容量、速度、價(jià)格三個(gè)指標(biāo)是互相制約的。 8南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.2 主要性能指標(biāo)可靠性存儲(chǔ)器可靠性用平均故障時(shí)間間隔MTBF（Mean Time Between Failures）來(lái)衡量。 MTBF可以理解為兩次故障之間的平均時(shí)間間隔。它的值越大表示存儲(chǔ)器的可靠型越高，可連續(xù)運(yùn)行時(shí)間就越長(zhǎng)。與MTBF意義相同的術(shù)語(yǔ)是平均無(wú)故障時(shí)間或平均無(wú)差錯(cuò)時(shí)間。 MTBF的計(jì)算公式為：t存儲(chǔ)器系統(tǒng)運(yùn)

7、行的一段時(shí)間N(t) 系統(tǒng)在0, t時(shí)間段內(nèi)的故障次數(shù)9南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.2 主要性能指標(biāo)其他性能指標(biāo)集成度：每個(gè)芯片所含的二進(jìn)制信息量。功耗：發(fā)熱程度和耗電量。 集成度和功耗是矛盾的兩個(gè)方面。我們希望集成度大而功耗小，但一般集成度越大，功耗也越大。10南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.3 存儲(chǔ)器分類(lèi)（1）按工作性質(zhì)/存取方式分類(lèi)隨機(jī)存取存儲(chǔ)器(RAM) ：每個(gè)單元的讀寫(xiě)時(shí)間一樣，且與各單元所在位置無(wú)關(guān)。如：內(nèi)存。順序存取存儲(chǔ)器(SAM)：數(shù)據(jù)按順序從存儲(chǔ)載體的始端讀出或?qū)懭?，因而存取時(shí)間的長(zhǎng)短與信息所在位置有關(guān)。例如：磁帶。直接存取存儲(chǔ)器：利用

8、一個(gè)共享讀寫(xiě)機(jī)制，直接定位到要讀寫(xiě)的數(shù)據(jù)塊，在讀寫(xiě)某個(gè)數(shù)據(jù)塊時(shí)按順序進(jìn)行。例如：磁盤(pán)。相聯(lián)存取存儲(chǔ)器：按內(nèi)容檢索到存儲(chǔ)位置進(jìn)行讀寫(xiě)。例如：快表。依據(jù)不同的特性有多種分類(lèi)方法11南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.3 存儲(chǔ)器分類(lèi)（2）按存儲(chǔ)介質(zhì)分類(lèi)半導(dǎo)體存儲(chǔ)器雙極型，靜態(tài)MOS型，動(dòng)態(tài)MOS型磁表面存儲(chǔ)器磁盤(pán)，磁帶，磁鼓光存儲(chǔ)器CD，CD-ROM，MO，DVD磁芯存儲(chǔ)器電荷耦合器件(CCD)磁泡存儲(chǔ)器12南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.3 存儲(chǔ)器分類(lèi)（3）按信息的可更改性分類(lèi)讀寫(xiě)存儲(chǔ)器（Read/Write Memory)：可讀可寫(xiě)。只讀存儲(chǔ)器（Read Only

9、 Memory)：只能讀不能寫(xiě)。（4）按斷電后信息的可保存性分類(lèi) 非易失性存儲(chǔ)器 ：信息可一直保留，不需電源維持。如 ： ROM，磁表面存儲(chǔ)器。易失性存儲(chǔ)器：電源關(guān)閉時(shí)信息自動(dòng)丟失。如：RAM 。13南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.3 存儲(chǔ)器分類(lèi)（5）按功能/容量/速度/所在位置分類(lèi)寄存器：封裝在CPU內(nèi)，用于存放當(dāng)前正在執(zhí)行的指令和使用的數(shù)據(jù)。Cache：位于CPU內(nèi)部或附近，用來(lái)存放當(dāng)前要執(zhí)行的局部程序段和數(shù)據(jù)。速度可與CPU匹配，容量小。內(nèi)存儲(chǔ)器（主存儲(chǔ)器）：位于CPU之外，用來(lái)存放已被啟動(dòng)的程序及所用的數(shù)據(jù)。容量較大，速度較快。外存儲(chǔ)器（輔助存儲(chǔ)器）：位于主機(jī)之外，用

10、來(lái)存放暫不運(yùn)行的程序和數(shù)據(jù)。容量大而速度慢。 從使用和維護(hù)角度來(lái)說(shuō)，計(jì)算機(jī)最好使用一個(gè)容量極大而速度極快的存儲(chǔ)器。但往往做不到。因而采用一種分級(jí)體系結(jié)構(gòu)，使各種不同功能/容量/速度/價(jià)格的存儲(chǔ)器相互協(xié)調(diào)以構(gòu)成最佳性能的存儲(chǔ)系統(tǒng)。 14南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.4 存儲(chǔ)器分級(jí)體系結(jié)構(gòu)五層金字塔形分層系統(tǒng)從上到下的特點(diǎn)：1，每位價(jià)格降低2，容量增大3，存取時(shí)間增大4，訪問(wèn)頻度降低Traditional Memory Hierarchy傳統(tǒng)結(jié)構(gòu)15南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.1.4 存儲(chǔ)器分級(jí)體系結(jié)構(gòu)Contemporary Memory Hierarchy

11、當(dāng)代結(jié)構(gòu)開(kāi)辟一部分內(nèi)存區(qū)，用作“Disk Cache”，用于存放將被送到磁盤(pán)上的數(shù)據(jù)。引入“Disk Cache”的好處：(1)寫(xiě)盤(pán)時(shí)按“簇”進(jìn)行，以避免頻繁地小塊數(shù)據(jù)寫(xiě)盤(pán)。(2)有些中間結(jié)果數(shù)據(jù)在寫(xiě)回盤(pán)之前可被快速地再次使用。16南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2 半導(dǎo)體隨機(jī)存儲(chǔ)器記憶單元的基本原理半導(dǎo)體RAM的組織再生與刷新只讀存儲(chǔ)器存儲(chǔ)器的數(shù)據(jù)檢/糾錯(cuò)17南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.1 記憶單元的基本原理作為記憶材料的條件：有兩種穩(wěn)態(tài)，且是可逆的。在外部信號(hào)激勵(lì)下，兩種穩(wěn)態(tài)能進(jìn)行無(wú)限次相互轉(zhuǎn)換。在外部信號(hào)激勵(lì)下，能讀出兩種穩(wěn)定狀態(tài)。長(zhǎng)期存儲(chǔ)可靠可用作記

12、憶單元(位元)的材料：磁性材料（磁芯、磁泡、CCD等，用的很少）半導(dǎo)體材料（TTL,ECL,MOS管，大量使用）半導(dǎo)體記憶單元雙極型MOS管靜態(tài)MOS動(dòng)態(tài)MOSSRAMDRAM目前的主流技術(shù)18南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.1 記憶單元的基本原理（1）速度快，但集成度低、功耗大電路速度主要取決于射極電流“撥動(dòng)”的速度，而電流變化的快慢，與管子的頻率特性有關(guān)，晶體管的頻率特性可以做得很高，所以雙極型記憶單元速度是很快的。（2）非破壞性讀出，也無(wú)需刷新。信息讀出后，原來(lái)的信息狀態(tài)不變，而且穩(wěn)定。主要用作高速小容量的Cache。對(duì)于大容量的主存儲(chǔ)器一般用功耗小、集成度高，但速度較

13、慢的MOS管電路。 雙極型記憶單元電路的特點(diǎn)19南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.1 記憶單元的基本原理靜態(tài)六管MOS有以下三個(gè)特點(diǎn)：非破壞性讀出，不需重寫(xiě)或刷新； 結(jié)構(gòu)簡(jiǎn)單，可靠性高，具有一定速度； 電路元件較多，占硅片面積大， 故功耗大，集成度不高。 20南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)動(dòng)態(tài)單管MOS記憶單元電路圖21南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)動(dòng)態(tài)單管記憶單元讀出電壓MOS電路中，數(shù)據(jù)線本身存在分布電容C0 ，故在讀出時(shí)，讀出線上的電荷在串接的兩電容C0和CS中間分配，使得讀出電壓下降，如果原存儲(chǔ)在CS上的電壓為VS則讀出電壓VR為：一般C0CS般

14、,故讀出電壓信號(hào)很微弱，通常需用放大電路。22南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.2 半導(dǎo)體RAM的組織存儲(chǔ)器芯片：存儲(chǔ)體+外圍電路(地址譯碼和讀寫(xiě)控制)記憶單元的組織： 位元字線W位線S0位線S1 讀寫(xiě)控制Din DoutR/W 位元選擇線(字線)數(shù)據(jù)線(位線)讀寫(xiě)控制Din DoutR/W存儲(chǔ)體： 由記憶單元(位元)構(gòu)成的存儲(chǔ)陣列記憶單元存儲(chǔ)器芯片內(nèi)存條（存儲(chǔ)器模塊）23南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.2 半導(dǎo)體RAM的組織存儲(chǔ)器芯片的種類(lèi)（由存儲(chǔ)體結(jié)構(gòu)來(lái)分）字片式（單方向譯碼，一維地址驅(qū)動(dòng)）陣列中的位元排列與存儲(chǔ)器中字的邏輯排列相同。存儲(chǔ)體的每一行構(gòu)成多位

15、的一個(gè)存儲(chǔ)字，一起被讀寫(xiě)。每列由相同位構(gòu)成，共用一個(gè)讀寫(xiě)電路，有多個(gè)讀寫(xiě)電路。在位方向上便于擴(kuò)充。 位片式（雙方向譯碼，二位地址驅(qū)動(dòng)）芯片陣列由行和列排列而成，每次只能讀寫(xiě)行、列交叉處的一位數(shù)據(jù)。每個(gè)芯片只有一位讀寫(xiě)電路。在字和位方向上都能擴(kuò)充，但需有片選信號(hào)。24南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)字片式存儲(chǔ)體陣列組織X向譯碼器一維地址譯碼系統(tǒng)地址驅(qū)動(dòng)線25南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)位片式存儲(chǔ)體陣列組織26南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)位片式芯片框圖27南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)字?jǐn)U展為芯片字?jǐn)?shù)的4倍位擴(kuò)展為芯片位數(shù)的16倍28南京大學(xué)計(jì)算機(jī)

16、系 多媒體技術(shù)研究所 袁春風(fēng)半導(dǎo)體隨機(jī)存儲(chǔ)器基本結(jié)構(gòu)圖主存儲(chǔ)器29南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.2 半導(dǎo)體RAM的組織地址譯碼（驅(qū)動(dòng)）器用于將總線上傳輸過(guò)來(lái)的地址信息進(jìn)行譯碼，在所有字線中選擇一根字線，使其驅(qū)動(dòng)為高電平。地址線有n條時(shí)，譯碼器輸出2n條字線，能驅(qū)動(dòng)2n個(gè)存儲(chǔ)單元中任一個(gè)。 問(wèn)題：對(duì)于一個(gè)具有2n個(gè)單元的位片式芯片（即：采用二維地址譯碼的存儲(chǔ)器芯片），其地址驅(qū)動(dòng)（選擇）線的條數(shù)為多少？ 2n/2 +2n/230南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)地址譯碼器電路示意圖31南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.2 半導(dǎo)體RAM的組織讀寫(xiě)控制 存儲(chǔ)

17、器的基本操作是讀操作和寫(xiě)操作。讀寫(xiě)控制電路用于接收總線送來(lái)的讀/寫(xiě)控制信號(hào)，控制數(shù)據(jù)寫(xiě)入記憶單元，或?qū)?shù)據(jù)從記憶單元讀出。 下圖是一個(gè)二進(jìn)制位的讀寫(xiě)與I/O電路示意圖。讀寫(xiě)控制電路由門(mén)電路1、2組成，“讀寫(xiě)命令R/W”接受總線傳送過(guò)來(lái)的讀/寫(xiě)命令。當(dāng)R/W=1時(shí)是讀操作命令，R/W=0時(shí)是寫(xiě)操作。 32南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)16M位=4Mb x 4=2048 x 2048 x 4=211x211x4(1) 地址線：11根 分時(shí)復(fù)用,由RAS和CAS提供控制時(shí)序。 采用分時(shí)復(fù)用技術(shù)使得每出現(xiàn)新一代存儲(chǔ)器芯片，容量至少 提高四倍。（因?yàn)槊吭黾右桓刂肪€，行和列各擴(kuò)大2倍， 總的

18、擴(kuò)大4倍）(2) 這個(gè)DRAM芯片的存儲(chǔ)字是4位，所以還需將多個(gè)這樣的芯 片連接到DRAM控制器，才能在總線上讀寫(xiě)相應(yīng)的位數(shù)。(3) 所有DRAM芯片都同時(shí)刷新，由刷新計(jì)數(shù)器自動(dòng)計(jì)數(shù)、按行 刷新（只產(chǎn)生行地址），對(duì)CPU透明。 舉例2：典型的16M位DRAM（4M*4）33南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例2：典型的16M位DRAM（4M*4）34南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例3：256K字節(jié)存儲(chǔ)器組織256KB=256Kb x 8=512 x 512 x 8=29 x 29 x 8 所以要8個(gè)512 x 512的位片式芯片 每個(gè)芯片的地址線為9+9=18。存儲(chǔ)器容

19、量等于芯片的字?jǐn)?shù)，所以只需在位方向上進(jìn)行擴(kuò)充。而字方向不需擴(kuò)充。 字：512 x 512 =256K (未擴(kuò)充) 位：1位8位。若需要更大容量的存儲(chǔ)器時(shí)，則需一個(gè)芯片陣列。 即芯片在字和位方向都要擴(kuò)充。35南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例3：256K字節(jié)存儲(chǔ)器組織36南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.3 DRAM的刷新什么樣的存儲(chǔ)芯片要刷新？ 動(dòng)態(tài)RAM芯片要刷新。為什么要刷新？ 因?yàn)镈RAM芯片是靠電容上存儲(chǔ)電荷來(lái)暫存信息的。而電容的絕緣電阻不是無(wú)窮大，總會(huì)有漏電。因而需要定期進(jìn)行刷新，即對(duì)原存信息的電容補(bǔ)充電荷。電荷泄漏程度取決于制造工藝，目前多數(shù)DRAM芯片

20、需要在2ms以內(nèi)全部刷新一遍，若間隔超過(guò)2ms，有可能丟失信息。刷新與再生 刷新是因?yàn)橛洃涬娙莘烹姸枰亩〞r(shí)充電操作，因而需要對(duì)所有單元定時(shí)按行進(jìn)行； 再生則是因?yàn)橛洃泦卧黄茐男宰x出后的充電操作，因而是對(duì)個(gè)別單元及所在行的其他單元隨機(jī)進(jìn)行的。37南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.3 DRAM的刷新如何進(jìn)行刷新？所有存儲(chǔ)芯片同時(shí)進(jìn)行。對(duì)每個(gè)DRAM芯片來(lái)說(shuō)，按行進(jìn)行。 每次刷新一行，每一行在2ms內(nèi)必須保證被刷新一次。 若某存儲(chǔ)器有若干塊DRAM芯片，每個(gè)芯片的行數(shù)為128，則在2ms之中至少應(yīng)刷新128次，故在15.625 s內(nèi)至少刷新一行。（ 2ms128= 15.625

21、 s ）刷新地址（行號(hào)）由存儲(chǔ)器控制邏輯逐行自主循環(huán)產(chǎn)生，它不依賴外部的訪問(wèn)，所以刷新對(duì)CPU是透明的。常用的刷新方式有四種： 集中、分散、異步、透明38南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.3 DRAM的刷新集中刷新方式在2ms間隔內(nèi)集中對(duì)所有行進(jìn)行刷新，每行的刷新時(shí)間等于一個(gè)存取周期。由一個(gè)定時(shí)器每2ms請(qǐng)求刷新一次，由刷新計(jì)數(shù)器控制一個(gè)計(jì)數(shù)循環(huán)，逐行刷新一遍。優(yōu)點(diǎn)是主存利用率高，控制簡(jiǎn)單；缺點(diǎn)是在連續(xù)、集中的這段刷新期間，CPU不能使用存儲(chǔ)器，因而形成一段死區(qū)。39南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.3 DRAM的刷新分散刷新方式將每個(gè)存取周期分為兩部分，前半期

22、用于正常讀寫(xiě)或保持，后半期用于刷新，也就是將各刷新周期分散地安排在讀寫(xiě)周期之后。分散刷新方式的優(yōu)點(diǎn)是時(shí)序控制簡(jiǎn)單，主存沒(méi)有長(zhǎng)的死區(qū)；缺點(diǎn)是刷新過(guò)于頻繁，主存利用率不高，速度大約降低一半。 現(xiàn)在，個(gè)人計(jì)算機(jī)主存的存取周期大約為10ns，若采用分散刷新方式，將增至20ns，在2ms內(nèi)將刷新105次，大大超過(guò)行數(shù)。因此，分散刷新方式只能用于低速系統(tǒng)之中。 40南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.3 DRAM的刷新異步刷新方式結(jié)合集中和分散兩種方式。將2ms的刷新時(shí)間間隔平均分配到每行。例如：行地址為7位時(shí)，共128行，所以行間刷新時(shí)間間隔為：2ms/128=15.625s。這樣就能保證

23、:對(duì)某行而言，在2ms之內(nèi)必須刷新一次且僅被刷新一次。透明刷新方式CPU在指令譯碼時(shí)不訪問(wèn)存儲(chǔ)器，因此，存儲(chǔ)器可利用這段時(shí)間插入刷新操作。這樣，刷新過(guò)程便不占用CPU時(shí)間，對(duì)CPU而言是透明的。41南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)動(dòng)態(tài)刷新方式時(shí)間分配關(guān)系圖42南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器特點(diǎn)：信息只能讀不能寫(xiě)。非破壞性讀出，無(wú)需再生。也以隨機(jī)存取方式工作。信息用特殊方式寫(xiě)入，一經(jīng)寫(xiě)入，就可長(zhǎng)久保存，不受斷電影響。故是非易失性存儲(chǔ)器。用途：用來(lái)存放一些固定程序。如監(jiān)控程序、啟動(dòng)程序等。只要一接通電源，這些程序就能自動(dòng)地運(yùn)行；可作為控制存儲(chǔ)器，存放微程

24、序。還可作為函數(shù)發(fā)生器和代碼轉(zhuǎn)換器。在輸入、輸出設(shè)備中，被用作字符發(fā)生器，漢字庫(kù)等。43南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器分類(lèi)：腌膜只讀存儲(chǔ)器（Mask ROM）-MROM可編程只讀存儲(chǔ)器（Programmable ROM）- PROM可擦除可編程只讀存儲(chǔ)器（Erasable PROM）-EPROM電可擦除可編程只讀存儲(chǔ)器（Electrically EPROM）-EEPROM (E2PROM)閃存（flash memory）44南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器掩膜型只讀存儲(chǔ)器(MROM)類(lèi)似于字片式RAM，沒(méi)有寫(xiě)入機(jī)構(gòu)行、列交叉點(diǎn)的

25、MOS管，在最后一道掩膜工藝，根據(jù)特定的編碼布局來(lái)決定是否行、列互連，接上者為0(或1) ，未接上者為1(或0) 。特點(diǎn)： (1)存儲(chǔ)內(nèi)容一次寫(xiě)入，不能修改，因而靈活性差。 (2)存儲(chǔ)內(nèi)容固定，所以可靠性高。 (3) 生產(chǎn)周期長(zhǎng)，用戶和廠家間依賴性大，只適合定型批量生產(chǎn)。45南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器可編程序只讀存儲(chǔ)器 (PROM)芯片出廠時(shí)內(nèi)容全部為0(半成品)，用戶可用專門(mén)的PROM寫(xiě)入器將信息寫(xiě)入，所以稱為可編程型。寫(xiě)入不可逆，某位寫(xiě)入1后，就不能再變?yōu)?，因此稱為一次編程型。有兩種工藝：熔絲型和反向二極管型 熔絲型較常用，在行列交點(diǎn)處連接一段熔絲，

26、存入0。若該位需寫(xiě)入1，則讓它通過(guò)較大電流，使熔絲燒斷。 反向二極管型在行列交點(diǎn)處有一對(duì)反向的二極管，它們因反向而不導(dǎo)通，稱為0。若該位需要寫(xiě)入1，則在相應(yīng)行列之間加較高電壓，將其中反向二極管永久性擊穿，留正向可導(dǎo)通的一只二極管。(書(shū)中稱為P-N結(jié)破壞型)46南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)可擦除可編程只讀存儲(chǔ)器(EPROM) 是一種以讀為主的可讀可寫(xiě)存儲(chǔ)器?？捎米贤饩€擦除（每次20分鐘），然后重新寫(xiě)入新的信息。EPROM比MROM和PROM靈活與實(shí)用。但是EPROM采用MOS工藝，速度比較慢。擦除時(shí)，芯片中所有信息都會(huì)消失，不靈活。因而又引入了一種電可擦除的EPROM（E2PROM

27、）。4.2.4 只讀存儲(chǔ)器47南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器電擦除EPROM（E2PROM）也是一種以讀為主的可讀可寫(xiě)存儲(chǔ)器。使用電可擦除技術(shù)（加高電壓擦除），可擦除個(gè)別單元。 它采用金屬-氮-氧化硅（MNOS）集成工藝，可實(shí)現(xiàn)正常的只讀不寫(xiě)，在擦除時(shí)只需加高壓對(duì)指定單元產(chǎn)生電流，形成“電子隧道”，將該單元信息擦除，而其它未通電流的單元內(nèi)容保持不變。寫(xiě)操作比讀操作化更多的時(shí)間。集成度比EPROM低，而且更貴。48南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器快閃存儲(chǔ)器（閃存、Flash Memory） 八十年代中期，研制出一種快擦寫(xiě)型存儲(chǔ)器（

28、Flash Memory）。它具備RAM（隨機(jī)存儲(chǔ)器）與ROM（只讀存儲(chǔ)器）的所有特點(diǎn)，而且功耗低、集成度高，發(fā)展前景非常廣闊，這種器件沿用了EPROM的簡(jiǎn)單結(jié)構(gòu)和浮柵/熱電子注入的編程寫(xiě)入方式，又兼?zhèn)銭2PROM的可擦除特點(diǎn)，而且可在計(jì)算機(jī)內(nèi)進(jìn)行擦除和編程寫(xiě)入。因此稱為快擦型電可擦除重編程ROM，即Flash EEPROM。功能和價(jià)格介于EPROM和EEPROM之間?？砂磯K進(jìn)行電擦除，而不提供字節(jié)級(jí)擦除。速度比EPROM快，集成度比EEPROM高。 49南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.2.4 只讀存儲(chǔ)器閃存的發(fā)展趨勢(shì)現(xiàn)階段Flash EEPROM正在取代EPROM和E2PROM

29、。將來(lái)可望部分地取代磁盤(pán)存儲(chǔ)器。 因?yàn)檫@種芯片具有非易失性，當(dāng)電源斷開(kāi)后仍能長(zhǎng)久保存信息，屬于非易失性半導(dǎo)體存儲(chǔ)器，不需后備電源。從速度上講，它的讀取速度與DRAM芯片相近，是磁盤(pán)讀取速度的100倍左右；而它的寫(xiě)數(shù)據(jù)時(shí)間（快擦寫(xiě)）則與硬盤(pán)相近。因此它適于做成半導(dǎo)體盤(pán)，即用半導(dǎo)體存儲(chǔ)器當(dāng)成磁盤(pán)使用。由于沒(méi)有機(jī)電運(yùn)動(dòng)，可靠性高，也被稱為固態(tài)盤(pán)。這種存儲(chǔ)器有可能對(duì)傳統(tǒng)的磁表面存儲(chǔ)器發(fā)起挑戰(zhàn)，目前的劣勢(shì)是價(jià)格高，價(jià)格/位約為硬盤(pán)存儲(chǔ)器的15倍。在某些應(yīng)用之中，F(xiàn)lash EEPROM還可能取代DRAM與SRAM。 50南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4 高速緩沖存儲(chǔ)器（Cache)引入高

30、速緩存的目的解決CPU速度和主存速度匹配問(wèn)題（另一種方法是采用多模塊存儲(chǔ)器結(jié)構(gòu)）Cache的工作原理Cache設(shè)計(jì)的要素Cache大小映射方式替換算法寫(xiě)策略塊大小Cache個(gè)數(shù)奔騰機(jī)的Cache組織51南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.1 程序訪問(wèn)的局部化什么是程序訪問(wèn)的局部化性質(zhì)？ 對(duì)大量典型程序的運(yùn)行情況進(jìn)行分析的結(jié)果表明：在一個(gè)較短的時(shí)間間隔內(nèi)，由程序產(chǎn)生的地址往往集中在存儲(chǔ)器的一個(gè)很小的范圍內(nèi)。因?yàn)橹噶畹刂肥沁B續(xù)的，再加上循環(huán)程序段或子程序段要重復(fù)執(zhí)行。因此，對(duì)這些地址的訪問(wèn)就自然地具有在時(shí)間上集中分布的傾向。這種在某一時(shí)間段，對(duì)局部范圍的存儲(chǔ)器地址頻繁訪問(wèn)的現(xiàn)象就是所

31、謂的程序訪問(wèn)局部性?；诔绦蛟L問(wèn)的局部性使訪存要求快速響應(yīng)如果在CPU和主存之間設(shè)置一個(gè)快速小容量的存儲(chǔ)器，其中總是存放最活躍（被頻繁訪問(wèn)）的程序塊和數(shù)據(jù)，CPU訪問(wèn)這些程序或數(shù)據(jù)時(shí)，就不必訪問(wèn)主存，而直接從這個(gè)高速緩存中取得。這樣便使得CPU和主存速度匹配起來(lái)了。52南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)程序局部性原理圖為什么引入Cache能達(dá)到快速訪問(wèn)的目的？主要是基于程序訪問(wèn)的局部化性質(zhì)53南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.2 Cache的工作原理在主存-Cache存儲(chǔ)體系中，所有的程序和數(shù)據(jù)都在主存中，Cache中只存放主存一部分程序塊和數(shù)據(jù)的副本。 主存由多達(dá)2n

32、個(gè)可尋址的字組成，每個(gè)字有唯一的n位地址。為了實(shí)現(xiàn)映射，我們把這個(gè)存儲(chǔ)器看成由許多定長(zhǎng)的塊(block)組成，每塊有K個(gè)字，即有L=2nK個(gè)字塊。Cache由M個(gè)槽(slot)組成，每個(gè)槽有K個(gè)字。槽(或稱為行l(wèi)ine)的數(shù)量遠(yuǎn)遠(yuǎn)小于主存儲(chǔ)器塊的數(shù)目。在任何時(shí)侯，存儲(chǔ)器中的幾個(gè)塊駐留在Cache的槽中。如果要讀取存儲(chǔ)塊中的某個(gè)字，則整個(gè)塊被傳送到Cache的一個(gè)槽中。由于塊數(shù)多于槽數(shù)，所以單個(gè)的槽不能久久地被某塊專用。因此，每個(gè)槽有一個(gè)標(biāo)記(tag)，用來(lái)識(shí)別當(dāng)前存儲(chǔ)的是哪個(gè)塊。這個(gè)標(biāo)記通常是主存儲(chǔ)器地址的一部分。 54南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.2 Cache的工作原理

33、55南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)56南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.2 Cache的工作原理57南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)58南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)Cache工作原理圖59南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.2 Cache的工作原理引入cache后系統(tǒng)的效率估算 假定主存的訪問(wèn)時(shí)間為tM，Cache的訪問(wèn)時(shí)間為tC ，Cache的命中率為p，則CPU訪問(wèn)該存儲(chǔ)系統(tǒng)的平均訪問(wèn)速度為： TA=p tC+(1-p)tM= tM (tM- tC ) p 所以，采用 Cache后系統(tǒng)的訪存速度提高倍數(shù)為： tM / TA=

34、tM / (p tC+(1-p)tM ) =1 / (1 - (1- tC / tM ) p) 60南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3 Cache設(shè)計(jì)要素Cache大小寫(xiě)策略映射功能 寫(xiě)通過(guò)（Write Through） 直接 回寫(xiě)（Write Back） 相聯(lián) 寫(xiě)一次（Write Once） 組相聯(lián)塊大小替換算法Cache數(shù)目 最近最少使用 一級(jí)或二級(jí) 先進(jìn)先出 統(tǒng)一或分離 最不經(jīng)常使用 隨機(jī)61南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.1 Cache大小原則上說(shuō)，Cache的大小選定應(yīng)使得使用Cache后的位平均價(jià)格接近于不使用Cache時(shí)主存的平均價(jià)格，即C

35、ache應(yīng)足夠??；而使用Cache后的平均訪問(wèn)速度接近于Cache的速度，即Cache應(yīng)足夠大。一些研究表明，Cache大小取1K512K字是最好的。62南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.2 映射功能什么是Cache的映射功能？由于Cache槽比主存塊少，因此需要一種算法把主存中的塊映射到Cache槽中。這種反映主存塊和Cache槽之間對(duì)應(yīng)關(guān)系的技術(shù)稱為映射功能。通常采用3種映射技術(shù) 直接、 相聯(lián)、組相聯(lián) 為了說(shuō)明方便起見(jiàn)，假定： 數(shù)據(jù)在主存和Cache之間按塊傳送，單位為512字。 Cache大?。?13字=8K字=16槽 x 512字/槽 主存大?。?220字=1024

36、K字=2048塊 x 512字/塊63南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.2 映射功能-直接映射是一種最簡(jiǎn)單的映射技術(shù)。把主存的每一塊映射到一個(gè)固定的Cache槽中。 也稱模映射，映射關(guān)系為： Cache槽號(hào)=主存塊號(hào) mod Cache槽數(shù) 舉例：4=100 mod 16 (說(shuō)明主存第100塊應(yīng)映射到Cache的第4槽中。)每個(gè)槽有個(gè)標(biāo)志字段，用于指出該槽取自主存的哪個(gè)塊群。主存共有128個(gè)塊群。故標(biāo)志位有7位。每個(gè)塊群中的16塊與Cache的16個(gè)槽一一對(duì)應(yīng)。主存地址共20位：7位標(biāo)志、4位槽號(hào)、9位字號(hào)。高7位標(biāo)志表示該地址位于主存哪一個(gè)塊群。64南京大學(xué)計(jì)算機(jī)系 多媒

37、體技術(shù)研究所 袁春風(fēng)直接映射Cache組織示意圖65南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)訪存過(guò)程： CPU給出20位主存地址，根據(jù)地址中間4位找到Cache相應(yīng)的槽，然后取出該槽的標(biāo)志，與地址中高7位進(jìn)行比較。 若相等，則說(shuō)明該主存單元所在的塊在Cache中，再根據(jù)低9位字地址，從Cache的這一槽中取出字地址指出的那個(gè)單元送CPU。 若不相等，則說(shuō)明要訪問(wèn)的主存單元所在的那一塊不在主存。此時(shí)將主存中該塊調(diào)入Cache對(duì)應(yīng)的槽中,并將該單元送CPU。特點(diǎn)：容易實(shí)現(xiàn)，但不夠靈活，Cache存儲(chǔ)空間得不到充分利用。例如，需將主存第0塊與第16塊同時(shí)復(fù)制到Cache中時(shí)，由于它們都只能復(fù)制到C

38、ache第0槽，即使Cache其它槽空閑，也有一個(gè)主存塊不能寫(xiě)入Cache。這樣就會(huì)產(chǎn)生頻繁的 Cache裝入。4.4.3.2 映射功能-直接映射66南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.2 映射功能-相聯(lián)映射每個(gè)主存塊可裝入到Cache的任何一槽中。也稱全映射或全相聯(lián)映射。每個(gè)槽有個(gè)標(biāo)志字段，用于指出該槽取自主存的哪個(gè)塊。主存共有2048塊。故標(biāo)志位有11位。主存地址共20位：11位標(biāo)志、9位字號(hào)。 高11位表示該地址位于主存哪一塊。67南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)68南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.2 映射功能-相聯(lián)映射訪存過(guò)程： CPU

39、給出一個(gè)20位主存地址，根據(jù)高11位的內(nèi)容依次與Cache中各槽的標(biāo)志位進(jìn)行比較。 若能找到相等的槽，則說(shuō)明要訪問(wèn)的單元在該槽中。再根據(jù)后9位字號(hào)找到相應(yīng)的字取到CPU中。 若全都不相等，則說(shuō)明要訪問(wèn)的單元不在Cache中。特點(diǎn)：比直接映射靈活。采用相聯(lián)存取技術(shù)（按內(nèi)容訪問(wèn)），實(shí)現(xiàn)復(fù)雜、速度慢。Cache標(biāo)志位數(shù)增加，比較邏輯成本隨之增加。 69南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.2 映射功能-組相聯(lián)映射結(jié)合了直接映射和相聯(lián)映射的特點(diǎn)。將Cache所有槽分組，把主存塊映射到Cache固定組的任一槽中。也即：組間模映射、組內(nèi)全映射。映射關(guān)系為： Cache組號(hào)=主存塊號(hào) mod

40、 Cache組數(shù) 舉例：假定Cache劃分為：8K字=8組x2槽/組x512字/槽 4=100 mod 8 (說(shuō)明主存第100塊應(yīng)映射到Cache的第4組的任意槽中。)每個(gè)槽有個(gè)標(biāo)志字段，用于指出該槽取自主存的哪個(gè)組群。主存共有256個(gè)組群。故標(biāo)志位有8位。每個(gè)組群中的8塊與Cache的8個(gè)組一一對(duì)應(yīng)。主存地址共20位：8位標(biāo)志、3位組號(hào)、9位字號(hào)。高8位標(biāo)志表示該地址位于主存的哪個(gè)組群。70南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)組相聯(lián)映射的Cache組織圖71南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.2 映射功能-組相聯(lián)映射訪存過(guò)程： CPU給出一個(gè)20位主存地址，根據(jù)中間3

41、位的內(nèi)容找到對(duì)應(yīng)的Cache組，再將前8位依次與該組中各槽的標(biāo)志位進(jìn)行比較。 若能找到相等的槽，則說(shuō)明要訪問(wèn)的單元在該槽中。再根據(jù)后9位字號(hào)找到相應(yīng)的字取到CPU中。 若全都不相等，則說(shuō)明要訪問(wèn)的單元不在該組中。特點(diǎn)：結(jié)合了直接映射和相聯(lián)映射的優(yōu)點(diǎn)。 當(dāng)Cache的組數(shù)為1時(shí)，則變?yōu)橄嗦?lián)映射；當(dāng)每組只有一個(gè)槽時(shí)，則變?yōu)橹苯佑成洹Ｃ拷M兩個(gè)槽（稱為2路組相聯(lián)）最常用。一般每組4個(gè)槽 以上的情況很少用。72南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.3 替換算法替換問(wèn)題的提出： 當(dāng)對(duì)應(yīng)的Cache槽已被占滿而需要調(diào)入新的主存塊時(shí)，必須考慮從cache槽中調(diào)出一個(gè)主存塊。例如：組相聯(lián)映射時(shí)，

42、假定第0組的兩個(gè)槽分別被主存第0和8塊占滿，此時(shí)若需調(diào)入主存第16塊，根據(jù)映射關(guān)系，它只能放到Cache第一組，因此，第一組中必須調(diào)出一塊，那么調(diào)出哪一塊呢？這就是淘汰策略問(wèn)題，也稱替換算法。常用替換算法有：先進(jìn)先出FIFO （first-in-first-out）最近最少用LRU （ least-recently used）最不經(jīng)常用LFU （ least-frequently used）隨機(jī)替換算法（Random）等等73南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.3 替換算法-先進(jìn)先出總是把最先進(jìn)入的那一塊淘汰掉。例：假定主存中的5塊1,2,3,4,5同時(shí)映射到Cache同一組

43、中，對(duì)于同一地址流，考察3槽/組、 4槽/組的情況。由此可見(jiàn)，F(xiàn)IFO不是一種堆棧算法，即命中率并不隨組的增大而提高。1*1*4231*442*13*4* 51*1*2355*2*34 1 2 3 4 1 2 5 1 2 3 4 5 23122 51*2 55*34 3槽/組1*1*4231*44243*1* 512*3*15*421*223233 512 5452* 1*21*4*3334槽/組74南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.3 替換算法-最近最少用總是把最近最少用的那一塊淘汰掉。例：假定主存中的5塊1,2,3,4,5同時(shí)映射到Cache同一組中，對(duì)于同一地址流，考

44、察3槽/組、 4槽/組、 5槽/組的情況。3 1 2211 3143332 522423413222141 515 2543 4414512 1 2 3 4 1 2 5 1 2 3 4 5 3134513槽/組4槽/組5槽/組75南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.3 替換算法-最近最少用是一種堆棧算法，它的命中率隨組的增大而提高。當(dāng)分塊局部化范圍超過(guò)了Cache存儲(chǔ)容量時(shí)，命中率變得很低。極端情況下，假設(shè)地址流是1,2,3,4,1 2,3,4,1,，而Cache每組只有3槽，那么，不管是FIFO，還是LRU算法，其命中率都為0。這種現(xiàn)象稱為顛簸(Thrashing)。該算法

45、具體實(shí)現(xiàn)時(shí)，并不是通過(guò)移動(dòng)塊來(lái)實(shí)現(xiàn)的，而是通過(guò)給每槽設(shè)定一個(gè)計(jì)數(shù)器，根據(jù)計(jì)數(shù)值來(lái)記錄這些主存塊的使用情況。這個(gè)計(jì)數(shù)值稱為L(zhǎng)RU位。 具體實(shí)現(xiàn)76南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.3 替換算法-最近最少用計(jì)數(shù)器變化規(guī)則：每組4槽時(shí)，計(jì)數(shù)器有2位。計(jì)數(shù)值越小則說(shuō)明越被常用。命中時(shí)，被訪問(wèn)的那個(gè)槽的計(jì)數(shù)器置0，比其低的計(jì)數(shù)器加1，其余不變。未命中且該組未滿時(shí)，新槽計(jì)數(shù)器置為0，其余全加1。未命中且該組已滿時(shí)，計(jì)數(shù)值為3的那一槽中的主存塊被淘汰，新槽計(jì)數(shù)器置為0，其余加1。 1 2 3 4 1 2 5 1 2 3 4 5 543203211243320112532130125410

46、23125402131254210312341032123403211234321012321012101077南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)最不經(jīng)常用（LFU）算法： 替換掉Cache中引用次數(shù)最少的塊。LFU也用與每個(gè)槽相關(guān)的計(jì)數(shù)器來(lái)實(shí)現(xiàn)。隨機(jī)算法： 隨機(jī)地從候選的槽中選取一個(gè)淘汰，與使用情況無(wú)關(guān)。模擬試驗(yàn)表明，隨機(jī)替換算法在性能上只稍遜于基于使用情況的算法。4.4.3.3 替換算法-其他算法78南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例假定計(jì)算機(jī)系統(tǒng)有一個(gè)容量為32Kx16位的主存，且有一個(gè)4K字的4路組相聯(lián)Cache，主存和Cache之間的數(shù)據(jù)交換塊的大小為64字。假定

47、Cache開(kāi)始為空，處理器順序地從存儲(chǔ)單元0、1、4351中取數(shù)，然后重復(fù)9次。設(shè)Cache比主存快10倍。采用LRU算法。試分析cache的結(jié)構(gòu)和主存地址的劃分。說(shuō)明采用Cache后速度提高了多少？采用MRU算法后呢？答：假定主存按字編址。每字16位。 主存：32K字=512塊x64字/塊 Cache：4K字=16組x4槽/組x64字/槽 主存地址劃分為：字號(hào)標(biāo)志位組號(hào)6454352/64=68，所以處理器的訪問(wèn)過(guò)程是對(duì)前68塊連續(xù)訪問(wèn)10次。79南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例0組1組2組3組4組15組0 槽1 槽2 槽3 槽0/64/481/65/492/66/503/67

48、/51415組16/0/6417/1/6518/2/6619/3/67203132/1633/1734/1835/19364748/3249/3350/3451/355263LRU算法：第一次循環(huán),對(duì)于每一塊只有第一字未命中,其余都命中;以后9次循環(huán),有20塊的第一字未命中,其余都命中.所以,命中率p為（43520-68-9x20）/43520=99.43%速度提高：tm/ta=tm/(ptc+(1-p)tm)=10/(p+10 x(1-p)=9.5倍80南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例0組1組2組3組4組15組0 槽1 槽2 槽3 槽0/16/32/481/17/33/492/

49、18/34/503/19/35/52415組16/32/48/6417/33/49/6518/34/50/6619/35/51/67203132/48/64/033/49/65/134/50/66/235/51/67/3364748/64/0/1649/65/1/1750/66/2/1851/67/3/195263MRU算法：第一次68字未命中；第2,3,4,6,7,8,10次各有4字未命中；第5,9次各有8字未命中；其余都命中.所以,命中率p為（43520-68-7x4-2 x8）/43520=99.74%速度提高：tm/ta=tm/(ptc+(1-p)tm)=10/(p+10 x(1-p)

50、=9.77倍81南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例原版書(shū)的解法(對(duì)于LRU算法)假定從Cache讀64字的時(shí)間為T(mén),則從主存讀64字的時(shí)間為10T。如果某塊不在Cache中，那么該塊必須先從主存讀入Cache，然后再?gòu)腃ache讀入。故時(shí)間為11T。 不用Cache時(shí),訪問(wèn)時(shí)間為： 10 x68x10T=6800T 有Cache時(shí),訪問(wèn)時(shí)間為： 1x(68x11T)+9x(48x1T+20 x11T) =3160T故：速度提高6800T/ 3160T=2.15倍。82南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)舉例對(duì)兩種解法的分析結(jié)論：我們給出解法更精確。為什么？考察訪存過(guò)程：不使用

51、Cache時(shí)，64個(gè)字的訪問(wèn)時(shí)間為：64x10T/64=10T。使用Cache時(shí), (1)若第一字命中,則64字訪問(wèn)時(shí)間為：64xT/64=1T。 (2)若第一字未命中,則64字訪問(wèn)時(shí)間約為：10T/64+1T=74T/64所以按原版書(shū)的解法，應(yīng)該為：有Cache時(shí),訪問(wèn)時(shí)間約為：(68+9x20)74T/64+9x48xT=719T故：速度提高6800T/ 719T=9.5倍。83南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.4 寫(xiě)策略（Cache一致性問(wèn)題）一致性問(wèn)題的提出：因?yàn)镃ache中的內(nèi)容是主存塊的副本，當(dāng)對(duì)Cache中的內(nèi)容進(jìn)行更新時(shí)，就存在Cache和主存如何保持一致性

52、的問(wèn)題。以下情況也會(huì)出現(xiàn)“Cache一致性問(wèn)題”當(dāng)多個(gè)設(shè)備都允許訪問(wèn)主存時(shí) 例如：I/O設(shè)備可直接讀寫(xiě)內(nèi)存時(shí)，如果Cache中的內(nèi)容被修改，則I/O設(shè)備讀出的對(duì)應(yīng)主存單元的內(nèi)容無(wú)效；若I/O設(shè)備修改了主存單元的內(nèi)容，則對(duì)應(yīng)Cache槽中的內(nèi)容無(wú)效。當(dāng)多個(gè)CPU都帶有各自的Cache而共享主存時(shí) 某個(gè)CPU修改了自身Cache中的內(nèi)容，則對(duì)應(yīng)的主存單元和其他CPU中對(duì)應(yīng)的Cache槽的內(nèi)容都變?yōu)闊o(wú)效。84南京大學(xué)計(jì)算機(jī)系 多媒體技術(shù)研究所 袁春風(fēng)4.4.3.4 寫(xiě)策略（Cache一致性問(wèn)題）寫(xiě)策略方式：Write back(一次性寫(xiě)、寫(xiě)回法) 先暫時(shí)只寫(xiě)入Cache有關(guān)單元，并用標(biāo)志予以注明，直到該塊內(nèi)容需從Cache中替換出來(lái)時(shí)，才一次寫(xiě)入主存。這種方式不在快速寫(xiě)入Cache中插入慢速的寫(xiě)主存操作，可以保持程序運(yùn)行的快速性；但在寫(xiě)回主存前，主存中內(nèi)容失效，主存與Cache 內(nèi)容不一致，有可能導(dǎo)致工作失誤。Write through(通過(guò)式寫(xiě)、寫(xiě)直達(dá)法) 即每次寫(xiě)入Cache時(shí)也同時(shí)寫(xiě)入主存，主存與Cache始終保持一致性。這種方式比較簡(jiǎn)單，能保持主存與Cache副本的一致性，但要插入慢速訪