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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、.33次。試分析Cache對性能的影響。 解 CPU時間有cacheIC （CPIexecution每條指令的平均訪存次數 不命中率不命中開銷） 時鐘周期時間 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越低，固定周期數的Cache不命中開銷的相對影響就越大。在計算CPI時，不命中開銷的單位是時鐘周期數。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的不命中開銷較大，其CPI中存儲器停頓這部分也就較大。 因此Cache對于低CPI、高時鐘頻率的CPU來說更加重要。 例7.2 考慮兩種不同組織結構的Cache：直接映象Cache和兩路組相聯Cache，試問它們對CPU的性能有何影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設： (1)理想Cache（命中率為100%）情況下的CPI為2.0，時

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

25、兩種結構的平均訪存時間分別是： 平均訪存時間1路2.0（0.01470）2.98ns 平均訪存時間2路2.01.10（0.01070）2.90ns 兩路組相聯Cache的平均訪存時間比較低。 CPU時間IC（CPIexecution每條指令的平均訪存次數 不命中率不命中開銷） 時鐘周期時間 IC（CPIexecution 時鐘周期時間每條指令的 平均訪存次數不命中率不命中開銷時鐘周期時間）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優化技術8種用于降低不命中率5種用于減少不命中開銷4種用于減少命中時間 7.2.8 改進Cache的性能三種類型的不命中(3C)強制性不命中(Compulsory miss)當第一次訪問一個塊時，該塊不在Cache中，需從下一級存儲器中調入Cache，這就是強制性不命中。 (冷啟動不命中，首次訪問不命中）容量不命中(Capacity miss ) 如果程序執行

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

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

29、命中。 Cache容量越大，使不命中率達到最低的塊大小就越大。增加塊大小會增加不命中開銷7.3.2 增加Cache塊大小7.3 降低Cache不命中率不命中率隨塊大小變化的曲線 7.3 降低Cache不命中率各種塊大小情況下Cache的不命中率 塊大小（字節） Cache容量（字節） 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不命中率采用相聯度超過8的方案的實際意義不大。2:1 Cache經驗規則 容量為N的直接映象Cache的不命中率和容量為N/2的兩路組相聯Cache的不命中率差不多相同。提高相聯度是以增加命中時間為代價。 7.3.4 提高相聯度7.3 降低Cache不命中率多路組相聯的低不命中率和直接映象的命中速度偽相聯Cache的優點命中時間小不命中率低7.

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

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

33、空閑帶寬，不能影響對正常不命中的處理，否則可能會降低性能。 7.3 降低Cache不命中率 在編譯時加入預取指令，在數據被用到之前發出預取請求。按照預取數據所放的位置，可把預取分為兩種類型：寄存器預取：把數據取到寄存器中。Cache預取：只將數據取到Cache中。按照預取的處理方式不同，可把預取分為：故障性預取：在預取時，若出現虛地址故障或違反保護權限，就會發生異常。7.3.7 編譯器控制的預取 7.3 降低Cache不命中率非故障性預取：在遇到這種情況時則不會發生異常，因為這時它會放棄預取，轉變為空操作。本節假定Cache預取都是非故障性的，也叫做非綁定預取。在預取數據的同時，處理器應能繼續

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

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

36、技術包括數組合并將本來相互獨立的多個數組合并成為一個復合數組，以提高訪問它們的局部性。內外循環交換循環融合將若干個獨立的循環融合為單個的循環。這些循環訪問同樣的數組，對相同的數據作不同的運算。這樣能使得讀入Cache的數據在被替換出去之前，能得到反復的使用 。分塊7.3 降低Cache不命中率內外循環交換 舉例： /* 修改前 */ 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不命中率分塊 把對數組的整行或整列訪問改為按塊進行。 /* 修改前 */ 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; 計算過程（不命中次數：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; 計算過程 (不命中次數：2N3 /B N2)7.3 降低Cache不命中率7.3 降低Cache不命中率一種能減少沖突不命中次數而又不影響時鐘頻率的方法。基本思想在Cache和它從下一級存儲器調數據的

39、通路之間設置一個全相聯的小Cache，稱為“犧牲”Cache（Victim Cache）。用于存放被替換出去的塊(稱為犧牲者)，以備重用。工作過程7.3.9 “犧牲” Cache 7.3 降低Cache不命中率作用對于減小沖突不命中很有效，特別是對于小容量的直接映象數據Cache，作用尤其明顯。例如項數為4的Victim Cache: 能使4KB Cache的沖突不命中減少20%90%應把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的不命中次數/到達該 級Cache的訪問次數 例如：上述式子中的不命中率L2全局不命中率該級Cache的不命中次數/CPU發 出的訪存的總次數7.4 減少Cache不命中開銷全局不命中率L2不命中率L1不命中率L2 評價第二級Cache時，應使用全局不命中率這個指標。它指出了在CPU發出的訪存中，究竟有多大比例是穿過各級Cache，最終

41、到達存儲器的。采用兩級Cache時，每條指令的平均訪存停頓時間：每條指令的平均訪存停頓時間 每條指令的平均不命中次數L1命中時間L2 每條指令的平均不命中次數L2不命中開銷L27.4 減少Cache不命中開銷例7.3 考慮某一兩級Cache：第一級Cache為L1，第二級Cache為L2。 （1）假設在1000次訪存中，L1的不命中是40次，L2的不命中是20次。求各種局部不命中率和全局不命中率。 （2）假設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，我們有以下結論：在第

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

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

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

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

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

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

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