第5章存儲(chǔ)系統(tǒng)

第5章存儲(chǔ)系統(tǒng)張晨曦劉依www.A微信公眾號(hào)：arch3655.1 存儲(chǔ)系統(tǒng)的基本知識(shí)5.2 Cache基本知識(shí)5.3 降低Cache不命中率5.4 減少Cache不命中開銷5.5 減少命中時(shí)間5.6 并行主存系統(tǒng)5.7 虛擬存儲(chǔ)器5.8 實(shí)例：AMDOpteron的存儲(chǔ)器層次結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)中關(guān)鍵的問題之一

：如何以合理的價(jià)格，設(shè)計(jì)容量和速度都滿足計(jì)算機(jī)系統(tǒng)要求的存儲(chǔ)器系統(tǒng)？人們對(duì)這三個(gè)指標(biāo)的要求

容量大、速度快、價(jià)格低三個(gè)要求是相互矛盾的速度越快，每位價(jià)格就越高；容量越大，每位價(jià)格就越低；容量越大，速度越慢。5.1存儲(chǔ)系統(tǒng)的基本知識(shí)5.1.1存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)

5.1存儲(chǔ)系統(tǒng)的基本知識(shí)解決方法：采用多種存儲(chǔ)器技術(shù)，構(gòu)成多級(jí)存儲(chǔ)層次結(jié)構(gòu)。程序訪問的局部性原理：對(duì)于絕大多數(shù)程序來(lái)說(shuō)，程序所訪問的指令和數(shù)據(jù)在地址上不是均勻分布的，而是相對(duì)簇聚的。(局部性原理)程序訪問的局部性包含兩個(gè)方面時(shí)間局部性：程序馬上將要用到的信息很可能就是現(xiàn)在正在使用的信息?？臻g局部性：程序馬上將要用到的信息很可能與現(xiàn)在正在使用的信息在存儲(chǔ)空間上是相鄰的。5.1存儲(chǔ)系統(tǒng)的基本知識(shí)存儲(chǔ)系統(tǒng)的多級(jí)層次結(jié)構(gòu)

演示多級(jí)存儲(chǔ)層次5.1存儲(chǔ)系統(tǒng)的基本知識(shí)假設(shè)第i個(gè)存儲(chǔ)器Mi的訪問時(shí)間為Ti，容量為Si，平均每位價(jià)格為Ci，則訪問時(shí)間：T1<T2<…<Tn容量：S1<S2<…<Sn平均每位價(jià)格：C1>C2>…>Cn

整個(gè)存儲(chǔ)系統(tǒng)要達(dá)到的目標(biāo)：從CPU來(lái)看，該存儲(chǔ)系統(tǒng)的速度接近于M1的，而容量和每位價(jià)格都接近于Mn的。存儲(chǔ)器越靠近CPU，則CPU對(duì)它的訪問頻度越高，而且最好大多數(shù)的訪問都能在M1完成。5.1存儲(chǔ)系統(tǒng)的基本知識(shí)下面僅考慮由M1和M2構(gòu)成的兩級(jí)存儲(chǔ)層次：M1的參數(shù)：S1，T1，C1M2的參數(shù)：S2，T2，C25.1.2存儲(chǔ)層次的性能參數(shù)5.1存儲(chǔ)系統(tǒng)的基本知識(shí)存儲(chǔ)容量S一般來(lái)說(shuō)，整個(gè)存儲(chǔ)系統(tǒng)的容量即是第二級(jí)存儲(chǔ)器M2的容量，即S=S2。每位價(jià)格C當(dāng)S1<<S2時(shí)，C≈C2。

5.1存儲(chǔ)系統(tǒng)的基本知識(shí)命中率H和不命中率F命中率：CPU訪問存儲(chǔ)系統(tǒng)時(shí)，在M1中找到所需信息的概率。N1

──訪問M1的次數(shù)N2──訪問M2的次數(shù)

不命中率：F＝1－H5.1存儲(chǔ)系統(tǒng)的基本知識(shí)平均訪問時(shí)間TA

TA ＝HT1＋（1－H）（T1＋TM） ＝T1＋（1－H）TM

或TA ＝T1＋FTM分兩種情況來(lái)考慮CPU的一次訪存：當(dāng)命中時(shí)，訪問時(shí)間即為T1（命中時(shí)間）當(dāng)不命中時(shí)，情況比較復(fù)雜。不命中時(shí)的訪問時(shí)間為：T2＋TB＋T1＝T1＋TM

TM＝T2＋TB不命中開銷TM：從向M2發(fā)出訪問請(qǐng)求到把整個(gè)數(shù)據(jù)塊調(diào)入M1中所需的時(shí)間。傳送一個(gè)信息塊所需的時(shí)間為TB。5.1存儲(chǔ)系統(tǒng)的基本知識(shí)

三級(jí)存儲(chǔ)系統(tǒng)Cache（高速緩沖存儲(chǔ)器）主存儲(chǔ)器磁盤存儲(chǔ)器（輔存）可以看成是由“Cache—主存”層次和“主存—輔存”層次構(gòu)成的系統(tǒng)。5.1.3三級(jí)存儲(chǔ)系統(tǒng)5.1存儲(chǔ)系統(tǒng)的基本知識(shí)

從主存的角度來(lái)看“Cache－主存”層次：彌補(bǔ)主存速度的不足“主存－輔存”層次：彌補(bǔ)主存容量的不足“Cache—主存”層次主存與CPU的速度差距“Cache-主存”層次

“主存－輔存”層次5.1存儲(chǔ)系統(tǒng)的基本知識(shí)1980年以來(lái)存儲(chǔ)器和CPU性能隨時(shí)間而提高的情況（以1980年時(shí)的性能作為基準(zhǔn)）5.1存儲(chǔ)系統(tǒng)的基本知識(shí)兩種存儲(chǔ)層次5.1存儲(chǔ)系統(tǒng)的基本知識(shí)存儲(chǔ)層次CPU對(duì)第二級(jí)的

訪問方式比較項(xiàng)目目的存儲(chǔ)管理實(shí)現(xiàn)

訪問速度的比值

(第一級(jí)和第二級(jí))典型的塊(頁(yè))大小不命中時(shí)CPU是否切換“Cache－主存”層次“主存－輔存”層次為了彌補(bǔ)主存速度的不足為了彌補(bǔ)主存容量的不足主要由專用硬件實(shí)現(xiàn)主要由軟件實(shí)現(xiàn)幾比一幾萬(wàn)比一幾十個(gè)字節(jié)幾百到幾千個(gè)字節(jié)可直接訪問均通過(guò)第一級(jí)不切換切換到其他進(jìn)程“Cache－主存”與“主存－輔存”層次的區(qū)別5.1存儲(chǔ)系統(tǒng)的基本知識(shí)當(dāng)把一個(gè)塊調(diào)入高一層(靠近CPU)存儲(chǔ)器時(shí)，

可以放在哪些位置上?

（映像規(guī)則）當(dāng)所要訪問的塊在高一層存儲(chǔ)器中時(shí)，如何

找到該塊?（查找算法）當(dāng)發(fā)生不命中時(shí)，應(yīng)替換哪一塊？（替換算法）當(dāng)進(jìn)行寫訪問時(shí)，應(yīng)進(jìn)行哪些操作?

（寫策略）5.1.4存儲(chǔ)層次的四個(gè)問題存儲(chǔ)空間分割與地址計(jì)算Cache和主存分塊Cache是按塊進(jìn)行管理的。Cache和主存均被分割成大小相同的塊。信息以塊為單位調(diào)入Cache。主存塊地址（塊號(hào)）用于查找該塊在Cache中的位置。塊內(nèi)位移用于確定所訪問的數(shù)據(jù)在該塊中的位置。5.2Cache基本知識(shí)

5.2.1

基本結(jié)構(gòu)和原理

Cache的基本工作原理示意圖

5.2.2

映像規(guī)則

全相聯(lián)映像全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個(gè)位置。舉例對(duì)比：閱覽室位置──隨便坐特點(diǎn)：空間利用率最高，沖突概率最低，實(shí)現(xiàn)最復(fù)雜。5.2Cache基本知識(shí)5.2Cache基本知識(shí)5.2Cache基本知識(shí)直接映像直接映像：主存中的每一塊只能被放置到Cache中唯一的一個(gè)位置。舉例（循環(huán)分配）對(duì)比：閱覽室位置──只有一個(gè)位置可以坐特點(diǎn)：空間利用率最低，沖突概率最高，實(shí)現(xiàn)最簡(jiǎn)單。對(duì)于主存的第i

塊，若它映像到Cache的第j

塊，則:

j＝imod(M

)

（M為Cache的塊數(shù)）設(shè)M=2m，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，j實(shí)際上就是i的低m位:

ji：m位5.2Cache基本知識(shí)5.2Cache基本知識(shí)組相聯(lián)映像組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個(gè)組中的任何一個(gè)位置。舉例組相聯(lián)是直接映像和全相聯(lián)的一種折中5.2Cache基本知識(shí)組的選擇常采用位選擇算法若主存第i

塊映像到第k

組，則:

k＝imod（G）（G為Cache的組數(shù)）設(shè)G＝2g，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，k實(shí)際上就是i的低g位:低g位以及直接映像中的低m位通常稱為索引。

ki：g位5.2Cache基本知識(shí)n路組相聯(lián)：每組中有n個(gè)塊(n＝M/G)。

n稱為相聯(lián)度。相聯(lián)度越高，Cache空間的利用率就越高，塊沖突概率就越低，不命中率也就越低。絕大多數(shù)計(jì)算機(jī)的Cache:n≤4想一想：相聯(lián)度一定是越大越好？全相聯(lián)直接映像

組相聯(lián)n(路數(shù))G(組數(shù))MM111＜n＜M1＜G＜M5.2Cache基本知識(shí)當(dāng)CPU訪問Cache時(shí)，如何確定Cache中是否有所要訪問的塊？若有的話，如何確定其位置？通過(guò)查找目錄表來(lái)實(shí)現(xiàn)目錄表的結(jié)構(gòu)主存塊的塊地址的高位部分，稱為標(biāo)識(shí)。每個(gè)主存塊能唯一地由其標(biāo)識(shí)來(lái)確定5.2.3查找算法5.2Cache基本知識(shí)只需查找候選位置所對(duì)應(yīng)的目錄表項(xiàng)并行查找與順序查找提高性能的重要思想：主候選位置(MRU塊)

（前瞻執(zhí)行）并行查找的實(shí)現(xiàn)方法相聯(lián)存儲(chǔ)器目錄由2g個(gè)相聯(lián)存儲(chǔ)區(qū)構(gòu)成，每個(gè)相聯(lián)存儲(chǔ)區(qū)的大小為n×（h+log2n）位。根據(jù)所查找到的組內(nèi)塊地址，從Cache存儲(chǔ)體中讀出的多個(gè)信息字中選一個(gè)，發(fā)送給CPU。

5.2Cache基本知識(shí)5.2Cache基本知識(shí)單體多字存儲(chǔ)器＋比較器舉例：４路組相聯(lián)并行標(biāo)識(shí)比較（比較器的個(gè)數(shù)及位數(shù)）４路組相聯(lián)Cache的查找過(guò)程直接映像Cache的查找過(guò)程優(yōu)缺點(diǎn)不必采用相聯(lián)存儲(chǔ)器，而是用按地址訪問的存儲(chǔ)器來(lái)實(shí)現(xiàn)。所需要的硬件為：大小為2g×n×h位的存儲(chǔ)器和n個(gè)h位的比較器。當(dāng)相聯(lián)度n增加時(shí)，不僅比較器的個(gè)數(shù)會(huì)增加，而且比較器的位數(shù)也會(huì)增加。5.2Cache基本知識(shí)5.2Cache基本知識(shí)例子：DEC的AlphaAXP21064中的內(nèi)部數(shù)據(jù)Cache簡(jiǎn)介容量：8KB塊大?。?2B塊數(shù)：256映像方法：直接映像寫緩沖器大?。?個(gè)塊5.2.4Cache的工作過(guò)程結(jié)構(gòu)圖5.2Cache基本知識(shí)工作過(guò)程“讀”訪問命中（完成4步需要2個(gè)時(shí)鐘周期）Cache的容量與索引index、相聯(lián)度、塊大小之間的關(guān)系

Cache的容量=2index×相聯(lián)度×塊大小

把容量為8192、相聯(lián)度為1、塊大小為32（字節(jié)）代入：索引index：8位標(biāo)識(shí)：29－8＝21位“寫”訪問命中5.2Cache基本知識(shí)設(shè)置了一個(gè)寫緩沖器（提高“寫”訪問的速度）按字尋址的，它含有4個(gè)塊，每塊大小為4個(gè)字。當(dāng)要進(jìn)行寫入操作時(shí)，如果寫緩沖器不滿，那么就把數(shù)據(jù)和完整的地址寫入緩沖器。對(duì)CPU而言，本次“寫”訪問已完成，CPU可以繼續(xù)往下執(zhí)行。由寫緩沖器負(fù)責(zé)把該數(shù)據(jù)寫入主存。在寫入緩沖器時(shí)，要進(jìn)行寫合并檢查。即檢查本次寫入數(shù)據(jù)的地址是否與緩沖器內(nèi)某個(gè)有效塊的地址匹配。如果匹配，就把新數(shù)據(jù)與該塊合并。5.2Cache基本知識(shí)發(fā)生讀不命中與寫不命中時(shí)的操作讀不命中：向CPU發(fā)出一個(gè)暫停信號(hào)，通知它等待，并從下一級(jí)存儲(chǔ)器中新調(diào)入一個(gè)數(shù)據(jù)塊（32字節(jié)）。寫不命中：將使數(shù)據(jù)“繞過(guò)”Cache，直接寫入主存。對(duì)比：AlphaAXP21264的數(shù)據(jù)Cache結(jié)構(gòu)容量：64KB

塊大?。?4字節(jié)

LRU替換策略主要區(qū)別采用2路組相聯(lián)采用寫回法沒有寫緩沖器5.2Cache基本知識(shí)替換算法所要解決的問題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時(shí)，替換哪一塊？直接映像Cache中的替換很簡(jiǎn)單因?yàn)橹挥幸粋€(gè)塊，別無(wú)選擇。在組相聯(lián)和全相聯(lián)Cache中，則有多個(gè)塊供選擇。主要的替換算法有三種隨機(jī)法優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單先進(jìn)先出法FIFO5.2.5替換算法5.2Cache基本知識(shí)最近最少使用法LRU選擇近期最少被訪問的塊作為被替換的塊。

（實(shí)現(xiàn)比較困難）實(shí)際上：選擇最久沒有被訪問過(guò)的塊作為被替換的塊。

優(yōu)點(diǎn)：命中率較高LRU和隨機(jī)法分別因其不命中率低和實(shí)現(xiàn)簡(jiǎn)單而被廣泛采用。模擬數(shù)據(jù)表明，對(duì)于容量很大的Cache，LRU和隨機(jī)法的命中率差別不大。5.2Cache基本知識(shí)LRU算法的硬件實(shí)現(xiàn)堆棧法用一個(gè)堆棧來(lái)記錄組相聯(lián)Cache的同一組中各塊被訪問的先后次序。用堆棧元素的物理位置來(lái)反映先后次序棧底記錄的是該組中最早被訪問過(guò)的塊，次棧底記錄的是該組中第二個(gè)被訪問過(guò)的塊，…，棧頂記錄的是剛訪問過(guò)的塊。當(dāng)需要替換時(shí)，從棧底得到應(yīng)該被替換的塊（塊地址）。5.2Cache基本知識(shí)5.2Cache基本知識(shí)堆棧中的內(nèi)容必須動(dòng)態(tài)更新當(dāng)Cache訪問命中時(shí)，通過(guò)用塊地址進(jìn)行相聯(lián)查找，在堆棧中找到相應(yīng)的元素，然后把該元素的上面的所有元素下壓一個(gè)位置，同時(shí)把本次訪問的塊地址抽出來(lái)，從最上面壓入棧頂。而該元素下面的所有元素則保持不動(dòng)。如果Cache訪問不命中，則把本次訪問的塊地址從最上面壓入棧頂，堆棧中所有原來(lái)的元素都下移一個(gè)位置。如果Cache中該組已經(jīng)沒有空閑塊，就要替換一個(gè)塊。這時(shí)從棧底被擠出去的塊地址就是需要被替換的塊的塊地址。5.2Cache基本知識(shí)堆棧法所需要的硬件需要為每一組都設(shè)置一個(gè)項(xiàng)數(shù)與相聯(lián)度相同的小堆棧，每一項(xiàng)的位數(shù)為log2n位。硬件堆棧所需的功能相聯(lián)比較能全部下移、部分下移和從中間取出一項(xiàng)的功能速度較低，成本較高（只適用于相聯(lián)度較小的LRU算法）比較對(duì)法基本思路讓各塊兩兩組合，構(gòu)成比較對(duì)。每一個(gè)比較對(duì)用一個(gè)觸發(fā)器的狀態(tài)來(lái)表示它所相關(guān)的兩個(gè)塊最近一次被訪問的遠(yuǎn)近次序，再經(jīng)過(guò)門電路就可找到LRU塊。5.2Cache基本知識(shí)

例如：假設(shè)有A、B、C三個(gè)塊，可以組成3對(duì)：AB、AC、BC。每一對(duì)中塊的訪問次序分別用“對(duì)觸發(fā)器”TAB、TAC、TBC表示。TAB為“1”，表示A比B更近被訪問過(guò)；TAB為“0”，表示B比A更近被訪問過(guò)。TAC、TBC也是按這樣的規(guī)則定義。

顯然，當(dāng)TAC＝1且TBC＝1時(shí)，C就是最久沒有被訪問過(guò)了。（A比C更近被訪問過(guò)、且B比C也是更近被訪問過(guò)）即：CLRU=TAC·TBC

同理可得：

用觸發(fā)器和與門實(shí)現(xiàn)上述邏輯的電路：5.2Cache基本知識(shí)用比較對(duì)法實(shí)現(xiàn)LRU算法

5.2Cache基本知識(shí)比較對(duì)法所需的硬件量與門有多少個(gè)塊，就要有多少個(gè)與門；每個(gè)與門的輸入端要連接所有與之相關(guān)的觸發(fā)器。對(duì)于一個(gè)具有P塊的組中的任何一個(gè)塊來(lái)說(shuō)，由于它可以跟除了它自己以外的所有其他的塊兩兩組合，所以與該塊相關(guān)的比較對(duì)觸發(fā)器個(gè)數(shù)為P－1，因而其相應(yīng)的與門的輸入端數(shù)是P－1。觸發(fā)器所需要的觸發(fā)器的個(gè)數(shù)與兩兩組合的比較對(duì)的數(shù)目相同。比較對(duì)觸發(fā)器個(gè)數(shù)、與門的個(gè)數(shù)、與門的輸入端數(shù)與塊數(shù)P的關(guān)系組內(nèi)塊數(shù)3481664256…P觸發(fā)器個(gè)數(shù)3628120201632640…與門個(gè)數(shù)3481664256…P與門輸入端個(gè)數(shù)2371563255…P-15.2Cache基本知識(shí)塊數(shù)少時(shí)，所需要的硬件較少，隨著組內(nèi)塊數(shù)P的增加，所需的觸發(fā)器的個(gè)數(shù)會(huì)以平方的關(guān)系迅速增加，門的輸入端數(shù)也線性增加。

（硬件實(shí)現(xiàn)的成本很高）當(dāng)組內(nèi)塊數(shù)較多時(shí)，可以用多級(jí)狀態(tài)位技術(shù)減少所需的硬件量。例如：在IBM3033中組內(nèi)塊數(shù)為16，可分成群、對(duì)、行3級(jí)。先分成4群，每群兩對(duì)，每對(duì)兩行。選LRU群需6個(gè)觸發(fā)器；每群中選LRU對(duì)需要一個(gè)觸法器，4個(gè)群共需要4個(gè)觸發(fā)器；5.2Cache基本知識(shí)每行中選LRU塊需要一個(gè)觸發(fā)器，8個(gè)行共需要8個(gè)觸發(fā)器。所需的觸發(fā)器總個(gè)數(shù)為：

6（選群）＋4（選對(duì)）＋8（選行）=18（個(gè)）

以犧牲速度為代價(jià)的。5.2Cache基本知識(shí)“寫”在所有訪存操作中所占的比例統(tǒng)計(jì)結(jié)果表明，對(duì)于一組給定的程序：load指令：26％store指令：9％“寫”在所有訪存操作中所占的比例：

9％/(100％＋26％＋9％)≈7％“寫”在訪問Cache操作中所占的比例：

9％/(26％＋9％)≈25％5.2.6寫策略5.2Cache基本知識(shí)“寫”操作必須在確認(rèn)是命中后才可進(jìn)行“寫”訪問有可能導(dǎo)致Cache和主存內(nèi)容的不一致兩種寫策略寫策略是區(qū)分不同Cache設(shè)計(jì)方案的一個(gè)重要標(biāo)志。寫直達(dá)法（也稱為存直達(dá)法）執(zhí)行“寫”操作時(shí)，不僅寫入Cache，而且也寫入下一級(jí)存儲(chǔ)器。寫回法（也稱為拷回法）執(zhí)行“寫”操作時(shí)，只寫入Cache。僅當(dāng)Cache中相應(yīng)的塊被替換時(shí)，才寫回主存。(設(shè)置“修改位”)

5.2Cache基本知識(shí)兩種寫策略的比較寫回法的優(yōu)點(diǎn)：速度快，所使用的存儲(chǔ)器

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

平均訪存時(shí)間＝命中時(shí)間＋不命中率×不命中開銷5.2.7Cache的性能分析程序執(zhí)行時(shí)間CPU時(shí)間＝（CPU執(zhí)行周期數(shù)+存儲(chǔ)器停頓周期數(shù)）×?xí)r鐘周期時(shí)間其中：存儲(chǔ)器停頓時(shí)鐘周期數(shù)＝“讀”的次數(shù)×讀不命中率×讀不命中開銷＋“寫”的次數(shù)×寫不命中率×寫不命中開銷存儲(chǔ)器停頓時(shí)鐘周期數(shù)＝訪存次數(shù)×不命中率×不命中開銷

CPU時(shí)間＝（CPU執(zhí)行周期數(shù)+訪存次數(shù)×不命中率×不命中開銷）

×?xí)r鐘周期時(shí)間=IC×（CPIexecution＋每條指令的平均訪存次數(shù)×不命中率

×不命中開銷）×?xí)r鐘周期時(shí)間5.2Cache基本知識(shí)

例5.1

用一個(gè)和AlphaAXP類似的機(jī)器作為第一個(gè)例子。假設(shè)Cache不命中開銷為50個(gè)時(shí)鐘周期，當(dāng)不考慮存儲(chǔ)器停頓時(shí)，所有指令的執(zhí)行時(shí)間都是2.0個(gè)時(shí)鐘周期，訪問Cache不命中率為2%，平均每條指令訪存1.33次。試分析Cache對(duì)性能的影響。

解

CPU時(shí)間有cache＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)

×不命中率×不命中開銷）×?xí)r鐘周期時(shí)間＝IC×（2.0＋1.33×2%×50）×?xí)r鐘周期時(shí)間＝IC×3.33×?xí)r鐘周期時(shí)間5.2Cache基本知識(shí)

考慮Cache的不命中后，性能為：

CPU時(shí)間有cache＝IC×（2.0＋1.33×2%×50）×?xí)r鐘周期時(shí)間

＝IC×3.33×?xí)r鐘周期時(shí)間

實(shí)際CPI：3.33

3.33/2.0=1.67(倍)

CPU時(shí)間也增加為原來(lái)的1.67倍。但若不采用Cache,則：

CPI＝2.0＋50×1.33＝68.55.2Cache基本知識(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í)鐘頻率較高的CPU的不命中開銷較大，其CPI中存儲(chǔ)器停頓這部分也就較大。因此Cache對(duì)于低CPI、高時(shí)鐘頻率的CPU來(lái)說(shuō)更加重要。

例5.2

考慮兩種不同組織結(jié)構(gòu)的Cache：直接映像Cache和兩路組相聯(lián)Cache，試問它們對(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)在組相聯(lián)Cache中，由于多路選擇器的存在而使CPU的時(shí)鐘周期增加到原來(lái)的1.10倍。這是因?yàn)閷?duì)Cache的訪問總是處于關(guān)鍵路徑上，對(duì)CPU的時(shí)鐘周期有直接的影響。

(4)這兩種結(jié)構(gòu)Cache的不命中開銷都是70ns。（在實(shí)際應(yīng)用中，應(yīng)取整為整數(shù)個(gè)時(shí)鐘周期）

(5)命中時(shí)間為1個(gè)時(shí)鐘周期，64KB直接映像Cache的不命中率為1.4%，相同容量的兩路組相聯(lián)Cache的不命中率為1.0%。5.2Cache基本知識(shí)

解平均訪存時(shí)間為：平均訪存時(shí)間＝命中時(shí)間＋不命中率×不命中開銷因此，兩種結(jié)構(gòu)的平均訪存時(shí)間分別是：

平均訪存時(shí)間1路＝2.0＋（0.014×70）＝2.98ns

平均訪存時(shí)間2路＝2.0×1.10＋（0.010×70）＝2.90ns

兩路組相聯(lián)Cache的平均訪存時(shí)間比較低。

CPU時(shí)間＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)×

不命中率×不命中開銷）×?xí)r鐘周期時(shí)間＝IC×（CPIexecution×?xí)r鐘周期時(shí)間＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷×?xí)r鐘周期時(shí)間）5.2Cache基本知識(shí)因此：CPU時(shí)間1路＝IC×(2.0×2＋(1.3×0.014×70))

＝5.27×ICCPU時(shí)間2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))

＝5.31×IC直接映像Cache的平均性能好一些。5.2Cache基本知識(shí)平均訪存時(shí)間＝命中時(shí)間＋不命中率×不命中開銷可以從三個(gè)方面改進(jìn)Cache的性能：降低不命中率減少不命中開銷減少Cache命中時(shí)間下面介紹17種Cache優(yōu)化技術(shù)8種用于降低不命中率5種用于減少不命中開銷4種用于減少命中時(shí)間5.2.8改進(jìn)Cache的性能三種類型的不命中(3C)強(qiáng)制性不命中(Compulsorymiss)當(dāng)?shù)谝淮卧L問一個(gè)塊時(shí)，該塊不在Cache中，需從下一級(jí)存儲(chǔ)器中調(diào)入Cache，這就是強(qiáng)制性不命中。(冷啟動(dòng)不命中，首次訪問不命中）容量不命中(Capacitymiss)如果程序執(zhí)行時(shí)所需的塊不能全部調(diào)入Cache中，則當(dāng)某些塊被替換后，若又重新被訪問，就會(huì)發(fā)生不命中。這種不命中稱為容量不命中。5.3降低Cache不命中率5.3.1三種類型的不命中5.3降低Cache不命中率沖突不命中(Conflictmiss)在組相聯(lián)或直接映像Cache中，若太多的塊映像到同一組(塊)中，則會(huì)出現(xiàn)該組中某個(gè)塊被別的塊替換(即使別的組或塊有空閑位置)，然后又被重新訪問的情況。這就是發(fā)生了沖突不命中。

(碰撞不命中，干擾不命中)三種不命中所占的比例圖示I(絕對(duì)值)圖示Ⅱ(相對(duì)值)5.3降低Cache不命中率5.3降低Cache不命中率5.3降低Cache不命中率可以看出：相聯(lián)度越高，沖突不命中就越少；強(qiáng)制性不命中和容量不命中不受相聯(lián)度的影響；強(qiáng)制性不命中不受Cache容量的影響，但容量不命中卻隨著容量的增加而減少。5.3降低Cache不命中率減少三種不命中的方法強(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ì)增加沖突不命中。

Cache容量越大，使不命中率達(dá)到最低的塊大小就越大。增加塊大小會(huì)增加不命中開銷5.3.2增加Cache塊大小5.3降低Cache不命中率不命中率隨塊大小變化的曲線

5.3降低Cache不命中率各種塊大小情況下Cache的不命中率

塊大小（字節(jié)）Cache容量（字節(jié)）1K4K16K64K256K1615.05%8.57%3.94%2.04%1.09%3213.34%

7.24%2.87%1.35%0.70%6413.76%7.00%

2.64%

1.06%0.51%12816.64%7.78%2.77%1.02%

0.49%

25622.01%9.51%3.29%1.15%0.49%5.3降低Cache不命中率最直接的方法是增加Cache的容量缺點(diǎn):增加成本可能增加命中時(shí)間這種方法在片外Cache中用得比較多

5.3.3增加Cache的容量5.3降低Cache不命中率采用相聯(lián)度超過(guò)8的方案的實(shí)際意義不大。2:1Cache經(jīng)驗(yàn)規(guī)則

容量為N的直接映像Cache的不命中率和容量為N/2的兩路組相聯(lián)Cache的不命中率差不多相同。提高相聯(lián)度是以增加命中時(shí)間為代價(jià)。5.3.4提高相聯(lián)度5.3降低Cache不命中率多路組相聯(lián)的低不命中率和直接映像的命中速度偽相聯(lián)Cache的優(yōu)點(diǎn)命中時(shí)間小不命中率低5.3.5偽相聯(lián)Cache(列相聯(lián)Cache)優(yōu)點(diǎn)缺點(diǎn)直接映像組相聯(lián)命中時(shí)間小命中時(shí)間大不命中率高不命中率低基本思想及工作原理（動(dòng)畫演示）在邏輯上把直接映像Cache的空間上下平分為兩個(gè)區(qū)。對(duì)于任何一次訪問，偽相聯(lián)Cache先按直接映像Cache的方式去處理。若命中，則其訪問過(guò)程與直接映像Cache的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下一級(jí)存儲(chǔ)器。5.3降低Cache不命中率

缺點(diǎn)：多種命中時(shí)間快速命中與慢速命中要保證絕大多數(shù)命中都是快速命中。不命中開銷5.3降低Cache不命中率指令和數(shù)據(jù)都可以預(yù)取預(yù)取內(nèi)容既可放入Cache，也可放在外緩沖器中。例如：指令流緩沖器指令預(yù)取通常由Cache之外的硬件完成預(yù)取效果Joppi的研究結(jié)果指令預(yù)取(4KB，直接映像Cache，塊大?。?6字節(jié))1個(gè)塊的指令流緩沖器：捕獲15％～25％的不命中4個(gè)塊的指令流緩沖器：捕獲50％16個(gè)塊的指令流緩沖器：捕獲72％5.3.6硬件預(yù)取

5.3降低Cache不命中率數(shù)據(jù)預(yù)取(4KB,直接映像Cache)1個(gè)數(shù)據(jù)流緩沖器：捕獲25％的不命中還可以采用多個(gè)數(shù)據(jù)流緩沖器Palacharla和Kessler的研究結(jié)果流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)對(duì)于兩個(gè)64KB四路組相聯(lián)Cache來(lái)說(shuō)：8個(gè)流緩沖器能捕獲50％～70％的不命中預(yù)取應(yīng)利用存儲(chǔ)器的空閑帶寬，不能影響對(duì)正常不命中的處理，否則可能會(huì)降低性能。5.3降低Cache不命中率

在編譯時(shí)加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請(qǐng)求。按照預(yù)取數(shù)據(jù)所放的位置，可把預(yù)取分為兩種類型：寄存器預(yù)取：把數(shù)據(jù)取到寄存器中。Cache預(yù)?。褐粚?shù)據(jù)取到Cache中。按照預(yù)取的處理方式不同，可把預(yù)取分為：故障性預(yù)?。涸陬A(yù)取時(shí)，若出現(xiàn)虛地址故障或違反保護(hù)權(quán)限，就會(huì)發(fā)生異常。5.3.7編譯器控制的預(yù)取

5.3降低Cache不命中率非故障性預(yù)?。涸谟龅竭@種情況時(shí)則不會(huì)發(fā)生異常，因?yàn)檫@時(shí)它會(huì)放棄預(yù)取，轉(zhuǎn)變?yōu)榭詹僮?。本?jié)假定Cache預(yù)取都是非故障性的，也叫做非綁定預(yù)取。在預(yù)取數(shù)據(jù)的同時(shí)，處理器應(yīng)能繼續(xù)執(zhí)行。只有這樣，預(yù)取才有意義。非阻塞Cache(非鎖定Cache)

編譯器控制預(yù)取的目的使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。循環(huán)是預(yù)取優(yōu)化的主要對(duì)象5.3降低Cache不命中率不命中開銷小時(shí)：循環(huán)體展開1～2次不命中開銷大時(shí)：循環(huán)體展開許多次每次預(yù)取需要花費(fèi)一條指令的開銷保證這種開銷不超過(guò)預(yù)取所帶來(lái)的收益編譯器可以通過(guò)把重點(diǎn)放在那些可能會(huì)導(dǎo)致不命中的訪問上，使程序避免不必要的預(yù)取，從而較大程度地減少平均訪存時(shí)間。5.3降低Cache不命中率基本思想：通過(guò)對(duì)軟件進(jìn)行優(yōu)化來(lái)降低不命中率。

（特色：無(wú)需對(duì)硬件做任何改動(dòng)）程序代碼和數(shù)據(jù)重組可以重新組織程序而不影響程序的正確性把一個(gè)程序中的過(guò)程重新排序，就可能會(huì)減少?zèng)_突不命中，從而降低指令不命中率。McFarling研究了如何使用配置文件（profile）來(lái)進(jìn)行這種優(yōu)化。把基本塊對(duì)齊，使得程序的入口點(diǎn)與Cache塊的5.3.8編譯器優(yōu)化

5.3降低Cache不命中率

起始位置對(duì)齊，就可以減少順序代碼執(zhí)行時(shí)所發(fā)生的Cache不命中的可能性。

（提高大Cache塊的效率）如果編譯器知道一個(gè)分支指令很可能會(huì)成功轉(zhuǎn)移，那么它就可以通過(guò)以下兩步來(lái)改善空間局部性：將轉(zhuǎn)移目標(biāo)處的基本塊和緊跟著該分支指令后的基本塊進(jìn)行對(duì)調(diào)；把該分支指令換為操作語(yǔ)義相反的分支指令。數(shù)據(jù)對(duì)存儲(chǔ)位置的限制更少，更便于調(diào)整順序。5.3降低Cache不命中率編譯優(yōu)化技術(shù)包括數(shù)組合并將本來(lái)相互獨(dú)立的多個(gè)數(shù)組合并成為一個(gè)復(fù)合數(shù)組，以提高訪問它們的局部性。內(nèi)外循環(huán)交換循環(huán)融合將若干個(gè)獨(dú)立的循環(huán)融合為單個(gè)的循環(huán)。這些循環(huán)訪問同樣的數(shù)組，對(duì)相同的數(shù)據(jù)作不同的運(yùn)算。這樣能使得讀入Cache的數(shù)據(jù)在被替換出去之前，能得到反復(fù)的使用。分塊5.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（j=0;j<100;j=j+1）

x[i][j]=2*x[i][j];5.3降低Cache不命中率分塊把對(duì)數(shù)組的整行或整列訪問改為按塊進(jìn)行。

/*修改前*/for（i=0;i<N;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;}計(jì)算過(guò)程（不命中次數(shù)：2N3＋N2）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,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不命中率5.3降低Cache不命中率一種能減少?zèng)_突不命中次數(shù)而又不影響時(shí)鐘頻率的方法?；舅枷朐贑ache和它從下一級(jí)存儲(chǔ)器調(diào)數(shù)據(jù)的通路之間設(shè)置一個(gè)全相聯(lián)的小Cache，稱為“犧牲”Cache（VictimCache）。用于存放被替換出去的塊(稱為犧牲者)，以備重用。工作過(guò)程5.3.9“犧牲”

Cache

5.3降低Cache不命中率作用對(duì)于減小沖突不命中很有效，特別是對(duì)于小容量的直接映像數(shù)據(jù)Cache，作用尤其明顯。例如項(xiàng)數(shù)為4的VictimCache:

能使4KB

Cache的沖突不命中減少20%～90%應(yīng)把Cache做得更快？還是更大？答案：二者兼顧，再增加一級(jí)Cache第一級(jí)Cache(L1)小而快第二級(jí)Cache(L2)容量大性能分析平均訪存時(shí)間＝命中時(shí)間L1＋不命中率L1×不命中開銷L1不命中開銷L1

＝命中時(shí)間L2＋不命中率L2×不命中開銷L25.4.1采用兩級(jí)Cache5.4減少Cache不命中開銷5.4減少Cache不命中開銷平均訪存時(shí)間＝命中時(shí)間L1＋不命中率L1×

（命中時(shí)間L2＋不命中率L2×不命中開銷L2）局部不命中率與全局不命中率局部不命中率＝該級(jí)Cache的不命中次數(shù)/到達(dá)該級(jí)Cache的訪問次數(shù)例如：上述式子中的不命中率L2全局不命中率＝該級(jí)Cache的不命中次數(shù)/CPU發(fā)出的訪存的總次數(shù)5.4減少Cache不命中開銷全局不命中率L2＝不命中率L1×不命中率L2

評(píng)價(jià)第二級(jí)Cache時(shí)，應(yīng)使用全局不命中率這個(gè)指標(biāo)。它指出了在CPU發(fā)出的訪存中，究竟有多大比例是穿過(guò)各級(jí)Cache，最終到達(dá)存儲(chǔ)器的。采用兩級(jí)Cache時(shí)，每條指令的平均訪存停頓時(shí)間：每條指令的平均訪存停頓時(shí)間＝每條指令的平均不命中次數(shù)L1×命中時(shí)間L2＋每條指令的平均不命中次數(shù)L2×不命中開銷L25.4減少Cache不命中開銷例5.3考慮某一兩級(jí)Cache：第一級(jí)Cache為L(zhǎng)1，第二級(jí)Cache為L(zhǎng)2。（1）假設(shè)在1000次訪存中，L1的不命中是40次，L2的不命中是20次。求各種局部不命中率和全局不命中率。（2）假設(shè)L2的命中時(shí)間是10個(gè)時(shí)鐘周期，L2的不命中開銷是100時(shí)鐘周期，L1的命中時(shí)間是1個(gè)時(shí)鐘周期，平均每條指令訪存1.5次，不考慮寫操作的影響。問：平均訪存時(shí)間是多少？每條指令的平均停頓時(shí)間是多少個(gè)時(shí)鐘周期？

解(1)

第一級(jí)Cache的不命中率（全局和局部）是40/1000，即4%；第二級(jí)Cache的局部不命中率是20/40，即50%；第二級(jí)Cache的全局不命中率是20/1000，即2%。5.4減少Cache不命中開銷（2）平均訪存時(shí)間＝命中時(shí)間L1＋不命中率L1×（命中時(shí)間L2＋不命中率L2×不命中開銷L2）＝1＋4%×（10＋50%×100）＝1＋4%×60＝3.4個(gè)時(shí)鐘周期由于平均每條指令訪存1.5次，且每次訪存的平均停頓時(shí)間為：

3.4－1.0＝2.4所以：每條指令的平均停頓時(shí)間＝2.4×1.5＝3.6個(gè)時(shí)鐘周期5.4減少Cache不命中開銷對(duì)于第二級(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è)問題：5.4減少Cache不命中開銷它能否降低CPI中的平均訪存時(shí)間部分？它的成本是多少？第二級(jí)Cache的參數(shù)容量第二級(jí)Cache的容量一般比第一級(jí)的大許多。大容量意味著第二級(jí)Cache可能實(shí)際上沒有容量不命中，只剩下一些強(qiáng)制性不命中和沖突不命中。相聯(lián)度第二級(jí)Cache可采用較高的相聯(lián)度或偽相聯(lián)方法。5.4減少Cache不命中開銷

例5.4

給出有關(guān)第二級(jí)Cache的以下數(shù)據(jù)：（1）對(duì)于直接映像，命中時(shí)間L2

＝10個(gè)時(shí)鐘周期

（2）兩路組相聯(lián)使命中時(shí)間增加0.1個(gè)時(shí)鐘周期，即為10.1個(gè)時(shí)鐘周期。（3）對(duì)于直接映像，局部不命中率L2

＝25%

（4）對(duì)于兩路組相聯(lián)，局部不命中率L2＝20%

（5）不命中開銷L2

＝50個(gè)時(shí)鐘周期試問第二級(jí)Cache的相聯(lián)度對(duì)不命中開銷的影響如何？5.4減少Cache不命中開銷

解對(duì)一個(gè)直接映像的第二級(jí)Cache來(lái)說(shuō)，第一級(jí)Cache的不命中開銷為：

不命中開銷直接映像，L1

＝10＋25%×50＝22.5個(gè)時(shí)鐘周期對(duì)于兩路組相聯(lián)第二級(jí)Cache來(lái)說(shuō)，命中時(shí)間增加了10%（0.1）個(gè)時(shí)鐘周期，故第一級(jí)Cache的不命中開銷為：

不命中開銷兩路組相聯(lián)，L1

＝10.1＋20%×50＝20.1個(gè)時(shí)鐘周期把第二級(jí)Cache的命中時(shí)間取整，得10或11，則：不命中開銷兩路組相聯(lián)，L1

＝10＋20%×50＝20.0個(gè)時(shí)鐘周期不命中開銷兩路組相聯(lián)，L1

＝11＋20%×50＝21.0個(gè)時(shí)鐘周期故對(duì)于第二級(jí)Cache來(lái)說(shuō)，兩路組相聯(lián)優(yōu)于直接映像。5.4減少Cache不命中開銷塊大小第二級(jí)Cache可采用較大的塊如64、128、256字節(jié)為減少平均訪存時(shí)間，可以讓容量較小的第一級(jí)Cache采用較小的塊，而讓容量較大的第二級(jí)Cache采用較大的塊。多級(jí)包容性需要考慮的另一個(gè)問題：第一級(jí)Cache中的數(shù)據(jù)是否總是同時(shí)存在于第二級(jí)Cache中。

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

對(duì)應(yīng)的位置又是空閑的，就把這次要寫入的數(shù)據(jù)與該項(xiàng)合并。這就叫寫緩沖合并。如果寫緩沖器滿且又沒有能進(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.4請(qǐng)求字處理技術(shù)5.4減少Cache不命中開銷這種技術(shù)在以下情況下效果不大：Cache塊較小下一條指令正好訪問同一Cache塊的另一部分5.4減少Cache不命中開銷非阻塞Cache：Cache不命中時(shí)仍允許CPU進(jìn)行其他的命中訪問。即允許“不命中下命中”。進(jìn)一步提高性能：“多重不命中下命中”

“不命中下不命中”（存儲(chǔ)器必須能夠處理多個(gè)不命中）可以同時(shí)處理的不命中次數(shù)越多，所能帶來(lái)的性能上的提高就越大。（不命中次數(shù)越多越好？）5.4.5非阻塞Cache技術(shù)5.4減少Cache不命中開銷模擬研究數(shù)據(jù)Cache的平均存儲(chǔ)器等待時(shí)間（以周期為單位）與阻塞Cache平均存儲(chǔ)器等待時(shí)間的比值測(cè)試條件：8K直接映像Cache，塊大小為32字節(jié)測(cè)試程序：SPEC92（14個(gè)浮點(diǎn)程序，4個(gè)整數(shù)程序）結(jié)果表明在重疊不命中個(gè)數(shù)為1、2和64的情況下浮點(diǎn)程序的平均比值分別為：76%、51%和39%整數(shù)程序的平均比值則分別為：81%、78%和78%對(duì)于整數(shù)程序來(lái)說(shuō)，重疊次數(shù)對(duì)性能提高影響不大，簡(jiǎn)單的“一次不命中下命中”就幾乎可以得到所有的好處。

命中時(shí)間直接影響到處理器的時(shí)鐘頻率。在當(dāng)今的許多計(jì)算機(jī)中，往往是Cache的訪問時(shí)間限制了處理器的時(shí)鐘頻率。5.5減少命中時(shí)間5.5.1容量小、結(jié)構(gòu)簡(jiǎn)單的Cache硬件越簡(jiǎn)單，速度就越快；應(yīng)使Cache足夠小，以便可以與CPU一起放在同一塊芯片上。5.5減少命中時(shí)間

某些設(shè)計(jì)采用了一種折衷方案：

把Cache的標(biāo)識(shí)放在片內(nèi)，而把Cache的數(shù)據(jù)存儲(chǔ)器放在片外。5.5.2虛擬Cache物理Cache使用物理地址進(jìn)行訪問的傳統(tǒng)Cache。標(biāo)識(shí)存儲(chǔ)器中存放的是物理地址，進(jìn)行地址檢測(cè)也是用物理地址。5.5減少命中時(shí)間缺點(diǎn)：地址轉(zhuǎn)換和訪問Cache串行進(jìn)行，訪問速度很慢。物理Cache存儲(chǔ)系統(tǒng)5.5減少命中時(shí)間虛擬Cache可以直接用虛擬地址進(jìn)行訪問的Cache。標(biāo)識(shí)存儲(chǔ)器中存放的是虛擬地址，進(jìn)行地址檢測(cè)用的也是虛擬地址。優(yōu)點(diǎn)：在命中時(shí)不需要地址轉(zhuǎn)換，省去了地址轉(zhuǎn)換的時(shí)間。即使不命中，地址轉(zhuǎn)換和訪問Cache也是并行進(jìn)行的，其速度比物理Cache快很多。

5.5減少命中時(shí)間并非都采用虛擬Cache(為什么?)虛擬Cache的清空問題解決方法：在地址標(biāo)識(shí)中增加PID字段

(進(jìn)程標(biāo)識(shí)符)三種情況下不命中率的比較單進(jìn)程，PIDs，清空PIDs與單進(jìn)程相比：＋0.3％～＋0.6％PIDs與清空相比：－0.6％～－4.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)度舉例：IBM3033的Cache頁(yè)大?。?KB相聯(lián)度＝16

頁(yè)地址

地址標(biāo)識(shí)頁(yè)內(nèi)位移索引塊內(nèi)位移31121105.5減少命中時(shí)間Cache容量＝16×4KB＝64KB另一種方法：硬件散列變換5.5.3Cache訪問流水化對(duì)第一級(jí)Cache的訪問按流水方式組織訪問Cache需要多個(gè)時(shí)鐘周期才可以完成例如Pentium訪問指令Cache需要一個(gè)時(shí)鐘周期PentiumPro到PentiumⅢ需要兩個(gè)時(shí)鐘周期Pentium4則需要4個(gè)時(shí)鐘周期5.5減少命中時(shí)間開發(fā)指令級(jí)并行性所遇到的一個(gè)挑戰(zhàn)是：當(dāng)要每個(gè)時(shí)鐘周期流出超過(guò)4條指令時(shí)，要提供足夠多條彼此互不相關(guān)的指令是很困難的。一個(gè)解決方法：采用蹤跡Cache存放CPU所執(zhí)行的動(dòng)態(tài)指令序列包含了由分支預(yù)測(cè)展開的指令，該分支預(yù)測(cè)是否正確需要在取到該指令時(shí)進(jìn)行確認(rèn)。5.5.4蹤跡Cache5.5減少命中時(shí)間優(yōu)缺點(diǎn)地址映像機(jī)制復(fù)雜，相同的指令序列有可能被當(dāng)作條件分支的不同選擇而重復(fù)存放,能夠提高指令Cache的空間利用率。5.5.5Cache優(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)容易；Pentium4的第二級(jí)Cache采用了128字節(jié)的塊增加Cache容量+1被廣泛采用，特別是第二級(jí)Cache提高相聯(lián)度+

1被廣泛采用犧牲Cache

+2AMDAthlon采用了8個(gè)項(xiàng)的VictimCache偽相聯(lián)Cache+2MIPSR10000的第二級(jí)Cache采用硬件預(yù)取指令和數(shù)據(jù)+2～3許多機(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)鍵字優(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)容易，已被Alpha21164和UltraSPARCⅢ采用流水化Cache訪問

+1被廣泛采用TraceCache+3Pentium4采用主存的主要性能指標(biāo)：延遲和帶寬以往：Cache主要關(guān)心延遲，I/O主要關(guān)心帶寬?，F(xiàn)在：Cache關(guān)心兩者并行主存系統(tǒng)是在一個(gè)訪存周期內(nèi)能并行訪問多個(gè)存儲(chǔ)字的存儲(chǔ)器。能有效地提高存儲(chǔ)器的帶寬。5.6并行主存系統(tǒng)5.6并行主存系統(tǒng)一個(gè)單體單字寬的存儲(chǔ)器字長(zhǎng)與CPU的字長(zhǎng)相同。每一次只能訪問一個(gè)存儲(chǔ)字。假設(shè)該存儲(chǔ)器的訪問周期是TM，字長(zhǎng)為W位，則其帶寬為：

普通存儲(chǔ)器5.6并行主存系統(tǒng)在相同的器件條件（即TM相同）下，可以采用兩種并行存儲(chǔ)器結(jié)構(gòu)來(lái)提高主存的帶寬：?jiǎn)误w多字存儲(chǔ)器多體交叉存儲(chǔ)器

5.6并行主存系統(tǒng)一個(gè)單體m字（這里m=4）存儲(chǔ)器

動(dòng)畫5.6.1單體多字存儲(chǔ)器5.6并行主存系統(tǒng)存儲(chǔ)器能夠每個(gè)存儲(chǔ)周期讀出m個(gè)CPU字。因此其最大帶寬提高到原來(lái)的m倍。單體多字存儲(chǔ)器的實(shí)際帶寬比最大帶寬小優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：訪存效率不高

5.6并行主存系統(tǒng)原因：如果一次讀取的m個(gè)指令字中有分支指令，而且分支成功，那么該分支指令之后的指令是無(wú)用的。一次取出的m個(gè)數(shù)據(jù)不一定都是有用的。另一方面，當(dāng)前執(zhí)行指令所需要的多個(gè)操作數(shù)也不一定正好都存放在同一個(gè)長(zhǎng)存儲(chǔ)字中。寫入有可能變得復(fù)雜。當(dāng)要讀出的數(shù)據(jù)字和要寫入的數(shù)據(jù)字處于同一個(gè)長(zhǎng)存儲(chǔ)字內(nèi)時(shí)，讀和寫的操作就無(wú)法在同一個(gè)存儲(chǔ)周期內(nèi)完成。5.6并行主存系統(tǒng)多體交叉存儲(chǔ)器：由多個(gè)單字存儲(chǔ)體構(gòu)成，每個(gè)體都有自己的地址寄存器以及地址譯碼和讀/寫驅(qū)動(dòng)等電路。問題：對(duì)多體存儲(chǔ)器如何進(jìn)行編址？存儲(chǔ)器是按順序線性編址的。如何在二維矩陣和線性地址之間建立對(duì)應(yīng)關(guān)系？?jī)煞N編址方法高位交叉編址低位交叉編址（有效地解決訪問沖突問題）5.6.2多體交叉存儲(chǔ)器5.6并行主存系統(tǒng)多體（m=4）交叉存儲(chǔ)器5.6并行主存系統(tǒng)高位交叉編址對(duì)存儲(chǔ)單元矩陣按列優(yōu)先的方式進(jìn)行編址特點(diǎn)：同一個(gè)體中的高log2m位都是相同的（體號(hào)）

處于第i行第j列的單元，即體號(hào)為j、體內(nèi)地址為i的單元，其線性地址為：

A＝j(luò)×n＋i其中：j＝０，1，2，…，m－1i＝０，1，2，…，n－1一個(gè)單元的線性地址為A，則其體號(hào)j和體內(nèi)地址i為：

i＝Amodn5.6并行主存系統(tǒng)5.6并行主存系統(tǒng)把A表示為二進(jìn)制數(shù)，則其高log2m位就是體號(hào)，而剩下的部分就是體內(nèi)地址。

低位交叉編址

對(duì)存儲(chǔ)單元矩陣按行優(yōu)先進(jìn)行編址特點(diǎn)：同一個(gè)體中的低log2m位都是相同的（體號(hào)）5.6并行主存系統(tǒng)處于第i行第j列的單元，即體號(hào)為j、體內(nèi)地址為i的單元，其線性地址為：

A＝i×m＋j

其中：i＝０，1，2，…，n－1j＝０，1，2，…，m－15.6并行主存系統(tǒng)一個(gè)單元的線性地址為A，則其體號(hào)j和體內(nèi)地址i為：

j＝Amodm把A表示為二進(jìn)制數(shù)，則其低log2m位就是體號(hào)，而剩下的部分就是體內(nèi)地址。

例：采用低位交叉編址的存儲(chǔ)器由8個(gè)存儲(chǔ)體構(gòu)成、總?cè)萘繛?4。格子中的編號(hào)為線性地址。

5.6并行主存系統(tǒng)為了提高主存的帶寬，需要多個(gè)或所有存儲(chǔ)體能并行工作。

在每一個(gè)存儲(chǔ)周期內(nèi)，分時(shí)啟動(dòng)m個(gè)存儲(chǔ)體。如果每個(gè)存儲(chǔ)體的訪問周期是TM，則各存儲(chǔ)體的啟動(dòng)間隔為：

t=TM/m。5.6并行主存系統(tǒng)增加m的值就能夠提高主存儲(chǔ)器的帶寬。但是，由于存在訪問沖突，實(shí)際加速比小于m。通過(guò)一個(gè)模型分析并行主存系統(tǒng)的實(shí)際帶寬一個(gè)由m個(gè)獨(dú)立分體組成的主存系統(tǒng)CPU發(fā)出的一串地址為A1，A2，…，Aq的訪存申請(qǐng)隊(duì)列存儲(chǔ)控制器掃描這個(gè)隊(duì)列，并截取從頭起的A1，A2，…，Ak序列作為申請(qǐng)序列。申請(qǐng)序列是滿足以下條件的最長(zhǎng)序列：k個(gè)地址所訪問的存儲(chǔ)器單元都處在不同的分體中。5.6并行主存系統(tǒng)A1～Ak不一定是順序地址，只要它們之間不出現(xiàn)分體沖突。k越接近于m，系統(tǒng)的效率就越高。設(shè)P(k)表示申請(qǐng)序列長(zhǎng)度為k的概率，用B表示k的平均值，則其中：k=1，2，…，m

每個(gè)主存周期所能訪問到的字?jǐn)?shù)的平均值，正比于主存實(shí)際帶寬。5.6并行主存系統(tǒng)P(k)與具體程序的運(yùn)行狀況密切相關(guān)。如果訪存申請(qǐng)隊(duì)列都是指令的話，那么影響最大的是轉(zhuǎn)移概率λ。轉(zhuǎn)移概率λ：給定指令的下條指令地址為非順序地址的概率。當(dāng)k＝1時(shí)，所表示的情況是：第一條就是轉(zhuǎn)移指令且轉(zhuǎn)移成功。

P（1）＝λ＝（1－λ）0·λ當(dāng)k＝2時(shí)，所表示的情況是：第一條指令沒有轉(zhuǎn)移（其概率為1－λ），第二條是轉(zhuǎn)移指令且轉(zhuǎn)移成功。所以有：

P（2）＝（1－λ）1·λ5.6并行主存系統(tǒng)同理，P（3）＝（1－λ）2·λ依此類推，P（k）＝（1－λ）k－1·λ

其中：1≤k＜m如果前m－1條指令均不轉(zhuǎn)移，則不管第m條指令是否轉(zhuǎn)移，k都等于m，因此有：

P（m）＝（1－λ）m－1

5.6并行主存系統(tǒng)m等于4、8、16時(shí)，B與λ的關(guān)系曲線

5.6并行主存系統(tǒng)對(duì)于數(shù)據(jù)來(lái)說(shuō)，由于其順序性差，m值的增大給B帶來(lái)的好處就更差一些。若機(jī)器主要是運(yùn)行標(biāo)量運(yùn)算的程序，一般取m≤8。如果是向量處理機(jī)，其m值可以取大些。單純靠增大m來(lái)提高并行主存系統(tǒng)的帶寬是有限的，而且性能價(jià)格比還會(huì)隨m的增大而下降。原因：程序的轉(zhuǎn)移概率不會(huì)很低數(shù)據(jù)分布的離散性較大5.6并行主存系統(tǒng)5.6.3避免存儲(chǔ)體沖突體沖突：兩個(gè)請(qǐng)求要訪問同一個(gè)體。減少體沖突次數(shù)的一種方法：采用許多體例如，NECSX/3最多可使用128個(gè)體

5.6并行主存系統(tǒng)

這種方法存在問題：假如我們有128個(gè)存儲(chǔ)體，按字交叉方式工作，并執(zhí)行以下程序：

intx[256][512]；

for（j=0；j<512；j=j+1）

for（i=0；i<256；i=i+1）

x[i][j]=2*x[i][j]；

因?yàn)?12是128的整數(shù)倍，同一列中的所有元素都在同一個(gè)體內(nèi)，無(wú)論CPU或存儲(chǔ)系統(tǒng)多么高級(jí)，該程序都會(huì)在數(shù)據(jù)Cache不命中時(shí)暫停。5.6并行主存系統(tǒng)解決體沖突的方法軟件方法(編譯器)循環(huán)交換優(yōu)化擴(kuò)展數(shù)組的大小，使之不是2的冪。硬件方法使體數(shù)為素?cái)?shù)體內(nèi)地址＝地址Amod(存儲(chǔ)體中的字?jǐn)?shù))

可以直接截取舉例體內(nèi)地址存儲(chǔ)體順序交叉取模交叉012345順序交叉和取模交叉的地址映像舉例670120120120168345678910111213142122231516171819209