1、第7章 存儲系統(tǒng)7.1存儲系統(tǒng)的基本知識7.2Cache基本知識7.3降低Cache不命中率7.4減少Cache不命中開銷7.5減少命中時間7.6并行主存系統(tǒng)7.7虛擬存儲器7.8實例：AMD Opteron的存儲器層次結(jié)構(gòu)計算機系統(tǒng)結(jié)構(gòu)設(shè)計中關(guān)鍵的問題之一 ： 如何以合理的價格，設(shè)計容量和速度都滿足計算機系統(tǒng)要求的存儲器系統(tǒng)？ 人們對這三個指標的要求 容量大、速度快、價格低三個要求是相互矛盾的速度越快，每位價格就越高；容量越大，每位價格就越低；容量越大，速度越慢。7.1 存儲系統(tǒng)的基本知識7.1.1 存儲系統(tǒng)的層次結(jié)構(gòu)7.1 存儲系統(tǒng)的基本知識解決方法：采用多種存儲器技術(shù)，構(gòu)成多級存儲層次結(jié)

2、構(gòu)。程序訪問的局部性原理：對于絕大多數(shù)程序來說，程序所訪問的指令和數(shù)據(jù)在地址上不是均勻分布的，而是相對簇聚的。 (局部性原理)程序訪問的局部性包含兩個方面 時間局部性：程序馬上將要用到的信息很可能就是現(xiàn)在正在使用的信息。空間局部性：程序馬上將要用到的信息很可能與現(xiàn)在正在使用的信息在存儲空間上是相鄰的。 7.1 存儲系統(tǒng)的基本知識存儲系統(tǒng)的多級層次結(jié)構(gòu) 演示 演示多級存儲層次7.1 存儲系統(tǒng)的基本知識假設(shè)第i個存儲器Mi的訪問時間為Ti，容量為Si，平均每位價格為Ci，則訪問時間： T1 T2 Tn容量： S1 S2 C2 Cn 整個存儲系統(tǒng)要達到的目標：從CPU來看，該存儲系統(tǒng)的速度接近于M1

3、的，而容量和每位價格都接近于Mn的。存儲器越靠近CPU，則CPU對它的訪問頻度越高，而且最好大多數(shù)的訪問都能在M1完成。7.1 存儲系統(tǒng)的基本知識下面僅考慮由M1和M2構(gòu)成的兩級存儲層次：M1的參數(shù)：S1，T1，C1M2的參數(shù)：S2，T2，C27.1.2 存儲層次的性能參數(shù)7.1 存儲系統(tǒng)的基本知識存儲容量S一般來說，整個存儲系統(tǒng)的容量即是第二級存儲器M2的容量，即S=S2。每位價格C當(dāng)S1S2時，CC2。 7.1 存儲系統(tǒng)的基本知識命中率H 和不命中率F命中率：CPU訪問存儲系統(tǒng)時，在M1中找到所需信息的概率。N1 訪問M1的次數(shù)N2 訪問M2的次數(shù) 不命中率 ：F1H7.1 存儲系統(tǒng)的基本

4、知識平均訪問時間TA TA HT1（1H）（T1TM） T1（1H）TM 或 TA T1FTM分兩種情況來考慮CPU的一次訪存：當(dāng)命中時，訪問時間即為T1（命中時間）當(dāng)不命中時，情況比較復(fù)雜。 不命中時的訪問時間為：T2TBT1T1TM TM T2TB不命中開銷TM：從向M2發(fā)出訪問請求到把整個數(shù)據(jù)塊調(diào)入M1中所需的時間。傳送一個信息塊所需的時間為TB。 7.1 存儲系統(tǒng)的基本知識 三級存儲系統(tǒng)Cache（高速緩沖存儲器）主存儲器磁盤存儲器（輔存）可以看成是由“Cache主存”層次和“主存輔存”層次構(gòu)成的系統(tǒng)。7.1.3 三級存儲系統(tǒng)7.1 存儲系統(tǒng)的基本知識 從主存的角度來看“Cache主存

5、”層次：彌補主存速度的不足“主存輔存”層次： 彌補主存容量的不足“Cache主存”層次主存與CPU的速度差距“Cache - 主存”層次 “主存輔存”層次7.1 存儲系統(tǒng)的基本知識1980年以來存儲器和CPU性能隨時間而提高的情況 （以1980年時的性能作為基準）7.1 存儲系統(tǒng)的基本知識兩種存儲層次7.1 存儲系統(tǒng)的基本知識存儲層次CPU對第二級的訪問方式比較項目目的存儲管理實現(xiàn) 訪問速度的比值(第一級和第二級)典型的塊(頁)大小不命中時CPU是否切換“Cache 主存”層次“主存輔存”層次為了彌補主存速度的不足為了彌補主存容量的不足主要由專用硬件實現(xiàn)主要由軟件實現(xiàn)幾比一幾萬比一幾十個字節(jié)幾

6、百到幾千個字節(jié)可直接訪問均通過第一級不切換切換到其他進程“Cache主存”與“主存輔存”層次的區(qū)別7.1 存儲系統(tǒng)的基本知識當(dāng)把一個塊調(diào)入高一層(靠近CPU)存儲器時，可以放在哪些位置上? （映象規(guī)則）當(dāng)所要訪問的塊在高一層存儲器中時，如何找到該塊?（查找算法）當(dāng)發(fā)生不命中時，應(yīng)替換哪一塊？（替換算法）當(dāng)進行寫訪問時，應(yīng)進行哪些操作? （寫策略）7.1.4 存儲層次的四個問題存儲空間分割與地址計算Cache和主存分塊Cache是按塊進行管理的。Cache和主存均被分割成大小相同的塊。信息以塊為單位調(diào)入Cache。 主存塊地址（塊號）用于查找該塊在Cache中的位置。塊內(nèi)位移用于確定所訪問的數(shù)據(jù)

7、在該塊中的位置。7.2 Cache基本知識 7.2.1基本結(jié)構(gòu)和原理 Cache的基本工作原理示意圖 7.2.2映象規(guī)則 全相聯(lián)映象 全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個位置。舉例對比：閱覽室位置 隨便坐特點：空間利用率最高，沖突概率最低，實現(xiàn)最復(fù)雜。 7.2 Cache基本知識7.2 Cache基本知識7.2 Cache基本知識直接映象 直接映象：主存中的每一塊只能被放置到Cache中唯一的一個位置。舉例（循環(huán)分配）對比：閱覽室位置 只有一個位置可以坐特點：空間利用率最低，沖突概率最高， 實現(xiàn)最簡單。對于主存的第i 塊，若它映象到Cache的第j 塊，則: ji mod

8、(M ) （M為Cache的塊數(shù)）設(shè)M=2m，則當(dāng)表示為二進制數(shù)時，j實際上就是i的低m位: ji：m位7.2 Cache基本知識7.2 Cache基本知識組相聯(lián)映象 組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個組中的任何一個位置。 舉例組相聯(lián)是直接映象和全相聯(lián)的一種折衷7.2 Cache基本知識組的選擇常采用位選擇算法若主存第i 塊映象到第k 組，則: ki mod（G） （G為Cache的組數(shù)）設(shè)G2g，則當(dāng)表示為二進制數(shù)時，k 實際上就是i 的低 g 位: 低g位以及直接映象中的低m位通常稱為索引。 ki：g位7.2 Cache基本知識n 路組相聯(lián)：每組中有n個塊(nM/G

9、)。n 稱為相聯(lián)度。相聯(lián)度越高，Cache空間的利用率就越高，塊沖突概率就越低，不命中率也就越低。 絕大多數(shù)計算機的Cache: n 4想一想：相聯(lián)度一定是越大越好？全相聯(lián)直接映象組相聯(lián)n (路數(shù))G (組數(shù))MM111nM1GM7.2 Cache基本知識當(dāng)CPU訪問Cache時，如何確定Cache中是否有所要訪問的塊？若有的話，如何確定其位置？通過查找目錄表來實現(xiàn)目錄表的結(jié)構(gòu)主存塊的塊地址的高位部分，稱為標識 。每個主存塊能唯一地由其標識來確定7.2.3 查找算法7.2 Cache基本知識只需查找候選位置所對應(yīng)的目錄表項并行查找與順序查找提高性能的重要思想：主候選位置(MRU塊) （前瞻執(zhí)行

10、）并行查找的實現(xiàn)方法相聯(lián)存儲器目錄由2g個相聯(lián)存儲區(qū)構(gòu)成，每個相聯(lián)存儲區(qū)的大小為n（h+log2n）位。根據(jù)所查找到的組內(nèi)塊地址，從Cache存儲體中讀出的多個信息字中選一個，發(fā)送給CPU。 7.2 Cache基本知識7.2 Cache基本知識單體多字存儲器比較器 舉例： 路組相聯(lián)并行標識比較（比較器的個數(shù)及位數(shù)）路組相聯(lián)Cache的查找過程直接映象Cache的查找過程優(yōu)缺點不必采用相聯(lián)存儲器，而是用按地址訪問的存儲器來實現(xiàn)。所需要的硬件為：大小為2g nh位的存儲器和n個h位的比較器。當(dāng)相聯(lián)度n增加時，不僅比較器的個數(shù)會增加，而且比較器的位數(shù)也會增加。 7.2 Cache基本知識7.2 Ca

11、che基本知識例子：DEC的Alpha AXP21064中的內(nèi)部數(shù)據(jù)Cache簡介容量：8KB塊大小：32B塊數(shù)：256映象方法：直接映象寫緩沖器大小：4個塊7.2.4 Cache的工作過程結(jié)構(gòu)圖7.2 Cache基本知識工作過程“讀”訪問命中（完成4步需要2個時鐘周期 ）Cache的容量與索引index、相聯(lián)度、塊大小之間的關(guān)系 Cache的容量=2index相聯(lián)度塊大小 把容量為8192、相聯(lián)度為1、塊大小為32（字節(jié)）代入： 索引index：8位 標識：29821位 “寫”訪問命中7.2 Cache基本知識設(shè)置了一個寫緩沖器 （提高“寫”訪問的速度）按字尋址的，它含有4個塊，每塊大小為4

12、個字。當(dāng)要進行寫入操作時，如果寫緩沖器不滿，那么就把數(shù)據(jù)和完整的地址寫入緩沖器。對CPU而言，本次“寫”訪問已完成，CPU可以繼續(xù)往下執(zhí)行。由寫緩沖器負責(zé)把該數(shù)據(jù)寫入主存。在寫入緩沖器時，要進行寫合并檢查。即檢查本次寫入數(shù)據(jù)的地址是否與緩沖器內(nèi)某個有效塊的地址匹配。如果匹配，就把新數(shù)據(jù)與該塊合并 。7.2 Cache基本知識發(fā)生讀不命中與寫不命中時的操作讀不命中：向CPU發(fā)出一個暫停信號，通知它等待，并從下一級存儲器中新調(diào)入一個數(shù)據(jù)塊（32字節(jié)）。寫不命中：將使數(shù)據(jù)“繞過”Cache，直接寫入主存。 對比：Alpha AXP 21264的數(shù)據(jù)Cache結(jié)構(gòu)容量：64KB 塊大小：64字節(jié) LR

13、U替換策略 主要區(qū)別采用2路組相聯(lián)采用寫回法 沒有寫緩沖器7.2 Cache基本知識替換算法所要解決的問題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時，替換哪一塊？直接映象Cache中的替換很簡單 因為只有一個塊，別無選擇。在組相聯(lián)和全相聯(lián)Cache中，則有多個塊供選擇。主要的替換算法有三種隨機法 優(yōu)點：實現(xiàn)簡單先進先出法FIFO7.2.5 替換算法7.2 Cache基本知識最近最少使用法LRU選擇近期最少被訪問的塊作為被替換的塊。（實現(xiàn)比較困難）實際上：選擇最久沒有被訪問過的塊作為被替換的塊。 優(yōu)點：命中率較高LRU和隨機法分別因其不命中率低和實現(xiàn)簡單而被廣泛采用。模擬數(shù)據(jù)表明，對于容量很大的C

14、ache，LRU和隨機法的命中率差別不大。7.2 Cache基本知識LRU算法的硬件實現(xiàn) 堆棧法 用一個堆棧來記錄組相聯(lián)Cache的同一組中各塊被訪問的先后次序。用堆棧元素的物理位置來反映先后次序棧底記錄的是該組中最早被訪問過的塊，次棧底記錄的是該組中第二個被訪問過的塊，棧頂記錄的是剛訪問過的塊。當(dāng)需要替換時，從棧底得到應(yīng)該被替換的塊（塊地址）。 7.2 Cache基本知識7.2 Cache基本知識堆棧中的內(nèi)容必須動態(tài)更新 當(dāng)Cache訪問命中時，通過用塊地址進行相聯(lián)查找，在堆棧中找到相應(yīng)的元素，然后把該元素的上面的所有元素下壓一個位置，同時把本次訪問的塊地址抽出來，從最上面壓入棧頂。而該元素

15、下面的所有元素則保持不動。如果Cache訪問不命中，則把本次訪問的塊地址從最上面壓入棧頂，堆棧中所有原來的元素都下移一個位置。如果Cache中該組已經(jīng)沒有空閑塊，就要替換一個塊。這時從棧底被擠出去的塊地址就是需要被替換的塊的塊地址。7.2 Cache基本知識堆棧法所需要的硬件需要為每一組都設(shè)置一個項數(shù)與相聯(lián)度相同的小堆棧，每一項的位數(shù)為log2n位。硬件堆棧所需的功能相聯(lián)比較能全部下移、部分下移和從中間取出一項的功能速度較低，成本較高（只適用于相聯(lián)度較小的LRU算法）比較對法 基本思路 讓各塊兩兩組合，構(gòu)成比較對。每一個比較對用一個觸發(fā)器的狀態(tài)來表示它所相關(guān)的兩個塊最近一次被訪問的遠近次序，再

16、經(jīng)過門電路就可找到LRU塊。 7.2 Cache基本知識 例如：假設(shè)有A、B、C三個塊，可以組成3對：AB、AC、BC。每一對中塊的訪問次序分別用“對觸發(fā)器”TAB、TAC、TBC表示。TAB為“1”，表示A比B更近被訪問過；TAB為“0”，表示B比A更近被訪問過。TAC、TBC也是按這樣的規(guī)則定義。 顯然，當(dāng)TAC1且TBC1時，C就是最久沒有被訪問過了。 （A比C更近被訪問過、且B比C也是更近被訪問過） 即：CLRU = TACTBC 同理可得： 用觸發(fā)器和與門實現(xiàn)上述邏輯的電路： 7.2 Cache基本知識用比較對法實現(xiàn)LRU算法 7.2 Cache基本知識比較對法所需的硬件量與門 有多

17、少個塊，就要有多少個與門； 每個與門的輸入端要連接所有與之相關(guān)的觸發(fā)器。 對于一個具有P塊的組中的任何一個塊來說，由于它可以跟除了它自己以外的所有其他的塊兩兩組合，所以與該塊相關(guān)的比較對觸發(fā)器個數(shù)為P1，因而其相應(yīng)的與門的輸入端數(shù)是P1。 觸發(fā)器 所需要的觸發(fā)器的個數(shù)與兩兩組合的比較對的數(shù)目相同。 比較對觸發(fā)器個數(shù)、與門的個數(shù)、與門的輸入端數(shù)與塊數(shù)P的關(guān)系 組內(nèi)塊數(shù)3481664256P觸發(fā)器個數(shù)3628120201632640與門個數(shù)3481664256P與門輸入端個數(shù)2371563255P-17.2 Cache基本知識塊數(shù)少時，所需要的硬件較少， 隨著組內(nèi)塊數(shù)P的增加，所需的觸發(fā)器的個數(shù)會

18、以平方的關(guān)系迅速增加，門的輸入端數(shù)也線性增加。 （硬件實現(xiàn)的成本很高） 當(dāng)組內(nèi)塊數(shù)較多時，可以用多級狀態(tài)位技術(shù)減少所需的硬件量。 例如：在IBM 3033中 組內(nèi)塊數(shù)為16，可分成群、對、行3級。 先分成4群，每群兩對，每對兩行。 選LRU群需6個觸發(fā)器； 每群中選LRU對需要一個觸法器，4個群共需要4個觸發(fā)器；7.2 Cache基本知識每行中選LRU塊需要一個觸發(fā)器，8個行共需要8個觸發(fā)器。所需的觸發(fā)器總個數(shù)為： 6（選群）4（選對）8（選行）= 18（個） 以犧牲速度為代價的。7.2 Cache基本知識“寫”在所有訪存操作中所占的比例 統(tǒng)計結(jié)果表明，對于一組給定的程序：load指令：26s

19、tore指令：9“寫”在所有訪存操作中所占的比例：9/(100269)7“寫”在訪問Cache操作中所占的比例： 9/(269)257.2.6 寫策略7.2 Cache基本知識“寫”操作必須在確認是命中后才可進行“寫”訪問有可能導(dǎo)致Cache和主存內(nèi)容的不一致兩種寫策略寫策略是區(qū)分不同Cache設(shè)計方案的一個重要標志。寫直達法（也稱為存直達法） 執(zhí)行“寫”操作時，不僅寫入Cache，而且也寫入下一級存儲器。寫回法（也稱為拷回法） 執(zhí)行“寫”操作時，只寫入Cache。僅當(dāng)Cache中相應(yīng)的塊被替換時，才寫回主存。 (設(shè)置“修改位”)7.2 Cache基本知識兩種寫策略的比較寫回法的優(yōu)點：速度快，

20、所使用的存儲器帶寬較低。寫直達法的優(yōu)點：易于實現(xiàn)，一致性好。采用寫直達法時，若在進行“寫”操作的過程中CPU必須等待，直到“寫”操作結(jié)束，則稱CPU寫停頓。減少寫停頓的一種常用的優(yōu)化技術(shù)：采用寫緩沖器7.2 Cache基本知識“寫”操作時的調(diào)塊按寫分配(寫時取)寫不命中時，先把所寫單元所在的塊調(diào)入Cache，再行寫入。不按寫分配(繞寫法)寫不命中時，直接寫入下一級存儲器而不調(diào)塊。寫策略與調(diào)塊寫回法 按寫分配寫直達法 不按寫分配7.2 Cache基本知識不命中率與硬件速度無關(guān)容易產(chǎn)生一些誤導(dǎo)平均訪存時間平均訪存時間 命中時間不命中率不命中開銷7.2.7 Cache的性能分析程序執(zhí)行時間CPU時間

21、（CPU執(zhí)行周期數(shù)+存儲器停頓周期數(shù)） 時鐘周期時間其中： 存儲器停頓時鐘周期數(shù)“讀”的次數(shù)讀不命中率讀不命中開銷“寫”的次數(shù)寫不命中率寫不命中開銷存儲器停頓時鐘周期數(shù)訪存次數(shù)不命中率不命中開銷 CPU時間（CPU執(zhí)行周期數(shù)+訪存次數(shù)不命中率不命中開銷） 時鐘周期時間=IC（CPIexecution每條指令的平均訪存次數(shù)不命中率 不命中開銷） 時鐘周期時間7.2 Cache基本知識 例7.1 用一個和Alpha AXP類似的機器作為第一個例子。假設(shè)Cache不命中開銷為50個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期，訪問Cache不命中率為2%，平均每條指令訪存1

22、.33次。試分析Cache對性能的影響。 解 CPU時間有cacheIC （CPIexecution每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時鐘周期時間 IC （2.01.332 %50） 時鐘周期時間 IC 3.33 時鐘周期時間7.2 Cache基本知識考慮Cache的不命中后，性能為： CPU時間有cacheIC（2.01.332 %50）時鐘周期時間 IC3.33時鐘周期時間實際CPI ：3.333.33/2.0 = 1.67(倍) CPU時間也增加為原來的1.67倍。 但若不采用Cache,則：CPI2.0501.3368.57.2 Cache基本知識Cache不命中對于一個C

23、PI較小而時鐘頻率較高的CPU來說，影響是雙重的：CPIexecution越低，固定周期數(shù)的Cache不命中開銷的相對影響就越大。在計算CPI時，不命中開銷的單位是時鐘周期數(shù)。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的不命中開銷較大，其CPI中存儲器停頓這部分也就較大。 因此Cache對于低CPI、高時鐘頻率的CPU來說更加重要。 例7.2 考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象Cache和兩路組相聯(lián)Cache，試問它們對CPU的性能有何影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設(shè)： (1)理想Cache（命中率為100%）情況下的CPI為2.0，時

24、鐘周期為2ns，平均每條指令訪存1.3次。 (2)兩種Cache容量均為64KB，塊大小都是32字節(jié)。 (3)在組相聯(lián)Cache中，由于多路選擇器的存在而使CPU的時鐘周期增加到原來的1.10倍。這是因為對Cache的訪問總是處于關(guān)鍵路徑上，對CPU的時鐘周期有直接的影響。 (4) 這兩種結(jié)構(gòu)Cache的不命中開銷都是70ns。（在實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期） (5) 命中時間為1個時鐘周期，64KB直接映象Cache的不命中率為1.4%，相同容量的兩路組相聯(lián)Cache的不命中率為1.0%。7.2 Cache基本知識 解 平均訪存時間為： 平均訪存時間命中時間不命中率不命中開銷 因此，

25、兩種結(jié)構(gòu)的平均訪存時間分別是： 平均訪存時間1路2.0（0.01470）2.98ns 平均訪存時間2路2.01.10（0.01070）2.90ns 兩路組相聯(lián)Cache的平均訪存時間比較低。 CPU時間IC（CPIexecution每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時鐘周期時間 IC（CPIexecution 時鐘周期時間每條指令的 平均訪存次數(shù)不命中率不命中開銷時鐘周期時間）7.2 Cache基本知識因此：CPU時間1路 IC(2.02(1.30.01470) 5.27ICCPU時間2路 IC(2.021.10(1.30.01070) 5.31IC5.31ICCPU時間1路 1.

26、015.27ICCPU時間2路直接映象Cache的平均性能好一些。7.2 Cache基本知識平均訪存時間命中時間不命中率不命中開銷可以從三個方面改進Cache的性能：降低不命中率減少不命中開銷減少Cache命中時間下面介紹17種Cache優(yōu)化技術(shù)8種用于降低不命中率5種用于減少不命中開銷4種用于減少命中時間 7.2.8 改進Cache的性能三種類型的不命中(3C)強制性不命中(Compulsory miss)當(dāng)?shù)谝淮卧L問一個塊時，該塊不在Cache中，需從下一級存儲器中調(diào)入Cache，這就是強制性不命中。 (冷啟動不命中，首次訪問不命中）容量不命中(Capacity miss ) 如果程序執(zhí)行

27、時所需的塊不能全部調(diào)入Cache中，則當(dāng)某些塊被替換后，若又重新被訪問，就會發(fā)生不命中。這種不命中稱為容量不命中。7.3 降低Cache不命中率7.3.1 三種類型的不命中7.3 降低Cache不命中率沖突不命中(Conflict miss)在組相聯(lián)或直接映象Cache中，若太多的塊映象到同一組(塊)中，則會出現(xiàn)該組中某個塊被別的塊替換(即使別的組或塊有空閑位置)，然后又被重新訪問的情況。這就是發(fā)生了沖突不命中。 (碰撞不命中，干擾不命中)三種不命中所占的比例 圖示I(絕對值)圖示(相對值)7.3 降低Cache不命中率7.3 降低Cache不命中率7.3 降低Cache不命中率可以看出：相聯(lián)

28、度越高，沖突不命中就越少；強制性不命中和容量不命中不受相聯(lián)度的影響；強制性不命中不受Cache容量的影響，但容量不命中卻隨著容量的增加而減少。7.3 降低Cache不命中率減少三種不命中的方法強制性不命中：增加塊大小，預(yù)取 （本身很少）容量不命中：增加容量 （抖動現(xiàn)象）沖突不命中：提高相聯(lián)度（理想情況：全相聯(lián)）許多降低不命中率的方法會增加命中時間或不命中開銷7.3 降低Cache不命中率不命中率與塊大小的關(guān)系對于給定的Cache容量，當(dāng)塊大小增加時，不命中率開始是下降，后來反而上升了。 原因：一方面它減少了強制性不命中；另一方面，由于增加塊大小會減少Cache中塊的數(shù)目，所以有可能會增加沖突不

29、命中。 Cache容量越大，使不命中率達到最低的塊大小就越大。增加塊大小會增加不命中開銷7.3.2 增加Cache塊大小7.3 降低Cache不命中率不命中率隨塊大小變化的曲線 7.3 降低Cache不命中率各種塊大小情況下Cache的不命中率 塊大小（字節(jié)） Cache容量（字節(jié)） 1K 4K 16K 64K 256K 16 15.05% 8.57% 3.94% 2.04% 1.09% 32 13.34% 7.24% 2.87% 1.35% 0.70% 64 13.76% 7.00% 2.64% 1.06% 0.51% 128 16.64% 7.78% 2.77% 1.02% 0.49% 2

30、56 22.01% 9.51% 3.29% 1.15% 0.49% 7.3 降低Cache不命中率最直接的方法是增加Cache的容量缺點:增加成本可能增加命中時間這種方法在片外Cache中用得比較多 7.3.3 增加Cache的容量7.3 降低Cache不命中率采用相聯(lián)度超過8的方案的實際意義不大。2:1 Cache經(jīng)驗規(guī)則 容量為N的直接映象Cache的不命中率和容量為N/2的兩路組相聯(lián)Cache的不命中率差不多相同。提高相聯(lián)度是以增加命中時間為代價。 7.3.4 提高相聯(lián)度7.3 降低Cache不命中率多路組相聯(lián)的低不命中率和直接映象的命中速度偽相聯(lián)Cache的優(yōu)點命中時間小不命中率低7.

31、3.5 偽相聯(lián) Cache (列相聯(lián) Cache )優(yōu)點缺點直接映象組相聯(lián)命中時間小命中時間大不命中率高不命中率低基本思想及工作原理 （動畫演示） 在邏輯上把直接映象Cache的空間上下平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián)Cache先按直接映象Cache的方式去處理。若命中，則其訪問過程與直接映象Cache的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下一級存儲器。7.3 降低Cache不命中率 缺點： 多種命中時間快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。不命中開銷7.3 降低Cache不命中率指令和數(shù)據(jù)都可以預(yù)取預(yù)取內(nèi)容既可放入Cac

32、he，也可放在外緩沖器中。例如：指令流緩沖器指令預(yù)取通常由Cache之外的硬件完成預(yù)取效果Joppi的研究結(jié)果指令預(yù)取 (4KB，直接映象Cache，塊大小16字節(jié))1個塊的指令流緩沖器： 捕獲1525的不命中4個塊的指令流緩沖器： 捕獲5016個塊的指令流緩沖器：捕獲727.3.6 硬件預(yù)取 7.3 降低Cache不命中率數(shù)據(jù)預(yù)取 (4KB,直接映象Cache)1個數(shù)據(jù)流緩沖器：捕獲25的不命中還可以采用多個數(shù)據(jù)流緩沖器Palacharla和Kessler的研究結(jié)果流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)對于兩個64KB四路組相聯(lián)Cache來說：8個流緩沖器能捕獲5070的不命中預(yù)取應(yīng)利用存儲器的

33、空閑帶寬，不能影響對正常不命中的處理，否則可能會降低性能。 7.3 降低Cache不命中率 在編譯時加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請求。按照預(yù)取數(shù)據(jù)所放的位置，可把預(yù)取分為兩種類型：寄存器預(yù)取：把數(shù)據(jù)取到寄存器中。Cache預(yù)取：只將數(shù)據(jù)取到Cache中。按照預(yù)取的處理方式不同，可把預(yù)取分為：故障性預(yù)取：在預(yù)取時，若出現(xiàn)虛地址故障或違反保護權(quán)限，就會發(fā)生異常。7.3.7 編譯器控制的預(yù)取 7.3 降低Cache不命中率非故障性預(yù)取：在遇到這種情況時則不會發(fā)生異常，因為這時它會放棄預(yù)取，轉(zhuǎn)變?yōu)榭詹僮鳌１竟?jié)假定Cache預(yù)取都是非故障性的，也叫做非綁定預(yù)取。在預(yù)取數(shù)據(jù)的同時，處理器應(yīng)能繼續(xù)

34、執(zhí)行。 只有這樣，預(yù)取才有意義。 非阻塞Cache (非鎖定Cache) 編譯器控制預(yù)取的目的 使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。 循環(huán)是預(yù)取優(yōu)化的主要對象7.3 降低Cache不命中率不命中開銷小時：循環(huán)體展開12次不命中開銷大時：循環(huán)體展開許多次每次預(yù)取需要花費一條指令的開銷保證這種開銷不超過預(yù)取所帶來的收益編譯器可以通過把重點放在那些可能會導(dǎo)致不命中的訪問上，使程序避免不必要的預(yù)取，從而較大程度地減少平均訪存時間。7.3 降低Cache不命中率基本思想：通過對軟件進行優(yōu)化來降低不命中率。 （特色：無需對硬件做任何改動）程序代碼和數(shù)據(jù)重組可以重新組織程序而不影響程序的正確性把一個程序中的過程

35、重新排序，就可能會減少沖突不命中，從而降低指令不命中率。McFarling研究了如何使用配置文件（profile）來進行這種優(yōu)化。把基本塊對齊，使得程序的入口點與Cache塊的7.3.8 編譯器優(yōu)化 7.3 降低Cache不命中率 起始位置對齊，就可以減少順序代碼執(zhí)行時所發(fā)生的Cache不命中的可能性。 （提高大Cache塊的效率）如果編譯器知道一個分支指令很可能會成功轉(zhuǎn)移，那么它就可以通過以下兩步來改善空間局部性：將轉(zhuǎn)移目標處的基本塊和緊跟著該分支指令后的基本塊進行對調(diào)；把該分支指令換為操作語義相反的分支指令。數(shù)據(jù)對存儲位置的限制更少，更便于調(diào)整順序。 7.3 降低Cache不命中率編譯優(yōu)化

36、技術(shù)包括數(shù)組合并將本來相互獨立的多個數(shù)組合并成為一個復(fù)合數(shù)組，以提高訪問它們的局部性。內(nèi)外循環(huán)交換循環(huán)融合將若干個獨立的循環(huán)融合為單個的循環(huán)。這些循環(huán)訪問同樣的數(shù)組，對相同的數(shù)據(jù)作不同的運算。這樣能使得讀入Cache的數(shù)據(jù)在被替換出去之前，能得到反復(fù)的使用 。分塊7.3 降低Cache不命中率內(nèi)外循環(huán)交換 舉例： /* 修改前 */ for （ j = 0 ; j 100 ; j = j+1 ） for （ i = 0 ; i 5000 ; i = i+1 ） x i j = 2 * x i j ; /* 修改后 */ for （ i = 0 ; i 5000 ; i = i+1 ） for

37、（ j = 0 ; j 100 ; j = j+1 ） x i j = 2 * x i j ;7.3 降低Cache不命中率分塊 把對數(shù)組的整行或整列訪問改為按塊進行。 /* 修改前 */ for （ i = 0; iN; i = i+1 ） for （ j = 0; j N; j = j+1 ） r = 0; for （ k = 0; k N; k = k+1） r = r + y i k * z k j ; x i j = r; 計算過程（不命中次數(shù)：2N3N2）7.3 降低Cache不命中率7.3 降低Cache不命中率/* 修改后 */ for （ jj = 0; jj N; jj =

38、 jj+B ） for （ kk = 0; kk N; kk = kk+B ） for （ i = 0; i N; i =i+1 ） for （ j = jj; j min（jj+B-1, N）; j = j+1 ） r = 0; for （ k = kk; k min（kk+B-1, N）; k = k+1） r = r + y i k * z k j ; x i j = x i j + r; 計算過程 (不命中次數(shù)：2N3 /B N2)7.3 降低Cache不命中率7.3 降低Cache不命中率一種能減少沖突不命中次數(shù)而又不影響時鐘頻率的方法。基本思想在Cache和它從下一級存儲器調(diào)數(shù)據(jù)的

39、通路之間設(shè)置一個全相聯(lián)的小Cache，稱為“犧牲”Cache（Victim Cache）。用于存放被替換出去的塊(稱為犧牲者)，以備重用。工作過程7.3.9 “犧牲” Cache 7.3 降低Cache不命中率作用對于減小沖突不命中很有效，特別是對于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。例如項數(shù)為4的Victim Cache: 能使4KB Cache的沖突不命中減少20%90%應(yīng)把Cache做得更快？還是更大？答案：二者兼顧，再增加一級Cache第一級Cache(L1)小而快第二級Cache(L2)容量大性能分析 平均訪存時間 命中時間L1不命中率L1不命中開銷L1不命中開銷L1 命中

40、時間L2不命中率L2不命中開銷L27.4.1 采用兩級Cache7.4 減少Cache不命中開銷7.4 減少Cache不命中開銷平均訪存時間 命中時間L1不命中率L1 （命中時間L2不命中率L2不命中開銷L2）局部不命中率與全局不命中率局部不命中率該級Cache的不命中次數(shù)/到達該 級Cache的訪問次數(shù) 例如：上述式子中的不命中率L2全局不命中率該級Cache的不命中次數(shù)/CPU發(fā) 出的訪存的總次數(shù)7.4 減少Cache不命中開銷全局不命中率L2不命中率L1不命中率L2 評價第二級Cache時，應(yīng)使用全局不命中率這個指標。它指出了在CPU發(fā)出的訪存中，究竟有多大比例是穿過各級Cache，最終

41、到達存儲器的。采用兩級Cache時，每條指令的平均訪存停頓時間：每條指令的平均訪存停頓時間 每條指令的平均不命中次數(shù)L1命中時間L2 每條指令的平均不命中次數(shù)L2不命中開銷L27.4 減少Cache不命中開銷例7.3 考慮某一兩級Cache：第一級Cache為L1，第二級Cache為L2。 （1）假設(shè)在1000次訪存中，L1的不命中是40次，L2的不命中是20次。求各種局部不命中率和全局不命中率。 （2）假設(shè)L2的命中時間是10個時鐘周期，L2的不命中開銷是100時鐘周期，L1的命中時間是1個時鐘周期，平均每條指令訪存1.5次，不考慮寫操作的影響。問：平均訪存時間是多少？每條指令的平均停頓時間

42、是多少個時鐘周期？ 解 (1) 第一級Cache的不命中率（全局和局部）是40/1000，即4%； 第二級Cache的局部不命中率是20/40，即50%； 第二級Cache的全局不命中率是20/1000，即2%。 7.4 減少Cache不命中開銷（2）平均訪存時間命中時間L1不命中率L1（命中時間L2 不命中率L2不命中開銷L2） 14%（1050%100） 14%603.4個時鐘周期 由于平均每條指令訪存1.5次，且每次訪存的平均停頓時間為： 3.41.02.4所以： 每條指令的平均停頓時間2.41.53.6個時鐘周期7.4 減少Cache不命中開銷對于第二級Cache，我們有以下結(jié)論：在第

43、二級Cache比第一級 Cache大得多的情況下，兩級Cache的全局不命中率和容量與第二級Cache相同的單級Cache的不命中率非常接近。局部不命中率不是衡量第二級Cache的一個好指標，因此，在評價第二級Cache時，應(yīng)用全局不命中率這個指標。第二級Cache不會影響CPU的時鐘頻率，因此其設(shè)計有更大的考慮空間。兩個問題：7.4 減少Cache不命中開銷它能否降低CPI中的平均訪存時間部分？它的成本是多少？第二級Cache的參數(shù)容量第二級Cache的容量一般比第一級的大許多。大容量意味著第二級Cache可能實際上沒有容量不命中，只剩下一些強制性不命中和沖突不命中。 相聯(lián)度第二級Cache

44、可采用較高的相聯(lián)度或偽相聯(lián)方法。7.4 減少Cache不命中開銷 例7.4 給出有關(guān)第二級Cache的以下數(shù)據(jù)： （1）對于直接映象，命中時間L2 10個時鐘周期 （2）兩路組相聯(lián)使命中時間增加0.1個時鐘周期，即為10.1個時鐘周期。 （3） 對于直接映象，局部不命中率L2 25% （4） 對于兩路組相聯(lián)，局部不命中率L2 20% （5） 不命中開銷L2 50個時鐘周期 試問第二級Cache的相聯(lián)度對不命中開銷的影響如何？7.4 減少Cache不命中開銷 解 對一個直接映象的第二級Cache來說，第一級Cache的不命中開銷為： 不命中開銷直接映象，L1 1025%50 22.5 個時鐘周期

45、 對于兩路組相聯(lián)第二級Cache來說，命中時間增加了10%（0.1）個時鐘周期，故第一級Cache的不命中開銷為： 不命中開銷兩路組相聯(lián)，L1 10.120%50 20.1 個時鐘周期 把第二級Cache的命中時間取整，得10或11，則： 不命中開銷兩路組相聯(lián)，L1 1020%50 20.0 個時鐘周期 不命中開銷兩路組相聯(lián)，L1 1120%50 21.0 個時鐘周期 故對于第二級Cache來說，兩路組相聯(lián)優(yōu)于直接映象。7.4 減少Cache不命中開銷塊大小第二級Cache可采用較大的塊 如 64、128、256字節(jié) 為減少平均訪存時間，可以讓容量較小的第一級Cache采用較小的塊，而讓容量較

46、大的第二級Cache采用較大的塊。多級包容性 需要考慮的另一個問題： 第一級Cache中的數(shù)據(jù)是否總是同時存在于第二級Cache中。 Cache中的寫緩沖器導(dǎo)致對存儲器訪問的復(fù)雜化 在讀不命中時，所讀單元的最新值有可能還在寫緩沖器中，尚未寫入主存。 7.4.2 讓讀不命中優(yōu)先于寫7.4 減少Cache不命中開銷解決問題的方法(讀不命中的處理)推遲對讀不命中的處理（缺點：讀不命中的開銷增加）檢查寫緩沖器中的內(nèi)容在寫回法Cache中，也可采用寫緩沖器。7.4 減少Cache不命中開銷7.4.3 寫緩沖合并提高寫緩沖器的效率寫直達Cache依靠寫緩沖來減少對下一級存儲器寫操作的時間。如果寫緩沖器為空

47、，就把數(shù)據(jù)和相應(yīng)地址寫入該緩沖器。 從CPU的角度來看，該寫操作就算是完成了。如果寫緩沖器中已經(jīng)有了待寫入的數(shù)據(jù)，就要把這次的寫入地址與寫緩沖器中已有的所有地址進行比較，看是否有匹配的項。如果有地址匹配而7.4 減少Cache不命中開銷 對應(yīng)的位置又是空閑的，就把這次要寫入的數(shù)據(jù)與該項合并。這就叫寫緩沖合并。如果寫緩沖器滿且又沒有能進行寫合并的項，就必須等待。 提高了寫緩沖器的空間利用率，而且還能減少因?qū)懢彌_器滿而要進行的等待時間。7.4 減少Cache不命中開銷7.4 減少Cache不命中開銷請求字 從下一級存儲器調(diào)入Cache的塊中，只有一個字是立即需要的。這個字稱為請求字。 應(yīng)盡早把請求

48、字發(fā)送給CPU盡早重啟動：調(diào)塊時，從塊的起始位置開始讀起。一旦請求字到達，就立即發(fā)送給CPU，讓CPU繼續(xù)執(zhí)行。請求字優(yōu)先：調(diào)塊時，從請求字所在的位置讀起。這樣，第一個讀出的字便是請求字。將之立即發(fā)送給CPU。7.4.4 請求字處理技術(shù)7.4 減少Cache不命中開銷這種技術(shù)在以下情況下效果不大：Cache塊較小下一條指令正好訪問同一Cache塊的另一部分7.4 減少Cache不命中開銷非阻塞Cache：Cache不命中時仍允許CPU進行其它的命中訪問。即允許“不命中下命中”。進一步提高性能：“多重不命中下命中” “不命中下不命中” （存儲器必須能夠處理多個不命中）可以同時處理的不命中次數(shù)越多

49、，所能帶來的性能上的提高就越大。（不命中次數(shù)越多越好？）7.4.5 非阻塞Cache技術(shù)7.4 減少Cache不命中開銷模擬研究 數(shù)據(jù)Cache的平均存儲器等待時間（以周期為單位）與阻塞Cache平均存儲器等待時間的比值測試條件：8K直接映象Cache，塊大小為32字節(jié)測試程序：SPEC92（14個浮點程序，4個整數(shù)程序）結(jié)果表明 在重疊不命中個數(shù)為1、2和64的情況下浮點程序的平均比值分別為：76%、51%和39%整數(shù)程序的平均比值則分別為：81%、78%和78%對于整數(shù)程序來說，重疊次數(shù)對性能提高影響不大，簡單的“一次不命中下命中”就幾乎可以得到所有的好處。 命中時間直接影響到處理器的時鐘頻率。在當(dāng)今的許多計算機中，往往是Cache的訪問時間限制了處理器的時鐘頻率。7.5 減少命中時間7.5.1 容量小、結(jié)構(gòu)簡單的Cache硬件越簡單，速度就越快；應(yīng)使Cache足夠小，以便可以與CPU一起放在同一塊芯片上。7.5 減少命中時間 某些設(shè)計采用了一種折衷方案： 把Cache的標識放在片內(nèi)，而把Cache的數(shù)據(jù)存儲器放在片外。7.5.2 虛擬Cache物理Cache使用物理地址進行訪問的傳統(tǒng)Cache。標識存儲器中存放的是物理地址，進行