第七章 存儲器層次結(jié)構(gòu)

第七章存儲器層次結(jié)構(gòu)7.1存儲器概述7.2主存儲器7.3高速緩沖存儲器7.4Cache性能的評估與提高7.5虛擬存儲器7.1概述一、存儲器的分類1、按存儲介質(zhì)分：

半導體存儲器（TTL、MOS）磁表面存儲器光盤存儲器

2、按存取方式分：

隨機訪問存儲器（RAM、ROM）串行訪問存儲器（磁盤、磁帶）3、按在計算機中的作用分：

主存、輔存、緩存RAMROM磁盤、磁帶、光盤

高速緩沖存儲器（Cache）存儲器主存儲器輔助存儲器MROMPROMEPROMEEPROM靜態(tài)RAM動態(tài)RAM易失非易失高低小大快慢輔存寄存器緩存主存磁盤光盤磁帶光盤磁帶速度容量價格位／1.存儲器三個主要特性的關(guān)系二、存儲器的層次結(jié)構(gòu)CPUCPU主機緩存CPU主存輔存2.緩存主存層次和主存輔存層次緩存主存輔存主存10ns20ns200nsms（速度）（容量）7.2主存儲器1、主存的主要性能指標2、主存和cpu聯(lián)系3、半導體讀寫存儲器4、只讀存儲器5、存儲器與cpu的連接

S（容量）=W（存儲字數(shù)）*L（字長（位））難點：對于一定容量的存儲器，按字節(jié)或字尋址訪問范圍是不同的。例：設地址線24根：按字節(jié)尋址224=16M若字長16位：按字尋址8M

若字長32位：按字尋址4M一、

主存的技術(shù)指標(1)存儲容量主存存放二進制代碼的總位數(shù)(2)存儲速度一、

主存的技術(shù)指標讀出時間寫入時間存儲器的訪問時間

存取時間存取周期讀周期寫周期

連續(xù)兩次獨立的存儲器操作（讀或?qū)懀┧璧淖钚￠g隔時間

即單位時間內(nèi)存儲器存取的信息量，用字/秒，字節(jié)/秒，或位/秒為單位進行表示。例：存取周期為500ns，每個存取周期可訪問16位數(shù)據(jù)，

則存儲器帶寬為：16bit/500ns=32M位/秒存儲器帶寬決定了以存儲器為中心的機器獲得信息的傳輸速度，它是改善機器瓶頸的一個關(guān)鍵因素。為了提高存儲器帶寬，可采用如下措施：1、縮短存取周期2、增加存儲字長，使每個存取周期可讀/寫更多位3、增加存儲體，使用存儲器分段的交叉存取技術(shù)

(3)存儲器的帶寬二、主存和CPU的聯(lián)系MDRMARCPU主存讀數(shù)據(jù)總線地址總線寫芯片容量三、半導體讀寫存儲器1.半導體存儲芯片的基本結(jié)構(gòu)譯碼驅(qū)動存儲矩陣讀寫電路1K×4位16K×1位8K×8位片選線讀/寫控制線地址線…數(shù)據(jù)線…地址線（單向）數(shù)據(jù)線（雙向）104141138二、半導體存儲芯片簡介1.半導體存儲芯片的基本結(jié)構(gòu)譯碼驅(qū)動存儲矩陣讀寫電路片選線讀/寫控制線地址線…數(shù)據(jù)線…片選線讀/寫控制線（低電平寫高電平讀）（允許讀）CSCEWE（允許寫）WEOE存儲芯片片選線的作用用16K×1位的存儲芯片組成64K×8位的存儲器

32片當?shù)刂窞?5535時，此8片的片選有效8片16K×1位8片16K×1位8片16K×1位8片16K×1位0,015,015,70,7

讀/寫控制電路

地址譯碼器

字線015……16×8矩陣………07D07D位線讀/寫選通A3A2A1A0……2.半導體存儲芯片的譯碼驅(qū)動方式(1)線選法00000,00,7…0…07…D07D讀/寫選通

讀/寫控制電路

A3A2A1A0A40,310,031,031,31

Y地址譯碼器

X地址譯碼器

32×32矩陣……A9I/OA8A7A56AY0Y31X0X31D讀/寫……(2)重合法00000000000,031,00,31……I/OD0,0讀3、靜態(tài)RAM芯片舉例（1）Intel2114外特性存儲容量1K×4

位I/O1I/O2I/O3I/O4A0A8A9WECSVCCGNDIntel2114…ACSDOUT地址有效地址失效片選失效數(shù)據(jù)有效數(shù)據(jù)穩(wěn)定高阻（2）靜態(tài)RAM讀時序tAtCOtOHAtOTDtRC片選有效讀周期

tRC

地址有效下一次地址有效讀時間

tA

地址有效數(shù)據(jù)穩(wěn)定tCO

片選有效數(shù)據(jù)穩(wěn)定tOTD

片選失效輸出高阻tOHA

地址失效后的數(shù)據(jù)維持時間ACSWEDOUTDIN(3)靜態(tài)RAM(2114)寫

時序tWCtWtAWtDWtDHtWR寫周期

tWC

地址有效下一次地址有效寫時間

tW

寫命令WE

的有效時間tAW

地址有效片選有效的滯后時間tWR

片選失效下一次地址有效tDW

數(shù)據(jù)穩(wěn)定

WE失效tDH

WE失效后的數(shù)據(jù)維持時間時序與控制行時鐘列時鐘寫時鐘

WERASCAS

A'6A'0存儲單元陣列基準單元行譯碼列譯碼器再生放大器列譯碼器讀出放大基準單元存儲單元陣列行譯碼

I/O緩存器數(shù)據(jù)輸出驅(qū)動數(shù)據(jù)輸入寄存器

DINDOUT~行地址緩存器列地址緩存器

4、動態(tài)RAM芯片舉例（1）RAM4116(16K×

1位)外特性

讀放大器

讀放大器

讀放大器………………………06364127128根行線Cs01271128列選擇讀/寫線數(shù)據(jù)輸入I/O緩沖輸出驅(qū)動DOUTDINCs

（2）4116(16K×1位)芯片讀

原理

讀放大器

讀放大器

讀放大器……63000I/O緩沖輸出驅(qū)動OUTD

讀放大器

讀放大器

讀放大器………………………06364127128根行線Cs01271128列選擇讀/寫線數(shù)據(jù)輸入I/O緩沖輸出驅(qū)動DOUTDINCs…

4116(16K×1位)芯片寫

原理數(shù)據(jù)輸入I/O緩沖I/O緩沖DIN讀出放大器

讀放大器630(3)動態(tài)RAM時序

行、列地址分開傳送寫時序行地址RAS有效寫允許WE有效(高)數(shù)據(jù)

DOUT

有效數(shù)據(jù)

DIN

有效讀時序行地址RAS有效寫允許WE有效(低)列地址CAS有效列地址CAS有效

5.動態(tài)RAM和靜態(tài)RAM的比較DRAMSRAM存儲原理集成度芯片引腳功耗價格速度刷新電容觸發(fā)器高低少多小大低高慢快有無主存緩存四、只讀存儲器（ROM）1.掩模ROM(MROM)行列選擇線交叉處有MOS管為“1”行列選擇線交叉處無MOS管為“0”2.PROM(一次性編程)VCC行線列線熔絲熔絲斷為“0”為“1”熔絲未斷3.EPROM(多次性編程)(1)N型溝道浮動柵MOS電路G柵極S源D漏紫外線全部擦洗D端加正電壓形成浮動柵S與D不導通為“0”D端不加正電壓不形成浮動柵S與D導通為“1”SGDN+N+P基片GDS浮動柵

SiO2+++++___

…控制邏輯Y譯碼X譯碼數(shù)據(jù)緩沖區(qū)Y控制128×

128存儲矩陣……PD/ProgrCSA10A7…A6A0……DO0…DO7112…A7A1A0VSSDO2DO0DO1…27162413…VCCA8A9VPPCSA10PD/ProgrDO3DO7…(2)2716EPROM的邏輯圖和引腳PD/ProgrPD/Progr功率下降/編程輸入端

讀出時為低電平4.EEPROM(多次性編程)電可擦寫局部擦寫全部擦寫5.FlashMemory(閃速型存儲器)比EEPROM快EPROM價格便宜集成度高EEPROM電可擦洗重寫具備RAM功能用1K

×

4位存儲芯片組成1K

×

8位的存儲器？片五、存儲器與CPU的連接1.存儲器容量的擴展(1)位擴展（增加存儲字長）10根地址線8根數(shù)據(jù)線DD……D0479AA0???21142114CSWE2片(2)字擴展（增加存儲字的數(shù)量）用1K

×

8位存儲芯片組成2K

×

8位的存儲器11根地址線8根數(shù)據(jù)線？片2片1K×8位1K×8位D7D0???????????????WEA1A0???A9CS0A10

1CS1(3)字、位擴展用1K

×

4位存儲芯片組成4K

×

8位的存儲器8根數(shù)據(jù)線12根地址線WEA8A9A0...D7D0…A11A10CS0CS1CS2CS3片選譯碼……………………1K×41K×41K×41K×41K×41K×41K×41K×4？片8片

2.存儲器與CPU的連接

(1)地址線的連接(2)數(shù)據(jù)線的連接(3)讀/寫命令線的連接(4)片選線的連接(5)合理選擇存儲芯片(6)其他時序、負載例：某機器字長是16位，cpu可輸出20條地址線，16條數(shù)據(jù)線，一條控制線we.實際使用主存空間為64K*16位。由16k*8位的ROM芯片4片構(gòu)成32K*16位的ＲＯＭ空間；由１６K*16位的ＲＡＭ芯片２片構(gòu)成32K*16位的ＲＡＭ空間．要求畫出ｃｐｕ與主存之間的連線圖，并說明實際存儲器中ROM和RAM的地址范圍。六、提高訪存速度的措施采用高速器件調(diào)整主存結(jié)構(gòu)1.單體多字系統(tǒng)W位W位W位W位W位

地址寄存器

主存控制器......單字長寄存器數(shù)據(jù)寄存器存儲體采用層次結(jié)構(gòu)Cache–主存增加存儲器的帶寬

加長存儲器的字長2.多體并行系統(tǒng)(1)高位交叉M0……M1……M2M3…………體內(nèi)地址體號體號地址000000000001001111010000010001011111100000100001101111110000110001111111順序編址各個體并行工作M0地址01……n－1M1nn+1……2n－1M22n2n+13n－1M33n3n+14n－1…………地址譯碼體內(nèi)地址體號體號(1)高位交叉M0……M1……M2M3…………

體號體內(nèi)地址地址000000000001000010000011000100000101000110000111111100111101111110111111(2)低位交叉各個體輪流編址M0地址04……4n－4M115……4n－3M2264n－2M3374n－1…………地址譯碼

體號體內(nèi)地址

體號(2)低位交叉各個體輪流編址低位交叉的特點在不改變存取周期的前提下，增加存儲器的帶寬時間單體訪存周期單體訪存周期啟動存儲體0啟動存儲體1啟動存儲體2啟動存儲體37.3高速緩沖存儲器Cache問題的提出避免CPU“空等”現(xiàn)象CPU和主存（DRAM）的速度差異緩存CPU主存容量小速度高容量大速度低程序訪問的局部性原理一、局部性原理CPU從主存取指令或取數(shù)據(jù)，在一定時間內(nèi)，只是對主存局部地址區(qū)域的訪問，稱為程序訪問的局部性原理。分為時間局部性和空間局部性兩種：1、時間局部性如果一個數(shù)據(jù)項被引用，在不久的將來它很可能再次被引用。例如：循環(huán)程序中某個變量的引用。2、空間局部性如果一個數(shù)據(jù)項被引用，那么與它地址相近的數(shù)據(jù)項可能很快也會被引用。例如：數(shù)組處理。基于程序訪問的局部性原理，使得存儲器層次結(jié)構(gòu)系統(tǒng)變得可行。由于每次數(shù)據(jù)只能在相鄰的兩級存儲器中進行交換，因此存儲器管理是以兩級存儲器為單位進行的。相鄰兩級存儲器之間信息交換的最小單位稱為塊（block）

兩級存儲器層次結(jié)構(gòu)二、命中與缺失

兩級存儲器可以分為高層存儲器和低層存儲器，如果CPU要訪問的字塊已經(jīng)在高層存儲器中，就稱為命中（hit），反之稱為缺失（miss）。存儲器訪問命中的概率稱為命中率（hitrate）。

缺失率（missrate）則是指存儲器訪問失效的概率。

命中時間是訪問高層存儲器所需時間，包括了判斷本次訪問是命中還是失效的時間。缺失損失包括了用低層存儲器中相應的塊替換高層存儲器中的塊的時間以及將所訪問的數(shù)據(jù)傳送到處理器的時間。因為高層存儲器與低層存儲器相比容量小、速度快，所以命中時間要遠低于缺失損失，也就是說缺失損失對存儲器性能的影響更大。

根據(jù)時間局部性，我們應盡可能地將最近用過的數(shù)據(jù)和指令存放在靠近CPU的存儲器中。根據(jù)空間局部性，將與最近使用過的數(shù)據(jù)和指令相鄰近的數(shù)據(jù)和指令也盡可能存放在高層存儲器中。在存儲器層次結(jié)構(gòu)中，靠近CPU的存儲器容量雖小但速度更快。介于CPU與主存之間的高速緩沖存儲器稱為Cache。

在下圖中我們可以看到Cache中有字串X1,X2……X(n-1),當訪問字Xn時，將發(fā)生缺失，這時需要將主存中的字Xn調(diào)入到Cache中。三、主存與Cache的地址映射使用Cache有兩個問題需要解決：第一，怎樣知道一個數(shù)據(jù)項是否在Cache中？第二，如果在怎樣找到它？

如果每個字都放在Cache中確定的位置，那么如果它在Cache中，就知道如何找到它。這就是地址映射所解決的問題。1、直接映射（多對一映射）最簡單的解決方法是采用直接映射（directmapped），即主存中的每個信息塊只能對應Cache中的一個特定塊。可以用如下規(guī)則建立起主存與Cache之間的對應關(guān)系:Cache單元地址=(主存中的塊地址ma)mod（Cache中的塊數(shù)k）直接映射

000001010011100101110111CacheMainMemory0000100101010010110110001101011100111101

多對一映射，多個內(nèi)存塊競爭同一Cache塊位置，易產(chǎn)生沖突而造成頻繁的塊替換，故效率不高，但實現(xiàn)機制簡單。2、直接映射方式下Cache塊的構(gòu)成因為有多個存儲器地址對應到同一個Cache塊上，所以是多對一關(guān)系，因此CPU在某一Cache塊中訪問到的數(shù)據(jù)具體是哪一個內(nèi)存單元中的數(shù)據(jù)無法確定，為此，在每個Cache塊中增加一個標記項（tag），用來存放存儲器地址的高位。還需要一種方法判斷Cache塊中沒有數(shù)據(jù)，例如：當處理器啟動時，Cache是空的，而此時的標記字段沒有意義，為此，在每個Cache塊中再增加一個有效位字段，用來說明此塊中是否為空，最后Cache塊的構(gòu)成如下：有效位（1位）標記位（30-m位）數(shù)據(jù)位（32位）NY10110101….01………N000001010111四、訪問CacheCPU以32位的內(nèi)存地址訪問Cache，此內(nèi)存地址首先轉(zhuǎn)換成主存塊地址，用主存塊地址的低m位定位Cache塊，若有效位為Y，將Cache塊中的標記與主存塊地址的高（30-m）位比較，若相等，則命中，否則缺失。例：假設一個Cache的大小為8個字，采用直接映射方式。下圖說明了該Cache如何響應處理器的讀請求。假設CPU需要訪問的主存塊地址序列為22、26、22、26、16、3、16、18。來自CPU的主存物理地址由幾部分組成如下：

索引（下標）：用于選取Cache中的單元。

標記：用于與Cache中每一單元的標志進行比較。

Ｂyteoffset：字節(jié)偏移，由塊大小確定。

在直接映射方式中，當CPU給出一地址，首先由索引確定Cache中的一單元，然后地址標志和該單元的單元標記進行比較。若相同且Cache中的該單元已經(jīng)置了有效位，就命中，即要訪問的信息塊在Cache中，否則缺失。CPU地址與Cache結(jié)構(gòu)的關(guān)系

下標用于選取Cache中的單元，假如下標有n位，則下標可以有2n個值，因此Cache中的單元數(shù)必須是以2為基數(shù)的指數(shù)在MIPS機器結(jié)構(gòu)中，一個字由四個字節(jié)組成，因此CPU地址的最后兩位用作塊偏移地址，用于從信息塊中選取所需字節(jié)Cache的實際位數(shù)為： Cache單元數(shù)×(字塊大小﹢標志位數(shù)﹢有效位數(shù))，以上機器的Cache實際位數(shù)為2n×(32﹢(32﹣n﹣2)﹢1)=2n×(63﹣n)。例：Cache中的位數(shù)假設一個直接映射的Cache有64KB數(shù)據(jù)，塊大小為一個字，地址為32位，那么該Cache共需要多少位？【解答】塊大小為1個字，則Cache共有16K塊，那么Cache塊地址為14位，每個Cache塊中標記字段為30-14=16位，有效位1位，則每個Cache塊共1+16+32=49位Cache大小總計為16K×49bit=784Kbit=98KB

即：該Cache實際大小約為Cache數(shù)據(jù)容量的1.5倍五、Cache讀缺失處理數(shù)據(jù)缺失和指令缺失的處理方法完全相同，處理指令缺失,流程如下所示：1、取得實際指令地址（當前PC-4）。2、指示主存根據(jù)取得的指令地址進行讀操作并等待操作完成。3、從指令地址中獲取索引號來找到Cache中相應的單元，將從主存中讀出的數(shù)據(jù)寫入Cache，然后再將指令地址的高位寫入Cache的單元標志字段Ｔag，并置有效位V為Ｙ。4、從Cache中讀取指令，重新開始指令的執(zhí)行。Cache實例介紹

為了滿足在一個時鐘周期內(nèi)同時得到指令位和數(shù)據(jù)位的這種要求，DECStation3100工作站機器使用了兩個獨立的Cache，指令Cache和數(shù)據(jù)Cache。下圖展示了DECStation3100工作站數(shù)據(jù)Cache的結(jié)構(gòu)。

對這兩個Cache(指令cache和數(shù)據(jù)cache)的讀操作如下：

1．給這兩個緩存分別送入不同的地址。這兩個地址分別來自于PC(用于讀指令)和ALU(用于數(shù)據(jù)訪問)。

2．假如Cache命中，我們可以從數(shù)據(jù)線上直接讀取信息。如果發(fā)生失效，就把地址送入主存，將主存讀到的信息寫入Cache。DECStation3100的Cache結(jié)構(gòu)

寫操作的情況不同。對存儲指令，我們僅將數(shù)據(jù)寫入Cache而不改變主存的內(nèi)容會導致稱作Cache和主存的不一致。1、直寫信息在被寫入Cache的同時，利用CPU和主存之間的數(shù)據(jù)通路寫入主存的對應塊中，稱作直寫（writethrough）。2、回寫除了直寫，另外一個策略就是回寫（writeback），即信息只寫入Cache，僅當被修改過的單元被替換出Cache時，才將它寫入主存的相應存儲塊中。DECStation3100的寫Cache操作采用直寫策略，流程如下：1、使用地址的15～2位作為索引號查找Cache中映射的單元。2、將地址的31～16位作為標志寫入Cache特定單元的標志字段，把數(shù)據(jù)寫入該單元的數(shù)據(jù)位，置有效位為Ｙ。3、將數(shù)據(jù)寫入主存中的相應塊。

采用直寫策略，每一次寫Cache都將引起一次主存的寫操作。處理器將停下來等待寫主存完成，性能并不好。解決方法是設置寫緩沖器(writebuffer)。采用回寫策略，其性能很高，特別是當處理器產(chǎn)生寫操作的速度比主存完成寫操作的速度快時。但是這種策略要比直寫復雜得多。六、空間局部性原理的利用為了利用空間局部性原理，我們需要增加Cache的字塊容量。當發(fā)生缺失時，我們需要把引起缺失的字塊的相鄰幾個字也讀入Cache，因為鄰近的幾個字在將來可能會被用到。處理器采用前文提到的映射公式從Cache中找到需要訪問的塊：

(主存中的塊地址)modulo（Cache中的塊數(shù)）主存中的塊地址可以通過字地址除以每一塊的字數(shù)求得（或是由字節(jié)地址除以每一塊的字節(jié)數(shù)）。每個塊為四個字的Cache

例：

某Cache大小為64塊，塊大小為16字節(jié)。求字節(jié)地

址1200所映射Cache的塊號。

塊地址所映射的Cache中的塊號為（75mod64）＝11其中包括了位于：字節(jié)地址11×16—字節(jié)地址11×16+(16-1)之間的所有地址

多字塊和單字塊，處理讀Cache缺失是一樣的，總是將主存中的整個字塊調(diào)入Cache。

多字塊和單字塊，處理寫Cache缺失不一樣。因為多字塊Cache的塊包含不止一個字，我們不能直接寫入標志Tag和數(shù)據(jù)。為解決這個問題，在執(zhí)行寫操作前要先比較標志Tag，如果命中就將數(shù)據(jù)直接寫入Cache。假如缺失，就需要先訪問主存，讀取主存的塊（四個字）把它寫入Cache，然后處理器再向Cache寫入引起寫缺失的字。

與單字塊Cache不同的是，多字塊Cache寫之前需要先訪問主存將引起寫失效的字所在的塊從內(nèi)存讀出然后寫入Cache。增加塊大小能有效地降低失效率，因為大塊較好地利用了空間局部性。當塊的容量增大時，Cache所能容納的塊數(shù)減少，映射到Cache的主存塊之間的競爭就非常激烈。因此當Cache的大小超過某個上限值時再繼續(xù)增加塊大小，反而會使失效率上升。因而可知：當Cache容量較小時，不能使塊取得過大。塊大小與缺失率的關(guān)系：見P439

增加塊大小引起的另一個問題是增大了缺失損失。

兩種方法可以適量減少缺失損失：1、一種叫作預取法（earlyrestart）。CPU在接收到第一個它所需要的字時就開始執(zhí)行，而不是等到完整的塊到達時才執(zhí)行。適用于取指令，而對取數(shù)據(jù)則效用不大。2、另一種稱為申請字優(yōu)先法（criticalwordfirst）。它讓主存首先傳輸處理器申請訪問的字，其余的字稍后再傳。但需要復雜的機制來重新組織存儲器。

還可以通過提高存儲器帶寬減少缺失損失。7.3Cache性能的評估與提高一、Cache性能的測量與分析CPU時間分為CPU執(zhí)行程序的時鐘周期和CPU等待存儲系統(tǒng)的時鐘周期，正常情況下，把Cache訪問命中的開銷看成是CPU正常執(zhí)行周期中的一部分，因此有：

CPU時間=（CPU執(zhí)行程序的時鐘周期數(shù)+存儲器引起阻塞的時鐘周期數(shù)）×時鐘周期長度存儲器引起阻塞的時鐘周期數(shù)主要來自Cache缺失，而此Cache缺失主要指讀缺失和寫缺失兩部分，在此僅討論存儲器系統(tǒng)的簡化模型，則讀和寫缺失引起的阻塞時間可定義為：定量計算這種Cache/主存存儲器層次結(jié)構(gòu)對CPU性能的影響程度

例6.3假設我們用gcc檢測一機器，發(fā)現(xiàn)指令Cache缺失率是2%，數(shù)據(jù)Cache缺失率4%。在不考慮訪存等待延遲時所有指令的平均執(zhí)行時間（CPI）為2個時鐘周期。Cache的缺失損失為40個時鐘周期。（gcc程序中各類指令的使用頻率見第四章的圖4.54。）若有一個從不產(chǎn)生缺失的理想Cache，則機器速度能快多少？【解答】假設指令總數(shù)為I，則由指令Cache失效引起的總

的失效損失為I×2%×40＝0.80I。gcc程序中存儲器訪問指令的頻率是36%，因此由數(shù)據(jù)Cache失效引起的總的失效損失為：I×36%×4%×40＝0.56I。

因此訪存等待時鐘周期數(shù)為0.80I＋0.56I=1.36I。考慮到訪存等待延遲，CPI由2變成了2＋1.36=3.36。所以這種Cache/主存存儲層次結(jié)構(gòu)對CPU性能的影響是使CPI由2變成了3.36，CPU時間增大了0.68。如果CPU的速度更快，而存儲器系統(tǒng)保持原狀，整體性能會怎么樣？CPI由2減為1，帶有Cache缺失的系統(tǒng)CPI=1+1.36=2.36，理想Cache系統(tǒng)性能是它的2.36/1=2.36倍。CPU時間中用來處理訪存的時間所占比率也由 1.36/3.36=41%增加到了1.36/2.36＝58%同樣地，增加處理器時鐘頻率但不改變存儲器結(jié)構(gòu),反而會增加由于Cache失效帶來的性能損失。見下例。例6.4為提高上題中機器的性能，將它的時鐘頻率加倍。因為主存的速度不變，所以用于Cache失效處理的絕對時間不變，假設Cache的失效率與上題相同。機器的時鐘頻率加快后，它的性能怎樣？【解答】

因為機器的時鐘頻率加倍，而用于Cache失效處理的絕對時間沒有變化，所以Cache缺失損失要加倍，由40變?yōu)?0。假設I為指令總數(shù)，則有：訪存等待時鐘周期數(shù)＝(2%×80)×I＋36%×(4%×80)×I＝2.75I

因此時鐘頻率較快機器的CPI為4.75。使用這一節(jié)介紹的CPU時間公式，我們將兩個時鐘頻率不同機器的性能作個比較：時鐘頻率加快了一倍，但機器的性能卻只是原有的1.41倍，而不是2倍。因此對于CPU時鐘頻率較高、CPI較小的處理器（越快的處理器），Cache缺失對性能的影響是更嚴重的。二、提高Cache性能1、降低Cache的缺失率：通過改變映射關(guān)系實現(xiàn)①全關(guān)聯(lián)映射（一對多映射）這種映射中，一個主存塊可放到Cache中任何一個塊的位置，減少了多塊競爭同一個位置的情況，從而可減少缺失率。但這種情況下，為了找到某個數(shù)據(jù)，需與每個Cache塊中的標記進行比較，只有相同的那個Cache塊被選中，否則為不命中，為減少比較時間，比較需同時進行，這就需要為每個Cache塊增加一個比較器，硬件開銷過大，只適用于塊數(shù)量較少的Cache。②組關(guān)聯(lián)映射（組間直接映射，組內(nèi)全關(guān)聯(lián)映射）介于直接映射和全關(guān)聯(lián)映射之間的一種設計，將Cache分成n個組，每組m塊，則一個內(nèi)存塊可直接映射到某個組，但可放置在m塊的任意一塊位置上，某個內(nèi)存塊號為j的塊，會映射到第i=jmodn

個組中，但可存放在第i組的m個位置上任意一塊位置中。其中i為對應的Cache組號，j為主存塊號，n為Cache的組數(shù)，如每組有R個塊，稱為R路組關(guān)聯(lián)，R即為其關(guān)聯(lián)度。這樣，三種映射可看成關(guān)聯(lián)度的取值，直接映射關(guān)聯(lián)度為1，全關(guān)聯(lián)映射關(guān)聯(lián)度為n，組關(guān)聯(lián)映射關(guān)聯(lián)度介于1—n之間。例如：主存地址為12的塊在容量為8的cache中。從圖中可以看出三種映射方式的差異。地址為12的主存信息塊映射于Cache相應行示意圖

如圖所示是大小為8個塊的Cache幾種可能的組相聯(lián)映射結(jié)構(gòu)。不同關(guān)聯(lián)度情況之下Cache缺失率的示意圖組關(guān)聯(lián)的Cache，當訪問Cache缺失時，如果相應的組中有效位被置位，我們選擇Cache中最近最少被使用的塊被替換出去，而換之以從主存中送來的數(shù)據(jù)塊。關(guān)聯(lián)度對失效率的影響效果如下：CPU地址組成：

下圖中，一個四路組相聯(lián)Cache需要四個比較器和一個四選一的多路選擇器。比較器用于標志位之間的比較，多路選擇器用于選擇組內(nèi)經(jīng)過比較后命中的塊?？梢娊M相聯(lián)Cache需要額外的硬件代價，而且組內(nèi)比較和選擇也增加了訪問時間2、在cache中進行塊尋址

四路組相聯(lián)Cache結(jié)構(gòu)示意圖

在Cache容量、塊大小一定的情況下，關(guān)聯(lián)度越高，Cache塊沖突率、失效率越低，而映射機構(gòu)的實現(xiàn)越復雜、成本越高。

3、Cache替換策略最常用的替換策略是最近最少使用策略(LRU)，在候選塊中

選擇最近最少訪問到的那一塊進行替換。

先進先出替換策略（FIFO）

隨機替換策略4、減少缺失損失：利用多級Cache技術(shù)設計Cache時要考慮兩方面的需求：

一方面要將Cache設計得更快（意味著容量小）以匹配CPU的速度增長

另一方面則要將Cache設計得更大（意味著速度慢）以縮小主存和CPU之間日益增大的速度差距。為了滿足這兩種需求，許多高性能處理器支持多級Cache，一般是采用二級Cache。當?shù)谝患塁ache（一般做在處理器芯片上）發(fā)生缺失時，就需要訪問第二級Cache（一般位于處理器芯片外，也稱為片外Cache）。

P453例：多級Cache的性能作業(yè)1．簡述提高主存儲器性能的措施。2．指令和數(shù)據(jù)均存放在內(nèi)存中，計算機如何從時間和空間上區(qū)分它們是指令還是數(shù)據(jù)？3．一個Cache采用直接映射方式，數(shù)據(jù)容量為64KB，塊大小為一個字。假設CPU地址為32位，求這個Cache的實際大?。?．假設執(zhí)行g(shù)cc程序指令Cache的缺失率為2%，數(shù)據(jù)Cache的缺失率為4%。如果一臺機器CPI為2，且不存在存儲器阻塞。所有缺失引起的損失為40個時鐘周期。若有一個從不產(chǎn)生缺失的理想Cache，則機器速度能快多少？（gcc中存字和取字指令出現(xiàn)的頻率為36%。）6.4虛擬存儲器虛擬存儲器（virtualmemory）是整個存儲器體系結(jié)構(gòu)中用于管理主存/輔存存儲層次的存儲管理技術(shù)是為了多道程序間安全有效地共享主存，滿足應用程序?qū)Ω咚俅笕萘恐鞔娴男枨筇摂M存儲器實現(xiàn)了程序的邏輯地址與物理地址之間的轉(zhuǎn)換，這種轉(zhuǎn)換保證了每道程序的私有主存空間不會與別的程序沖突。虛擬存儲器中，用頁面(page)來表示塊這個概念。稱缺失為缺頁中斷（pagefault）由CPU產(chǎn)生虛地址(virtualaddress),由軟硬件共同將其轉(zhuǎn)換成物理地址(physicaladdress)以訪問主存,這個過程稱為存儲映射（memorymapping）或地址變換。圖6.20主存物理地址與虛地址之間的映射關(guān)系示意圖

虛擬存儲器由一個地址映射表機構(gòu)以完成地址的重定位（relocation）虛地址被分成虛頁號（virtualpagenumber）和頁內(nèi)偏移（pageoffset）部分。頁內(nèi)偏移也稱頁內(nèi)邏輯地址。虛地址轉(zhuǎn)化為物理地址在虛擬存儲器中，失效意味著訪問磁存儲器（磁盤）。由于磁盤的低速度，失效代價可能要幾百萬個時鐘周期高昂的失效代價決定了設計虛擬存儲器時的幾個關(guān)鍵要素：頁面必須足夠大以彌補高昂失效代價帶來的損失為了減少失效損失，虛擬存儲器一般總是采用全相聯(lián)映射方式。虛擬存儲器頁面損失的處理總是由操作系統(tǒng)完成的。采用回寫技術(shù)。

6.4.1地址變換從虛存空間到主存物理空間的映射關(guān)系是通過稱為頁表（pagetable）的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。頁表存放在主存中，由頁表項組成。每個虛頁面都對應于一個頁表項。頁表項的主要內(nèi)容是與一虛頁面對應的主存物理頁號。每道程序都有自己的頁表，對應于各自的虛存空間。有專門的一個寄存器用于存放頁表在主存中的首地址，稱為頁表寄存器。與Cache一樣，每一頁表項都有一個有效位（validbit）。

6.4.1地址變換（續(xù)1）

圖6.22使用頁表的虛地址與物理地址之間的轉(zhuǎn)換6.4.2缺頁中斷假如虛地址所對應頁表某單元未置標志位，那就發(fā)生了缺頁中斷。當操作系統(tǒng)生成進程時，它生成一個數(shù)據(jù)結(jié)構(gòu)(既可以是頁表的一部分，也可以是頁表的輔助數(shù)據(jù)結(jié)構(gòu))用來記錄每一個虛頁面在磁盤上的位置。在許多系統(tǒng)中，物理頁號和磁盤的頁面地址在邏輯上共存一個表中，實際上存放在兩個獨立的數(shù)據(jù)結(jié)構(gòu)里。使用兩個表是為了記錄所有頁面的磁盤地址。

6.4.2缺頁中斷(續(xù)1)圖6.23含物理頁號和輔存地址的頁表結(jié)構(gòu)

6.4.2缺頁中斷(續(xù)2)當發(fā)生頁面失效時，操作系統(tǒng)選擇一個最近沒有使用過的頁面替換出去（LRU算法）。 例如:最近的頁面訪問序列為10，12，9，7，11，10。此時要訪問地址為8的頁面，但發(fā)生了失效。我們選擇地址為12的頁面被替換，因為它最近最少使用。假如下一個訪問地址也發(fā)生失效，則選擇地址為9的頁面替換。

操作系統(tǒng)只是近似地使用LRU。為了便于系統(tǒng)選擇LRU塊，每個頁面都有一個使用位（userbit）或訪問位（referencebit），一旦頁面被訪問就置位。操作系統(tǒng)定期記錄并清除這些使用位就可以知道在一定時間間隔內(nèi)哪些頁面近期被訪問過，從而選擇出最近最少被訪問的頁面。

6.4.3寫策略虛擬存儲器寫磁盤的訪問時間則高達幾百萬個時鐘周期。因此為虛擬存儲器增加一個寫緩沖器以采用寫通的策略是完全行不通的。虛擬存儲器必須采用回寫方式，當修改過的頁面被替換出主存時，它才寫回到磁盤上的頁面。將修改頁面寫回到底層存儲器被稱為磁盤復錄（copyback）。回寫操作另一個優(yōu)點是寫回整個頁面。缺點是為了知道頁面當被替換出主存時是否一定要寫回到磁盤，虛擬存儲器要為每個頁面增加了一個改寫位（dirtybit）。6.4.4加快地址變換：TLB頁表存放在主存中，所以每一次存儲訪問都至少要訪存兩次：第一次訪存為查頁表得到主存物理地址第二次存取所需的數(shù)據(jù)。跟據(jù)程序的局部性原理，在一段時間內(nèi)，地址變換只會用到頁表中相對集中的一些頁表項?；诖耍S多機器使用專用于地址變換的Cache也稱為快查表TLB（translation-lookasidebuffer）來實現(xiàn)只含有部分頁表項的地址變換。TLB中與Cache標志Tag相對應的是虛頁號與數(shù)據(jù)和指令對應的是物理頁號。此外還有一些控制信息，如訪問位和改寫位。當處理器訪存時，首先訪問TLB。

6.4.4加快地址變換：TLB（續(xù)1）圖6.24使用TLB的存儲器訪問

6.4.4加快地址變換：TLB（續(xù)2）TLB的常用結(jié)構(gòu)參數(shù)如下：TLB大?。?2～4096項塊大小：4～8個字節(jié)(一到兩個頁表項)命中時間：0.5～1個時鐘周期失效損失：10～30個時鐘周期失效率：0.01%～1%一些系統(tǒng)的TLB容量很小，采用全相聯(lián)映射方式。另外一些系統(tǒng)使用容量較大的TLB，因此采用組數(shù)較小的組相聯(lián)映射方式。對于全相聯(lián)映射方式的TLB，使用LRU替換算法的代價過于昂貴。TLB一般采用硬件代價較小的隨機替換算法。

6.4.5MIPSR2000TLB圖6.25DECStation3100的TLB與Cache

6.4.5MIPSR2000TLB(續(xù)1)圖6.26DECStation3100的TLB和Cache處理訪存讀寫操作6.4.5MIPSR2000TLB(續(xù)2)在TLB中增加了一個寫訪問位（writeaccessbit）。它阻止程序?qū)χ蛔x頁面進單元寫操作。6.4.6虛擬存儲器、TLB、Cache之間的聯(lián)系在理想沒有失效的狀態(tài)下，虛擬地址通過TLB翻譯成物理地址，然后以該地址訪問Cache，獲得數(shù)據(jù)后再傳送給處理器。在最壞的情況下，TLB、頁表、Cache都發(fā)生失效。下表是Cache失效，TLB失效和缺頁中斷這三種失效合成的七種情況

6.4.6虛擬存儲器、TLB、Cache之間的聯(lián)系（續(xù)1）6.4.7存儲保護對于支持多道程序設計的計算機系統(tǒng)來說，在主存中往往同時存在多個進程，因此虛擬存儲器必須提供存儲保護機制為此，硬件系統(tǒng)必須至少提供以下三種機制：至少提供兩種工作狀態(tài)。用戶狀態(tài)和管理狀態(tài)，指明當前運行進程是用戶進程還是操作系統(tǒng)進程。用戶進程只能讀取不能改寫CPU狀態(tài)。在CPU狀態(tài)中增設用戶/管理狀態(tài)位（user/supervisormodebit）表明進程的狀態(tài)。提供CPU在兩種工作狀態(tài)之間相互轉(zhuǎn)換的機制。

6.4.7存儲保護（續(xù)1）實現(xiàn)存儲共享功能相對簡單，只要將不同的虛頁面映射到同一物理頁面即可。寫訪問位此時可以保證僅僅是讀共享。頁表和TLB都必須包括有關(guān)共享權(quán)限的位，因為只有TLB失效時才會訪問頁表。進程P1切換到進程P2時，要清除TLB所有的單元，然后在TLB中寫入有關(guān)P2頁表的內(nèi)容。假如進程切換率高，則以上做法的效率低下。一種解決方法是在虛擬地址空間內(nèi)增加進程標志（processidentifier）或任務標志（taskidentifier）。這個標志指出了目前正運行的進程。同樣的問題也發(fā)生在Cache中，我們同樣可以在Cache地址標志中加入進程標志。

6.4.8處理缺頁中斷和TLB失效TLB失效可以說明以下其中一種情況：頁面存在于存儲器中，只要在TLB中添加相應單元就行了。頁面不存在于存儲器中，要把控制權(quán)轉(zhuǎn)移給操作系統(tǒng)處理缺頁中斷。假如匹配單元的有效位關(guān)閉就說明虛頁號對應的頁面不存在于主存中，發(fā)生缺頁中斷。假如有效位置位，則可將頁表中相應單元寫入TLB。為了能在缺頁中斷被處理完后能繼續(xù)執(zhí)行被中斷進程，引起缺頁中斷的指令的程序計數(shù)器(PC)的值必須保存。

6.4.8處理缺頁中斷和TLB失效(續(xù)1)當缺頁中斷發(fā)生時，我們必須阻止寫主存操作的完成。通常的做法是阻斷主存的寫控制線。

須保存活動進程的所有狀態(tài)，包括所有的通用和浮點數(shù)寄存器，頁表地址寄存器，EPC和異常原因寄存器。產(chǎn)生失效的地址保存在EPC內(nèi)。假如是指令缺頁中斷，EPC包含了缺頁中斷的虛地址；假如是數(shù)據(jù)頁面失效，則要檢查引起失效的指令（地址存放在EPC內(nèi)）尋找基址寄存器和偏移地址，通過計算得到失效數(shù)據(jù)的虛地址。

6.4.8處理缺頁中斷和TLB失效(續(xù)2)一旦操作系統(tǒng)知道了引起缺頁中斷的虛地址，它必須完成以下三步： 1．使用虛地址查找頁表，找到失效頁面在磁盤上存放的位置。 2．從主存中挑選一個物理頁面替換。假如替換頁面的改寫位是置位的，則在我們用新的虛頁面替換選中頁面之前，必須將替換頁面寫回磁盤。 3．將磁盤的相應頁面寫到主存，替換第二步選出的物理頁面。一些技術(shù)可以減少cache失效率：選擇大的塊（通常稱作頁面），利用空間局部性減少失效率。使用全相聯(lián)映射方式實現(xiàn)頁表，允許虛頁面能映射到主存中的任意頁面。操作系統(tǒng)采用LRU替換策略。為了便于系統(tǒng)選擇LRU塊，每個頁面還都增加了一個訪問位（referencebit）。每個頁面都設置有一個“改寫位”，頁面被調(diào)出主存時，對應的改寫位被置位時才寫回磁盤。虛擬存儲器同樣提供從虛地址到主存物理地址的轉(zhuǎn)換。使進程就不能訪問其它不屬于自己的存儲區(qū)域，也簡化了主存分配。同時，為了保證多道程序系統(tǒng)正確工作，只有操作系統(tǒng)才能修改進程的頁表。為每個頁面增加寫訪問位,以規(guī)定其他進程的訪問權(quán)限，避免共享時本進程的頁面被修改。為了加快處理器查找頁表進行地址變換的速度，虛擬存儲器在CPU和主存間增加了一個含有部分頁表項的特殊Cache,稱作快查表TLB,專用于地址變換。6.4.9小結(jié)總結(jié)1、存儲器的層次結(jié)構(gòu)2、主存性能指標及主存和cpu間的連接3、領(lǐng)會多體并行交叉的基本原理4、綜合應用存儲器字、位、字位擴展方法5、高速cache：簡單應用cache地址映像分析、替換和更新策略6、計算cache性能7、虛擬存儲器原理。1．提高主存性能的措施：提高器件性能：采用同步的DRAM或帶CASHE的DRAM;加長存儲器字長;采用層次結(jié)構(gòu)Cache–主存;調(diào)整主存結(jié)構(gòu)，采用單體多字系統(tǒng)和多體并行結(jié)構(gòu)（高位交叉和低位交叉）.2．時間上講，取指令事件發(fā)生在“取指周期”，取數(shù)據(jù)事件發(fā)生在“執(zhí)行周期”?？臻g上講，從內(nèi)存讀出的指令流流向控制器（指令寄存器），從內(nèi)存讀出的數(shù)據(jù)流流向運算器（通用寄存器）。

1某計算機主存容量為64KB,其中ROM區(qū)為4KB，其余為RAM區(qū)，按字節(jié)編址。現(xiàn)要用2K×8位的ROM芯片和4K×4位的RAM芯片來設計該存儲器，則需要上述規(guī)格的ROM芯片和RAM芯片數(shù)分別是（

）

(A)1，15(B)2，15(C)1，30(D)2，302某計算機的Cache共有16塊，采用2路組相聯(lián)映射方式(即每組2塊)。每個主存塊大為32字節(jié)，按字節(jié)編址。主存129號單元所在主存塊應裝入到的Cache組號是（）

(A)0(B)2(C)4(D)63假設某計算機的存儲系統(tǒng)由Cache和主存組成，某程序執(zhí)行過程中訪存1000次，其中，訪問Cache缺失(未命中)50次，則Cache的命中率是（）

(A)5%(B)9.5%(C)50%(D)95%1.D2C3D6.5存儲層次的通用結(jié)構(gòu)機器中三種主要存儲層次的關(guān)鍵設計參數(shù)

圖6.28

6.5.1問題1：如何存放塊？塊的安置可以使用一系列策略，從直接映射,組相聯(lián)映射到全相聯(lián)映射。6.5.1問題1：如何存放塊？（續(xù)1）增加相聯(lián)度一般來說可以減少失效率，這是因為可以減少由于多個塊映射到Cache中同一行導致的沖突失效率。隨著Cache容量的增大，相聯(lián)度的提高對失效率的影響相對也越來越小，這是因為大容量Cache的失效率本來就比較低。當然相聯(lián)度的提高也會減慢Cache訪問速度。6.5.1問題1：如何存放塊？（續(xù)2）

失效率與相聯(lián)度的定量關(guān)系

圖6.29

6.5.2問題2：如何尋找塊？

如何定位塊取決于塊的映射方式，下面對塊定位策略作個小結(jié)：6.5.2問題2：如何尋找塊？（續(xù)1）在虛擬存儲系統(tǒng)中，以下四個因素決定了需要選擇全相聯(lián)和額外的表：全相聯(lián)是有利的，因為處理失效代價昂貴。全相聯(lián)映射方式允許軟件使用復雜的替換策略以減少失效率。全相聯(lián)的Cache索引非常容易，并不需要利用CPU地址中的索引號搜索Cache和增加額外的硬件。大的頁面意味著頁表不會很大。（對于Cache，像虛擬存儲器那樣使用獨立的搜索表并不可取。Cache的頁面不會很大，因此搜索表的大小要比頁表大得多，訪問的速度也會很慢。） 因此虛擬存儲器一般總是采用全相聯(lián)映射方式。組相聯(lián)映射方式一般用于Cache和TLB，需要先查找組，再比較組中的每一行。

6.5.3問題3：發(fā)生Cache失效時選擇哪個塊被替換？基本替換策略有以下兩種：隨機替換策略（Random）：隨機地在候選行中選擇一塊進行替換。可能需要硬件更多的支持。最近最少使用策略（LRU）：在候選塊中選擇最近最少被訪問到的那一塊進行替換虛擬存儲器一般采用近似LRU。6.5.4問題4：如何處理寫操作？我們已經(jīng)介紹了兩種寫策略:寫通（write-through）：信息被寫入Cache塊的同時，利用CPU和主存之間的直接數(shù)據(jù)通路寫入主存的對應塊中。