計(jì)算機(jī)體系結(jié)構(gòu)：第5章 存儲(chǔ)層次

1、5.1存儲(chǔ)器的層次結(jié)構(gòu)5.2Cache基本知識(shí)5.3降低Cache失效率的方法5.4減少Cache失效開銷5.5減少命中時(shí)間5.6主存第5章 存儲(chǔ)層次從用戶的角度來(lái)看，存儲(chǔ)器的三個(gè)主要指標(biāo)： 容量、速度和價(jià)格（指每位價(jià)格）對(duì)這三個(gè)指標(biāo)的要求 容量大、速度快、價(jià)格低三個(gè)要求相互矛盾速度越快，每位價(jià)格就越高；容量越大，每位價(jià)格就越低；容量越大，速度越慢。5.1 存儲(chǔ)器的層次結(jié)構(gòu)5.1.1 從單級(jí)存儲(chǔ)器到多級(jí)存儲(chǔ)器5.1 存儲(chǔ)器的層次結(jié)構(gòu)解決方法 采用多種存儲(chǔ)器技術(shù)，構(gòu)成所謂的存儲(chǔ)層次。 (局部性原理)多級(jí)存儲(chǔ)層次各級(jí)存儲(chǔ)器的主要性能特性 CPU與主存儲(chǔ)器的速度差距越來(lái)越大 目前相差兩個(gè)數(shù)量級(jí),今后

2、CPU與主存儲(chǔ)器的速度差距會(huì)更大5.1 存儲(chǔ)器的層次結(jié)構(gòu)1980年以來(lái)存儲(chǔ)器和CPU性能隨時(shí)間而提高的情況 （以1980年時(shí)的性能作為基準(zhǔn)）5.1 存儲(chǔ)器的層次結(jié)構(gòu) C，H，TA假設(shè)：S 容量 TA 訪問(wèn)時(shí)間 C 每位價(jià)格下面僅考慮由M1和M2構(gòu)成的兩級(jí)存儲(chǔ)層次：M1的參數(shù)：S1，TA1，C1M2的參數(shù)：S2，TA2，C25.1.2 存儲(chǔ)層次的性能參數(shù)5.1 存儲(chǔ)器的層次結(jié)構(gòu)每位價(jià)格C命中率H 和失效率F命中率：CPU訪問(wèn)存儲(chǔ)系統(tǒng)時(shí)，在M1中找到所需信息的概率。N1 訪問(wèn)M1的次數(shù)N2 訪問(wèn)M2的次數(shù) 失效率 ：F1H5.1 存儲(chǔ)器的層次結(jié)構(gòu)平均訪問(wèn)時(shí)間TA分兩種情況來(lái)考慮CPU的一次訪存：當(dāng)

3、命中時(shí)，訪問(wèn)時(shí)間即為TA1（命中時(shí)間）當(dāng)不命中時(shí)，情況比較復(fù)雜。 不命中時(shí)的訪問(wèn)時(shí)間為：TA2TBTA1TA1TM TM TA2TB失效開銷TM：從向M2發(fā)出訪問(wèn)請(qǐng)求到把整個(gè)數(shù)據(jù)塊調(diào)入M1中所需的時(shí)間傳送一個(gè)信息塊所需的時(shí)間為TB所以: TA HTA1（1H）（TA1TM） TA1（1H）TM 或 TA TA1FTM5.1 存儲(chǔ)器的層次結(jié)構(gòu)從主存的角度來(lái)看“Cache主存”層次：彌補(bǔ)主存速度的不足主存與CPU的速度差距“Cache - 主存”層次 “主存輔存”層次：彌補(bǔ)主存容量的不足5.1.3 “Cache主存”和“主存輔存”層次5.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)層次CPU對(duì)第二級(jí)的訪問(wèn)方式比較項(xiàng)目

4、目的存儲(chǔ)管理實(shí)現(xiàn) 訪問(wèn)速度的比值(第一級(jí)和第二級(jí))典型的塊(頁(yè))大小失效時(shí)CPU是否切換“Cache 主存”層次“主存輔存”層次為了彌補(bǔ)主存速度的不足為了彌補(bǔ)主存容量的不足主要由專用硬件實(shí)現(xiàn)主要由軟件實(shí)現(xiàn)幾比一幾百比一幾十個(gè)字節(jié)幾百到幾千個(gè)字節(jié)可直接訪問(wèn)均通過(guò)第一級(jí)不切換切換到其他進(jìn)程“Cache主存”與“主存輔存”層次的區(qū)別5.1 存儲(chǔ)器的層次結(jié)構(gòu)當(dāng)把一個(gè)塊調(diào)入高一層(靠近CPU)存儲(chǔ)器時(shí)，可以放在哪些位置上? （映像規(guī)則）當(dāng)所要訪問(wèn)的塊在高一層存儲(chǔ)器中時(shí)，如何找到該塊?（查找算法）當(dāng)發(fā)生失效時(shí)，應(yīng)替換哪一塊？（替換算法）當(dāng)進(jìn)行寫訪問(wèn)時(shí)，應(yīng)進(jìn)行哪些操作? （寫策略）5.1.4 存儲(chǔ)層次的四個(gè)

5、問(wèn)題基本工作原理Cache和主存分塊5.2 Cache的基本知識(shí) 5.2 Cache的基本知識(shí)5.2.1映象規(guī)則 全相聯(lián)映象 全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個(gè)位置。對(duì)比：閱覽室位置 隨便坐特點(diǎn)：空間利用率最高，沖突概率最低，實(shí)現(xiàn)最復(fù)雜。 5.2 Cache的基本知識(shí)直接映象 直接映象：主存中的每一塊只能被放置到Cache中唯一的一個(gè)位置。（循環(huán)分配）對(duì)比：閱覽室位置 只有一個(gè)位置可以坐特點(diǎn)：空間利用率最低，沖突概率最高，實(shí)現(xiàn)最簡(jiǎn)單。對(duì)于主存的第i 塊，若它映象到Cache的第j 塊，則 ji mod (M ) （M為Cache的塊數(shù)）設(shè)M=2m，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，j

6、實(shí)際上就是i的低m位: ji：m位5.2 Cache的基本知識(shí)組相聯(lián)映象 組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個(gè)組中的任何一個(gè)位置。組相聯(lián)是直接映象和全相聯(lián)的一種折中5.2 Cache的基本知識(shí)組的選擇常采用位選擇算法若主存第i 塊映象到第k 組，則 ki mod（G） （G為Cache的組數(shù)）設(shè)G2g，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，k 實(shí)際上就是i 的低 g 位: 低g位以及直接映象中的低m位通常稱為索引。 ki：g位5.2 Cache的基本知識(shí)n 路組相聯(lián)：每組中有n個(gè)塊(nM/G )。n 稱為相聯(lián)度。相聯(lián)度越高，Cache空間的利用率就越高，塊沖突概率就越低，失效率也就越低。

7、絕大多數(shù)計(jì)算機(jī)的Cache: n 4想一想：相聯(lián)度一定是越大越好？全相聯(lián)直接映象組相聯(lián)n (路數(shù))G (組數(shù))MM111nM1GM5.2 Cache的基本知識(shí)當(dāng)CPU訪問(wèn)Cache時(shí)，如何確定Cache中是否有所要訪問(wèn)的塊？若有，如何確定其位置？通過(guò)查找目錄表來(lái)實(shí)現(xiàn)目錄表的結(jié)構(gòu)主存塊的塊地址的高位部分，稱為標(biāo)識(shí) 。每個(gè)主存塊能唯一地由其標(biāo)識(shí)來(lái)確定5.2.2 查找算法5.2 Cache的基本知識(shí)只需查找候選位置所對(duì)應(yīng)的目錄表項(xiàng)一個(gè)主存塊可以映像到Cache中的位置不同映像規(guī)則不同直接相聯(lián)：1個(gè)表項(xiàng)全相聯(lián)：所有表項(xiàng)（用相聯(lián)存儲(chǔ)器實(shí)現(xiàn)）n路組相聯(lián)：相鄰的n個(gè)表項(xiàng)標(biāo)識(shí)有效位(0/1)011目錄表項(xiàng) 主

8、存地址 區(qū)號(hào)E 塊號(hào)B 塊內(nèi)地址W Cache地址 塊號(hào)b 塊內(nèi)地址w 塊失效 相等比較 比較相等且有效為1 E 1 訪問(wèn)Cache 區(qū)號(hào)E（按地址訪問(wèn)） 有效位 區(qū)表存儲(chǔ)器 直接相聯(lián)的查找方法5.2 Cache的基本知識(shí)并行查找的實(shí)現(xiàn)方法相聯(lián)存儲(chǔ)器 全相聯(lián)單體多字存儲(chǔ)器比較器：組相聯(lián)路組相聯(lián)并行標(biāo)識(shí)比較（比較器的個(gè)數(shù)及位數(shù)）5.2 Cache的基本知識(shí)Index組內(nèi)塊號(hào)塊內(nèi)地址Cache地址：5.2 Cache的基本知識(shí)所要解決的問(wèn)題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時(shí)，替換哪一塊？直接映象Cache中的替換很簡(jiǎn)單因?yàn)橹挥幸粋€(gè)塊，別無(wú)選擇。在組相聯(lián)和全相聯(lián)Cache中，則有多個(gè)塊供選擇。

9、主要的替換算法有三種隨機(jī)法：實(shí)現(xiàn)簡(jiǎn)單先進(jìn)先出法（FIFO）最近最少使用法LRU5.2.3 替換算法5.2 Cache的基本知識(shí)最近最少使用法LRU選擇近期最少被訪問(wèn)的塊作為被替換的塊。（實(shí)現(xiàn)比較困難）實(shí)際上：選擇最久沒(méi)有被訪問(wèn)過(guò)的塊作為被替換的塊。 優(yōu)點(diǎn)：失效率低。LRU和隨機(jī)法分別因其失效率低和實(shí)現(xiàn)簡(jiǎn)單而被廣泛采用。5.2 Cache的基本知識(shí)“寫”在所有訪存操作中所占的比例 統(tǒng)計(jì)結(jié)果表明，對(duì)于一組給定的程序：load指令：26store指令：9“寫”在所有訪存操作中所占的比例：9/(100269)7“寫”在訪問(wèn)數(shù)據(jù)Cache操作中所占的比例： 9/(269)255.2.4 寫策略5.2 C

10、ache的基本知識(shí)“寫”操作必須在確認(rèn)是命中后才可進(jìn)行“寫”訪問(wèn)有可能導(dǎo)致Cache和主存內(nèi)容的不一致兩種寫策略寫策略是區(qū)分不同Cache設(shè)計(jì)方案的一個(gè)重要標(biāo)志。寫直達(dá)法執(zhí)行“寫”操作時(shí)，不僅寫入Cache，而且也寫入下一級(jí)存儲(chǔ)器。寫回法（也稱為拷回法） 執(zhí)行“寫”操作時(shí)，只寫入Cache。僅當(dāng)Cache中相應(yīng)的塊被替換時(shí)，才寫回主存。 (設(shè)置“修改位”)5.2 Cache的基本知識(shí)兩種寫策略的比較寫回法的優(yōu)點(diǎn)：速度快，所使用的存儲(chǔ)器帶寬較低。寫直達(dá)法的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，一致性好。采用寫直達(dá)法時(shí)，若在進(jìn)行“寫”操作的過(guò)程中CPU必須等待，直到“寫”操作結(jié)束，則稱CPU寫停頓。減少寫停頓的一種常用

11、的優(yōu)化技術(shù)：采用寫緩沖器5.2 Cache的基本知識(shí)“寫”操作時(shí)的調(diào)塊按寫分配(寫時(shí)取)寫失效時(shí)，先把所寫單元所在的塊調(diào)入Cache，再行寫入。不按寫分配(繞寫法)寫失效時(shí)，直接寫入下一級(jí)存儲(chǔ)器而不調(diào)塊。寫策略與調(diào)塊寫回法 按寫分配寫直達(dá)法 不按寫分配5.2 Cache的基本知識(shí)例：DEC的Alpha AXP21064中的內(nèi)部數(shù)據(jù)Cache簡(jiǎn)介容量：8 KB塊大?。?2 B塊數(shù)：256采用不按寫分配映象方法：直接映象 “寫”策略：寫直達(dá)寫緩沖器大小：4個(gè)塊5.2.5 Cache的結(jié)構(gòu)結(jié)構(gòu)圖5.2 Cache的基本知識(shí)失效率與硬件速度無(wú)關(guān)容易產(chǎn)生一些誤導(dǎo)平均訪存時(shí)間 平均訪存時(shí)間 命中時(shí)間失效率

12、失效開銷5.2.6 Cache的性能分析5.2 Cache的基本知識(shí)例5.1 假設(shè)Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效開銷為50個(gè)時(shí)鐘周期，在混合Cache中一次load或store操作訪問(wèn)Cache的命中時(shí)間都要增加1個(gè)時(shí)鐘周期（因?yàn)榛旌螩ache只有一個(gè)端口，無(wú)法同時(shí)滿足兩個(gè)請(qǐng)求，會(huì)導(dǎo)致結(jié)構(gòu)沖突），根據(jù)下表所列的失效率，試問(wèn)指令Cache和數(shù)據(jù)Cache容量均為16 KB的分離Cache和容量為32 KB的混合Cache相比，哪種Cache的失效率更低？又假設(shè)采用寫直達(dá)策略，且有一個(gè)寫緩沖器，并且忽略寫緩沖器引起的等待。請(qǐng)問(wèn)上述兩種情況下平均訪存時(shí)間各是多少？5.2 Cache的基本知

13、識(shí)16 KB容量1 KB2 KB4 KB8 KB32 KB指令 Cache3.06%失 效 率 的 比 較64 KB128 KB數(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%4.82%3.77%2.88%13.34%9.78%7.24%4.57%2.87%1.99%1.36%0.95%5.2 Cache的基本知識(shí)解 約100%/(100%+26%+9%)=75%的訪存為取指令。因此，分離Cache的總體失效率為： （75%0.64%）（25%6.47%）2.10%根據(jù)表中容量為32

14、 KB的混合Cache的失效率略低一些，只有1.99%。平均訪存時(shí)間公式可以分為指令訪問(wèn)和數(shù)據(jù)訪問(wèn)兩部分： 平均訪存時(shí)間指令所占的百分比（指令命中時(shí)間指令失效率失效開銷） 數(shù)據(jù)所占的百分比（數(shù)據(jù)命中時(shí)間數(shù)據(jù)失效率失效開銷） 5.2 Cache的基本知識(shí)所以，兩種結(jié)構(gòu)的平均訪存時(shí)間分別為： 平均訪存時(shí)間分離75%（1+0.64%50）+25%（1+6.47%50）（75%1.32）+（25%4.325）0.990+1.0592.05 平均訪存時(shí)間混合75%（1+1.99%50）+25%（1+1+1.99%50）（75%1.995）+（25%2.995）1.496+0.7492.24因此，盡管分離

15、Cache的實(shí)際失效率比混合Cache的高，但其平均訪存時(shí)間反而較低。分離Cache提供了兩個(gè)端口，消除了結(jié)構(gòu)沖突。5.2 Cache的基本知識(shí)程序執(zhí)行時(shí)間CPU時(shí)間（CPU執(zhí)行周期數(shù)+存儲(chǔ)器停頓周期數(shù)） 時(shí)鐘周期時(shí)間其中： 存儲(chǔ)器停頓時(shí)鐘周期數(shù)“讀”的次數(shù)讀失效率讀失效開銷“寫”的次數(shù)寫失效率寫失效開銷存儲(chǔ)器停頓時(shí)鐘周期數(shù)訪存次數(shù)失效率失效開銷 5.2 Cache的基本知識(shí)例5.2 假設(shè)Cache失效開銷為50個(gè)時(shí)鐘周期，當(dāng)不考慮存儲(chǔ)器停頓時(shí)，所有指令的執(zhí)行時(shí)間都是2.0個(gè)時(shí)鐘周期，訪問(wèn)Cache失效率為2%，平均每條指令訪存1.33次。試分析Cache對(duì)性能的影響。 解CPU 時(shí)間IC(C

16、PIexe ) 時(shí)鐘周期時(shí)間存儲(chǔ)器停頓周期數(shù)指令數(shù)考慮Cache的失效后，性能為： CPU時(shí)間有cacheIC（2.01.332 %50）時(shí)鐘周期時(shí)間 IC3.33時(shí)鐘周期時(shí)間實(shí)際CPI ：3.333.33/2.0 = 1.67(倍) CPU時(shí)間也增加為原來(lái)的1.67倍。但若不采用Cache,則：CPI2.0501.3368.55.2 Cache的基本知識(shí)Cache失效對(duì)于一個(gè)CPI較小而時(shí)鐘頻率較高的CPU來(lái)說(shuō)，影響是雙重的：CPIexecution越低，固定周期數(shù)的Cache失效開銷的相對(duì)影響就越大。在計(jì)算CPI時(shí)，失效開銷的單位是時(shí)鐘周期數(shù)。因此，即使兩臺(tái)計(jì)算機(jī)的存儲(chǔ)層次完全相同，時(shí)鐘頻

17、率較高的CPU的失效開銷較大，其CPI中存儲(chǔ)器停頓這部分也就較大。 因此Cache對(duì)于低CPI、高時(shí)鐘頻率的CPU來(lái)說(shuō)更加重要。 5.2 Cache的基本知識(shí)例5.3 考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象Cache和2路組相聯(lián)Cache，試問(wèn)它們對(duì)CPU的性能有何影響？先求平均訪存時(shí)間，然后再計(jì)算CPU性能。分析時(shí)請(qǐng)用以下假設(shè)： (1)理想Cache（命中率為100%）情況下的CPI為2.0，時(shí)鐘周期為2ns，平均每條指令訪存1.3次。 (2)兩種Cache容量均為64KB，塊大小都是32字節(jié)。 (3)圖5.8說(shuō)明，在組相聯(lián)Cache中，必須增加一個(gè)多路選擇器，用于根據(jù)標(biāo)識(shí)匹配結(jié)果從相應(yīng)

18、組的塊中選擇所需的數(shù)據(jù)。因?yàn)镃PU的速度直接與Cache命中的速度緊密相關(guān)，所以對(duì)于組相聯(lián)Cache，由于多路選擇器的存在而使CPU的時(shí)鐘周期增加到原來(lái)的1.10倍。 (4) 這兩種結(jié)構(gòu)Cache的失效開銷都是70 ns。（在實(shí)際應(yīng)用中，應(yīng)取整為整數(shù)個(gè)時(shí)鐘周期） (5) 命中時(shí)間為1個(gè)時(shí)鐘周期，64 KB直接映象Cache的失效率為1.4%，相同容量的2路組相聯(lián)Cache的失效率為1.0%。5.2 Cache的基本知識(shí)5.2 Cache的基本知識(shí) 解 平均訪存時(shí)間為： 平均訪存時(shí)間命中時(shí)間失效率失效開銷 因此，兩種結(jié)構(gòu)的平均訪存時(shí)間分別是： 平均訪存時(shí)間1路2.02（0.01470）4.98

19、ns 平均訪存時(shí)間2路2.021.10（0.01070）5.10 ns 直接相聯(lián)Cache的平均訪存時(shí)間比較低。 CPU 時(shí)間IC(CPIexe每條指令的平均存儲(chǔ)器 停頓周期數(shù))時(shí)鐘周期時(shí)間 IC (CPIexe時(shí)鐘周期時(shí)間 每條指令的平均存儲(chǔ)器停頓時(shí)間)5.2 Cache的基本知識(shí)因此：CPU時(shí)間1路 IC(2.02(1.30.01470) 5.27ICCPU時(shí)間2路 IC(2.021.10(1.30.01070) 5.31IC5.31ICCPU時(shí)間1路 1.015.27ICCPU時(shí)間2路直接映象Cache的平均性能好一些。5.2 Cache的基本知識(shí)平均訪存時(shí)間命中時(shí)間失效率失效開銷可以從

20、三個(gè)方面改進(jìn)Cache的性能：降低失效率減少失效開銷減少Cache命中時(shí)間下面介紹17種Cache優(yōu)化技術(shù)8種用于降低失效率5種用于減少失效開銷4種用于減少命中時(shí)間 5.2.7 改進(jìn)Cache的性能三種失效(3C)強(qiáng)制性失效(Compulsory miss)當(dāng)?shù)谝淮卧L問(wèn)一個(gè)塊時(shí)，該塊不在Cache中，需從下一級(jí)存儲(chǔ)器中調(diào)入Cache。(冷啟動(dòng)失效，首次訪問(wèn)失效)容量失效(Capacity miss ) 如果程序執(zhí)行時(shí)所需的塊不能全部調(diào)入Cache中，則當(dāng)某些塊被替換后，若又重新被訪問(wèn)，就會(huì)發(fā)生失效。沖突失效(Conflict miss)在組相聯(lián)或直接映象Cache中，若太多的塊映象到同一組(塊

21、)中，則會(huì)出現(xiàn)該組中某個(gè)塊被別的塊替換(即使別的組或塊有空閑位置)，然后又被重新訪問(wèn)的情況。(碰撞失效，干擾失效)5.3 降低Cache失效率的方法5.3 降低Cache失效率的方法三種失效所占的比例 絕對(duì)值5.3 降低Cache失效率的方法相對(duì)值5.3 降低Cache失效率的方法可以看出：相聯(lián)度越高，沖突失效就越少；強(qiáng)制性失效和容量失效不受相聯(lián)度的影響；強(qiáng)制性失效不受Cache容量的影響，但容量失效卻隨著容量的增加而減少；表中的數(shù)據(jù)符合2:1的Cache經(jīng)驗(yàn)規(guī)則，即大小為N的直接映象Cache的失效率約等于大小為N/2的2路組相聯(lián)Cache的失效率。5.3 降低Cache失效率的方法減少三種

22、失效的方法強(qiáng)制性失效：增加塊大小，預(yù)?。ū旧砗苌伲┤萘渴В涸黾尤萘?（抖動(dòng)現(xiàn)象）沖突失效：提高相聯(lián)度（理想情況：全相聯(lián)）許多降低失效率的方法會(huì)增加命中時(shí)間或失效開銷5.3 降低Cache失效率的方法失效率與塊大小的關(guān)系對(duì)于給定的Cache容量，當(dāng)塊大小增加時(shí)，失效率開始是下降，后來(lái)反而上升了。 原因：一方面它減少了強(qiáng)制性失效；另一方面，由于增加塊大小會(huì)減少Cache中塊的數(shù)目，所以有可能會(huì)增加沖突失效。 5.3.1 增加Cache塊大小5.3 降低Cache失效率的方法5.3 降低Cache失效率的方法各種塊大小情況下Cache的失效率 塊大?。ㄗ止?jié)） Cache容量（字節(jié)） 1K 4K 1

23、6K 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% Cache容量越大，使失效率達(dá)到最低的塊大小就越大。5.3 降低Cache失效率的方法增加塊大小會(huì)增加失效開銷例5.4 假定存儲(chǔ)系統(tǒng)在延遲40個(gè)時(shí)鐘周期后，每2個(gè)時(shí)鐘周期能送出16個(gè)字節(jié)。即，經(jīng)過(guò)42個(gè)時(shí)鐘周期，它可提供16個(gè)字節(jié)；

24、經(jīng)過(guò)44個(gè)時(shí)鐘周期，可提供32個(gè)字節(jié)；依此類推。請(qǐng)問(wèn)對(duì)于表5.6中列出的各種容量的Cache，在塊大小分別為多少時(shí)，平均訪存時(shí)間最??？解 平均訪存時(shí)間命中時(shí)間失效率失效開銷假設(shè)命中時(shí)間與塊大小無(wú)關(guān)，為1個(gè)時(shí)鐘周期，對(duì)16B塊大小，容量為1KB的Cache： 平均訪存時(shí)間115.05%42=7.321個(gè)時(shí)鐘周期對(duì)256B塊大小，容量為256KB的Cache： 平均訪存時(shí)間10.49%72=1.353個(gè)時(shí)鐘周期5.3 降低Cache失效率的方法各種塊大小情況下Cache的平均訪存時(shí)間 塊大?。ㄗ止?jié)） 失效開銷（時(shí)鐘周期） Cache容量（字節(jié)） 1K 4K 16K 64K 256K 16427.3

25、21 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 1 KB、4 KB、16 KB Cache: 塊大小32 B64 KB Cache: 塊大小128 B256 KB Cache: 塊大小64 B5.3 降低Cache失效率的方法采用相聯(lián)度超過(guò)8的方案的實(shí)際意義不大 8路組相聯(lián)的命中率與全相聯(lián)的命中率差別不大。2:1

26、 Cache經(jīng)驗(yàn)規(guī)則 容量為N的直接映象Cache的失效率和容量為N/2的2路組相聯(lián)Cache的失效率差不多相同。提高相聯(lián)度是以增加命中時(shí)間為代價(jià)。 例如：TTL或ECL板級(jí)Cache，2路組相聯(lián)：增加10定制的CMOS Cache, 2路組相聯(lián)： 增加25.3.2 提高相聯(lián)度5.3 降低Cache失效率的方法例5.5 假定提高相聯(lián)度會(huì)按下列比例增大處理器時(shí)鐘周期： 時(shí)鐘周期2路 1.10時(shí)鐘周期1路 時(shí)鐘周期4路 1.12時(shí)鐘周期1路 時(shí)鐘周期8路 1.14時(shí)鐘周期1路 假定命中時(shí)間為一個(gè)時(shí)鐘周期，直接映象情況下失效開銷為50個(gè)時(shí)鐘周期，而且假設(shè)不必將失效開銷取整。使用表5.5中的失效率，試

27、問(wèn)當(dāng)Cache為多大時(shí)，以下不等式成立？ 平均訪存時(shí)間8路 平均訪存時(shí)間4路 平均訪存時(shí)間4路 平均訪存時(shí)間2路 平均訪存時(shí)間2路 平均訪存時(shí)間1路5.3 降低Cache失效率的方法解 在各種相聯(lián)度的情況下，平均訪存時(shí)間分別為： 平均訪存時(shí)間8路 = 命中時(shí)間8路 + 失效率8路失效開銷8路 = 1.14失效率8路50 平均訪存時(shí)間4路 = 1.12 失效率4路50 平均訪存時(shí)間2路 = 1.10 失效率2路50 平均訪存時(shí)間1路 = 1.00 失效率1路50 把相應(yīng)的失效率代入上式，即可得平均訪存時(shí)間。 例如，1 KB的直接映象Cache的平均訪存時(shí)間為： 平均訪存時(shí)間1路 = 1.000.

28、133507.65 128 KB的8路組相聯(lián)Cache的平均訪存時(shí)間為： 平均訪存時(shí)間8路1.140.006501.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)度情況下Cache的平均訪存時(shí)間5.3 降低Cache失效率的方法 當(dāng)Cache容

29、量不超過(guò)16 KB時(shí)，上述三個(gè)不等式成立。 從32 KB開始，對(duì)于平均訪存時(shí)間有：4路組相聯(lián)的平均訪存時(shí)間小于2路組相聯(lián)的;2路組相聯(lián)的小于直接映象的;但8路組相聯(lián)的卻比4路組相聯(lián)的大。5.3 降低Cache失效率的方法最直接的方法是增加Cache的容量缺點(diǎn):增加成本可能增加命中時(shí)間這種方法在片外Cache中用得比較多 5.3.3 增加Cache的容量5.3 降低Cache失效率的方法一種能減少?zèng)_突失效次數(shù)而又不影響時(shí)鐘頻率的方法?；舅枷朐贑ache和它從下一級(jí)存儲(chǔ)器調(diào)數(shù)據(jù)的通路之間設(shè)置一個(gè)全相聯(lián)的小Cache，用于存放被替換出去的塊(稱為Victim)，以備重用。工作過(guò)程5.3.4 Vic

30、tim Cache 5.3 降低Cache失效率的方法Victim Cache在存儲(chǔ)層次中的位置 5.3 降低Cache失效率的方法作用對(duì)于減小沖突失效很有效，特別是對(duì)于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。例如項(xiàng)數(shù)為4的Victim Cache: 能使4 KB Cache的沖突失效減少20%90%5.3 降低Cache失效率的方法多路組相聯(lián)的低失效率和直接映象的命中速度偽相聯(lián)Cache的優(yōu)點(diǎn)命中時(shí)間小失效率低5.3.5 偽相聯(lián) Cache 優(yōu)點(diǎn)缺點(diǎn)直接映象組相聯(lián)命中時(shí)間小命中時(shí)間大失效率高失效率低基本思想及工作原理 在邏輯上把直接映象Cache的空間上下平分為兩個(gè)區(qū)。對(duì)于任何一次訪問(wèn)

31、，偽相聯(lián)Cache先按直接映象Cache的方式去處理。若命中，則其訪問(wèn)過(guò)程與直接映象Cache的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問(wèn)下一級(jí)存儲(chǔ)器。快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。5.3 降低Cache失效率的方法例5.6 假設(shè)當(dāng)在按直接映象找到的位置處沒(méi)有發(fā)現(xiàn)匹配，而在另一個(gè)位置才找到數(shù)據(jù)（偽命中）需要2個(gè)額外的周期。仍用上個(gè)例子中的數(shù)據(jù)，問(wèn)：當(dāng)Cache容量分別為2 KB和128 KB時(shí)，直接映象、2路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度最快？ 解 首先考慮標(biāo)準(zhǔn)的平均訪存時(shí)間公式： 平均訪存時(shí)間偽相聯(lián) 命中時(shí)間偽相

32、聯(lián)失效率偽相聯(lián)失效開銷偽相聯(lián)由于： 失效率偽相聯(lián)失效率2路 命中時(shí)間偽相聯(lián)命中時(shí)間1路偽命中率偽相聯(lián)2偽相聯(lián)查找的命中率等于2路組相聯(lián)Cache的命中率和直接映象Cache命中率之差。 偽命中率偽相聯(lián) 命中率2路命中率1路 （1失效率2路）（1失效率1路） 失效率1路失效率2路5.3 降低Cache失效率的方法綜合上述分析，有： 平均訪存時(shí)間偽相聯(lián)命中時(shí)間1路（失效率1路失效率2路）2 失效率2路失效開銷1路將前面表中的數(shù)據(jù)代入上面的公式，得： 平均訪存時(shí)間偽相聯(lián)，2 KB1（0.0980.076）2（0.07650）4.844 平均訪存時(shí)間偽相聯(lián)，128 KB1（0.0100.007）2（0

33、.00750）1.356根據(jù)上一個(gè)例子中的表，對(duì)于2 KB Cache，可得： 平均訪存時(shí)間1路 5.90 個(gè)時(shí)鐘 平均訪存時(shí)間2路 4.90 個(gè)時(shí)鐘對(duì)于128KB的Cache有，可得： 平均訪存時(shí)間1路 1.50 個(gè)時(shí)鐘 平均訪存時(shí)間2路 1.45 個(gè)時(shí)鐘可見(jiàn)，對(duì)于這兩種Cache容量，偽相聯(lián)Cache都是速度最快的。5.3 降低Cache失效率的方法指令和數(shù)據(jù)都可以預(yù)取預(yù)取內(nèi)容既可放入Cache，也可放在外緩沖器中。例如：指令流緩沖器指令預(yù)取通常由Cache之外的硬件完成預(yù)取效果Joppi的研究結(jié)果指令預(yù)取 (4 KB，直接映象Cache，塊大小16 B)1個(gè)塊的指令流緩沖器： 捕獲152

34、5的失效4個(gè)塊的指令流緩沖器： 捕獲5016個(gè)塊的指令流緩沖器：捕獲72數(shù)據(jù)預(yù)取 (4 KB,直接映象Cache)1個(gè)數(shù)據(jù)流緩沖器：捕獲25的失效還可以采用多個(gè)數(shù)據(jù)流緩沖器5.3.6 硬件預(yù)取 5.3 降低Cache失效率的方法Palacharla和Kessler的研究結(jié)果流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)對(duì)于兩個(gè)64 KB四路組相聯(lián)Cache來(lái)說(shuō)：8個(gè)流緩沖器能捕獲5070的失效5.3 降低Cache失效率的方法例5.7 Alpha AXP 21064采用指令預(yù)取技術(shù)，其實(shí)際失效率是多少？若不采用指令預(yù)取技術(shù)，Alpha AXP 21064的指令Cache必須為多大才能保持平均訪存時(shí)間不變？

35、解 假設(shè)當(dāng)指令不在指令Cache里，而在預(yù)取緩沖器中找到時(shí)，需要多花一個(gè)時(shí)鐘周期。修改后的公式： 平均訪存時(shí)間預(yù)取 命中時(shí)間失效率預(yù)取命中率1 失效率（1預(yù)取命中率）失效開銷假設(shè)預(yù)取命中率為25%，命中時(shí)間為2個(gè)時(shí)鐘周期，失效開銷為50個(gè)時(shí)鐘周期。查表可知8 KB指令Cache的失效率為1.10%。則： 平均訪存時(shí)間預(yù)取 2（1.10 %25 %1）1.10 %（125 %）50 20.002750.413 2.415為了得到相同性能下的實(shí)際失效率，由原始公式得： 平均訪存時(shí)間 命中時(shí)間失效率失效開銷 失效率 （平均訪存時(shí)間命中時(shí)間）/失效開銷 （2.4152）/500.83 %5.3 降低C

36、ache失效率的方法在編譯時(shí)加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請(qǐng)求。預(yù)取有以下幾種類型：寄存器預(yù)?。喊褦?shù)據(jù)取到寄存器中。Cache預(yù)?。褐粚?shù)據(jù)取到Cache中。故障性預(yù)?。涸陬A(yù)取時(shí)，若出現(xiàn)虛地址故障或違反保護(hù)權(quán)限，就會(huì)發(fā)生異常。非故障性預(yù)?。涸谟龅竭@種情況時(shí)則不會(huì)發(fā)生異常，因?yàn)檫@時(shí)它會(huì)放棄預(yù)取，轉(zhuǎn)變?yōu)榭詹僮?。本?jié)假定Cache預(yù)取都是非故障性的，也稱非綁定預(yù)取。5.3.7 編譯器控制的預(yù)取 5.3 降低Cache失效率的方法在預(yù)取數(shù)據(jù)的同時(shí)，處理器應(yīng)能繼續(xù)執(zhí)行。只有這樣，預(yù)取才有意義。非阻塞Cache (非鎖定Cache) 編譯器控制預(yù)取的目的使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。 循環(huán)是預(yù)取

37、優(yōu)化的主要對(duì)象失效開銷小時(shí)：循環(huán)體展開12次失效開銷大時(shí)：循環(huán)體展開許多次5.3 降低Cache失效率的方法 例5.8 對(duì)于下面的程序，首先判斷哪些訪問(wèn)可能會(huì)導(dǎo)致數(shù)據(jù)Cache失效。然后，加入預(yù)取指令以減少失效。最后，計(jì)算所執(zhí)行的預(yù)取指令的條數(shù)以及通過(guò)預(yù)取避免的失效次數(shù)。假定： (1) 我們用的是一個(gè)容量為8 KB、塊大小為16 B的直接映象Cache，它采用寫回法并且按寫分配。 (2) a、b分別為3100（3行100列）和1013的雙精度浮點(diǎn)數(shù)組，每個(gè)元素都是8 B。當(dāng)程序開始執(zhí)行時(shí)，這些數(shù)據(jù)都不在Cache內(nèi)。 for （ i = 0 ; i 3 ; i = i + 1 ） for （

38、j = 0 ; j 100 ; j = j + 1 ） a i j = b j 0 * b j+1 0 ; 5.3 降低Cache失效率的方法解計(jì)算過(guò)程失效情況 總的失效次數(shù)251次 改進(jìn)后的程序假設(shè)失效開銷很大，預(yù)取必須至少提前7次循環(huán)進(jìn)行。5.3 降低Cache失效率的方法for （ j = 0; j 100; j = j+1 ） prefetch （ b j+7 0 ）; /* 預(yù)取7次循環(huán)后所需的b （ j , 0 ） */ prefetch （ a 0 j+7 ）; /* 預(yù)取7次循環(huán)后所需的a （0 , j ） */ for （ i = 1; i 3; i = i+1 ） for

39、（ j = 0; j 100; j = j+1 ） prefetch （ a i j+7 ）; /* 預(yù)取7次循環(huán)后所需的a （ i , j ） */ a i j = b j 0 * b j+1 0 ; 失效情況 總的失效次數(shù)19次5.3 降低Cache失效率的方法 例5.9 在以下條件下，計(jì)算例5.8中所節(jié)約的時(shí)間： (1) 忽略指令Cache失效，并假設(shè)數(shù)據(jù)Cache無(wú)沖突失效和容量失效。 (2) 假設(shè)預(yù)取可以被重疊或與Cache失效重疊執(zhí)行，從而能以最大的存儲(chǔ)帶寬傳送數(shù)據(jù)。 (3) 不考慮Cache失效時(shí)，修改前的循環(huán)每7個(gè)時(shí)鐘周期循環(huán)一次。修改后的程序中，第一個(gè)預(yù)取循環(huán)每9個(gè)時(shí)鐘周期循

40、環(huán)一次，而第二個(gè)預(yù)取循環(huán)每8個(gè)時(shí)鐘周期循環(huán)一次（包括外層for循環(huán)的開銷）。 (4) 一次失效需50個(gè)時(shí)鐘周期。5.3 降低Cache失效率的方法解修改前：循環(huán)時(shí)間3007 2100失效開銷2515012550/14650 21001255014650修改后：循環(huán)時(shí)間100920082500失效時(shí)間195095025009503450 加速比14650/34504.25.3 降低Cache失效率的方法基本思想 在編譯時(shí)，對(duì)程序中的指令和數(shù)據(jù)進(jìn)行重新組織，以降低Cache失效率。McFaring 發(fā)現(xiàn)： 通過(guò)對(duì)指令進(jìn)行重新排序，可有效地降低指令Cache的失效率。2KB Cache: 降低508

41、KB Cache：降低75%數(shù)據(jù)對(duì)存儲(chǔ)位置的限制比指令的少，因此更便于優(yōu)化。5.3.8 編譯器優(yōu)化 5.3 降低Cache失效率的方法通過(guò)把數(shù)據(jù)重新組織，使得一塊數(shù)據(jù)在被從Cache替換出去之前，能最大限度利用其中的數(shù)據(jù)(訪問(wèn)次數(shù)最多)。數(shù)組合并舉例： /* 修改前 */ int val SIZE ; int key SIZE ;5.3 降低Cache失效率的方法/* 修改后 */struct merge int val ;int key ; ;struct merge merged_array SIZE ;5.3 降低Cache失效率的方法內(nèi)外循環(huán)交換 舉例： /* 修改前 */ for （

42、 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 （ j = 0 ; j 100 ; j = j+1 ） x i j = 2 * x i j ;5.3 降低Cache失效率的方法循環(huán)融合 /* 修改前 */ for （ i = 0 ; i N ; i = i+1 ） for （ j = 0 ; j N ; j = j+1 ） a i j = 1/ b i j * c i j ; for （ i

43、 = 0 ; i N ; i = i+1 ） for （ j = 0 ; j N ; j = j+1 ） d i j = a i j + c i j ; /* 修改后 */ for （ i = 0 ; i N ; i = i+1 ） for （ j = 0 ; j N ; j = j+1 ） a i j = 1/ b i j * c i j ; d i j = a i j + c i j ; 5.3 降低Cache失效率的方法分塊 把對(duì)數(shù)組的整行或整列訪問(wèn)改為按塊進(jìn)行。 /* 修改前 */ for （ i = 0; iN; i = i+1 ） for （ j = 0; j N; j = j+1

44、 ） r = 0; for （ k = 0; k N; k = k+1） r = r + y i k * z k j ; x i j = r; 計(jì)算過(guò)程（失效次數(shù)：2N3N2）5.3 降低Cache失效率的方法5.3 降低Cache失效率的方法/* 修改后 */ for （ jj = 0; jj N; jj = 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,

45、N）; k = k+1） r = r + y i k * z k j ; x i j = x i j + r; 計(jì)算過(guò)程 (失效次數(shù)：2N3 /B N2)5.3 降低Cache失效率的方法提高寫直達(dá)Cache性能的最重要方法是使用寫緩沖區(qū)。Cache中的寫緩沖器導(dǎo)致對(duì)存儲(chǔ)器訪問(wèn)的復(fù)雜化 寫緩沖器進(jìn)行的寫入操作是滯后進(jìn)行的，所以該緩沖器也被稱為后行寫數(shù)緩沖器。例5.10 考慮以下指令序列： SW R3, 512（R0） ；M512R3 （Cache索引為0） LW R1, 1024（R0） ；R1M1024 （Cache索引為0） LW R2, 512（R0） ；R2M512 （Cache索引為

46、0）5.4 減少Cache失效開銷5.4.1 讓讀失效優(yōu)先于寫5.4 減少Cache失效開銷解決問(wèn)題的方法(讀失效的處理)推遲對(duì)讀失效的處理（缺點(diǎn)：讀失效的開銷增加，如50）檢查寫緩沖器中的內(nèi)容在寫回法Cache中，也可采用寫緩沖器。5.4.2 寫緩沖合并提高寫緩沖器的效率寫直達(dá)Cache依靠寫緩沖來(lái)減少對(duì)下一級(jí)存儲(chǔ)器寫操作的時(shí)間。 5.4 減少Cache失效開銷如果寫緩沖器為空，就把數(shù)據(jù)和相應(yīng)地址寫入該緩沖器。從CPU的角度來(lái)看，該寫操作就算完成了。如果寫緩沖器中已經(jīng)有了待寫入的數(shù)據(jù)，就要把這次的寫入地址與寫緩沖器中已有的所有地址進(jìn)行比較，看是否有匹配的項(xiàng)。如果有地址匹配而對(duì)應(yīng)的位置又是空閑

47、的，就把這次要寫入的數(shù)據(jù)與該項(xiàng)合并。這就叫寫緩沖合并。如果寫緩沖器滿且又沒(méi)有能進(jìn)行寫合并的項(xiàng)，就必須等待。 提高了寫緩沖器的空間利用率，而且還能減少因?qū)懢彌_器滿而要進(jìn)行的等待時(shí)間。5.4 減少Cache失效開銷5.4 減少Cache失效開銷請(qǐng)求字 從下一級(jí)存儲(chǔ)器調(diào)入Cache的塊中，只有一個(gè)字是立即需要的。這個(gè)字稱為請(qǐng)求字。 應(yīng)盡早把請(qǐng)求字發(fā)送給CPU盡早重啟動(dòng)：調(diào)塊時(shí)，從塊的起始位置開始讀起。一旦請(qǐng)求字到達(dá)，就立即發(fā)送給CPU，讓CPU繼續(xù)執(zhí)行。請(qǐng)求字優(yōu)先：調(diào)塊時(shí)，從請(qǐng)求字所在的位置讀起。這樣，第一個(gè)讀出的字便是請(qǐng)求字。將之立即發(fā)送給CPU。5.4.3 請(qǐng)求字處理技術(shù)5.4 減少Cache失

48、效開銷這種技術(shù)在以下情況下效果不大：Cache塊較小下一條指令正好訪問(wèn)同一Cache塊的另一部分5.4 減少Cache失效開銷非阻塞Cache：Cache失效時(shí)仍允許CPU進(jìn)行其他的命中訪問(wèn)。即允許“失效下命中”。進(jìn)一步提高性能：“多重失效下命中” “失效下失效”（存儲(chǔ)器必須能夠處理多個(gè)失效）重疊失效個(gè)數(shù)對(duì)平均訪問(wèn)時(shí)間的影響5.4.4 非阻塞Cache技術(shù)5.4 減少Cache失效開銷 例5.11 對(duì)于上圖描述的Cache，在2路組相聯(lián)和“一次失效下命中”這兩種措施中，哪一種對(duì)浮點(diǎn)程序更重要？對(duì)整數(shù)程序的情況如何？ 假設(shè)8KB數(shù)據(jù)Cache的平均失效率為：對(duì)于浮點(diǎn)程序，直接映象Cache為11

49、.4%，而2路組相聯(lián)Cache為10.7%；對(duì)于整數(shù)程序，直接映象Cache為7.4%，2路組相聯(lián)Cache為6.0%。并且假設(shè)平均存儲(chǔ)器等待時(shí)間是失效率和失效開銷的積，失效開銷為16個(gè)時(shí)鐘周期。5.4 減少Cache失效開銷解 對(duì)于浮點(diǎn)程序，平均存儲(chǔ)器等待時(shí)間為： 失效率直接映象 失效開銷 11.4 % 16 1.84 失效率2路組相聯(lián) 失效開銷 10.7 % 16 1.71 1.71/1.840.93 對(duì)于整數(shù)程序： 失效率直接映象 失效開銷 7.4 % 16 1.18 失效率2路組相聯(lián) 失效開銷 6.0 % 16 0.96 0.96/1.180.81“失效下命中”方法有一個(gè)潛在優(yōu)點(diǎn)： 它

50、不會(huì)影響命中時(shí)間，而組相聯(lián)卻會(huì)。 5.4 減少Cache失效開銷應(yīng)把Cache做得更快？還是更大？答案：二者兼顧，再增加一級(jí)Cache第一級(jí)Cache(L1)小而快第二級(jí)Cache(L2)容量大性能分析 平均訪存時(shí)間 命中時(shí)間L1失效率L1失效開銷L1失效開銷L1 命中時(shí)間L2失效率L2失效開銷L2平均訪存時(shí)間 命中時(shí)間L1失效率L1 （命中時(shí)間L2失效率L2失效開銷L2） 5.4.5 采用兩級(jí)Cache5.4 減少Cache失效開銷局部失效率與全局失效率局部失效率該級(jí)Cache的失效次數(shù)/到達(dá)該級(jí) Cache的訪問(wèn)次數(shù)例如：上述式子中的失效率L2全局失效率該級(jí)Cache的失效次數(shù)/CPU發(fā)出

51、的 訪存的總次數(shù)全局失效率L2失效率L1失效率L2 評(píng)價(jià)第二級(jí)Cache時(shí)，應(yīng)使用全局失效率這個(gè)指標(biāo)。它指出了在CPU發(fā)出的訪存中，究竟有多大比例是穿過(guò)各級(jí)Cache，最終到達(dá)存儲(chǔ)器的。5.4 減少Cache失效開銷 例5.12 假設(shè)在1000次訪存中，第一級(jí)Cache失效40次， 第二級(jí)Cache失效20次。試問(wèn)：在這種情況下，該Cache系統(tǒng)的局部失效率和全局失效率各是多少？ 解 第一級(jí)Cache的失效率（全局和局部）是40/1000，即4%； 第二級(jí)Cache的局部失效率是20/40，即50%； 第二級(jí)Cache的全局失效率是20/1000，即2%。 5.4 減少Cache失效開銷對(duì)于第

52、二級(jí)Cache，我們有以下結(jié)論：在第二級(jí)Cache比第一級(jí) Cache大得多的情況下，兩級(jí)Cache的全局失效率和容量與第二級(jí)Cache相同的單級(jí)Cache的失效率非常接近。局部失效率不是衡量第二級(jí)Cache的一個(gè)好指標(biāo)，因此，在評(píng)價(jià)第二級(jí)Cache時(shí)，應(yīng)用全局失效率這個(gè)指標(biāo)。第二級(jí)Cache不會(huì)影響CPU的時(shí)鐘頻率，因此其設(shè)計(jì)有更大的考慮空間。兩個(gè)問(wèn)題：它能否降低CPI中的平均訪存時(shí)間部分？它的成本是多少？5.4 減少Cache失效開銷第二級(jí)Cache的參數(shù)容量第二級(jí)Cache的容量一般比第一級(jí)的大許多。如512 KB，1024 KB相聯(lián)度第二級(jí)Cache可采用較高的相聯(lián)度或偽相聯(lián)方法。5.

53、4 減少Cache失效開銷 例5.13 給出有關(guān)第二級(jí)Cache的以下數(shù)據(jù)： （1） 2路組相聯(lián)使命中時(shí)間增加10%CPU時(shí)鐘周期 （2） 對(duì)于直接映象，命中時(shí)間L2 10個(gè)時(shí)鐘周期 （3） 對(duì)于直接映象，局部失效率L2 25% （4） 對(duì)于2路組相聯(lián)，局部失效率L2 20% （5） 失效開銷L2 50個(gè)時(shí)鐘周期 試問(wèn)第二級(jí)Cache的相聯(lián)度對(duì)失效開銷的影響如何？5.4 減少Cache失效開銷 解 對(duì)一個(gè)直接映象的第二級(jí)Cache來(lái)說(shuō)，第一級(jí)Cache的失效開銷為： 失效開銷直接映象，L1 1025%50 22.5 個(gè)時(shí)鐘周期 對(duì)于2路組相聯(lián)第二級(jí)Cache來(lái)說(shuō)，命中時(shí)間增加了10%（0.1）

54、個(gè)時(shí)鐘周期，故第一級(jí)Cache的失效開銷為： 失效開銷2路組相聯(lián)，L1 10.120%50 20.1 個(gè)時(shí)鐘周期 把第二級(jí)Cache的命中時(shí)間取整，得10或11，則： 失效開銷2路組相聯(lián)，L1 1020%50 20.0 個(gè)時(shí)鐘周期 失效開銷2路組相聯(lián)，L1 1120%50 21.0 個(gè)時(shí)鐘周期 故對(duì)于第二級(jí)Cache來(lái)說(shuō)，2路組相聯(lián)優(yōu)于直接映象。5.4 減少Cache失效開銷塊大小第二級(jí)Cache可采用較大的塊 如 64 B、128 B、256 B 為減少平均訪存時(shí)間，可以讓容量較小的第一級(jí)Cache采用較小的塊，而讓容量較大的第二級(jí)Cache采用較大的塊。需要考慮的另一個(gè)問(wèn)題：多級(jí)包容性：第

55、一級(jí)Cache中的數(shù)據(jù)是否總是同時(shí)存在于第二級(jí)Cache中。 命中時(shí)間直接影響到處理器的時(shí)鐘頻率。在許多現(xiàn)代計(jì)算機(jī)中，往往是Cache的訪問(wèn)時(shí)間限制了處理器的時(shí)鐘頻率。5.5 減少命中時(shí)間5.5.1 容量小、結(jié)構(gòu)簡(jiǎn)單的Cache硬件越簡(jiǎn)單，速度就越快。應(yīng)使Cache足夠小，以便可以與CPU一起放在同一塊芯片上。 某些設(shè)計(jì)采用了一種折中方案： 把Cache的標(biāo)識(shí)放在片內(nèi)，而把Cache的數(shù)據(jù)存儲(chǔ)器放在片外。5.5 減少命中時(shí)間5.5.2 虛擬Cache物理Cache：使用物理地址的傳統(tǒng)Cache。虛擬Cache訪問(wèn)Cache的索引以及Cache中的標(biāo)識(shí)都是虛擬地址(一部分)。5.5 減少命中時(shí)間

56、并非都采用虛擬Cache(為什么?)虛擬Cache的清空問(wèn)題解決方法：在地址標(biāo)識(shí)中增加PID字段 (進(jìn)程標(biāo)識(shí)符)三種情況下失效率的比較單進(jìn)程，PIDs，清空PIDs與單進(jìn)程相比：0.30.6PIDs與清空相比： 0.64.3%同義和別名解決方法：反別名法、頁(yè)著色5.5 減少命中時(shí)間5.5 減少命中時(shí)間虛擬索引物理標(biāo)識(shí)優(yōu)點(diǎn)：兼得虛擬Cache和物理Cache的好處局限性：Cache容量受到限制 (頁(yè)內(nèi)位移) Cache容量頁(yè)大小相聯(lián)度舉例：IBM 3033的Cache頁(yè)大小4 KB 相聯(lián)度16 頁(yè)地址地址標(biāo)識(shí)頁(yè)內(nèi)位移索 引塊內(nèi)位移3112 110 Cache容量164 KB64 KB另一種方法：

57、硬件散列變換5.5 減少命中時(shí)間5.5.3 Cache訪問(wèn)流水化對(duì)第一級(jí)Cache的訪問(wèn)按流水方式組織訪問(wèn)Cache需要多個(gè)時(shí)鐘周期才可以完成例如Pentium訪問(wèn)指令Cache需要一個(gè)時(shí)鐘周期Pentium Pro到Pentium 需要兩個(gè)時(shí)鐘周期Pentium 4 則需要4個(gè)時(shí)鐘周期5.5 減少命中時(shí)間開發(fā)指令級(jí)并行性所遇到的一個(gè)挑戰(zhàn)是：當(dāng)要每個(gè)時(shí)鐘周期流出超過(guò)4條指令時(shí)，要提供足夠多條彼此互不相關(guān)的指令是很困難的。一個(gè)解決方法：采用Trace Cache存放CPU所執(zhí)行的動(dòng)態(tài)指令序列。 包含了由分支預(yù)測(cè)展開的指令，該分支預(yù)測(cè)是否正確需要在取到該指令時(shí)進(jìn)行確認(rèn)。5.5.4 Trace Ca

58、che優(yōu)缺點(diǎn)地址映象機(jī)制復(fù)雜。相同的指令序列有可能被當(dāng)作條件分支的不同選擇而重復(fù)存放。能夠提高指令Cache的空間利用率。5.5 減少命中時(shí)間5.5.5 Cache優(yōu)化技術(shù)總結(jié)“”號(hào)：表示改進(jìn)了相應(yīng)指標(biāo)?！啊碧?hào)：表示它使該指標(biāo)變差?？崭駲冢罕硎舅鼘?duì)該指標(biāo)無(wú)影響。復(fù)雜性：0表示最容易，3表示最復(fù)雜。 優(yōu)化技術(shù) 失效率 失效開銷 命中時(shí)間 硬件復(fù)雜度 說(shuō) 明 增加塊大小 + 0 實(shí)現(xiàn)容易；Pentium 4 的第二級(jí)Cache采用了128 B的塊 增加Cache容量 + 被廣泛采用，特別是第二級(jí)Cache 提高相聯(lián)度 + 1 被廣泛采用 Victim Cache + 2 AMD Athlon采用了

59、8個(gè)項(xiàng)的Victim Cache偽相聯(lián)Cache + 2 MIPS R10000的第二級(jí)Cache采用 硬件預(yù)取指令和數(shù)據(jù) + 23 許多機(jī)器預(yù)取指令，UltraSPARC 預(yù)取數(shù)據(jù) Cache優(yōu)化技術(shù)總結(jié) 優(yōu)化技術(shù) 失效率 失效開銷 命中時(shí)間 硬件復(fù)雜度 說(shuō) 明 編譯器控制的預(yù)取 + 3 需同時(shí)采用非阻塞Cache；有幾種微處理器提供了對(duì)這種預(yù)取的支持 用編譯技術(shù)減少Cache失效次數(shù) + 0 向軟件提出了新要求；有些機(jī)器提供了編譯器選項(xiàng) 使讀失效優(yōu)先于寫 + 1 在單處理機(jī)上實(shí)現(xiàn)容易，被廣泛采用 寫緩沖歸并 +1 與寫直達(dá)合用，廣泛應(yīng)用，例如21164，UltraSPARC 盡早重啟動(dòng)和關(guān)

60、鍵字優(yōu)先 +2 被廣泛采用 非阻塞Cache +3 在支持亂序執(zhí)行的CPU中使用 優(yōu)化技術(shù) 失效率 失效開銷 命中時(shí)間 硬件復(fù)雜度 說(shuō) 明 兩級(jí)Cache +2 硬件代價(jià)大；兩級(jí)Cache的塊大小不同時(shí)實(shí)現(xiàn)困難；被廣泛采用 容量小且結(jié)構(gòu)簡(jiǎn)單的Cache +0實(shí)現(xiàn)容易，被廣泛采用 對(duì)Cache進(jìn)行索引時(shí)不必進(jìn)行地址變換 +2 對(duì)于小容量Cache來(lái)說(shuō)實(shí)現(xiàn)容易，已被Alpha 21164和UltraSPARC 采用 流水化Cache訪問(wèn) +1 被廣泛采用 Trace Cache +3 Pentium 4 采用主存的主要性能指標(biāo)：延遲和帶寬以往：Cache主要關(guān)心延遲，I/O主要關(guān)心帶寬。現(xiàn)在：Ca