第5章 存儲層次

1、1 1/154/154第5章 存儲層次張晨曦張晨曦 劉依劉依www.GotoS2 2/154/1545.1存儲器的層次結(jié)構(gòu)5.2Cache基本知識5.3降低Cache失效率的方法5.4減少Cache失效開銷5.5減少命中時間5.6主存5.7虛擬存儲器5.8進程保護和虛存實例5.9Alpha AXP 21064存儲層次3 3/154/1541. 從用戶的角度來看，存儲器的三個主要指標： 容量、速度和價格（指每位價格）2. 人們對這三個指標的要求 容量大、速度快、價格低3. 三個要求是相互矛盾的q速度越快，每位價格就越高；速度越快，每位價格就越高；q容量越大，每位價格就越低；容量越大，每位價格就越

2、低；q容量越大，速度越慢。容量越大，速度越慢。5.1 存儲器的層次結(jié)構(gòu)5.1.1 從單級存儲器到多級存儲器4 4/154/1545.1 存儲器的層次結(jié)構(gòu) 解決方法 采用多種存儲器技術(shù)，構(gòu)成所謂的存儲層次。 演示演示 演示演示 ( (局部性原理局部性原理) )多級存儲層次多級存儲層次5 5/154/1545.1 存儲器的層次結(jié)構(gòu) C，H，TA假設(shè)：S 容量 TA 訪問時間 C 每位價格下面僅考慮由M1和M2構(gòu)成的兩級存儲層次：pM M1 1的參數(shù)：的參數(shù)：S S1 1，T TA1A1，C C1 1pM M2 2的參數(shù)：的參數(shù)：S S2 2，T TA2A2，C C2 25.1.2 存儲層次的性能參

3、數(shù)6 6/154/1545.1 存儲器的層次結(jié)構(gòu)1. 每位價格C2. 命中率H 和失效率F命中率：CPU訪問存儲系統(tǒng)時，在M1中找到所需信息的概率。qN N1 1 訪問訪問M M1 1的次數(shù)的次數(shù)qN N2 2 訪問訪問M M2 2的次數(shù)的次數(shù) 失效率 ：F1H212211SSSCSCC211NNNH7 7/154/1545.1 存儲器的層次結(jié)構(gòu) 平均訪問時間TA T TA A HTHTA1A1（1 1H H）（）（T TA1A1T TM M） T TA1A1（1 1H H）T TM M 或或 T TA A T TA1A1FTFTM M分兩種情況來考慮CPU的一次訪存：q當命中時，訪問時間即為

4、當命中時，訪問時間即為T TA1A1（命中時間命中時間）q當不命中時，情況比較復雜。當不命中時，情況比較復雜。 不命中時的訪問時間為：不命中時的訪問時間為：T TA2A2T TB BT TA1A1T TA1A1T TM M T TM M T TA2A2T TB Bn失效開銷失效開銷T TM M：從向：從向M M2 2發(fā)出訪問請求到把整個數(shù)據(jù)發(fā)出訪問請求到把整個數(shù)據(jù)塊調(diào)入塊調(diào)入M M1 1中所需的時間。中所需的時間。n傳送一個信息塊所需的時間為傳送一個信息塊所需的時間為T TB B。 8 8/154/1545.1 存儲器的層次結(jié)構(gòu) 從主存的角度來看q“CacheCache主存主存”層次：彌補主存

5、層次：彌補主存速度的不足速度的不足q“主存輔存主存輔存”層次：層次： 彌補主存彌補主存容量的不足容量的不足1. “Cache主存”層次主存與CPU的速度差距“Cache - 主存”層次 “主存輔存”層次5.1.3 “Cache主存”和“主存輔存”層次9 9/154/1545.1 存儲器的層次結(jié)構(gòu)19801980年以來存儲器和年以來存儲器和CPUCPU性能隨時間而提高的情況性能隨時間而提高的情況 （以（以19801980年時的性能作為基準）年時的性能作為基準）1010/154/1545.1 存儲器的層次結(jié)構(gòu)兩種存儲層次兩種存儲層次1111/154/1545.1 存儲器的層次結(jié)構(gòu)存儲層次存儲層次C

6、PU對第二級的對第二級的訪問方式訪問方式比較項目比較項目目的目的存儲管理實現(xiàn)存儲管理實現(xiàn) 訪問速度的比值訪問速度的比值(第一級和第二級第一級和第二級)典型的塊典型的塊(頁頁)大小大小失效時失效時CPU是否切換是否切換“Cache 主存主存”層次層次“主存輔存主存輔存”層次層次為了彌補主存速度的不足為了彌補主存速度的不足 為了彌補主存容量的不足為了彌補主存容量的不足主要由專用硬件實現(xiàn)主要由專用硬件實現(xiàn)主要由軟件實現(xiàn)主要由軟件實現(xiàn)幾比一幾比一幾百比一幾百比一幾十個字節(jié)幾十個字節(jié)幾百到幾千個字節(jié)幾百到幾千個字節(jié)可直接訪問可直接訪問均通過第一級均通過第一級不切換不切換切換到其他進程切換到其他進程“Ca

7、che“Cache主存主存”與與“主存輔存主存輔存”層次的區(qū)別層次的區(qū)別1212/154/1545.1 存儲器的層次結(jié)構(gòu)1. 當把一個塊調(diào)入高一層(靠近CPU)存儲器時，可以放在哪些位置上? （映像規(guī)則）映像規(guī)則）當所要訪問的塊在高一層存儲器中時，如何找到該塊?（查找算法）（查找算法）當發(fā)生失效時，應(yīng)替換哪一塊？（替換算法）（替換算法）當進行寫訪問時，應(yīng)進行哪些操作? （寫策略）寫策略）5.1.4 存儲層次的四個問題1313/154/1541. 存儲空間分割與地址計算2. Cache和主存分塊5.2 Cache的基本知識 5.2.1映象規(guī)則 1. 全相聯(lián)映象 全相聯(lián)：主存中的任一塊可以被放置到

8、Cache中的任意一個位置。舉例對比：閱覽室位置 隨便坐特點：空間利用率最高，沖突概率最低，實現(xiàn)最復雜。 1414/154/1545.2 Cache的基本知識1515/154/1545.2 Cache的基本知識 直接映象 直接映象：主存中的每一塊只能被放置到Cache中唯一的一個位置。舉例（循環(huán)分配）（循環(huán)分配）對比：閱覽室位置 只有一個位置可以坐特點：空間利用率最低，沖突概率最高，實現(xiàn)最簡單。對于主存的第i 塊，若它映象到Cache的第j 塊，則 ji mod (M ) （M為Cache的塊數(shù)）1616/154/154設(shè)M=2m，則當表示為二進制數(shù)時，j實際上就是i的低m位: ji：m位位5

9、.2 Cache的基本知識1717/154/1545.2 Cache的基本知識 組相聯(lián)映象 組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個組中的任何一個位置。 舉例組相聯(lián)是直接映象和全相聯(lián)的一種折中1919/154/1545.2 Cache的基本知識組的選擇常采用位選擇算法q若主存第若主存第i i 塊映象到第塊映象到第k k 組，則組，則 k ki i modmod（G G） （G G為為CacheCache的組數(shù)）的組數(shù)）q設(shè)設(shè)G G2 2g g，則當表示為二進制數(shù)時，則當表示為二進制數(shù)時，k k 實際上就是實際上就是i i 的低的低 g g 位位: : 低g位以及直接映象中的低m

10、位通常稱為索引。 ki：g位位2020/154/1545.2 Cache的基本知識n 路組相聯(lián)：每組中有n個塊(nM/G )。n 稱為相聯(lián)度。相聯(lián)度越高，相聯(lián)度越高，CacheCache空間的利用率就越高，塊沖突空間的利用率就越高，塊沖突概率就越低，失效率也就越低。概率就越低，失效率也就越低。 絕大多數(shù)計算機的Cache: n 4想一想：想一想：相聯(lián)度一定是越大越好？相聯(lián)度一定是越大越好？全相聯(lián)全相聯(lián)直接映象直接映象組相聯(lián)組相聯(lián)n n ( (路數(shù)路數(shù)) )G G ( (組數(shù)組數(shù)) )M MM M1 11 11 1n nM M1 1G GM M2121/154/1545.2 Cache的基本知識

11、當CPU訪問Cache時，如何確定Cache中是否有所要訪問的塊？若有，如何確定其位置？1. 通過查找目錄表來實現(xiàn)目錄表的結(jié)構(gòu)q主存塊的塊地址的高位部分，稱為主存塊的塊地址的高位部分，稱為標識標識 。q每個主存塊能唯一地由其標識來確定每個主存塊能唯一地由其標識來確定5.2.2 查找算法 主主存存地地址址： 塊塊內(nèi)內(nèi)位位移移 索索 引引 標標 識識 塊塊地地址址 2222/154/1545.2 Cache的基本知識只需查找候選位置所對應(yīng)的目錄表項并行查找與順序查找提高性能的重要思想：主候選位置(MRU塊) （前瞻執(zhí)行）（前瞻執(zhí)行） 并行查找的實現(xiàn)方法相聯(lián)存儲器單體多字存儲器比較器 q舉例：舉例：

12、 路組相聯(lián)并行標識比較路組相聯(lián)并行標識比較（比較器的個數(shù)及位數(shù)）（比較器的個數(shù)及位數(shù)）q路組相聯(lián)路組相聯(lián)CacheCache的查找過程的查找過程2.2.直接映象直接映象CacheCache的查找過程的查找過程2323/154/1545.2 Cache的基本知識2424/154/1545.2 Cache的基本知識1. 所要解決的問題：當新調(diào)入一塊，而Cache又已被占滿時，替換哪一塊？直接映象Cache中的替換很簡單 因為只有一個塊，別無選擇。因為只有一個塊，別無選擇。在組相聯(lián)和全相聯(lián)Cache中，則有多個塊供選擇。 主要的替換算法有三種隨機法 優(yōu)點：優(yōu)點：實現(xiàn)簡單實現(xiàn)簡單2.先進先出法（FIF

13、O）5.2.3 替換算法2525/154/1545.2 Cache的基本知識最近最少使用法LRUq選擇近期最少被訪問的塊作為被替換的塊。選擇近期最少被訪問的塊作為被替換的塊。（實現(xiàn)比較困難）（實現(xiàn)比較困難）q實際上：實際上：選擇最久沒有被訪問過的塊作為被替換的塊。選擇最久沒有被訪問過的塊作為被替換的塊。 q優(yōu)點：優(yōu)點：失效率低。失效率低。LRU和隨機法的失效率的比較2626/154/1545.2 Cache的基本知識LRULRU和隨機法分別因其失效率低和實現(xiàn)簡單而被廣泛采用。和隨機法分別因其失效率低和實現(xiàn)簡單而被廣泛采用。2727/154/1545.2 Cache的基本知識1. “寫”在所有訪

14、存操作中所占的比例 統(tǒng)計結(jié)果表明，對于一組給定的程序：ql loadoad指令：指令：2626qs storetore指令：指令：9 9“寫”在所有訪存操作中所占的比例：9 9/(100/(10026269 9)7)7“寫”在訪問Cache操作中所占的比例： 9 9/(26/(269 9)25)255.2.4 寫策略2828/154/1545.2 Cache的基本知識 “寫”操作必須在確認是命中后才可進行 “寫”訪問有可能導致Cache和主存內(nèi)容的不一致 兩種寫策略寫策略是區(qū)分不同Cache設(shè)計方案的一個重要標志。寫直達法q執(zhí)行執(zhí)行“寫寫”操作時，不僅寫入操作時，不僅寫入CacheCache，

15、而且也寫入下，而且也寫入下一級存儲器。一級存儲器。寫回法（也稱為拷回法） q執(zhí)行執(zhí)行“寫寫”操作時，只寫入操作時，只寫入CacheCache。僅當。僅當CacheCache中相中相應(yīng)的塊被替換時，才寫回主存。應(yīng)的塊被替換時，才寫回主存。 ( (設(shè)置設(shè)置“修改位修改位”) )2929/154/1545.2 Cache的基本知識 兩種寫策略的比較寫回法的優(yōu)點：速度快，所使用的存儲器帶寬較低。寫直達法的優(yōu)點：易于實現(xiàn)，一致性好。 采用寫直達法時，若在進行“寫”操作的過程中CPU必須等待，直到“寫”操作結(jié)束，則稱CPU寫停頓。減少寫停頓的一種常用的優(yōu)化技術(shù)：采用寫緩沖器采用寫緩沖器3030/154/1

16、545.2 Cache的基本知識 “寫”操作時的調(diào)塊按寫分配(寫時取)寫失效時，先把所寫單元所在的塊調(diào)入寫失效時，先把所寫單元所在的塊調(diào)入CacheCache，再行寫入。再行寫入。不按寫分配(繞寫法)寫失效時，直接寫入下一級存儲器而不調(diào)塊。寫失效時，直接寫入下一級存儲器而不調(diào)塊。 寫策略與調(diào)塊寫回法 按寫分配寫直達法 不按寫分配3131/154/1545.2 Cache的基本知識例：DEC的Alpha AXP21064中的內(nèi)部數(shù)據(jù)Cache1. 簡介容量：8 KB塊大小：32 B塊數(shù)：256采用不按寫分配映象方法：直接映象 “寫”策略：寫直達寫緩沖器大?。?個塊5.2.5 Cache的結(jié)構(gòu) 結(jié)

17、構(gòu)圖3333/154/1545.2 Cache的基本知識 工作過程“讀”訪問命中“寫”訪問命中失效情況下的操作 混合Cache與分離Cache優(yōu)缺點失效率的比較3434/154/1545.2 Cache的基本知識16 KB16 KB容量容量1 KB1 KB2 KB2 KB4 KB4 KB8 KB8 KB32 KB32 KB指令指令 Cache3.06%失失 效效 率率 的的 比比 較較64 KB64 KB128 KB128 KB數(shù)據(jù)數(shù)據(jù) Cache混合混合 Cache2.26%1.78%1.10%0.64%0.39%0.15%0.02%24.61%20.57%15.94%10.19%6.47%

18、4.82%3.77%2.88%13.34%9.78%7.24%4.57%2.87%1.99%1.36%0.95%3535/154/1545.2 Cache的基本知識1. 失效率與硬件速度無關(guān)容易產(chǎn)生一些誤導2. 平均訪存時間 平均訪存時間 命中時間失效率失效開銷5.2.6 Cache的性能分析3636/154/1545.2 Cache的基本知識 例例5.1 5.1 假設(shè)假設(shè)CacheCache的命中時間為的命中時間為1 1個時鐘周期，失效開銷為個時鐘周期，失效開銷為5050個時鐘周期，在混合個時鐘周期，在混合CacheCache中一次中一次loadload或或storestore操作訪問操作訪

19、問CacheCache的命中時間都要增加的命中時間都要增加1 1個時鐘周期（因為混合個時鐘周期（因為混合CacheCache只有一個端只有一個端口，無法同時滿足兩個請求，會導致結(jié)構(gòu)沖突），根據(jù)表口，無法同時滿足兩個請求，會導致結(jié)構(gòu)沖突），根據(jù)表5.45.4所所列的失效率，試問指令列的失效率，試問指令CacheCache和數(shù)據(jù)和數(shù)據(jù)CacheCache容量均為容量均為1616 KBKB的分離的分離CacheCache和容量為和容量為3232 KBKB的混合的混合CacheCache相比，哪種相比，哪種CacheCache的失效率更低？的失效率更低？又假設(shè)采用寫直達策略，且有一個寫緩沖器，并且忽略

20、寫緩沖又假設(shè)采用寫直達策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。請問上述兩種情況下平均訪存時間各是多少？器引起的等待。請問上述兩種情況下平均訪存時間各是多少？3737/154/1545.2 Cache的基本知識解解 如前所述，約如前所述，約75%75%的訪存為取指令。的訪存為取指令。因此，分離因此，分離CacheCache的總體失效率為：的總體失效率為： （75%75%0.64%0.64%）（）（25%25%6.47%6.47%）2.10%2.10%根據(jù)表根據(jù)表5.45.4，容量為，容量為3232 KBKB的混合的混合CacheCache的失效率略的失效率略低一些，只有低一些，只有1

21、.99%1.99%。平均訪存時間公式可以分為平均訪存時間公式可以分為指令訪問指令訪問和和數(shù)據(jù)訪問數(shù)據(jù)訪問兩部分：兩部分： 平均訪存時間平均訪存時間指令所占的百分比指令所占的百分比（指令命中時間指令失效率（指令命中時間指令失效率失效開銷）失效開銷） 數(shù)據(jù)所占的百分比數(shù)據(jù)所占的百分比（數(shù)據(jù)命中時間數(shù)據(jù)失效率（數(shù)據(jù)命中時間數(shù)據(jù)失效率失效開銷）失效開銷） 3838/154/1545.2 Cache的基本知識所以，兩種結(jié)構(gòu)的平均訪存時間分別為：所以，兩種結(jié)構(gòu)的平均訪存時間分別為： 平均訪存時間平均訪存時間分離分離75%75%（1+0.64%1+0.64%5050）+25%+25%（1+6.47%1+6.

22、47%5050）（75%75%1.321.32）+ +（25%25%4.3254.325）0.990+1.0590.990+1.0592.052.05 平均訪存時間平均訪存時間混合混合75%75%（1+1.99%1+1.99%5050）+25%+25%（1+1+1.99%1+1+1.99%5050）（75%75%1.9951.995）+ +（25%25%2.9952.995）1.496+0.7491.496+0.7492.242.24因此，盡管分離因此，盡管分離CacheCache的實際失效率比混合的實際失效率比混合CacheCache的高，但其平均的高，但其平均訪存時間反而較低。分離訪存時間

23、反而較低。分離CacheCache提供了兩個端口，消除了結(jié)構(gòu)沖突。提供了兩個端口，消除了結(jié)構(gòu)沖突。3939/154/1545.2 Cache的基本知識 程序執(zhí)行時間CPUCPU時間（時間（CPUCPU執(zhí)行周期數(shù)執(zhí)行周期數(shù)+ +存儲器停頓周期數(shù)）存儲器停頓周期數(shù)） 時鐘周期時間時鐘周期時間其中：其中： 存儲器停頓時鐘周期數(shù)存儲器停頓時鐘周期數(shù)“讀讀”的次數(shù)的次數(shù)讀失效率讀失效率讀失讀失效開銷效開銷“寫寫”的次數(shù)的次數(shù)寫失效率寫失效率寫失效開銷寫失效開銷存儲器停頓時鐘周期數(shù)訪存次數(shù)存儲器停頓時鐘周期數(shù)訪存次數(shù)失效率失效率失效開銷失效開銷 時鐘周期時間失效開銷失效率指令數(shù)訪存次數(shù)時間executio

24、nCPIICCPU指令數(shù) 失效率 訪存次數(shù) 指令數(shù) 失效次數(shù) 每條指令的平均失效次數(shù) 時鐘周期時間指令數(shù)存儲器停頓周期數(shù)時間executionCPIICCPU4040/154/1545.2 Cache的基本知識 例例5.25.2 我們用一個和我們用一個和Alpha AXPAlpha AXP類似的機器作為第一個例子。類似的機器作為第一個例子。假設(shè)假設(shè)CacheCache失效開銷為失效開銷為5050個時鐘周期，當不考慮存儲器停頓時，所個時鐘周期，當不考慮存儲器停頓時，所有指令的執(zhí)行時間都是有指令的執(zhí)行時間都是2.02.0個時鐘周期，訪問個時鐘周期，訪問CacheCache失效率為失效率為2%2%，

25、平均每條指令訪存平均每條指令訪存1.331.33次。試分析次。試分析CacheCache對性能的影響。對性能的影響。 解解CPU CPU 時間時間ICIC( (CPICPIexeexe ) ) 時鐘周期時間時鐘周期時間存儲器停頓周期數(shù)存儲器停頓周期數(shù)指令數(shù)指令數(shù)4141/154/1545.2 Cache的基本知識考慮考慮CacheCache的失效后，性能為：的失效后，性能為： CPUCPU時間時間有有cachecacheICIC（2.02.01.331.332 %2 %5050）時鐘周期時間時鐘周期時間 ICIC3.333.33時鐘周期時間時鐘周期時間實際實際CPI CPI ：3.333.33

26、3.33/2.0 = 1.67(3.33/2.0 = 1.67(倍倍) ) CPUCPU時間也增加為原來的時間也增加為原來的1.671.67倍。倍。 但若不采用但若不采用Cache,Cache,則：則：CPICPI2.02.050501.331.3368.568.54242/154/1545.2 Cache的基本知識 Cache失效對于一個CPI較小而時鐘頻率較高的CPU來說，影響是雙重的：CPIexecution越低，固定周期數(shù)的Cache失效開銷的相對影響就越大。在計算CPI時，失效開銷的單位是時鐘周期數(shù)。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的失效開銷較大，其CPI

27、中存儲器停頓這部分也就較大。 因此Cache對于低CPI、高時鐘頻率的CPU來說更加重要。 4343/154/1545.2 Cache的基本知識 例例5.35.3 考慮兩種不同組織結(jié)構(gòu)的考慮兩種不同組織結(jié)構(gòu)的CacheCache：直接映象：直接映象CacheCache和和2 2路組相聯(lián)路組相聯(lián)CacheCache，試問它們對，試問它們對CPUCPU的性能有何影響？先求平均訪的性能有何影響？先求平均訪存時間，然后再計算存時間，然后再計算CPUCPU性能。分析時請用以下假設(shè)：性能。分析時請用以下假設(shè)： (1)(1)理想理想CacheCache（命中率為（命中率為100%100%）情況下的）情況下的

28、CPICPI為為2.02.0，時鐘周，時鐘周期為期為2ns2ns，平均每條指令訪存，平均每條指令訪存1.31.3次。次。 (2)(2)兩種兩種CacheCache容量均為容量均為64KB64KB，塊大小都是，塊大小都是3232字節(jié)。字節(jié)。 (3)(3)圖圖5.85.8說明，在組相聯(lián)說明，在組相聯(lián)CacheCache中，必須增加一個多路選擇中，必須增加一個多路選擇器，用于根據(jù)標識匹配結(jié)果從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。器，用于根據(jù)標識匹配結(jié)果從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。因為因為CPUCPU的速度直接與的速度直接與CacheCache命中的速度緊密相關(guān)，所以對于組命中的速度緊密相關(guān)，所以對于組相聯(lián)

29、相聯(lián)CacheCache，由于多路選擇器的存在而使，由于多路選擇器的存在而使CPUCPU的時鐘周期增加到的時鐘周期增加到原來的原來的1.101.10倍。倍。4444/154/1545.2 Cache的基本知識 (4) (4) 這兩種結(jié)構(gòu)這兩種結(jié)構(gòu)CacheCache的失效開銷都是的失效開銷都是7070 nsns。（在實際應(yīng)用。（在實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期）中，應(yīng)取整為整數(shù)個時鐘周期） (5) (5) 命中時間為命中時間為1 1個時鐘周期，個時鐘周期，6464 KBKB直接映象直接映象CacheCache的失效的失效率為率為1.4%1.4%，相同容量的，相同容量的2 2路組相聯(lián)路組相聯(lián)

30、CacheCache的失效率為的失效率為1.0%1.0%。4545/154/1545.2 Cache的基本知識4646/154/1545.2 Cache的基本知識 解解 平均訪存時間為：平均訪存時間為： 平均訪存時間命中時間失效率平均訪存時間命中時間失效率失效開銷失效開銷 因此，兩種結(jié)構(gòu)的平均訪存時間分別是：因此，兩種結(jié)構(gòu)的平均訪存時間分別是： 平均訪存時間平均訪存時間1 1路路2.02.0（0.0140.0147070）2.982.98 nsns 平均訪存時間平均訪存時間2 2路路2.02.01.101.10（0.0100.0107070）2.902.90 nsns 2 2路組相聯(lián)路組相聯(lián)C

31、acheCache的平均訪存時間比較低。的平均訪存時間比較低。 CPU CPU 時間時間ICIC( (CPICPIexeexe每條指令的平均存儲器每條指令的平均存儲器 停頓周期數(shù)停頓周期數(shù)) )時鐘周期時間時鐘周期時間 IC IC ( (CPICPIexeexe時鐘周期時間時鐘周期時間 每條指令的平均存儲器停頓時間每條指令的平均存儲器停頓時間) )4747/154/1545.2 Cache的基本知識因此：因此：CPUCPU時間時間1 1路路 ICIC(2.0(2.02 2(1.3(1.30.0140.01470)70) 5.275.27ICICCPUCPU時間時間2 2路路 ICIC(2.0(

32、2.02 21.101.10(1.3(1.30.0100.01070)70) 5.315.31ICIC5.315.31ICICCPUCPU時間時間1 1路路 1.011.015.275.27ICICCPUCPU時間時間2 2路路直接映象直接映象CacheCache的平均性能好一些。的平均性能好一些。4848/154/1545.2 Cache的基本知識1. 平均訪存時間命中時間失效率失效開銷2. 可以從三個方面改進Cache的性能：降低失效率減少失效開銷減少Cache命中時間3. 下面介紹17種Cache優(yōu)化技術(shù)q8 8種種用于降低失效率用于降低失效率q5 5種種用于減少失效開銷用于減少失效開銷

33、q4 4種種用于減少命中時間用于減少命中時間 5.2.7 改進Cache的性能4949/154/1541. 三種失效(3C)強制性失效(Compulsory miss)q當?shù)谝淮卧L問一個塊時，該塊不在當?shù)谝淮卧L問一個塊時，該塊不在CacheCache中，需從中，需從下一級存儲器中調(diào)入下一級存儲器中調(diào)入CacheCache，這就是強制性失效。，這就是強制性失效。 ( (冷啟動冷啟動失效，首次訪問失效失效，首次訪問失效)容量失效(Capacity miss ) q如果程序執(zhí)行時所需的塊不能全部調(diào)入如果程序執(zhí)行時所需的塊不能全部調(diào)入CacheCache中，中，則當某些塊被替換后，若又重新被訪問，就會

34、發(fā)生則當某些塊被替換后，若又重新被訪問，就會發(fā)生失效。這種失效稱為容量失效。失效。這種失效稱為容量失效。5.3 降低Cache失效率的方法5050/154/1545.3 降低Cache失效率的方法沖突失效(Conflict miss)q在組相聯(lián)或直接映象在組相聯(lián)或直接映象CacheCache中，若太多的塊映象到中，若太多的塊映象到同一組同一組( (塊塊) )中，則會出現(xiàn)該組中某個塊被別的塊替中，則會出現(xiàn)該組中某個塊被別的塊替換換( (即使別的組或塊有空閑位置即使別的組或塊有空閑位置) )，然后又被重新訪，然后又被重新訪問的情況。這就是發(fā)生了沖突失效。問的情況。這就是發(fā)生了沖突失效。 ( (碰撞

35、失效，干擾失效碰撞失效，干擾失效) ) 三種失效所占的比例 圖示I(絕對值)2.圖示(相對值)5151/154/1545.3 降低Cache失效率的方法5252/154/1545.3 降低Cache失效率的方法5353/154/1545.3 降低Cache失效率的方法可以看出：q相聯(lián)度越高，沖突失效就越少；相聯(lián)度越高，沖突失效就越少；q強制性失效和容量失效不受相聯(lián)度的影響；強制性失效和容量失效不受相聯(lián)度的影響；q強制性失效不受強制性失效不受CacheCache容量的影響，但容量失效卻隨容量的影響，但容量失效卻隨著容量的增加而減少；著容量的增加而減少；q表中的數(shù)據(jù)符合表中的數(shù)據(jù)符合2:12:1的

36、的CacheCache經(jīng)驗規(guī)則經(jīng)驗規(guī)則，即大小為，即大小為N N的的直接映象直接映象CacheCache的失效率約等于大小為的失效率約等于大小為N/2N/2的的2 2路組相路組相聯(lián)聯(lián)CacheCache的失效率。的失效率。5454/154/1545.3 降低Cache失效率的方法減少三種失效的方法q強制性失效：強制性失效：增加塊大小，預(yù)取增加塊大小，預(yù)?。ū旧砗苌伲ū旧砗苌伲﹒容量失效：容量失效：增加容量增加容量 （抖動現(xiàn)象）（抖動現(xiàn)象）q沖突失效：沖突失效：提高相聯(lián)度提高相聯(lián)度（理想情況：全相聯(lián)）（理想情況：全相聯(lián)）許多降低失效率的方法會增加命中時間或失效開銷5555/154/1545.3

37、 降低Cache失效率的方法1. 失效率與塊大小的關(guān)系對于給定的Cache容量，當塊大小增加時，失效率開始是下降，后來反而上升了。 原因：q一方面它減少了強制性失效；一方面它減少了強制性失效；q另一方面，由于增加塊大小會減少另一方面，由于增加塊大小會減少CacheCache中塊的數(shù)目，中塊的數(shù)目，所以有可能會增加沖突失效。所以有可能會增加沖突失效。 Cache容量越大，使失效率達到最低的塊大小就越大。5.3.1 增加Cache塊大小5656/154/1545.3 降低Cache失效率的方法5757/154/1545.3 降低Cache失效率的方法各種塊大小情況下Cache的失效率 塊大小（字節(jié)

38、） 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% 256 22.01% 9.51% 3.29% 1.15% 0.49% 5858/154/1545.3 降低Cache失效率的方法 增加塊大小會增加失效開銷 例例5.45.4 假定存儲系統(tǒng)在延遲假定存儲系統(tǒng)在延遲4040個時鐘周期后，每個時鐘周期后，每2 2個時

39、鐘周個時鐘周期能送出期能送出1616個字節(jié)。即，經(jīng)過個字節(jié)。即，經(jīng)過4242個時鐘周期，它可提供個時鐘周期，它可提供1616個字個字節(jié)；經(jīng)過節(jié)；經(jīng)過4444個時鐘周期，可提供個時鐘周期，可提供3232個字節(jié)；依此類推。請問對個字節(jié)；依此類推。請問對于表于表5.65.6中列出的各種容量的中列出的各種容量的CacheCache，在塊大小分別為多少時，在塊大小分別為多少時，平均訪存時間最??？平均訪存時間最小？ 解解 解題過程解題過程 1 1 KBKB、4 4 KBKB、1616 KB Cache: KB Cache: 塊大小塊大小3232 B B 6464 KBKB、256256 KB Cache:

40、 KB Cache: 塊大小塊大小6464 B B5959/154/1545.3 降低Cache失效率的方法各種塊大小情況下Cache的平均訪存時間 塊大小（字節(jié)） 失效開銷（時鐘周期） Cache容量（字節(jié)） 1K 4K 16K 64K 256K 16427.321 4.599 2.655 1.857 1.458 32446.870 4.186 2.263 1.857 1.308 64487.605 4.360 2.267 1.594 1.245 1285610.318 5.357 2.551 1.509 1.274 2567216.847 7.847 3.369 1.571 1.353 6

41、060/154/1545.3 降低Cache失效率的方法1. 采用相聯(lián)度超過8的方案的實際意義不大。2. 2:1 Cache經(jīng)驗規(guī)則 容量為N的直接映象Cache的失效率和容量為N/2的2路組相聯(lián)Cache的失效率差不多相同。 提高相聯(lián)度是以增加命中時間為代價。 例如：qTTLTTL或或ECLECL板級板級CacheCache，2 2路組相聯(lián)：路組相聯(lián)： 增加增加1010q定制的定制的CMOS Cache, 2CMOS Cache, 2路組相聯(lián)：路組相聯(lián)： 增加增加2 25.3.2 提高相聯(lián)度6161/154/1545.3 降低Cache失效率的方法 例例5.55.5 假定提高相聯(lián)度會按下列比

42、例增大處理器時鐘周期：假定提高相聯(lián)度會按下列比例增大處理器時鐘周期： 時鐘周期時鐘周期2 2路路 1.101.10時鐘周期時鐘周期1 1路路 時鐘周期時鐘周期4 4路路 1.121.12時鐘周期時鐘周期1 1路路 時鐘周期時鐘周期8 8路路 1.141.14時鐘周期時鐘周期1 1路路 假定命中時間為一個時鐘周期，直接映象情況下失效開銷為假定命中時間為一個時鐘周期，直接映象情況下失效開銷為5050個個時鐘周期，而且假設(shè)不必將失效開銷取整。使用表時鐘周期，而且假設(shè)不必將失效開銷取整。使用表5.55.5中的失效率，試中的失效率，試問當問當CacheCache為多大時，以下不等式成立？為多大時，以下不

43、等式成立？ 平均訪存時間平均訪存時間8 8路路 平均訪存時間平均訪存時間4 4路路 平均訪存時間平均訪存時間4 4路路 平均訪存時間平均訪存時間2 2路路 平均訪存時間平均訪存時間2 2路路 平均訪存時間平均訪存時間1 1路路 6262/154/1545.3 降低Cache失效率的方法解解 在各種相聯(lián)度的情況下，平均訪存時間分別為：在各種相聯(lián)度的情況下，平均訪存時間分別為： 平均訪存時間平均訪存時間8 8路路 = = 命中時間命中時間8 8路路 + + 失效率失效率8 8路路失效開銷失效開銷8 8路路 = 1.14= 1.14失效率失效率8 8路路5050 平均訪存時間平均訪存時間4 4路路

44、= 1.12 = 1.12 失效率失效率4 4路路5050 平均訪存時間平均訪存時間2 2路路 = 1.10 = 1.10 失效率失效率2 2路路5050 平均訪存時間平均訪存時間1 1路路 = 1.00 = 1.00 失效率失效率1 1路路5050 把相應(yīng)的失效率代入上式，即可得平均訪存時間。把相應(yīng)的失效率代入上式，即可得平均訪存時間。 例如，例如，1 1 KBKB的直接映象的直接映象CacheCache的平均訪存時間為：的平均訪存時間為： 平均訪存時間平均訪存時間1 1路路 = 1.00= 1.000.1330.13350507.657.65 128128 KBKB的的8 8路組相聯(lián)路組相

45、聯(lián)CacheCache的平均訪存時間為：的平均訪存時間為： 平均訪存時間平均訪存時間8 8路路060.00650501.441.44Cache容量相聯(lián)度（路） 124817.65 6.60 6.22 5.44 25.90 4.90 4.62 4.09 44.60 3.95 3.57 3.19 83.30 3.00 2.87 2.59 162.45 2.20 2.12 2.04 322.00 1.80 1.77 1.79 641.70 1.60 1.57 1.59 1281.50 1.45 1.42 1.44 在各種容量和相聯(lián)度情況下在各種容量和相聯(lián)度情況下CacheCac

46、he的平均訪存時間的平均訪存時間6464/154/1545.3 降低Cache失效率的方法 當當CacheCache容量不超過容量不超過1616 KBKB時，上述三個不等式成立。時，上述三個不等式成立。 從從3232 KBKB開始，對于平均訪存時間有：開始，對于平均訪存時間有：4 4路組相聯(lián)的平均訪存時間小于路組相聯(lián)的平均訪存時間小于2 2路組相聯(lián)的路組相聯(lián)的; ;2 2路組相聯(lián)的小于直接映象的路組相聯(lián)的小于直接映象的; ;但但8 8路組相聯(lián)的卻比路組相聯(lián)的卻比4 4路組相聯(lián)的大。路組相聯(lián)的大。6565/154/1545.3 降低Cache失效率的方法1. 最直接的方法是增加Cache的容量缺

47、點:q增加成本增加成本q可能增加命中時間可能增加命中時間2. 這種方法在片外Cache中用得比較多 5.3.3 增加Cache的容量6666/154/1545.3 降低Cache失效率的方法1. 一種能減少沖突失效次數(shù)而又不影響時鐘頻率的方法。2. 基本思想在Cache和它從下一級存儲器調(diào)數(shù)據(jù)的通路之間設(shè)置一個全相聯(lián)的小Cache，用于存放被替換出去的塊(稱為Victim)，以備重用。工作過程5.3.4 Victim Cache 6767/154/1545.3 降低Cache失效率的方法Victim Cache在存儲層次中的位置 6868/154/1545.3 降低Cache失效率的方法 作用

48、對于減小沖突失效很有效，特別是對于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。例如項數(shù)為項數(shù)為4 4的的Victim Cache:Victim Cache: 能使能使4 4 KBKB CacheCache的沖突失效減少的沖突失效減少20%20%90%90%6969/154/1545.3 降低Cache失效率的方法1. 多路組相聯(lián)的低失效率和直接映象的命中速度2. 偽相聯(lián)Cache的優(yōu)點命中時間小失效率低5.3.5 偽相聯(lián) Cache 優(yōu)點優(yōu)點缺點缺點直接映象直接映象組相聯(lián)組相聯(lián)命中時間小命中時間小命中時間大命中時間大失效率高失效率高失效率低失效率低 基本思想及工作原理 （動畫演示） 在邏輯上

49、把直接映象在邏輯上把直接映象CacheCache的空間上下平分為兩個區(qū)。對于的空間上下平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián)任何一次訪問，偽相聯(lián)CacheCache先按直接映象先按直接映象CacheCache的方式去處理。的方式去處理。若命中，則其訪問過程與直接映象若命中，則其訪問過程與直接映象CacheCache的情況一樣。若不命中，的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下一級存儲器。則就只好訪問下一級存儲器。 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。7171/154/15

50、45.3 降低Cache失效率的方法 例例5.65.6 假設(shè)當在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配，而假設(shè)當在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配，而在另一個位置才找到數(shù)據(jù)（偽命中）需要在另一個位置才找到數(shù)據(jù)（偽命中）需要2 2個額外的周期。仍用個額外的周期。仍用上個例子中的數(shù)據(jù)，問：當上個例子中的數(shù)據(jù)，問：當CacheCache容量分別為容量分別為2 2 KBKB和和128128 KBKB時，直時，直接映象、接映象、2 2路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度最路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度最快？快？ 解解 首先考慮標準的平均訪存時間公式：首先考慮標準的平均訪存時間公式：

51、平均訪存時間平均訪存時間偽相聯(lián)偽相聯(lián) 命中時間命中時間偽相聯(lián)偽相聯(lián)失效率失效率偽相聯(lián)偽相聯(lián)失效開銷失效開銷偽相聯(lián)偽相聯(lián)7272/154/1545.3 降低Cache失效率的方法 由于：由于： 失效率失效率偽相聯(lián)偽相聯(lián)失效率失效率2 2路路 命中時間命中時間偽相聯(lián)偽相聯(lián)命中時間命中時間1 1路路偽命中率偽命中率偽相聯(lián)偽相聯(lián)2 2 偽相聯(lián)查找的命中率等于偽相聯(lián)查找的命中率等于2 2路組相聯(lián)路組相聯(lián)CacheCache的命中率和直接映象的命中率和直接映象CacheCache命中率之差。命中率之差。 偽命中率偽命中率偽相聯(lián)偽相聯(lián) 命中率命中率2 2路路命中率命中率1 1路路 （1 1失效率失效率2 2

52、路路）（）（1 1失效率失效率1 1路路） 失效率失效率1 1路路失效率失效率2 2路路 綜合上述分析，有：綜合上述分析，有： 平均訪存時間平均訪存時間偽相聯(lián)偽相聯(lián)命中時間命中時間1 1路路（失效率（失效率1 1路路失效率失效率2 2路路）2 2 失效率失效率2 2路路失效開銷失效開銷1 1路路7373/154/1545.3 降低Cache失效率的方法將前面表中的數(shù)據(jù)代入上面的公式，得：將前面表中的數(shù)據(jù)代入上面的公式，得： 平均訪存時間平均訪存時間偽相聯(lián)，偽相聯(lián)，2 2 KBKB 1 1（0.0980.0980.0760.076）2 2（0.0760.0765050）4.8444.844 平均

53、訪存時間平均訪存時間偽相聯(lián)，偽相聯(lián)，128128 KBKB 1 1（0.0100.0100.0070.007）2 2（0.0070.0075050）1.3561.356根據(jù)上一個例子中的表，對于根據(jù)上一個例子中的表，對于2 2 KBKB Cache Cache，可得：，可得： 平均訪存時間平均訪存時間1 1路路 5.90 5.90 個時鐘個時鐘 平均訪存時間平均訪存時間2 2路路 4.90 4.90 個時鐘個時鐘7474/154/1545.3 降低Cache失效率的方法 對于對于128KB128KB的的CacheCache有，可得：有，可得： 平均訪存時間平均訪存時間1 1路路 1.50 1.

54、50 個時鐘個時鐘 平均訪存時間平均訪存時間2 2路路 1.45 1.45 個時鐘個時鐘可見，對于這兩種可見，對于這兩種CacheCache容量，偽相聯(lián)容量，偽相聯(lián)CacheCache都是速度最快的。都是速度最快的。 缺點： 多種命中時間7575/154/1545.3 降低Cache失效率的方法1. 指令和數(shù)據(jù)都可以預(yù)取2. 預(yù)取內(nèi)容既可放入Cache，也可放在外緩沖器中。例如：指令流緩沖器例如：指令流緩沖器3. 指令預(yù)取通常由Cache之外的硬件完成4. 預(yù)取效果Joppi的研究結(jié)果q指令預(yù)取指令預(yù)取 (4(4 KBKB，直接映象，直接映象CacheCache，塊大小，塊大小1616 B B

55、)n1 1個塊的指令流緩沖器：個塊的指令流緩沖器： 捕獲捕獲15152525的失效的失效n4 4個塊的指令流緩沖器：個塊的指令流緩沖器： 捕獲捕獲5050n1616個塊的指令流緩沖器：捕獲個塊的指令流緩沖器：捕獲72725.3.6 硬件預(yù)取 7676/154/1545.3 降低Cache失效率的方法q數(shù)據(jù)預(yù)取數(shù)據(jù)預(yù)取 (4(4 KB,KB,直接映象直接映象Cache)Cache)n1 1個數(shù)據(jù)流緩沖器：捕獲個數(shù)據(jù)流緩沖器：捕獲2525的失效的失效n還可以采用多個數(shù)據(jù)流緩沖器還可以采用多個數(shù)據(jù)流緩沖器Palacharla和Kessler的研究結(jié)果q流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)流緩沖器：既能

56、預(yù)取指令又能預(yù)取數(shù)據(jù)q對于兩個對于兩個6464 KBKB四路組相聯(lián)四路組相聯(lián)CacheCache來說：來說：n8 8個流緩沖器能捕獲個流緩沖器能捕獲50507070的失效的失效7777/154/1545.3 降低Cache失效率的方法 例例5.75.7 Alpha AXP 21064 Alpha AXP 21064采用指令預(yù)取技術(shù)，其實際失效率采用指令預(yù)取技術(shù)，其實際失效率是多少？若不采用指令預(yù)取技術(shù)，是多少？若不采用指令預(yù)取技術(shù)，Alpha AXP 21064Alpha AXP 21064的指令的指令CacheCache必須為多大才能保持平均訪存時間不變？必須為多大才能保持平均訪存時間不變？

57、 解解 假設(shè)當指令不在指令假設(shè)當指令不在指令CacheCache里，而在預(yù)取緩沖器中找到時，里，而在預(yù)取緩沖器中找到時，需要多花一個時鐘周期。需要多花一個時鐘周期。 下面是修改后的公式：下面是修改后的公式： 平均訪存時間預(yù)取平均訪存時間預(yù)取 命中時間失效率命中時間失效率預(yù)取命中率預(yù)取命中率1 1 失效率失效率（1 1預(yù)取命中率）預(yù)取命中率）失效開銷失效開銷7878/154/1545.3 降低Cache失效率的方法 假設(shè)預(yù)取命中率為假設(shè)預(yù)取命中率為25%25%，命中時間為，命中時間為2 2個時鐘周期，失效開銷個時鐘周期，失效開銷為為5050個時鐘周期。查表可知個時鐘周期。查表可知8 8 KBKB

58、指令指令CacheCache的失效率為的失效率為1.10%1.10%。則：。則： 平均訪存時間平均訪存時間預(yù)取預(yù)取 2 2（1.10 %1.10 %25 %25 %1 1）1.10 %1.10 %（1 125 %25 %）5050 2 20.002750.002750.413 0.413 2.4152.415 為了得到相同性能下的實際失效率，由原始公式得：為了得到相同性能下的實際失效率，由原始公式得： 平均訪存時間平均訪存時間 命中時間失效率命中時間失效率失效開銷失效開銷 失效率失效率 （平均訪存時間命中時間）（平均訪存時間命中時間）/ /失效開銷失效開銷 （2.4152.4152 2）/50

59、/500.83 %0.83 %7979/154/1545.3 降低Cache失效率的方法 在編譯時加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請求。1. 預(yù)取有以下幾種類型：寄存器預(yù)?。喊褦?shù)據(jù)取到寄存器中。Cache預(yù)?。褐粚?shù)據(jù)取到Cache中。故障性預(yù)取：在預(yù)取時，若出現(xiàn)虛地址故障或違反保護權(quán)限，就會發(fā)生異常。非故障性預(yù)?。涸谟龅竭@種情況時則不會發(fā)生異常，因為這時它會放棄預(yù)取，轉(zhuǎn)變?yōu)榭詹僮鳌?5.3.7 編譯器控制的預(yù)取 8080/154/1545.3 降低Cache失效率的方法本節(jié)假定本節(jié)假定CacheCache預(yù)取都是非故障性的，預(yù)取都是非故障性的，也稱非綁定預(yù)取。也稱非綁定預(yù)取。 在預(yù)取數(shù)

60、據(jù)的同時，處理器應(yīng)能繼續(xù)執(zhí)行。 只有這樣，預(yù)取才有意義。 非阻塞非阻塞Cache (Cache (非鎖定非鎖定Cache)Cache) 編譯器控制預(yù)取的目的 使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。 循環(huán)是預(yù)取優(yōu)化的主要對象失效開銷小時：循環(huán)體展開12次2.失效開銷大時：循環(huán)體展開許多次8181/154/1545.3 降低Cache失效率的方法 例例5.85.8 對于下面的程序，首先判斷哪些訪問可能會導致數(shù)對于下面的程序，首先判斷哪些訪問可能會導致數(shù)據(jù)據(jù)CacheCache失效。然后，加入預(yù)取指令以減少失效。最后，計算所失效。然后，加入預(yù)取指令以減少失效。最后，計算所執(zhí)