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

高速緩沖存儲器Cache和虛擬存儲器TLB5.5高速緩沖存儲器CacheCache二五三四一Cache的基本原理主存與Cache的地址映射方式替換算法寫策略Cache的多層次設(shè)計一、Cache的基本原理Cache的工作原理Cache的特點Cache的命中率1231、Cache的特點Cache是指位于CPU和主存之間的一個高速小容量的存儲器，一般由SRAM構(gòu)成。Cache功能：用于彌補(bǔ)CPU和主存之間的速度差異，提高CPU訪問主存的平均速度。設(shè)置Cache的理論基礎(chǔ)，是程序訪問的局部性原理。Cache的內(nèi)容是主存部分內(nèi)容的副本，Cache的功能均由硬件實現(xiàn)，對程序員是透明的。Cache存儲器工作原理（局部性工作原理）對大量典型程序的運行情況進(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)象。兩種局部性：時間局部性：最近被訪問的信息很可能還要被訪問。將最近被訪問的信息項裝入到Cache中?？臻g局部性：最近被訪問的信息臨近的信息也可能被訪問。將最近被訪問信息項附近的信息一起裝入到Cache中。如果能把正在執(zhí)行的指令地址附近的一部分指令或數(shù)據(jù)從主存成批調(diào)入一個能高速訪問的小容量存儲器(Cache)

，供CPU在一段時間內(nèi)隨時使用，從而大大減少CPU訪問主存的次數(shù)，加快程序的運行速度。Cache的速度比主存快5－10倍。Cache、主存與CPU的關(guān)系Cache的原理圖Cache的讀寫操作CPU在讀寫存儲器時，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)行寫操作；寫回：只寫Cache，僅當(dāng)此Cache塊被替換時，才將該塊寫入主存3、Cache的命中率命中率指CPU訪問主存數(shù)據(jù)時，命中Cache的次數(shù)，占全部訪問次數(shù)的比率。失效率就指不命中Cache的次數(shù)，占全部訪問次數(shù)的比率。命中率h取決于程序的行為、Cache的容量、組織方式、塊大小。在一個程序執(zhí)行期間，設(shè)Nc表示Cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，則命中率：若tc表示Cache的訪問時間，tm表示主存的訪問時間，則Cache/主存系統(tǒng)的平均訪問時間ta為：Cache/主存系統(tǒng)的訪問效率e:二、主存與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行，且：

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

j＝(imod2c’)*2r+k其中0≤k≤2r-1組相聯(lián)映像方式特點：組間為直接映像，組內(nèi)為全相聯(lián)映像。大大增加了映射的靈活性，主存中一塊可映射到Cache的2r塊，提高了命中率。每次比較只是進(jìn)行2r路比較，r較小時，硬件開銷不是很大。集中了兩個方式的優(yōu)點。成本也不太高。組相聯(lián)映像通常采用2路、4路和8路比較，即取r=1,r=2,r=3。組相聯(lián)硬件實現(xiàn)舉例三種映像方式比較全相聯(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)計哪一個Cache行是近段時間使用次數(shù)最少的Cache行，需替換時就將它替換出去。LRU替換算法可以通過為每個Cache行設(shè)置一個計數(shù)器來實現(xiàn)LRU替換算法，Cache每命中一次，命中行的計數(shù)器被清零，其他行的計數(shù)器加1，需要替換的話，就將計數(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)容，并計算命中率。如果Cache訪問時間為0.1μs，主存的訪問時間為1μs，問CPU訪問內(nèi)存的平均時間是多少？解：cache的塊數(shù)=16/4=4塊。

根據(jù)Cache塊號=主存地址/4(mod4)

可得到下表：塊0塊1塊2塊3Cache中最后的內(nèi)容如下：主存地址范圍塊號0—304—718—11212--15316—19020—23124--27228—31332-35036—39140--43244—47348—51052—55156--592序號12345678910111213141516地址14852017195691144356917塊號0121100222121120命中0001001001001100塊0塊1塊2塊3地址17地址6地址9空命中率=5/16=31.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法。

寫回策略（WriteBack）當(dāng)CPU寫Cache命中時，寫操作只是對Cache進(jìn)行，而不修改主存的相應(yīng)內(nèi)容，僅當(dāng)此Cache行被換出時，相應(yīng)的主存內(nèi)容才被修改；當(dāng)CPU寫Cache不命中時，先將該數(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è)計設(shè)計Cache主要考慮五個問題：容量Cache中行的大小Cache的組織（地址映射方式）指令和數(shù)據(jù)共用同一個Cache還是分享不同CacheCache的層次統(tǒng)一Cache和分離Cache統(tǒng)一Cache：只有一個Cache，指令和數(shù)據(jù)混放。分離Cache：分為指令Cache和數(shù)據(jù)Cache。它消除了流水線中指令處理器和執(zhí)行單元間的競爭，因此，特別適用于PentiumⅡ和PowerPC這樣的超標(biāo)量流水線中；是Cache結(jié)構(gòu)發(fā)展的趨勢。單級Cache與兩級Cache一級Cache（）和二級Cache采用兩級Cache結(jié)構(gòu)可以提高性能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與主存儲器每次交換信息的單位量(CacheLineSize)適中CACHE不同的組織方式，多路組相聯(lián)更好CACHE的多級組織可提高命中率CACHE裝滿后的替換算法cache的容量與命中率的關(guān)系CacheSizeinKBHitRatecachelinesize與缺失率的關(guān)系多級的cache結(jié)構(gòu)與命中率的關(guān)系

為增加cache容量，可以在已有的cache(第一級)存儲器系統(tǒng)之外，再增加一個容量更大的cache(第二級)。第二級cache的容量比第一級cache的容量要大得多，在第一級cache中保存的信息也一定保存在第二級cache中。當(dāng)CPU訪問第一級cache出現(xiàn)缺失情況時，就去訪問第二級cache。若第一級、第二級cache的命中率為90%，則它們合起來后的命中率為1-(1-90%)×(1-90%)=99%，而不會是81%。5.6虛擬存儲器虛擬存儲器的實現(xiàn)方式有三種：段式、頁式或段頁式頁式虛擬存儲器

頁式虛擬存儲器中邏輯地址與物理地址的轉(zhuǎn)換關(guān)系5.6虛擬存儲器段式虛擬存儲器段式虛擬存儲器中邏輯地址與物理地址的轉(zhuǎn)換關(guān)系5.6虛擬存儲器段頁式虛擬存儲器段頁式虛擬存儲器中邏輯地址與物理地址的轉(zhuǎn)換關(guān)系5.9IA32架構(gòu)的存儲系統(tǒng)舉例

P6微架構(gòu)下的Cache

IntelNetBurst微架構(gòu)下的Cache

IntelCore微架構(gòu)的多核高效內(nèi)存管理技術(shù)

一二三一、P6微架構(gòu)下的CachePentiumⅡ處理器框圖一、P6微架構(gòu)下的CacheL1級數(shù)據(jù)Cache的結(jié)構(gòu)二、IntelNetBurst微架構(gòu)下的CachePentium4的簡化圖三、IntelCore微架構(gòu)的多核高效內(nèi)存管理技術(shù)IntelCore的微架構(gòu)的兩個核心IntelCore微架構(gòu)在一個芯