第11章 存儲層次 張晨曦 劉依 www.GotoS ,11.1 存儲系統(tǒng)的層次結(jié)構(gòu) 11.2 Cache基本知識 11.3 降低Cache不命中率 11.4 減少Cache不命中開銷 11.5 減少命中時間,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)中關(guān)鍵的問題之一 ： 如何以合理的價(jià)格，設(shè)計(jì)容量和速度都滿足計(jì) 算機(jī)系統(tǒng)要求的存儲器系統(tǒng)？ 人們對這三個指標(biāo)的要求 容量大、速度快、價(jià)格低 三個要求是相互矛盾的 速度越快，每位價(jià)格就越高； 容量越大，每位價(jià)格就越低； 容量越大，速度越慢。,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),11.1.1 存儲系統(tǒng)的層次結(jié)構(gòu),11.1 存儲系統(tǒng)的層次結(jié)構(gòu),解決方法：采用多種存儲器技術(shù)，構(gòu)成多級存儲層次結(jié)構(gòu)。 程序訪問的局部性原理：對于絕大多數(shù)程序來說，程序所訪問的指令和數(shù)據(jù)在地址上不是均勻分布的，而是相對簇聚的。 程序訪問的局部性包含兩個方面 時間局部性：程序馬上將要用到的信息很可能就是現(xiàn)在正在使用的信息。 空間局部性：程序馬上將要用到的信息很可能與現(xiàn)在正在使用的信息在存儲空間上是相鄰的。,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),存儲系統(tǒng)的多級層次結(jié)構(gòu),多級存儲層次,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),假設(shè)第i個存儲器Mi的訪問時間為Ti，容量為Si，平均每位價(jià)格為Ci，則 訪問時間： T1 C2 Cn 整個存儲系統(tǒng)要達(dá)到的目標(biāo)：從CPU來看，該存儲系統(tǒng)的速度接近于M1的，而容量和每位價(jià)格都接近于Mn的。 存儲器越靠近CPU，則CPU對它的訪問頻度越高，而且最好大多數(shù)的訪問都能在M1完成。,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),在存儲層次中，各存儲器之間一般滿足包容關(guān)系，即任何一層存儲器中的內(nèi)容都是其下一層（離CPU更遠(yuǎn)的一層）存儲器中內(nèi)容的子集。 CPU與M1之間傳送信息一般是以字為單位，M1以外（含M1）的相鄰存儲器之間一般以塊或頁面為單位傳送信息。,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),下面僅考慮由M1和M2構(gòu)成的兩級存儲層次： M1的參數(shù)：S1，T1，C1 M2的參數(shù)：S2，T2，C2,11.1.2 存儲系統(tǒng)的性能參數(shù),11.1 存儲系統(tǒng)的層次結(jié)構(gòu),存儲容量S 一般來說，整個存儲系統(tǒng)的容量即是第二級存儲器M2的容量，即S=S2。 每位價(jià)格C 當(dāng)S1S2時，CC2。,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),命中率H 命中率：CPU訪問存儲系統(tǒng)時，在M1中找到所需信息的概率。 N1 訪問M1的次數(shù) N2 訪問M2的次數(shù) 不命中率 ：F1H,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),平均訪問時間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。,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),三級存儲系統(tǒng) Cache（高速緩沖存儲器） 主存儲器 磁盤存儲器（輔存） 可以看成是由“Cache主存”層次和“主存輔存”層次構(gòu)成的系統(tǒng)。,11.1.3 三級存儲系統(tǒng),11.1 存儲系統(tǒng)的層次結(jié)構(gòu),從主存的角度來看 “Cache主存”層次：彌補(bǔ)主存速度的不足 “主存輔存”層次： 彌補(bǔ)主存容量的不足 “Cache主存”層次 主存與CPU的速度差距 “Cache - 主存”層次 “主存輔存”層次 兩者的比較,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),1980年以來存儲器和CPU性能隨時間而提高的情況 （以1980年時的性能作為基準(zhǔn)）,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),兩種存儲層次,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),存儲層次,CPU對第二級的 訪問方式,比較項(xiàng)目,目 的,存儲管理實(shí)現(xiàn),訪問速度的比值 (第一級和第二級),典型的塊(頁)大小,不命中時CPU是否切換,“Cache 主存”層次,“主存輔存”層次,為了彌補(bǔ)主存速度的不足,為了彌補(bǔ)主存容量的不足,主要由專用硬件實(shí)現(xiàn),主要由軟件實(shí)現(xiàn),幾比一,幾萬比一,幾十個字節(jié),幾百到幾千個字節(jié),可直接訪問,均通過第一級,不切換,切換到其他進(jìn)程,“Cache主存”與“主存輔存”層次的區(qū)別,11.1 存儲系統(tǒng)的層次結(jié)構(gòu),當(dāng)把一個塊調(diào)入高一層(靠近CPU)存儲器時， 可以放在哪些位置上? （映象規(guī)則） 當(dāng)所要訪問的塊在高一層存儲器中時，如何 找到該塊? （查找算法） 當(dāng)發(fā)生不命中時，應(yīng)替換哪一塊？ （替換算法） 當(dāng)進(jìn)行寫訪問時，應(yīng)進(jìn)行哪些操作? （寫策略）,11.1.4 存儲層次的四個問題,Cache和主存分塊 Cache是按塊進(jìn)行管理的。Cache和主存均被分割成大小相同的塊。信息以塊為單位調(diào)入Cache。 主存塊地址（塊號）用于查找該塊在Cache中的位置。 塊內(nèi)位移用于確定所訪問的數(shù)據(jù)在該塊中的位置。,11.2 Cache基本知識,11.2.1 基本結(jié)構(gòu)和原理,Cache的基本工作原理示意圖,11.2.2 映象規(guī)則,全相聯(lián)映象 全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個位置。 對比：閱覽室位置 隨便坐 直接映象 直接映象：主存中的每一塊只能被放置到Cache中唯一的一個位置。 （循環(huán)分配）,11.2 Cache基本知識,11.2 Cache基本知識,11.2 Cache基本知識,對比：閱覽室位置 只有一個位置可以坐 對于主存的第i 塊，若它映象到Cache的第j 塊，則: ji mod (M ) （M為Cache的塊數(shù)） 設(shè)M=2m，則當(dāng)表示為二進(jìn)制數(shù)時，j實(shí)際上就是i的低m位:,j,i：,m位,11.2 Cache基本知識,組相聯(lián)映象 組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個組中的任何一個位置。 組相聯(lián)是直接映象和全相聯(lián)的一種折衷,11.2 Cache基本知識,組的選擇常采用位選擇算法 若主存第i 塊映象到第k 組，則: ki mod（G） （G為Cache的組數(shù)） 設(shè)G2g，則當(dāng)表示為二進(jìn)制數(shù)時，k 實(shí)際上就是i 的低 g 位: 低g位以及直接映象中的低m位通常稱為索引。,k,i：,g位,11.2 Cache基本知識,n 路組相聯(lián)：每組中有n個塊(nM/G )。 n 稱為相聯(lián)度。 相聯(lián)度越高，Cache空間的利用率就越高，塊沖突 概率就越低，不命中率也就越低。 絕大多數(shù)計(jì)算機(jī)的Cache: n 4 想一想：相聯(lián)度一定是越大越好？,全相聯(lián),直接映象,組相聯(lián),n (路數(shù)),G (組數(shù)),M,M,1,1,1nM,1GM,11.2 Cache基本知識,當(dāng)CPU訪問Cache時，如何確定Cache中是否有所要訪問的塊？ 若有的話，如何確定其位置？ 通過查找目錄表來實(shí)現(xiàn) 目錄表的結(jié)構(gòu) 主存塊的塊地址的高位部分，稱為標(biāo)識 。 每個主存塊能唯一地由其標(biāo)識來確定,11.2.3 查找算法,11.2 Cache基本知識,Cache中設(shè)有一個目錄表，每一個Cache塊在該表中都有唯一的一項(xiàng)，用于指出當(dāng)前該塊中存放的信息是哪個主存塊的。 目錄表中存放標(biāo)識，所以存放目錄表的存儲器又稱為標(biāo)識存儲器。 目錄表中給每一項(xiàng)設(shè)置一個有效位，用于指出Cache中的塊是否包含有效信息。 只需查找候選位置所對應(yīng)的目錄表項(xiàng) 候選位置：根據(jù)映象規(guī)則不同，一個主存塊可能映象到Cache中的一個或多個Cache塊的位置。 直接映象Cache的候選位置最少，只有一個； 全相聯(lián)Cache的候選位置最多，為M個；,11.2 Cache基本知識,n路組相聯(lián)則介于兩者之間，為n個。 并行查找 為了保證速度，對各候選位置的標(biāo)識的檢查應(yīng)并行進(jìn)行。 并行查找的實(shí)現(xiàn)方法 相聯(lián)存儲器 目錄由2g個相聯(lián)存儲區(qū)構(gòu)成，每個相聯(lián)存儲區(qū)的大小為n（h+log2n）位。 根據(jù)所查找到的組內(nèi)塊地址，從Cache存儲體中讀出的多個信息字中選一個，發(fā)送給CPU。,11.2 Cache基本知識,7.2 Cache基本知識,單體多字存儲器比較器 舉例： 路組相聯(lián)并行標(biāo)識比較 （比較器的個數(shù)及位數(shù)） 路組相聯(lián)Cache的查找過程 優(yōu)缺點(diǎn) 不必采用相聯(lián)存儲器，而是用按地址訪問的存儲器來實(shí)現(xiàn)。 所需要的硬件為：大小為2g nh位的存儲器和n個h位的比較器。 當(dāng)相聯(lián)度n增加時，不僅比較器的個數(shù)會增加，而且比較器的位數(shù)也會增加。,11.2 Cache基本知識,11.2 Cache基本知識,例子：DEC的Alpha AXP21064中的內(nèi)部數(shù)據(jù)Cache 簡介 容量：8KB 塊大?。?2B 塊數(shù)：256 映象方法：直接映象 寫緩沖器大?。?個塊,11.2.4 Cache的工作過程,11.2 Cache基本知識,結(jié)構(gòu)圖,11.2 Cache基本知識,工作過程 “讀”訪問命中 （完成4步需要2個時鐘周期 ） Cache的容量與索引index、相聯(lián)度、塊大小之間的關(guān)系 Cache的容量=2index相聯(lián)度塊大小 把容量為8192、相聯(lián)度為1、塊大小為32（字節(jié)）代入： 索引index：8位 標(biāo)識：29821位 “寫”訪問命中,11.2 Cache基本知識,設(shè)置了一個寫緩沖器 （提高“寫”訪問的速度） 按字尋址的，它含有4個塊，每塊大小為4個字。 當(dāng)要進(jìn)行寫入操作時，如果寫緩沖器不滿，那么就把數(shù)據(jù)和完整的地址寫入緩沖器。對CPU而言，本次“寫”訪問已完成，CPU可以繼續(xù)往下執(zhí)行。由寫緩沖器負(fù)責(zé)把該數(shù)據(jù)寫入主存。 在寫入緩沖器時，要進(jìn)行寫合并檢查。即檢查本次寫入數(shù)據(jù)的地址是否與緩沖器內(nèi)某個有效塊的地址匹配。如果匹配，就把新數(shù)據(jù)與該塊合并 。,11.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é) LRU替換策略 主要區(qū)別 采用2路組相聯(lián) 采用寫回法 沒有寫緩沖器,11.2 Cache基本知識,所要解決的問題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時，替換哪一塊？ 直接映象Cache中的替換很簡單 因?yàn)橹挥幸粋€塊，別無選擇。 在組相聯(lián)和全相聯(lián)Cache中，則有多個塊供選擇。 主要的替換算法有三種 隨機(jī)法 隨機(jī)地選擇被替換的塊 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單,11.2.5 替換算法,11.2 Cache基本知識,先進(jìn)先出法FIFO 選擇最早調(diào)入的塊作為被替換的塊。 優(yōu)點(diǎn)：容易實(shí)現(xiàn)。 最近最少使用法LRU 選擇近期最少被訪問的塊作為被替換的塊。 （實(shí)現(xiàn)比較困難） 實(shí)際上：選擇最久沒有被訪問過的塊作為被替換的塊。 優(yōu)點(diǎn)：命中率較高 LRU和隨機(jī)法分別因其不命中率低和實(shí)現(xiàn)簡單而被廣泛采用。 模擬數(shù)據(jù)表明，對于容量很大的Cache，LRU和隨機(jī)法的命中率差別不大。,11.2 Cache基本知識,“寫”在所有訪存操作中所占的比例 統(tǒng)計(jì)結(jié)果表明，對于一組給定的程序： load指令：26 store指令：9 “寫”在所有訪存操作中所占的比例： 9/(100269)7 “寫”在訪問Cache操作中所占的比例： 9/(269)25,11.2.6 寫策略,11.2 Cache基本知識,“寫”操作必須在確認(rèn)是命中后才可進(jìn)行 “寫”訪問有可能導(dǎo)致Cache和主存內(nèi)容的不一致 兩種寫策略 寫策略是區(qū)分不同Cache設(shè)計(jì)方案的一個重要標(biāo)志。 寫直達(dá)法（也稱為存直達(dá)法） 執(zhí)行“寫”操作時，不僅寫入Cache，而且也寫入下一級存儲器。 寫回法（也稱為拷回法） 執(zhí)行“寫”操作時，只寫入Cache。僅當(dāng)Cache中相應(yīng)的塊被替換時，才寫回主存。 (設(shè)置“修改位”),11.2 Cache基本知識,兩種寫策略的比較 寫回法的優(yōu)點(diǎn)：速度快，所使用的存儲器 帶寬較低。 寫直達(dá)法的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，一致性好。 采用寫直達(dá)法時，若在進(jìn)行“寫”操作的過程中CPU必須等待，直到“寫”操作結(jié)束，則稱CPU寫停頓。 減少寫停頓的一種常用的優(yōu)化技術(shù)： 采用寫緩沖器,11.2 Cache基本知識,“寫”操作時的調(diào)塊 按寫分配(寫時取) 寫不命中時，先把所寫單元所在的塊調(diào)入Cache， 再行寫入。 不按寫分配(繞寫法) 寫不命中時，直接寫入下一級存儲器而不調(diào)塊。 寫策略與調(diào)塊 寫回法 按寫分配 寫直達(dá)法 不按寫分配,11.2 Cache基本知識,不命中率 與硬件速度無關(guān) 容易產(chǎn)生一些誤導(dǎo) 平均訪存時間 平均訪存時間 命中時間不命中率不命中開銷,11.2.7 Cache的性能分析,程序執(zhí)行時間 CPU時間（CPU執(zhí)行周期數(shù)+存儲器停頓周期數(shù)） 時鐘周期時間 其中： 存儲器停頓時鐘周期數(shù)“讀”的次數(shù)讀不命中率讀不命中開銷“寫”的次數(shù)寫不命中率寫不命中開銷 存儲器停頓時鐘周期數(shù)訪存次數(shù)不命中率不命中開銷,CPU時間（CPU執(zhí)行周期數(shù)+訪存次數(shù)不命中率不命中開銷） 時鐘周期時間,=IC（CPIexecution每條指令的平均訪存次數(shù)不命中率 不命中開銷） 時鐘周期時間,11.2 Cache基本知識,例11.1 用一個和Alpha AXP類似的機(jī)器作為第一個例子。假設(shè)Cache不命中開銷為50個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期，訪問Cache不命中率為2%，平均每條指令訪存1.33次。試分析Cache對性能的影響。 解 CPU時間有cacheIC （CPIexecution每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時鐘周期時間 IC （2.01.332 %50） 時鐘周期時間 IC 3.33 時鐘周期時間,11.2 Cache基本知識,考慮Cache的不命中后，性能為： CPU時間有cacheIC（2.01.332 %50）時鐘周期時間 IC3.33時鐘周期時間 實(shí)際CPI ：3.33 3.33/2.0 = 1.67(倍) CPU時間也增加為原來的1.67倍。 但若不采用Cache,則： CPI2.0501.3368.5,例11.2 考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象Cache和兩路組相聯(lián)Cache，試問它們對CPU的性能有何影響？先求平均訪存時間，然后再計(jì)算CPU性能。分析時請用以下假設(shè)： (1)理想Cache（命中率為100%）情況下的CPI為2.0，時鐘周期為2ns，平均每條指令訪存1.3次。 (2)兩種Cache容量均為64KB，塊大小都是32字節(jié)。 (3)在組相聯(lián)Cache中，由于多路選擇器的存在而使CPU的時鐘周期增加到原來的1.10倍。這是因?yàn)閷ache的訪問總是處于關(guān)鍵路徑上，對CPU的時鐘周期有直接的影響。,(4) 這兩種結(jié)構(gòu)Cache的不命中開銷都是70ns。（在實(shí)際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期） (5) 命中時間為1個時鐘周期，64KB直接映象Cache的不命中率為1.4%，相同容量的兩路組相聯(lián)Cache的不命中率為1.0%。,11.2 Cache基本知識,解 平均訪存時間為： 平均訪存時間命中時間不命中率不命中開銷 因此，兩種結(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ù)不命中率不命中開銷時鐘周期時間）,11.2 Cache基本知識,因此： CPU時間1路 IC(2.02(1.30.01470) 5.27IC CPU時間2路 IC(2.021.10(1.30.01070) 5.31IC,5.31IC,CPU時間1路, 1.01,5.27IC,CPU時間2路,直接映象Cache的平均性能好一些。,11.2 Cache基本知識,平均訪存時間命中時間不命中率不命中開銷 可以從三個方面改進(jìn)Cache的性能： 降低不命中率 減少不命中開銷 減少Cache命中時間 下面介紹17種Cache優(yōu)化技術(shù) 8種用于降低不命中率 5種用于減少不命中開銷 4種用于減少命中時間,11.2.8 改進(jìn)Cache的性能,許多降低不命中率的方法會增加命中時間或不命中開銷。 增加Cache塊大小 不命中率與塊大小的關(guān)系 對于給定的Cache容量，當(dāng)塊大小增加時，不命中率開始是下降，后來反而上升了。 Cache容量越大，使不命中率達(dá)到最低的塊大小就越大。 增加塊大小會增加不命中開銷,11.3 降低Cache不命中率,11.3 降低Cache不命中率,不命中率隨塊大小變化的曲線,11.3 降低Cache不命中率,增加Cache的容量 缺點(diǎn): 增加成本 可能增加命中時間 這種方法在片外Cache中用得比較多 提高相聯(lián)度 采用相聯(lián)度超過8的方案的實(shí)際意義不大。 2:1 Cache經(jīng)驗(yàn)規(guī)則 容量為N的直接映象Cache的不命中率和容量為N/2的兩路組相聯(lián)Cache的不命中率差不多相同。,11.3 降低Cache不命中率,提高相聯(lián)度是以增加命中時間為代價(jià)。 偽相聯(lián) Cache (列相聯(lián) Cache ) 多路組相聯(lián)的低不命中率和直接映象的命中速度 基本思想 在邏輯上把直接映象Cache的空間上下平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián)Cache先按直接映象Cache的方式去處理。 若命中，則其訪問過程與直接映象Cache的情況一樣。 若不命中，則再到另一區(qū)相應(yīng)的位置去查找。 確定這個“另一塊”的一種簡單的方法：將索引字段的最高位取反。,11.3 降低Cache不命中率,缺點(diǎn)：多種命中時間會使CPU流水線的設(shè)計(jì)復(fù)雜化。 偽相聯(lián)技術(shù)往往是應(yīng)用在離處理器比較遠(yuǎn)的Cache上。 硬件預(yù)取 指令和數(shù)據(jù)都可以預(yù)取 預(yù)取內(nèi)容既可放入Cache，也可放在外緩沖器中。 指令預(yù)取通常由Cache之外的硬件完成 預(yù)取應(yīng)利用存儲器的空閑帶寬，不能影響對正常不命中的處理，否則可能會降低性能。,11.3 降低Cache不命中率,在編譯時加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā) 出預(yù)取請求。 按照預(yù)取數(shù)據(jù)所放的位置，可把預(yù)取分為兩種類型： 寄存器預(yù)?。喊褦?shù)據(jù)取到寄存器中。 Cache預(yù)?。褐粚?shù)據(jù)取到Cache中。 按照預(yù)取的處理方式不同，可把預(yù)取分為： 故障性預(yù)?。涸陬A(yù)取時，若出現(xiàn)虛地址故障或違反保護(hù)權(quán)限，就會發(fā)生異常。,11.3.1 編譯器控制的預(yù)取,11.3 降低Cache不命中率,非故障性預(yù)?。涸谟龅竭@種情況時則不會發(fā)生異常，因?yàn)檫@時它會放棄預(yù)取，轉(zhuǎn)變?yōu)榭詹僮鳌?本節(jié)假定Cache預(yù)取都是非故障性的，也叫做非綁定預(yù)取。 在預(yù)取數(shù)據(jù)的同時，處理器應(yīng)能繼續(xù)執(zhí)行。 只有這樣，預(yù)取才有意義。 非阻塞Cache (非鎖定Cache) 編譯器控制預(yù)取的目的 使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。 循環(huán)是預(yù)取優(yōu)化的主要對象,11.3 降低Cache不命中率,不命中開銷小時：循環(huán)體展開12次 不命中開銷大時：循環(huán)體展開許多次 每次預(yù)取需要花費(fèi)一條指令的開銷 保證這種開銷不超過預(yù)取所帶來的收益 編譯器可以通過把重點(diǎn)放在那些可能會導(dǎo)致不命中的訪問上，使程序避免不必要的預(yù)取，從而較大程度地減少平均訪存時間。,11.3 降低Cache不命中率,基本思想：通過對軟件進(jìn)行優(yōu)化來降低不命中率。 （特色：無需對硬件做任何改動） 程序代碼和數(shù)據(jù)重組 可以重新組織程序而不影響程序的正確性 例如：把一個程序中的過程重新排序，就可能降低指令 不命中率。 如果編譯器知道一個分支指令很可能會成功轉(zhuǎn)移，那么它就可以通過以下兩步來改善空間局部性：,11.3.2 編譯器優(yōu)化,11.3 降低Cache不命中率,將轉(zhuǎn)移目標(biāo)處的基本塊和緊跟著該分支指令后的基本塊進(jìn)行對調(diào)； 把該分支指令換為操作語義相反的分支指令。 數(shù)據(jù)對存儲位置的限制更少，更便于調(diào)整順序。 編譯優(yōu)化技術(shù)包括 數(shù)組合并 將本來相互獨(dú)立的多個數(shù)組合并成為一個復(fù)合數(shù)組，以提高訪問它們的局部性。 循環(huán)融合,11.3 降低Cache不命中率,將若干個獨(dú)立的循環(huán)融合為單個的循環(huán)。這些循環(huán)訪問同樣的數(shù)組，對相同的數(shù)據(jù)作不同的運(yùn)算。這樣能使得讀入Cache的數(shù)據(jù)在被替換出去之前，能得到反復(fù)的使用 。 內(nèi)外循環(huán)交換 分塊 通過提高時間局部性來減少不命中。 分塊算法不是對數(shù)組的整行或整列進(jìn)行訪問，而是對子矩陣或塊進(jìn)行操作。其目的仍然是使一個Cache塊在被替換之前最大限度地利用它。,11.3 降低Cache不命中率,一種能減少沖突不命中次數(shù)而又不影響時鐘頻率的方法。 基本思想 在Cache和它從下一級存儲器調(diào)數(shù)據(jù)的通路之間設(shè)置一個全相聯(lián)的小Cache，稱為“犧牲”Cache（Victim Cache）。用于存放被替換出去的塊(稱為犧牲者)，以備重用。 工作過程,11.3.3 “犧牲” Cache,應(yīng)把Cache做得更快？還是更大？ 答案：二者兼顧，再增加一級Cache 第一級Cache(L1)小而快 第二級Cache(L2)容量大 性能分析 平均訪存時間 命中時間L1不命中率L1不命中開銷L1 不命中開銷L1 命中時間L2不命中率L2不命中開銷L2,11.4.1 采用兩級Cache,11.4 減少Cache不命中開銷,11.4 減少Cache不命中開銷,平均訪存時間 命中時間L1不命中率L1 （命中時間L2不命中率L2不命中開銷L2）,局部不命中率與全局不命中率 局部不命中率該級Cache的不命中次數(shù)/到達(dá)該 級Cache的訪問次數(shù) 例如：上述式子中的不命中率L2 全局不命中率該級Cache的不命中次數(shù)/CPU發(fā) 出的訪存的總次數(shù),11.4 減少Cache不命中開銷,全局不命中率L2不命中率L1不命中率L2 評價(jià)第二級Cache時，應(yīng)使用全局不命中率這個指標(biāo)。它指出了在CPU發(fā)出的訪存中，究竟有多大比例是穿過各級Cache，最終到達(dá)存儲器的。 采用兩級Cache時，每條指令的平均訪存停頓時間： 每條指令的平均訪存停頓時間 每條指令的平均不命中次數(shù)L1命中時間L2 每條指令的平均不命中次數(shù)L2不命中開銷L2,11.4 減少Cache不命中開銷,對于第二級Cache，我們有以下結(jié)論： 在第二級Cache比第一級 Cache大得多的情況下，兩級Cache的全局不命中率和容量與第二級Cache相同的單級Cache的不命中率非常接近。 局部不命中率不是衡量第二級Cache的一個好指標(biāo)，因此，在評價(jià)第二級Cache時，應(yīng)用全局不命中率這個指標(biāo)。 第二級Cache不會影響CPU的時鐘頻率，因此其設(shè)計(jì)有更大的考慮空間。 兩個問題：,11.4 減少Cache不命中開銷,它能否降低CPI中的平均訪存時間部分？ 它的成本是多少？ 第二級Cache的參數(shù) 容量 第二級Cache的容量一般比第一級的大許多。 相聯(lián)度 第二級Cache可采用較高的相聯(lián)度或偽相聯(lián)方法。 塊大小,Cache中的寫緩沖器導(dǎo)致對存儲器訪問的復(fù)雜化 在讀不命中時，所讀單元的最新值有可能還在寫緩沖器中，尚未寫入主存。,11.4.2 讓讀不命中優(yōu)先于寫,11.4 減少Cache不命中開銷,解決問題的方法(讀不命中的處理) 推遲對讀不命中的處理 （缺點(diǎn)：讀不命中的開銷增加） 檢查寫緩沖器中的內(nèi)容 在寫回法Cache中，也可采用寫緩沖器。,11.4 減少Cache不命中開銷,11.4.3 寫緩沖合并,提高寫緩沖器的效率 寫直達(dá)Cache 依靠寫緩沖來減少對下一級存儲器寫操作的時間。 如果寫緩沖器為空，就把數(shù)據(jù)和相應(yīng)地址寫入該緩沖器。 從CPU的角度來看，該寫操作就算是完成了。 如果寫緩沖器中已經(jīng)有了待寫入的數(shù)據(jù)，就要把這次的寫入地址與寫緩沖器中已有的所有地址進(jìn)行比較，看是否有匹配的項(xiàng)。如果有地址匹配而,11.4 減少Cache不命中開銷,對應(yīng)的位置又是空閑的，就把這次要寫入的數(shù)據(jù)與該項(xiàng)合并。這就叫寫緩沖合并。 如果寫緩沖器滿且又沒有能進(jìn)行寫合并的項(xiàng)，就必須等待。 提高了寫緩沖器的空間利用率，而且還能減少因?qū)懢彌_ 器滿而要進(jìn)行的等待時間。,11.4 減少Cache不命中開銷,請求字 從下一級存儲器調(diào)入Cache的塊中，只有一個字 是立即需要的。這個字稱為請求字。 應(yīng)盡早把請求字發(fā)送給CPU 盡早重啟動：調(diào)塊時，從塊的起始位置開始讀起。一旦請求字到達(dá)，就立即發(fā)送給CPU，讓CPU繼續(xù)執(zhí)行。 請求字優(yōu)先：調(diào)塊時，從請求字所在的位置讀起。這樣，第一個讀出的字便是請求字。將之立即發(fā)送給CPU。,11.4.4 請求字處理技術(shù),11.4 減少Cache不命中開銷,這種技術(shù)在以下情況下效果不大： Cache塊較小 下一條指令正好訪問同一Cache塊的另一部分,11.4 減少Cache不命中開銷,非阻塞Cache：Cache不命中時仍允許CPU進(jìn)行其它的命中訪問。即允許“不命中下命中”。 增加了Cache控制器的復(fù)雜度。,11.4.5 非阻塞Cache技術(shù),命中時間直接影響到處理器的時鐘頻率。在當(dāng)今的許 多計(jì)算機(jī)中，往往是Cache的訪問時間限制了處理器的時 鐘頻率。,1