湘潭大學(xué)第4章 高速緩沖存儲器和虛擬存儲器

1、高速緩沖存儲器Cache和虛擬存儲器TLB5.5 高速緩沖存儲器Cache Cache的基本原理主存與Cache的地址映射方式替換算法寫策略Cache的多層次設(shè)計(jì)一、Cache的基本原理 Cache的工作原理Cache的特點(diǎn)Cache的命中率1231、Cache的特點(diǎn) Cache是指位于CPU和主存之間的一個高速小容量的存儲器，一般由SRAM構(gòu)成。 Cache功能：用于彌補(bǔ)CPU和主存之間的速度差異，提高CPU訪問主存的平均速度。 設(shè)置Cache的理論基礎(chǔ)，是程序訪問的局部性原理。 Cache的內(nèi)容是主存部分內(nèi)容的副本，Cache的功能均由硬件實(shí)現(xiàn)，對程序員是透明的。 Cache存儲器工作原理

2、（局部性工作原理）對大量典型程序的運(yùn)行情況進(jìn)行分析得到：在一個較短的時間間隔內(nèi)，由程序產(chǎn)生的地址往往集中在地址空間的很小范圍內(nèi)。原因：程序地址的分布一般是連續(xù)的，再加上循環(huán)程序、子程序等要重復(fù)執(zhí)行多次。因此對程序地址的訪問自然具有相對集中的傾向。數(shù)據(jù)分布不如指令明顯，但對數(shù)組的存儲和訪問使存儲器地址相對集中。2、Cache的工作原理 程序的簇聚性(局部性)指在每一小段時間內(nèi)，程序所要用到的指令或數(shù)據(jù)的地址往往集中在一個局部區(qū)域內(nèi)，因而對局部范圍內(nèi)的存儲器地址頻繁訪問，而對此范圍外的地址則訪問甚少的現(xiàn)象。 兩種局部性：時間局部性：最近被訪問的信息很可能還要被訪問。 將最近被訪問的信息項(xiàng)裝入到Ca

3、che中?？臻g局部性：最近被訪問的信息臨近的信息也可能被訪問。 將最近被訪問信息項(xiàng)附近的信息一起裝入到Cache中。 如果能把正在執(zhí)行的指令地址附近的一部分指令或數(shù)據(jù)從主存成批調(diào)入一個能高速訪問高速訪問的小容量存儲器的小容量存儲器( (Cache) ，供CPU在一段時間內(nèi)隨時使用，從而大大減少CPU訪問主存的次數(shù)，加快程序的運(yùn)行速度。 Cache的速度比主存快510倍。Cache、主存與CPU的關(guān)系 CPU主存Cache字傳送塊傳送CPU主存主存相聯(lián)存儲器相聯(lián)存儲器Cache存儲體存儲體硬件邏輯電路硬件邏輯電路地址總線地址總線數(shù)據(jù)總線數(shù)據(jù)總線Cache的原理圖Cache的讀寫操作 CPU在讀寫

4、存儲器時，Cache控制邏輯首先要依據(jù)地址來判斷這個字是否在Cache中，若在Cache中，則稱為“命中”；若不在，則稱為“不命中”。 針對命中/不命中、讀/寫操作，Cache的處理是不同的：讀命中：立即從Cache讀出送給CPU。讀不命中：通常有兩種解決方法：(1)將主存中該字所在的數(shù)據(jù)塊復(fù)制到Cache中，然后再把這個字傳送給CPU。(2)把此字從主存讀出送到CPU，同時，把包含這個字的數(shù)據(jù)塊從主存中讀出送到Cache中。Cache的讀寫操作寫不命中：直接將該字寫入主存中，且不再調(diào)入Cache；寫命中：通常也有兩種方法進(jìn)行處理：寫貫穿方法：同時對Cache和主存進(jìn)行寫操作；寫回：只寫Cac

5、he，僅當(dāng)此Cache塊被替換時，才將該塊寫入主存3、Cache的命中率 命中率指CPU訪問主存數(shù)據(jù)時，命中Cache的次數(shù)，占全部訪問次數(shù)的比率。 失效率就指不命中Cache的次數(shù)，占全部訪問次數(shù)的比率。 命中率h取決于程序的行為、Cache的容量、組織方式、塊大小。 在一個程序執(zhí)行期間，設(shè)Nc表示Cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，則命中率：actte mccNNNh mcath1htt）（ ）（）（cmcatth1htt v若tc表示Cache的訪問時間，tm表示主存的訪問時間，則Cache/主存系統(tǒng)的平均訪問時間ta為：vCache/主存系統(tǒng)的訪問效率e:二、主存

6、與Cache的地址映射方式 討論前提：Cache的數(shù)據(jù)塊稱為行，主存的數(shù)據(jù)塊稱為塊，行與塊是等長的；主存容量為2m塊，Cache容量為2c行，每個字塊中含2b字。主存中只有一小部分塊的內(nèi)容可放在Cache中。 Cache存儲單元的組成部分:數(shù)據(jù)字段：保存從主存單元復(fù)制過來的數(shù)據(jù)。標(biāo)志字段：保存相應(yīng)主存單元的地址信息。有效位字段：標(biāo)識數(shù)據(jù)字段和標(biāo)志字段的是否有效。 討論的問題：如何根據(jù)主存地址，判斷Cache有無命中并變換為Cache的地址，以便執(zhí)行讀寫。有三種地址映射方式：直接映射全相聯(lián)映射組相聯(lián)映射1、直接映射 直接映射是一種多對一的映射關(guān)系：主存的第i塊一定映射到Cache的第j行，且：

7、j=i mod 2c 直接映像方式特點(diǎn)：主存的字塊只可以和固定的Cache字塊對應(yīng)，映射方式直接、簡單，易實(shí)現(xiàn)，利用率低。標(biāo)志位較短，比較電路的成本低。如果主存空間有2m塊，Cache中字塊有2c塊，則標(biāo)志位只要有m-c位，且僅需要比較一次。機(jī)制不靈活，Cache命中率低。c2DIVik 標(biāo)記K：直接映像硬件實(shí)現(xiàn)舉例A d dre ss (sh ow ing b it p ositio ns)2010By teo ffse tV alidT agD a taIn de x01210 2110 2210 23T a gInd exH itD ata20323 1 30 1 3 12 11 2 1

8、 0 注意P358-359與這里講的區(qū)別。書上訪問Cache是訪問2個字(4字節(jié)/字)，這里是用W進(jìn)行選擇，不需要在外面加一個2選擇1多路器來選擇。2、全相聯(lián)映射 全相聯(lián)映射是多對多的映射關(guān)系：對于主存的任何一塊均可以映射到Cache的任何一行。 特點(diǎn)：主存的字塊可以和Cache的任何字塊(行)對應(yīng)，利用率高，方式靈活，命中率高。標(biāo)志位較長，比較電路的成本太，高難于設(shè)計(jì)和實(shí)現(xiàn)。如果主存空間有2m塊，則標(biāo)志位要有m位。如果Cache有n塊，則需要有n個比較電路。全相聯(lián)硬件實(shí)現(xiàn)舉例3、組相聯(lián)映射 組相聯(lián)映像是將Cache的行分成c=2c-r組，每組2r行。主存的字塊存放到Cache中的哪個組是固定

9、的，至于映射到該組哪一行是靈活的，即有如下函數(shù)關(guān)系： j(i mod 2c)*2r+k 其中 0k2r-1 組相聯(lián)映像方式特點(diǎn)：組間為直接映像，組內(nèi)為全相聯(lián)映像。大大增加了映射的靈活性，主存中一塊可映射到Cache 的2r塊，提高了命中率。每次比較只是進(jìn)行2r路比較，r 較小時，硬件開銷不是很大。集中了兩個方式的優(yōu)點(diǎn)。成本也不太高。 組相聯(lián)映像通常采用2路、4路和8路比較，即取r=1,r=2,r=3。組相聯(lián)硬件實(shí)現(xiàn)舉例Address228VTagIndex012253254255DataVTagDataVTagDataVTagData32224-to-1 multiplexorHitData1

10、238910111230310三種映像方式比較 全相聯(lián)映射主存中的一塊可以映射到Cache中任何一個位置 直接映像主存中的一塊只能映射到Cache中唯一的一個位置定位時，不需要判斷，只需替換 多路組相聯(lián)映射主存中的一塊可以選擇映射到Cache中多個位置 全相聯(lián)映射和多路組相聯(lián)映射的失效處理從主存中取出新塊為了騰出Cache空間，需要替換出一個Cache塊不唯一，則需要判斷應(yīng)替出哪塊三、替換算法1、隨機(jī)替換算法2、先進(jìn)先出算法（FIFO）3、最近最少使用算法（LRU）該算法統(tǒng)計(jì)哪一個Cache行是近段時間使用次數(shù)最少的Cache行，需替換時就將它替換出去。LRU替換算法可以通過為每個Cache行

11、設(shè)置一個計(jì)數(shù)器來實(shí)現(xiàn)LRU替換算法，Cache每命中一次，命中行的計(jì)數(shù)器被清零，其他行的計(jì)數(shù)器加1，需要替換的話，就將計(jì)數(shù)器值最大的行替換出去。LRU算法的平均命中率比FIFO要高，并且當(dāng)分組容量加大時，能提高LRU替換算法的命中率。如下圖。 圖 LRU算法替換登記表（數(shù)字為塊號） 例：假定cache是直接映射的，每塊4字。Cache的容量是16字，初始時cache為空。對于下述訪問主存地址序列(字地址)： 1,4,8,5,20,17,19,56,9,11,4,43,5,6,9,17。標(biāo)出每次訪問的cache命中情況以及最后cache的內(nèi)容，并計(jì)算命中率。如果Cache訪問時間為0.1s，主存

12、的訪問時間為1s，問CPU訪問內(nèi)存的平均時間是多少？ 解：cache的塊數(shù)=16/4=4塊。 根據(jù) Cache塊號=主存地址/4 (mod 4) 可得到下表：塊0塊1塊2塊3Cache中最后的內(nèi)容如下：主存地址范圍塊號030471811212-153161902023124-2722831332-3503639140-43244473485105255156-592序號12345678910111213141516地址14852017195691144356917塊號0121100222121120命中0001001001001100塊0塊1塊2塊3地址17地址6地址9空命中率=5/16=31

13、.25%CPU訪問內(nèi)存的平均時間Ta=H*Tc+(1-H)*Tm =0.3125*0.1+0.6875*1 =0.71875四、寫策略 常用的寫策略通常有寫貫穿和寫回兩種 寫貫穿策略 當(dāng)CPU寫Cache命中時，所有寫操作既對Cache也對主存進(jìn)行；當(dāng)CPU寫Cache不命中時，直接寫主存，有兩種做法： 不將該數(shù)據(jù)所在的塊拷貝到Cache行，稱為WTNWA法； 將該數(shù)據(jù)所在塊拷貝到Cache的某行，稱為WTWA法。 寫回策略（Write Back） 當(dāng)CPU寫Cache命中時，寫操作只是對Cache進(jìn)行，而不修改主存的相應(yīng)內(nèi)容，僅當(dāng)此Cache行被換出時，相應(yīng)的主存內(nèi)容才被修改；當(dāng)CPU寫Ca

14、che不命中時，先將該數(shù)據(jù)所在塊拷貝到Cache的某行，余下操作與Cache寫命中時相同。 為了區(qū)別Cache行是否被改寫過，應(yīng)為每個Cache行設(shè)置一個修改位，CPU修改Cache行時，標(biāo)記其修改位，當(dāng)此Cache行被換出時，判別此Cache行的修改位，從而決定是否將Cache行數(shù)據(jù)寫回主存相應(yīng)單元。 3、兩種寫策略比較寫貫穿策略保證了主存數(shù)據(jù)總是有效，寫回策略可能導(dǎo)致Cache和主存數(shù)據(jù)不一致；寫回策略的效率高于寫貫穿策略；寫回策略的控制比寫貫穿策略的控制復(fù)雜。五、Cache的多層次設(shè)計(jì) 設(shè)計(jì)Cache主要考慮五個問題：容量Cache中行的大小Cache的組織（地址映射方式）指令和數(shù)據(jù)共用

15、同一個Cache還是分享不同CacheCache的層次 統(tǒng)一Cache和分離Cache 統(tǒng)一Cache：只有一個Cache，指令和數(shù)據(jù)混放。 分離Cache：分為指令Cache和數(shù)據(jù)Cache。它消除了流水線中指令處理器和執(zhí)行單元間的競爭，因此，特別適用于Pentium 和Power PC這樣的超標(biāo)量流水線中；是Cache結(jié)構(gòu)發(fā)展的趨勢。 單級Cache與兩級Cache 一級Cache（）和二級Cache 采用兩級Cache結(jié)構(gòu)可以提高性能 Cache一致性問題 無效專有修改共享+RMSRHRMEWMRHWHWHRHWH無效專有修改共享SHWSHRSHWSHWSHRSHR（A）發(fā)起處理器的Ca

16、che行（B）監(jiān)聽Cache行MESI協(xié)議的狀態(tài)圖 RH讀命中；RMS讀不命中，共享；RME讀不命中，專有；WH寫命中；WM寫不命中；SHR讀監(jiān)聽命中；SHW寫監(jiān)聽命中或讀是用于修改；+無效處理；Cache行填入；無效行拷回；讀用于修改 CACHE使用中的幾個問題 CACHE的重要技術(shù)指標(biāo)：命中率 影響 CACHE 命中率的因素CACHE CACHE 的容量，大一些好的容量，大一些好CACHE CACHE 與主存儲器每次交換信息的單位量與主存儲器每次交換信息的單位量(Cache Line Size)(Cache Line Size)適中適中CACHE CACHE 不同的組織方式，多路組相聯(lián)更好

17、不同的組織方式，多路組相聯(lián)更好CACHE CACHE 的多級組織可提高命中率的多級組織可提高命中率CACHE CACHE 裝滿后的替換算法裝滿后的替換算法cache的容量與命中率的關(guān)系 Cache Size in KBHit Ratecache line size與缺失率的關(guān)系 多級的cache結(jié)構(gòu)與命中率的關(guān)系 為增加cache容量，可以在已有的cache(第一級)存儲器系統(tǒng)之外，再增加一個容量更大的cache(第二級) 。 第二級cache的容量比第一級cache的容量要大得多，在第一級cache中保存的信息也一定保存在第二級cache中。 當(dāng)CPU訪問第一級cache出現(xiàn)缺失情況時，就去

18、訪問第二級cache。 若第一級、第二級cache的命中率為90%，則它們合起來后的命中率為1-(1-90%)(1-90%)=99%，而不會是81%。5.6 虛擬存儲器 虛擬存儲器的實(shí)現(xiàn)方式有三種：段式、頁式或段頁式 頁式虛擬存儲器 頁式虛擬存儲器中邏輯地址與物理地址的轉(zhuǎn)換關(guān)系 5.6 虛擬存儲器 段式虛擬存儲器段式虛擬存儲器 段內(nèi)偏移段號段表基地址段長邏輯地址物理地址段表+ .段首地址 .段號01+段式虛擬存儲器中邏輯地址與物理地址的轉(zhuǎn)換關(guān)系 5.6 虛擬存儲器 段頁式虛擬存儲器 段號頁號頁內(nèi)地址頁內(nèi)地址物理頁號邏輯地址物理地址.段表頁表+段頁式虛擬存儲器中邏輯地址與物理地址的轉(zhuǎn)換關(guān)系 5.

19、9 IA32架構(gòu)的存儲系統(tǒng)舉例 P6P6微架構(gòu)下的微架構(gòu)下的CacheCache Intel NetBurstIntel NetBurst微架構(gòu)下的微架構(gòu)下的CacheCache Intel CoreIntel Core微架構(gòu)的多核高效內(nèi)存管理技術(shù)微架構(gòu)的多核高效內(nèi)存管理技術(shù) 一一二二三三一、P6微架構(gòu)下的Cache L2 Cache(256KB-1MB)總線接口單元取指令和譯碼單元派遣和執(zhí)行單元回收單元指令池（重定序緩沖區(qū)-ROB）L1 指令Cache(8KB-16KB)L1 數(shù)據(jù)Cache(8KB-16KB)取裝入存儲系統(tǒng)總線Pentium處理器框圖 一、P6微架構(gòu)下的CacheLRU 目

20、錄 0目錄 1標(biāo)記狀態(tài)路0（4KB）路1（4KB）32字節(jié)32 字節(jié)組0組127.狀態(tài)目錄標(biāo)記（頁面地址）組地址起始字節(jié)主存物理地址=3512115 40L1級數(shù)據(jù)Cache的結(jié)構(gòu) 二、Intel NetBurst微架構(gòu)下的Cache 指令取指令取/譯譯碼單元碼單元蹤跡蹤跡Cache(12K ops）整數(shù)寄存器組整數(shù)寄存器組裝入裝入地址地址單元單元存儲存儲地址地址單元單元8KB的的L1級數(shù)據(jù)級數(shù)據(jù)Cache256KB的的L2級級Cache(8路路)1MB的的L3級級Cache簡單簡單整數(shù)整數(shù)ALU簡單簡單整數(shù)整數(shù)ALU復(fù)雜復(fù)雜整數(shù)整數(shù)ALU浮點(diǎn)寄存器組浮點(diǎn)寄存器組FP/MMX單元單元FP傳送傳

21、送單元單元亂序執(zhí)行邏輯亂序執(zhí)行邏輯256位位64位位系統(tǒng)總線系統(tǒng)總線Pentium4的簡化圖 三、Intel Core微架構(gòu)的多核高效內(nèi)存管理技術(shù) 浮點(diǎn)運(yùn)算單元浮點(diǎn)運(yùn)算單元運(yùn)算核心運(yùn)算核心L1 Cache浮點(diǎn)運(yùn)算單元浮點(diǎn)運(yùn)算單元運(yùn)算核心運(yùn)算核心L1 CacheL2 Cache前端總線前端總線 Intel Core的微架構(gòu)的兩個核心 Intel Core微架構(gòu)在一個芯片內(nèi)封裝了兩個計(jì)算內(nèi)核，兩個核各具有一個8路32KB的L1級指令Cache和32KB的雙端口L1級數(shù)據(jù)Cache。兩核共享一個16路、容量為2MB或4MB的L2級Cache 三、Intel Core微架構(gòu)的多核高效內(nèi)存管理技術(shù) CACHE管理 L2 CacheL1CacheL1CacheCORE 1CORE 0主主 存存L2 CacheL1CacheL1CacheCORE 1CORE 0主主 存存Core微架構(gòu)的共享L2級Cache非共享L2級CacheL2 CacheCore微