再來看課程主要內(nèi)容

再來看課程主要內(nèi)容信息（指令和數(shù)據(jù)）在計算機中如何表示和運算？指令系統(tǒng)如何設計？如何設計高性能CPU?如何設計存儲器系統(tǒng)？如何設計I/O?如何設計總線BUS?指令集體系結(jié)構(gòu)ISA存儲器層次結(jié)構(gòu)系統(tǒng)總線輸入/輸出系統(tǒng)性能評價數(shù)據(jù)通路和控制器CPU設計，流水線技術(shù)2Ch4:MemoryHierarchy

存儲器層次結(jié)構(gòu)第一講基本概念和主存儲器第二講高速緩沖存儲器（Cache）第三講虛擬存儲器（VirtualMemory）

第一講基本概念和主存儲器主要內(nèi)容信息的存儲、傳送、處理單位的含義記憶單元/編址單位/存儲單位/傳輸單位/機器字長存儲器分類可按存取方式/易失性/可更改性/元器件/功能來分半導體存儲器隨機訪問存儲器SRAM的原理和特點DRAM的原理和特點RAM芯片組織如何由記憶單元構(gòu)成存儲陣列如何讀寫存儲陣列中的信息如何由芯片構(gòu)成存儲器提高存儲器速度的措施：芯片內(nèi)采用行緩存，同行內(nèi)數(shù)據(jù)直接從緩存中取采用多模塊存儲器，多個存儲器交叉存取引入Cache（下一講的主要內(nèi)容）回顧：存儲器基本術(shù)語記憶單元（存儲基元/存儲元/位元）（Cell）具有兩種穩(wěn)態(tài)的能夠表示二進制數(shù)碼0和1的物理器件存儲單元/編址單位（AddressingUnit）主存中具有相同地址的位構(gòu)成一個存儲單元，也稱為一個編址單位存儲體/存儲矩陣/存儲陣列（Bank）所有存儲單元構(gòu)成一個存儲陣列12345678……回顧：存儲器基本術(shù)語編址方式（AddressingMode）連續(xù)編址、交叉編址字節(jié)編址、按字編址每個存儲單元為1個字節(jié)/字存儲器地址寄存器（MemoryAddressRegister-MAR）用于存放主存單元地址的寄存器容納“1”-“max”所對應的二進制值存儲器數(shù)據(jù)寄存器（MemoryDataRegister-MDR(或MBR)）用于存放主存單元中的數(shù)據(jù)的寄存器容納8位/16位/32位…二進制數(shù)據(jù)8位16位…123…max回顧：存儲器分類（1）按工作性質(zhì)/存取方式分類隨機存取存儲器RandomAccessMemory(RAM)

每個單元讀寫時間一樣，且與各單元所在位置無關(guān)。如：內(nèi)存。順序存取存儲器SequentialAccessMemory(SAM)數(shù)據(jù)按順序從存儲載體的始端讀出或?qū)懭?，因而存取時間的長短與信息所在位置有關(guān)。例如：磁帶。直接存取存儲器DirectAccessMemory(DAM)直接定位到要讀寫的數(shù)據(jù)塊，在讀寫某個數(shù)據(jù)塊時按順序進行。例如：磁盤。相聯(lián)存儲器AssociateMemory/ContentAddressedMemory(CAM)按內(nèi)容檢索到存儲位置進行讀寫。例如：快表。依據(jù)不同的特性有多種分類方法回顧：存儲器分類（2）按存儲介質(zhì)分類半導體存儲器：雙極型，靜態(tài)MOS型，動態(tài)MOS型磁表面存儲器：磁盤（Disk）、磁帶（Tape）光存儲器：CD，CD-ROM，DVD（3）按信息的可更改性分類讀寫存儲器（Read/WriteMemory)：可讀可寫只讀存儲器（ReadOnlyMemory)：只能讀不能寫（4）按斷電后信息的可保存性分類非易失（不揮發(fā)）性存儲器(NonvolatileMemory)

信息可一直保留，不需電源維持。（如：ROM、磁表面存儲器、光存儲器等）易失（揮發(fā)）性存儲器(VolatileMemory)

電源關(guān)閉時信息自動丟失。（如：RAM、Cache等）回顧：存儲器分類（5）按功能/容量/速度/所在位置分類（由快到慢，由小容量到大容量）寄存器(Register)高速緩存(Cache)內(nèi)存儲器MM（主存儲器Main(Primary)Memory）外存儲器AM(輔助存儲器Auxiliary/SecondaryStorage)回顧：內(nèi)存與外存的關(guān)系及比較內(nèi)存儲器（簡稱內(nèi)存或主存）存取速度快成本高、容量相對較小直接與CPU連接，CPU對內(nèi)存中的指令及數(shù)據(jù)進行讀、寫操作屬于易失性存儲器(volatile)，用于臨時存放正在運行的程序和數(shù)據(jù)內(nèi)存儲器外存儲器CPU指令1指令2指令k指令n程序數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)m數(shù)據(jù)①程序和數(shù)據(jù)②CPU從內(nèi)存中逐條讀取指令及相關(guān)數(shù)據(jù)④將指令處理結(jié)果送回內(nèi)存保存⑤處理結(jié)果③逐條執(zhí)行指令

外存儲器（簡稱外存或輔存）存取速度慢成本低、容量很大不與CPU直接連接，先傳送到內(nèi)存，然后才能被CPU使用。屬于非易失性存儲器(Nonvolatile)，用于長久存放系統(tǒng)中幾乎所有的信息Cache和寄存器地址寄存器地址譯碼器讀寫控制電路控制線讀/寫控制信號數(shù)據(jù)線讀/寫的數(shù)據(jù)(64位)主存地址地址線(30位)····· 0110100110101010存儲內(nèi)容00001000000001000011001001111011111·······存儲單元地址MDRMARCPUMM主存的結(jié)構(gòu)問題：主存中存放的是什么信息？CPU何時會訪問主存？程序（指令）及其數(shù)據(jù)！執(zhí)行指令時要取指令、取數(shù)據(jù)、存數(shù)據(jù)性能指標：存儲容量：所包含的存儲單元的總數(shù)（單位：MB或GB）存取時間TA：從CPU送出內(nèi)存單元的地址碼開始，到完成讀寫,所需要的時間（單位：ns，1ns=10-9s）存儲周期TMC：連讀兩次訪問存儲器所需的最小時間間隔，它應等于存取時間加上下一存取開始前所要求的附加時間，因此，TMC比TA大

因為存儲器由于讀出放大器、驅(qū)動電路等都有一段穩(wěn)定恢復時間，所以讀出后不能立即進行下一次訪問。（就像一趟火車運行時間和發(fā)車周期是兩個不同概念一樣。）存儲器帶寬：單位時間內(nèi)讀出或?qū)懭氪鎯ζ鞯淖畲笮畔⒘恐鞔娴闹饕阅苤笜嘶仡櫍喊雽w存儲器的分類及應用半導體存儲器只讀存儲器(ROM)隨機存取存儲器(RAM)靜態(tài)存儲器SRAM動態(tài)存儲器DRAM不可在線改寫內(nèi)容的ROM閃存（FlashROM）（用作Cache）（用作主存儲器）每個記憶單元(cell)由6個晶體管組成只要加上電源，信息就能一直保持對電器干擾相對不很敏感比DRAM更快，也更貴每個cell由1個電容和1個晶體管組成.

每隔一段時間必須刷新一次對電器干擾比較敏感比SRAM慢，但便宜（用作BIOS）記憶單元的的結(jié)構(gòu)示意圖位元字線W位線S0位線S1

讀寫控制Din

DoutR/W

位元選擇線(字線)數(shù)據(jù)線(位線)讀寫控制Din

DoutR/WSRAM DRAM

位元選擇線(字線)(位線)半導體RAM的組織+外圍電路(地址譯碼和讀寫控制)記憶單元(Cell)存儲器芯片(Chip)內(nèi)存條（存儲器模塊）存儲體回顧：字片式存儲體陣列組織X向譯碼器一維地址譯碼系統(tǒng)地址驅(qū)動線假定有k位地址，則地址譯碼驅(qū)動（選擇）線的條數(shù)為多少？有2k條！字片式：只在x向上譯碼，同時讀出字線上所有位，適用于小容量芯片回顧：位片式存儲體陣列組織假定有k位地址，其地址譯碼驅(qū)動（選擇）線的條數(shù)為多少？有2k/2+1回顧：位片式芯片框圖位片式可在字方向和位方向擴充，需要有片選信號！MemoryBank位擴展芯片位數(shù)的16倍，字擴展芯片字數(shù)的4倍問題：連續(xù)編址還是交叉編址？低位選片(交叉編址)00000…000000…1…00111…101000…001000…1…000…000000…001000…010000…011000…100000…101…MAR片選邏輯10位2位4……b0b15MDR高位選片是連續(xù)編址共12位地址，兩位選片，10位片內(nèi)選址，編址單位16位。4x16個1K位的芯片，每次選中一行中的16個同時工作一個4Kx16位芯片舉例：連續(xù)編址下存儲器芯片的位擴展位擴展（字數(shù)不變，位數(shù)擴展）

用16M×1位芯片構(gòu)成16M×8位存儲器需幾個芯片？

地址范圍各是多少？

位方向擴展8倍，字方向無需擴展。即8個芯片，地址范圍都一樣：000000-FFFFFFH，地址共24位（224=16M），全部作為片內(nèi)地址(連續(xù)編址)

芯片的地址線及讀/寫控制線對應相接，而數(shù)據(jù)線單獨引出16M000000…FFFFFF代表存儲器的最終編址單位舉例：連續(xù)編址下存儲器芯片的字擴展字擴展（位數(shù)不變、擴充容量）用16M×8位芯片擴成64M×8位存儲器需幾個芯片？地址范圍？

字方向擴展4倍，即4個芯片。地址共26位，高兩位由外部譯碼器譯碼生成4個輸出，分別連到4個片選信號，片內(nèi)地址仍為24位(連續(xù)編址)地址線、讀/寫控制線等對應相接，片選信號連譯碼輸出16Mx80000000-0FFFFFF1000000-1FFFFFF2000000-2FFFFFF3000000-3FFFFFF舉例：連續(xù)編址下存儲器芯片的字位同時擴展字位同時擴展（字和位同時擴展）

用16M×1位芯片構(gòu)成64M×8位存儲器需幾個芯片，地址范圍各是多少？

字向4倍、位向8倍，32個芯片。地址分配結(jié)果同上頁（如圖，仍為連續(xù)編址）地址線、讀/寫控制線等對應相接，片選信號則分別與外部譯碼器各個譯碼輸出端相連8個16Mx10000000-0FFFFFF1000000-1FFFFFF2000000-2FFFFFF3000000-3FFFFFF主存地址27位，高24位為片內(nèi)地址。（12選行，12選列）存儲控制器(行地址i,列地址j)DRAM7DRAM003178151623243263394047485556bits0-7bits8-15bits16-23bits24-31bits32-39bits40-47bits48-55bits56-63最多讀64位03178151623243263394047485556主存儲器地址A處的64-bit數(shù)據(jù)地址A4096行舉例：交叉編址的128MB的DRAM存儲器8個芯片中(i,j)位置的字節(jié)。被同時讀出每片16Mx8bits字擴展：8片DRAM芯片行地址、列地址各12位每1行共4096列(8位/列)選中某一行并讀出之后再由列地址選擇其中的一列(8個二進位)送出主存低3位地址用來確定8個字節(jié)中的哪個，即選片。交叉編址。存儲控制器(行地址i,列地址j)DRAM7DRAM003178151623243263394047485556bits0-7bits8-15bits16-23bits24-31bits32-39bits40-47bits48-55bits56-63最多讀64位03178151623243263394047485556主存儲器地址A處的64-bit數(shù)據(jù)地址A4096行舉例：交叉編址的128MB的DRAM存儲器從該存儲器結(jié)構(gòu)可理解為什么規(guī)定數(shù)據(jù)對齊存放。例如，一個32位int型數(shù)據(jù)若存放在第8、9、10、11這4個單元，則需要訪問幾次內(nèi)存？若存放在6、7、8、9這4個單元，則需要訪問幾次內(nèi)存？1000100110101011對齊的0110011110001001不對齊的按1000訪問1次！拿到了8個字節(jié)，其中4個正是我們需要的按0110訪問再按1000訪問。共2次！DRAM芯片的刷新刷新周期：從上次對整個存儲器刷新結(jié)束到下次對整個存儲器全刷新一遍為止的時間間隔，為電容數(shù)據(jù)有效保存期的上限（如64ms）。有三種刷新方式：集中式、分散式、異步刷新。①集中刷新：前一段時間正常讀/寫，后一段時間停止讀/寫，集中逐行刷新。特點：集中刷新時間長，不能正常讀/寫（死區(qū)），很少使用。②分散刷新：每個存儲周期增長，并分為兩段:前一段用于正常讀/寫操作，后一段用于刷新操作。特點：不存在死區(qū)，但整體存儲系統(tǒng)效率太低。很少使用。③異步刷新：以4096行為例，在64ms時間內(nèi)必須輪流對每一行刷新一次，即每隔64ms/4096=15.625μs刷新一行。

特點：效率高，用得較多。三種刷新方式圖解8ms內(nèi)必須刷新一次（刷新周期），存儲周期1us，刷新一行的時間也為1us，存儲體共1000行7000us1000us1000x2=2000us3000x2=6000us2us2……27us1us7us1us……7us1us1000組（7+1）us1us1……1集中分散異步前7000us內(nèi)完成7000次讀寫。最后1000us為“死區(qū)”必須將存儲周期變成2us，每個周期中前1us讀寫，后1us刷新（其實只有前1000個周期內(nèi)真正需要刷新操作）結(jié)果8ms之內(nèi)只能完成1000+3000=4000次讀寫8ms/1000行=8us，每隔8us必須刷新一行，所以7次讀寫接1次刷新，如此往復1000次，恰好在8ms內(nèi)完成7000次讀寫，同時完成了1000行的刷新，且最多等待1us16M位=4Mbx4=2048x2048x4=211x211x4(1)地址線：11根分時復用,由RAS和CAS提供控制時序。(2)需4個位平面，對相同行、列交叉點的4位一起讀/寫(3)內(nèi)部結(jié)構(gòu)框圖舉例：典型的16M位DRAM（4Mx4）注意：行地址和列地址分時復用的情況下,每出現(xiàn)新一代存儲器芯片至少要增加一根地址線，每加一根地址線，則行地址和列地址各增加一位，所以行數(shù)和列數(shù)各增加一倍。因而容量至少提高到4倍。SKIP、舉例：典型的16M位DRAM（4Mx4）四個位平面各片同時按“行”進行刷新！二選一BACK刷新計數(shù)器的位數(shù)是幾位？為何刷新計數(shù)值不送列譯碼器？地址寄存器地址譯碼器讀寫控制電路控制線讀/寫控制信號數(shù)據(jù)線讀/寫的數(shù)據(jù)(64位)主存地址地址線(30位)····· 0110100110101010存儲內(nèi)容00001000000001000011001001111011111·······存儲單元地址MDRMARCPUMMCPU與存儲器之間的通信方式CPU如何“知道”主存工作是否已經(jīng)完成？緩沖和控制CPU與存儲器之間的通信方式CPU和主存之間有同步和異步兩種通信方式異步方式（讀操作）過程（需握手信號）CPU送地址到地址線，主存進行地址譯碼CPU發(fā)讀命令，然后等待存儲器發(fā)回“完成”信號主存收到讀命令后開始讀數(shù)，完成后發(fā)“完成”信號給CPUCPU接收到“完成”信號，從數(shù)據(jù)線取數(shù)寫操作過程類似同步方式的特點CPU和主存由統(tǒng)一時鐘信號控制，無需應答信號，如“完成”主存總是在確定的時間內(nèi)準備好數(shù)據(jù)CPU送出地址和讀命令后，總是在確定的時間取數(shù)據(jù)存儲器芯片必須支持同步方式

SDRAM芯片技術(shù)SDRAM是同步存儲芯片每步操作都在系統(tǒng)時鐘控制下進行有確定的等待時間（讀命令開始到數(shù)據(jù)線有效的時間,稱為CAS潛伏期）CL，例如CL=2clks利用總線時鐘上升沿與下降沿同步傳送連續(xù)傳送（Burst）數(shù)據(jù)個數(shù)BL=1/2/4/8多體(緩沖器)交叉存取DDR，DDR2，DDR3，DDR4…(DoubleDataRate)

SDRAM芯片的內(nèi)部結(jié)構(gòu)同步方式DDR一個時鐘2個數(shù)據(jù)DDR24個數(shù)據(jù)DDR38突發(fā)傳送：同一行中相鄰的存儲單元連續(xù)進行數(shù)據(jù)傳輸，只要指定列地址與突發(fā)長度，內(nèi)存就會一次地自動對后面相應數(shù)量的存儲單元進行讀/寫而不需要內(nèi)存控制器連續(xù)地提供列地址。（節(jié)省了CL等）地址寄存器地址譯碼器讀寫控制電路讀/寫控制信號讀/寫的數(shù)據(jù)主存地址MDRMARCPUMM存儲器芯片和CPU的連接——通過總線連接緩沖和控制片選地址CPU送出地址地址線存儲芯片地址數(shù)據(jù)線具體細節(jié)在第8章中控制線內(nèi)存條和內(nèi)存插槽機器內(nèi)存由若干內(nèi)存條組成內(nèi)存條的組成：把若干片DRAM芯片焊裝在一小條印制電路板上制成內(nèi)存條必須插在主板上的內(nèi)存條插槽中才能使用PC機主存儲器的物理結(jié)構(gòu)SIMM內(nèi)存條(singlein-linememorymodule，單邊接觸內(nèi)存模組),一般最多32位數(shù)據(jù)。SDRAM時代一次需傳輸至少64位，逐漸被DIMM取代。DIMM內(nèi)存條(Dual-Inline-Memory-Module,即雙列直插式存儲模組)。在奔騰CPU推出后出現(xiàn)的，其觸點分布在內(nèi)存條的兩面，提供64位的數(shù)據(jù)通道，在奔騰主板上可以單條使用。目前流行的是DDR系列內(nèi)存條屬于此類PC機主板中一般都配備有2個或4個DIMM插槽每次訪存操作總是在某一個內(nèi)存條內(nèi)進行！回顧：只讀存儲器(ReadOnlyMemory)還有一些屬于“主存”的存儲空間但不在“內(nèi)存條”上但同樣要被CPU訪問所以是“主存”地址范圍內(nèi)的：ROMMROM（MaskROM）：掩膜只讀存儲器PROM（ProgrammableROM）：可編程只讀存儲器EPROM（ErasablePROM）：可擦除可編程只讀存儲器EEPROM（E2PROM，ElectricallyEPROM）：電可擦除可編程只讀存儲器flashmemory：閃存（快擦存儲器）回顧：只讀存儲器(ReadOnlyMemory)特點：信息只能讀不能（在線）寫。非破壞性讀出，無需再生。也以隨機存取方式工作。信息用特殊方式寫入，一經(jīng)寫入，就可長久保存，不受斷電影響。故是非易失性存儲器。用途：用來存放一些固定程序。如監(jiān)控程序、啟動程序等。只要一接通電源，這些程序就能自動地運行；可作為控制存儲器，存放微程序。還可作為函數(shù)發(fā)生器和代碼轉(zhuǎn)換器。在輸入/出設備中，被用作字符發(fā)生器，漢字庫等。在嵌入式設備中用來存放固化的程序。ROM區(qū)和RAM區(qū)的劃分主存空間包括ROM區(qū)和RAM區(qū)；二者在物理上分開,邏輯上是整體(“主存”)ROM區(qū)用來存放BIOS等系統(tǒng)程序等，選用ROM芯片構(gòu)造；RAM區(qū)用來存放用戶程序，選用RAM芯片構(gòu)造；選擇存儲芯片的類型和數(shù)量時，必須先確定好ROM區(qū)和RAM區(qū)的地址范圍。000000000000FFFF00010000FFFFFFFF00012345?00002345?ROM區(qū)RAM區(qū)CPU地址舉例：CPU和主存的連接

CPU地址線A15～A0，數(shù)據(jù)線D7～D0，WR為讀/寫信號，MREQ為訪存請求信號。0000H～3FFFH為BIOS區(qū)，4000H～FFFFH為用戶程序區(qū)。用8K×4位ROM芯片和16K×8位RAM芯片構(gòu)成該存儲器，要求說明地址譯碼方案，并繪出ROM芯片、RAM芯片與CPU連接的方式。

解：

CPU地址16位，編址單位8位

00003FFF4000FFFFROM區(qū)RAM區(qū)CPU地址地址高兩位總是00，低14位為全譯碼。地址高兩位是01、10、11低14位為全譯碼。0000….0001…0010…0011…01…10…11…舉例：CPU和主存的連接（續(xù)）00003FFF4000FFFFROM區(qū)RAM區(qū)CPU地址8Kx416Kx8ROM區(qū)大小為：214×8位=16K×8位ROM芯片數(shù)為：2×2=4字方向擴展2倍，位方向擴展2倍。RAM區(qū)大小為：3×214×8位=48K×8位

每個ROM芯片內(nèi)地址位數(shù)為13位，連到CPU低13位地址線A12～A0。A13選擇字擴展后的2行中的1行A15和A14全0時進入ROM區(qū)RAM芯片數(shù)為：3×1=3，字方向上擴展3倍，位方向上不擴展。

每個RAM芯片內(nèi)地址位數(shù)為14位，連到CPU低14位地址線A13～A0。A15和A14直接用來選行0000….0001…0010…0011…01…10…11…片選信號CS00000101X11X10X00X舉例：CPU和主存的連接（續(xù)）問題：為什么WR不連到ROM芯片上？ROM片選由最高三位確定。RAM片選由最高兩位確定。ROM芯片只讀不寫問題：MREQ信號的作用是什么？有效(低電平)時，表示選中主存讀寫。問題：是交叉還是連續(xù)編址？連續(xù)編址！回顧：存儲器與CPU速度差距愈來愈大從上圖可以看出什么？DRAM、硬盤與CPU之間的速度差距愈來愈大！由于CPU很快，內(nèi)存較慢（差1～2個數(shù)量級），從內(nèi)存取數(shù)或向內(nèi)存寫數(shù)時，CPU往往需要等待。解決內(nèi)存訪問速度慢的措施有三個：提高主存芯片本身的速度采用多模塊存儲器技術(shù)在主存和CPU之間加入Cache提高DRAM存儲器速度的措施之一：采用芯片內(nèi)部行緩沖，以提高芯片本身的速度

反復多次使用芯片內(nèi)部緩存中的內(nèi)容，不需每次進行“行訪問”DDR和DDR2SDRAM

時鐘頻率 內(nèi)部頻率 傳輸頻率

=100MHz=200MHz =400MHz

時鐘頻率 內(nèi)部頻率 傳輸頻率

=100MHz=100MHz =200MHz存儲單元陣列數(shù)據(jù)總線DDRSDRAM存儲單元陣列數(shù)據(jù)總線DDR2SDRAM舉例：SPARCstation20’sMemoryModuleonememorymodule（內(nèi)存條）Smallest:4MB=16x2MbDRAMchips,8KBofPageSRAMBiggest:64MB=32x16Mbchips,16KBofPageSRAM512rows512colsDRAMChip0bits<7:0>8bits512×8SRAM256Kx8=2MbDRAM

Chip15bits<127:120>512×8SRAM256Kx8=2MbMemoryBus<127:0>Onepage行緩沖每個芯片有512行x512列，并有8個位平面每次讀/寫各芯片同行同列的8位，共16x8=128位當CPU訪問一塊連續(xù)區(qū)域（即行地址相同）時，可直接從行緩沖讀取，它用SRAM實現(xiàn)，速度極快！問題：行緩沖數(shù)據(jù)的地址有何特點？一定在同一行中！加快訪存速度措施之二：多模塊技術(shù)雙口存儲器（能同時進行兩個數(shù)據(jù)的讀/寫）兩套獨立的讀/寫控制電路、地址緩存、地址譯碼及地址線和數(shù)據(jù)線，通常作為雙口RAM或指令預取部件加快訪存速度措施之二：多模塊技術(shù)多模塊存儲器（能提高數(shù)據(jù)訪問速度）包含多個小體；每個體有其自己的MAR、MDR和讀寫電路可獨立組成一個存儲模塊可同時對多個模塊進行訪問

根據(jù)不同的編址方式可分為：連續(xù)編址、交叉編址連續(xù)編址多模塊存儲器按高位地址劃分模塊第0模塊第1模塊第7模塊從某單元開始，連續(xù)在同一模塊訪問，然后才跳到下一個模塊。如：一個模塊執(zhí)行程序，另一個實現(xiàn)外設和主存的數(shù)據(jù)交換（DMA訪問。）為什么能提高吞吐量？多個模塊可并行存?。?000000001…0FFFF1000010001…1FFFF7N7N+1…8N7FFFF交叉編址多模塊存儲器按低位地址劃分模塊第0模塊第1模塊第3模塊從某個單元開始后，總是在所有模塊間交替進行。為什么能提高吞吐量？多個模塊交叉存??！一個存儲周期內(nèi)可以完成4個模塊的存取第2模塊在存儲地址“相關(guān)”或出現(xiàn)“轉(zhuǎn)移”時，并行性被破壞。000000000100002000030000400005000060000700008000090000A0000B3FFFC3FFFD3FFFE3FFFF第一講小結(jié)信息的存儲、傳送、處理單位記憶單元/編址單位/存儲單位/傳輸單位/機器字長存儲器分類可按存取方式/易失性/可更改性/元器件/功能來分半導體存儲器隨機訪問存儲器SRAM：速度快，容量小，可做快速小容量存儲器DRAM：速度慢，容量大，用作主存RAM芯片組織：存儲陣列：按行、列排，分別由行地址和列地址指出位置地址譯碼器：分行、列地址譯碼器讀寫邏輯：可控制多個位平面的同一位數(shù)據(jù)一起讀/寫CPU和主存的連接同步方式，總線方式第二講高速緩沖存儲器(Cache)

什么是程序訪問的局部化特性具有Cache機制的CPU的基本訪存過程Cache和主存之間的映射方式直接映射/全相聯(lián)映射/組相聯(lián)映射cache容量和塊大小的選擇Cache替換算法Cache-friendly的程序Cache的寫策略WriteBack和WriteThroughCache失靶處理Cache性能評估回顧：計算機中存儲器的層次結(jié)構(gòu)cache主存(RAM和ROM)外存儲器（軟盤、硬盤、光盤）后備存儲器（磁帶庫、光盤庫）內(nèi)存儲器外存儲器寄存器典型容量<1KB1MB256MB~1GB40GB~200GB10TB~100TB典型存取時間1ns(0.5~1cycle)2ns(1~3cycle)10ns(10~100cycle)10ms(10~100c)10s列出的時間和容量會隨時間變化，但數(shù)量級相對關(guān)系不變。計算機中存儲器的層次結(jié)構(gòu)分析：速度越快，成本越高為提高性能/價格，組成一個層狀塔式結(jié)構(gòu)，取長補短，協(xié)調(diào)工作cache外存儲器寄存器工作過程：1）CPU運行時，需要的操作數(shù)大部分來自寄存器2）如需要從(向)存儲器中取(存)數(shù)據(jù)時，先訪問cache，如在，取自cache3）如操作數(shù)不在cache，則訪問RAM，如在RAM中，則取自RAM4）如操作數(shù)不在RAM，則訪問硬盤，操作數(shù)從硬盤中讀出→RAM→cacheCPU主存(RAM和ROM)Add$t0,$s1,$s2lw

$s1,100($s2)sw

$s1,100($s2)層次化存儲器結(jié)構(gòu)（MemoryHierarchy）

數(shù)據(jù)總是在相鄰兩層之間復制傳送

最小傳送單位是一個定長塊cache主存(RAM和ROM)外存儲器寄存器問題：為什么這種層次化結(jié)構(gòu)是有效的？基于“程序訪問局部化”特點！CPUABCDABCABB程序訪問的局部性大量典型程序的運行情況分析結(jié)果表明在較短時間間隔內(nèi)，程序產(chǎn)生的地址往往集中在一個很小范圍內(nèi)這種現(xiàn)象稱為程序訪問的局部性程序訪問局部性分為空間局部性和時間局部性程序具有訪問局部性特征的原因指令：指令按序存放，地址連續(xù)，循環(huán)程序段或子程序段重復執(zhí)行數(shù)據(jù)：連續(xù)存放，數(shù)組元素重復、按序訪問時間局部性（TemporalLocality）含義：剛被訪問過的單元很可能不久又被訪問做法：讓最近被訪問過的信息保留在靠近CPU的存儲器中空間局部性（SpatialLocality）含義：剛被訪問過的單元的鄰近單元很可能不久被訪問做法：將剛被訪問過的單元的鄰近單元調(diào)到靠近CPU的存儲器中程序的局部性原理舉例1sum=0;for(i=0;i<n;i++) sum+=a[i];*s=sum;每條指令4個字節(jié)；每個數(shù)組元素4字節(jié)指令和數(shù)組元素在內(nèi)存中均連續(xù)存放sum,ap,i,t均為通用寄存器；A，S為內(nèi)存地址I0: sum0I1: ap

AA是數(shù)組a的起始地址I2: i0I3: if(i>=n)gotodoneI4: loop: t

(ap)數(shù)組元素a[i]的值I5: sumsum+t

累計在sum中I6: apap+4

計算下個數(shù)組元素地址I7: ii+1

I8: if(i<n)gotoloopI9: done: Ssum

累計結(jié)果保存至地址SI1I2I3I4I5I60x1000x1040x1080x10C0x1100x114a[0]a[1]a[2]a[3]a[4]a[5]0x4000x4040x4080x40C0x4100x414?

?

?0x7A4?

?

?主存的布局:I00x0FC指令數(shù)據(jù)AS高級語言源程序?qū)膮R編語言程序偽代碼程序的局部性原理舉例1sum=0;for(i=0;i<n;i++) sum+=a[i];*s=sum;問題：指令和數(shù)據(jù)的時間局部性和空間局部性各自體現(xiàn)在哪里？指令：0x0FC（I0）…→0x108（I3）→0x10C（I4）→0x11C（I8）→0x120（I9）數(shù)據(jù)：只有數(shù)組在主存中：0x400→0x404→0x408→0x40C→……→0x7A4I1I2I3I4I5I60x1000x1040x1080x10C0x1100x114a[0]a[1]a[2]a[3]a[4]a[5]0x4000x4040x4080x40C0x4100x414?

?

?0x7A4?

?

?主存的布局:I00x0FC指令數(shù)據(jù)AS一段時間內(nèi)一直在局部區(qū)域內(nèi)取指令，故循環(huán)內(nèi)指令的時間局部性好；按順序執(zhí)行，故程序的空間局部性好！數(shù)組元素按順序存放，也按順序訪問，空間局部性好；每個數(shù)組元素都被訪問1次，所以沒有時間局部性。循環(huán)n次程序的局部性原理舉例2

以下兩種情況中，數(shù)組a/變量sum/指令中的for循環(huán)體，空間局部性和時間局部性如何？程序段B:intsumarraycols(inta[M][N]){inti,j,sum=0;for(j=0;j<N,j++) for(i=0;i<M,i++)sum+=a[i][j];returnsum;}程序段A:intsumarrayrows(inta[M][N]){inti,j,sum=0;for(i=0;i<M,i++) for(j=0;j<N,j++)sum+=a[i][j];returnsum;}M=N=2048時主存的布局:0x1000x17C0x1800x1840x4000x4040xc000xc040x0FC指令數(shù)據(jù)asumI34I35a[0][0]a[0][1]?

?

?a[0][2047]a[1][0]a[1][1]?

?

??

?

?I1I2I33?

?

?for循環(huán)體假定數(shù)組在存儲器中按行優(yōu)先順序存放程序的局部性原理舉例2程序段A的時間局部性和空間局部性分析（1）數(shù)組a：訪問順序為a[0][0],a[0][1],……,a[0][2047];a[1][0],a[1][1],……,a[1][2047];

……，與存放順序一致，故空間局部性好！每個a[i][j]只被訪問一次，故時間局部性不考慮（2）變量sum：單個變量不考慮空間局部性；每次循環(huán)都要訪問sum，所以其時間局部性較好！（3）for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！循環(huán)體被連續(xù)重復執(zhí)行2048x2048次，所以時間局部性好！0x1000x17C0x1800x1840x4000x4040xc000xc040x0FC指令數(shù)據(jù)asumI34I35a[0][0]a[0][1]?

?

?a[0][2047]a[1][0]a[1][1]?

?

??

?

?I1I2I33?

?

?for循環(huán)體實際上優(yōu)化的編譯器使循環(huán)中的sum分配在寄存器中，最后才寫回存儲器！程序的局部性原理舉例2程序段B的時間局部性和空間局部性分析（1）數(shù)組a：訪問順序為a[0][0],a[1][0],……,a[2047][0];a[0][1],a[1][1],……,a[2047][1];……，與存放順序不一致，每次跳過2048個單元，空間局部性差?。〞r間局部性同程序A）（2）變量sum：（同程序A）（3）for循環(huán)體：（同程序A）0x1000x17C0x1800x1840x4000x4040xc000xc040x0FC指令數(shù)據(jù)asumI34I35a[0][0]a[0][1]?

?

?a[0][2047]a[1][0]a[1][1]?

?

??

?

?I1I2I33?

?

?for循環(huán)體程序A實際運行可能比程序B快幾十倍!!（因為B中每次循環(huán)均需訪問主存）加快訪存速度措施之三：引入Cache為什么引入Cache會加快訪存速度？在CPU和主存之間的一個快速小容量的存儲器其中總是存放最活躍（被頻繁訪問）的程序塊和數(shù)據(jù)由于程序訪問的局部性特征，大多數(shù)情況下，CPU能直接從這個高速緩存中取得指令和數(shù)據(jù)，而不必訪問主存。位于主存和CPU之間的高速緩存：Cache！Cache(高速緩存)是什么樣的？Cache是一種小容量高速緩沖存儲器，它由SRAM組成。Cache直接制作在CPU芯片內(nèi)，速度幾乎與CPU一樣快。程序運行時，CPU使用的一部分數(shù)據(jù)/指令會預先成批拷貝在Cache中，Cache的內(nèi)容是主存儲器中部分內(nèi)容的映象（復制）。當CPU需要從內(nèi)存讀(寫)數(shù)據(jù)或指令時，先檢查Cache，若有，就直接從Cache中讀取，而不用訪問主存儲器。012345678910111213141589143444101010主存中的信息按“塊”送到Cache中Cache存儲器主存儲器數(shù)據(jù)訪問過程：Cache的操作過程若被訪問信息不在cache中，稱為缺失或失靶(miss)若被訪問信息在cache中，稱為命中(hit)問題：什么情況下，CPU產(chǎn)生訪存要求？執(zhí)行指令時！Cache（高速緩存）的實現(xiàn)問題：要實現(xiàn)Cache機制需要解決哪些問題？如何分塊？主存塊和Cache之間如何映射?如何根據(jù)主存地址訪問到cache中的數(shù)據(jù)？Cache已滿時，怎么辦？寫數(shù)據(jù)時怎樣保證Cache和MM的一致性？……注意：Cache對程序員(編譯器)是否透明？為什么？是透明的，程序員(編譯器)在編寫/生成高級或低級語言程序時無需了解Cache是否存在或如何設置，感覺不到cache的存在。但是，對Cache深入了解有助于編寫出高效的程序！Cache的分塊把主存空間劃分成大小相等的主存塊（Block）Cache中存放一個主存塊的對應單位稱為槽（Slot）或行（line）或塊（Block）Cache行比主存塊少，多個主存塊映射到一個Cache行中012345678910111213141589143441010主存中的“1塊”送到Cache的“1行”中Cache存儲器主存儲器MMCache映射(CacheMapping)什么是Cache的映射功能？Cache行比主存塊少，多個主存塊映射到一個Cache行中把訪問的局部主存區(qū)域取到Cache中時，該放到Cache的何處？如何進行映射？將主存塊和Cache行按照以下三種方式進行映射直接(Direct)：每個主存塊映射到Cache的固定行中全相聯(lián)(FullAssociate)：每個主存塊映射到Cache的任意行中組相聯(lián)(SetAssociate)：每個主存塊映射到Cache的固定組中的任意一行中

TheSimplestCache:DirectMappedCacheDirectMappedCache（直接映射Cache)把主存的每一塊映射到一個固定的Cache行（槽）也稱模映射(ModuleMapping)映射關(guān)系為：

Cache行號=主存塊號modCache行數(shù)舉例：4=100mod16（假定Cache共有16行）(說明：主存第100塊應映射到Cache的第4行中。)特點：容易實現(xiàn)，命中時間短無需考慮淘汰（替換）問題但不夠靈活，Cache存儲空間得不到充分利用，命中率低

例如，需將主存第0塊與第16塊同時復制到Cache中時，由于它們都只能復制到Cache第0行，即使Cache其它行空閑，也有一個主存塊不能寫入Cache。這樣就會產(chǎn)生頻繁的Cache裝入。SKIP塊（行）都從0開始編號直接映射Cache組織示意圖假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大?。?13字=8K字=16行x512字/行主存大?。?20字=1024K字=2048塊x512字/塊Cache標記(tag)指出對應行取自哪個主存塊群指出對應地址位于哪個塊群例：如何對0220CH單元進行訪問？0220CH00000010001000001100B是第1塊群中的0001塊（即第17塊）中第12個單元！0000001Cache索引有效位（ValidBit）

V為有效位，為1表示信息有效，為0表示信息無效開機或復位時，使所有行的有效位V=0某行被替換后使其V=1某行裝入新塊時使其V=1通過使V=0來沖刷Cache（例如：進程切換時，DMA傳送時）通常為操作系統(tǒng)設置“cache沖刷”指令，因此，cache對操作系統(tǒng)程序員不是透明的！為何要用有效位來區(qū)分是否有效？假定主存地址為32位,按字節(jié)編址假定Cache是塊大小為1B的直接映射CacheCacheIndex:主存地址中的低N位CacheTag:主存地址中的剩余(32-N)位031CacheIndex01232-1N:2NBytesByte

0Byte

1Byte2Byte

3Byte2-1N:CacheTagExample:0x50Ex:0x030x50Cache“tag”ValidBit:NCacheData①②=否？③=1否？1塊內(nèi)地址占幾位？沒有塊內(nèi)地址，即0位Ex1:2NBDirectMappedCachewith1BBlocks極端例子（塊大小=1B）的特點利用了時間局部性：某字節(jié)不久又可能被用沒有利用空間局部性：某字節(jié)的鄰近字節(jié)不久可能也被用，但沒有被調(diào)到Cache（每次調(diào)入的一塊信息只有一個字節(jié)！）可以通過增大“塊大小”來利用空間局部性塊大小多少才合理呢？Ex1:2NBDirectMappedCachewith1BBlocksEx2:1KBDirectMappedCachewith32BBlocksFora2N

bytecache(本例中N=10):高(32-N)位始終就是CacheTag低N位分為2部分：最低的M位是快內(nèi)地址(假設塊大小為2M)。中間的（N-M）位為cacheindexCache

Index0123:

CacheDataB005

431:CacheTagExample:

0x50Ex:0x010x50ValidBit:31B1B31:B32B33B63:B992B1023:

Cache

TagByteSelectEx:

0x0010

9本例中塊為32B,所以M=5，index也為5位②①④③

1Ex3:64KBDirectMappedCachewith16BBlocks

主存和Cache之間直接映射，塊大小為16B。Cache的數(shù)據(jù)區(qū)容量為64KB，主存地址為32位，按字節(jié)編址。要求：說明主存地址如何劃分和訪存過程。

ByteoffsetVtag163212832323232DataWordByteBlockoffsetTagIndexMUX4K=64kB/16Blines=Mux161612231

20MemoryAddressdata④①②Hit③⑤

問題：Cache有多少行？容量多大？容量4Kx(1+16)+64Kx8=580Kbits=72.5KB,數(shù)據(jù)占64KB/72.5KB=88.3%

例:Cache直接映射和容量計算假設一個cache有64行且塊為16B第1200個字節(jié)映射到cache中哪一行？答：第11行。因為：[1200/16=75]mod64=11 10010110000主存地址32位，假設一個Cache:直接映射方式、16K行數(shù)據(jù)、塊大小為32位（4B），則其總?cè)萘繎摓槎嗌伲?/p>

答：Cache的存儲布局如下：32位地址劃分為16(tag)+14(index)+2(塊內(nèi))所以，Cache的大小為：214×(32+(32-14-2)+1)=214×49=784Kbits32–14–2bit

32bit2141bit若塊大小為16B呢？214×(128+(32-14-4)+1)=214×143=2288KbitsCache共有16Kx4B=64KB數(shù)據(jù)BACK注意思考：容量，塊大小，局部性利用之間的權(quán)衡全相聯(lián)映射Cache組織示意圖Cache標記（tag）指出對應行取自哪個主存塊主存tag指出對應地址位于哪個主存塊如何對01E0CH單元進行訪問？00000001111000001100B是第15塊中的第12個單元！每個主存塊可裝到Cache任一行中。假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大小：213字=8K字=16行x512字/行主存大?。?20字=1024K字=2048塊x512字/塊00000001111按內(nèi)容訪問，是相聯(lián)存取方式！如何實現(xiàn)按內(nèi)容訪問？直接比較！為何地址中沒有cache索引字段？因為可映射到任cache行中！舉例：全相聯(lián)映射cache（fullyassociative）無需Cache索引因為同時比較所有Cache項的標志沒有沖突缺失，因為只要有空閑Cache塊，都不會發(fā)生沖突Example:32位主存地址,

32B的塊.

比較器位數(shù)多長？N個

27（32-5）位

的比較器?。∟代表cache的行數(shù)）0431:

CacheDataB

0:CacheTag(27bitslong)V:B

1B

31:B

32B33B63:

CacheTagByte

Select=====:問題：需要多少個比較器？每行一個比較器！組相聯(lián)映射（SetAssociative）組相聯(lián)映射結(jié)合直接映射和全相聯(lián)映射的特點將Cache所有行分組，把主存塊映射到Cache固定組的任一行中。也即：組間模映射、組內(nèi)全映射。映射關(guān)系為：

Cache組號=主存塊號modCache組數(shù)

特點：結(jié)合直接映射和全相聯(lián)映射的優(yōu)點。當Cache組數(shù)為1時，變?yōu)橄嗦?lián)映射；當每組只有一行時，變?yōu)橹苯佑成洹Ｃ拷M2或4行（稱為2-路或4-路組相聯(lián)）較常用。通常每組4行以上很少用。在較大容量的L2Cahce和L3Cahce中使用4-路以上。指出對應行取自哪個主存組群指出對應地址位于哪個主存組群中將主存地址標記和對應Cache組中每個Cache標記進行比較！例：如何對0120CH單元進行訪問？00000001

001000001100B是第1組群中的001塊（即第9塊）中第12個單元。

所以，映射到第一組中。假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大?。?13字=8K字=16行x512字/行主存大小：220字=1024K字=2048塊x512字/塊Cache索引例：2路組相聯(lián)Two-waySetAssociativeCacheN-waysetassociativeN個直接映射的行并行操作Example:Two-waysetassociativecacheCacheIndex選擇其中的一個Cache行集合（共2行）對這個集合中的兩個Cache行的Tag并行進行比較根據(jù)比較結(jié)果確定信息在哪個行，或不在Cache中CacheIndexCache

DataBlock0CacheTagValid:::CacheDataBlock0CacheTagValid:::Mux01

=

=ORHit④①AdrTag②②③③Cache

Block⑤⑤三種映射方式總結(jié)根據(jù)index找到唯一一行無index根據(jù)index找到一組一組中有2或N行命中率、缺失率、缺失損失Hit:要訪問的信息在Cache中HitRate(命中率α)：在Cache中的概率HitTime(命中時間tc)

：在Cache中的訪問時間，包括：判斷時間+Cache訪問Miss:要找的信息不在Cache中MissRate(缺失率1–α)MissPenalty(缺失損失tm)：訪問一個主存塊所花時間tc<<tm（Why?）平均訪問時間 Tave=αtc+(1-α)(tc+tm)=tc+(1-α)tm要提高平均訪問速度，必須提高命中率！關(guān)聯(lián)度三種映射方式直接映射：唯一映射（只有一個可能的位置）全相聯(lián)映射：任意映射（每個位置都可能）N-路組相聯(lián)映射：N-路映射（有N個可能的位置）什么叫關(guān)聯(lián)度？一個主存塊映射到Cache中時，可能存放的位置個數(shù)直接映射：關(guān)聯(lián)度最低，為1全相聯(lián)映射：關(guān)聯(lián)度最高，為Cache行數(shù)N-路組相聯(lián)映射：關(guān)聯(lián)度居中，為N關(guān)聯(lián)度和missrate有什么關(guān)系呢？和命中時間的關(guān)系呢？例子：Cache缺失和關(guān)聯(lián)度（直接映射）Cache共4行：Cache行號=主存塊號mod4缺失5次例子：Cache缺失和關(guān)聯(lián)度（組相聯(lián)）Cache共4行，但只有2組（每組2行）Cache組號=主存塊號mod2缺失4次例子：Cache缺失和關(guān)聯(lián)度（全相聯(lián)）缺失3次關(guān)聯(lián)度越高，缺失次數(shù)越少！Cache共4行標記位大小與關(guān)聯(lián)度關(guān)聯(lián)度不同，總的標記位數(shù)不同，也即額外空間開銷不同！全相聯(lián)直接映射組相聯(lián)關(guān)聯(lián)度越高，總的標記位數(shù)越多，額外空間開銷越大！(下面的比較符號代表性能的優(yōu)劣）關(guān)聯(lián)度越高：

命中率越高(缺失次數(shù)越少)！直<組<全 總的標記位數(shù)越多，額外空間開銷越大！直>組>全

行選擇和標記比較越耗時，命中時間也就越長!直>組>全新的問題： 當我們從主存取出一個新塊， 選擇一個有映射關(guān)系的Cache行（組）， 但該Cache位置已被占滿， 則必須考慮從Cache中調(diào)走一個已有的主存塊誰走誰留？對性能又有什么影響？何時需要替換？直接映射Cache:映射唯一，毫無選擇，目標行不空時，直接替換，無須考慮算法N路組相聯(lián)Cache:每個主存數(shù)據(jù)有N個Cache行可選擇當N個行都不空時，需考慮替換算法全相聯(lián)Cache:每個主存數(shù)據(jù)可存放到Cache任意行，當Cache全滿時，需考慮替換算法替換(Replacement)算法假定第0組的兩行分別被主存第0和8塊占滿，此時若需調(diào)入主存第16塊,該怎么辦？這就是淘汰策略問題，也稱替換算法。16塊第0組中必須調(diào)出一塊，那么，調(diào)出哪一塊呢？替換(Replacement)算法常用替換算法有：先進先出FIFO（first-in-first-out）最近最少用LRU（least-recentlyused）最不經(jīng)常用LFU（least-frequentlyused）隨機替換算法（Random）等等這里的替換策略和后面的虛擬存儲器所用的替換策略類似，將是以后操作系統(tǒng)課程的重要內(nèi)容。替換算法-先進先出（FIFO）總是把最先進入的那一塊淘汰掉。例：假定主存中的5塊{1,2,3,4,5}同時映射到Cache同一組中，對于同一地址流，考察3行/組、4行/組的情況。由此可見，F(xiàn)IFO命中率并不隨組的增大而提高。1*1*4231*442*13*4*51*1*2355*2*341234125123452312251*255*34

√√√

3行/組1*1*4231*442431*512*3*15*421*2232335125452*

√√

1*21*4*3334行/組替換算法-最近最少用(LRU)總是把最近最少用的那一塊淘汰掉。例：假定主存中的5塊{1,2,3,4,5}同時映射到Cache同一組中，對于同一地址流，考察3行/組、4行/組、5行/組的情況。31221131433325224234132221415152543

√√

√√√√√√√√√√√44145121234125123453134513行/組4行/組5行/組替換算法-LRU命中率隨組的增大而提高。當分塊局部化范圍(即：某段時間集中訪問的存儲區(qū))超過了Cache存儲容量時，命中率變得很低。極端情況下，假設地址流是1,2,3,4,12,3,4,1,……，而Cache每組只有3行，那么，不管是FIFO，還是LRU算法，其命中率都為0。這種現(xiàn)象稱為顛簸(Thrashing/PingPong)。該算法具體實現(xiàn)時，并不是通過移動塊來實現(xiàn)的，而是通過給每個cache行設定一個計數(shù)器，根據(jù)計數(shù)值來記錄這些主存塊的使用情況。這個計數(shù)值稱為LRU位。替換算法-LRU計數(shù)器變化規(guī)則：每組4行時，計數(shù)器有2位。計數(shù)值越小則說明越被常用。命中時，被訪問行的計數(shù)器置0，比其低的計數(shù)器加1，其余不變。未命中且該組未滿時，新行計數(shù)器置為0，其余全加1。未命中且該組已滿時，計數(shù)值為3的那一行中的主存塊被淘汰，新行計數(shù)器置為0，其余加1。123412512345543203211243320112532130125410231254021312542103123410321234032112343210123210121010最不經(jīng)常用（LFU）算法：

替換掉Cache中引用次數(shù)最少的塊。LFU也用與每個行相關(guān)的計數(shù)器來實現(xiàn)。（這種算法與LRU有點類似，但不完全相同。）隨機算法：

隨機地從候選的cache行中選取一個淘汰，與使用情況無關(guān)。

（模擬試驗表明，隨機替換算法在性能上只稍遜于基于使用情況的算法。而且代價低！）替換算法-其他算法舉例假定計算機系統(tǒng)主存空間大小為32Kx16位（按字編址。每字16位），且有一個4K字的4路組相聯(lián)Cache，主存和Cache之間的數(shù)據(jù)交換塊的大小為64字。假定Cache開始為空，處理器順序地從存儲單元0、1、…、4351中取數(shù)，一共重復10次。設Cache比主存快10倍。采用LRU算法。試分析Cache的結(jié)構(gòu)和主存地址的劃分。說明采用Cache后速度提高了多少？答：主存：32K字主存地址共15位 32K字=512塊x64字/塊

Cache：4K字=64行（16組x4行/組）x64字/行主存地址劃分為：字號標志位組號6454351/64=67.9，所以屬于第67塊，即實際上是對前68塊連續(xù)訪問10次。001000011111111

且：cache組號=塊號（0,1…67）mod16舉例第0組第1組第2組第3組第4組…………第15組第0行第1行第2行第3行0/64/481/65/492/66/503/67/514…………1516/0/6417/1/6518/2/6619/3/6720…………3132/1633/1734/1835/1936…………4748/3249/3350/3451/3552…………63LRU算法：第一次循環(huán),每一塊的第一字未命中,其余都命中;以后9次循環(huán),有20塊的第一字未命中,其余全部命中.所以,命中率p為(43520-68-9x20)/43520=99.43%速度提高：tm/ta=tm/(tc+(1-p)tm)=10/(1+10x(1-p))=9.5倍到目前為止介紹的都是有關(guān)cache的“讀”CPU執(zhí)行指令指令中給出主存地址按主存地址和當前計算機中的cache設計硬件完成：先訪問cache并判斷是否命中命中則從cache中讀數(shù)據(jù)缺失則從主存中讀，同時將相關(guān)塊復制入cache復制的時候如有沖突，則進行替換還有一種讀：每條指令在開始執(zhí)行之前都要從主存取出，而指令的地址有專門的寄存器（PC）給出，此時CPU根據(jù)PC內(nèi)容去訪存，也會產(chǎn)生同上一樣的cache讀過程。學了第6章后會更清楚數(shù)據(jù)cache指令cache處理Cache讀比Cache寫更容易，故指令Cache比數(shù)據(jù)Cache容易設計Cache性能評估CPU時間：CPU執(zhí)行時間+等待內(nèi)存訪問時間。即：等待內(nèi)存訪問時間即為Cache缺失引起的簡單來說，將讀和寫綜合考慮：(訪存次數(shù)/程序)x缺失率x缺失損失(指令條數(shù)/程序)x(缺失數(shù)/指令)x缺失損失總的來說:Cache性能由缺失率確定，缺失率和關(guān)聯(lián)度、替換算法有關(guān)。缺失率則和Cache大小、Block大小、Cache級數(shù)等有關(guān)Cache大?。篊ache越大，Miss率越低，但成本越高！Block大小：Block大小與Cache大小有關(guān)，且不能太大，也不能太??！BlockSizeTradeoff(塊