第4章存儲層次

第4章存儲層次4.1存儲器的層次結(jié)構(gòu)4.2Cache基本知識4.3降低Cache失效率的方法4.4減少Cache失效開銷4.5減少命中時間4.6主存4.7虛擬存儲器4.8進(jìn)程保護(hù)4.9IntelCorei7中的存儲器層次結(jié)構(gòu)計算機系統(tǒng)結(jié)構(gòu)第4章存儲層次4.1存儲器的層次結(jié)構(gòu)4.1.1從單級存儲器到多級存儲器1.從用戶的角度來看，存儲器的三個主要指標(biāo)是：

容量，速度，價格(每位價格)2.人們對這三個指標(biāo)的期望: 容量大，速度快，價格低3.這三個指標(biāo)相互矛盾 如：速度越高，價格越高；容量越大，價格越低；容量越大，速度越慢。4.解決方法采用多種存儲器技術(shù)，構(gòu)成存儲層次。4.1存儲器的層次結(jié)構(gòu)M1-Mn：用不同技術(shù)實現(xiàn)的存儲器它們之間以塊或頁面為單位傳送數(shù)據(jù)，M1離CPU最近，容量最小，每位價格最高。Mn離CPU最遠(yuǎn)，容量最大，每位價格最低?？紤]相鄰的兩級，靠近CPU的一級總是容量小一些，速度快一些，價格高一些。4.1存儲器的層次結(jié)構(gòu)整個系統(tǒng)的目標(biāo)：從CPU看去，這個存儲器系統(tǒng)的速度接近于M1的，而容量和價格則接近于Mn。須做到：存儲器越靠近CPU，CPU對它的訪問頻率越高。大多數(shù)訪問都能在M1完成（根據(jù)局部性原理）。任何一級存儲器中的內(nèi)容一般都是其下一層存儲器中內(nèi)容的子集。當(dāng)CPU訪存時，首先是訪問M1，若找到數(shù)據(jù)，則訪問結(jié)束。若沒有找到，就需要訪問M2，將包含所需數(shù)據(jù)的塊（或頁面）調(diào)入M1。若M2中還沒有找到，就需訪問M3，以此類推。小容量存儲器：速度高，價格也高。大容量存儲器：速度低，價格也低。高性能要求存儲器速度高，實際應(yīng)用要求存儲器容量大，互相矛盾。怎么辦？現(xiàn)代計算機一般采用存儲層次。4.1存儲器的層次結(jié)構(gòu)頂層包含最常用的信息。任何一層中包含的信息，都是其下一層中信息的一個副本。CPU訪問存儲器時，若在Cache中沒找到所要的信息，就從下一層中調(diào)入。4.1存儲器的層次結(jié)構(gòu)4.1.2存儲層次的性能參數(shù)每位價格C，命中率H，平均訪問時間TA假設(shè)：S──容量TA──訪問時間C──每位價格下面僅考慮由M1和M2構(gòu)成的兩級存儲層次：

M1的參數(shù)：S1，TA1，C1 M2的參數(shù)：S2，TA2，C21.

每位價格C

C＝C1S1＋C2S2S1＋S2顯然，當(dāng)S1<<S2時，C≈C24.1存儲器的層次結(jié)構(gòu)2.命中率H和失效率F 命中率為CPU訪問存儲系統(tǒng)時，在M1中找到所需信息的概率。

命中率一般用模擬的方法來確定，也就是通過模擬一組有代表性的程序，分別記錄下訪問M1和M2的次數(shù)N1和N2，則

H＝N1/(N1＋N2)

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

失效率F＝1－H4.1存儲器的層次結(jié)構(gòu)3.平均訪問時間TA 分兩種情況來考慮CPU的一次訪存：當(dāng)命中時，訪問時間即為TA1，所以TA1常稱為命中時間。不命中時，情況比較復(fù)雜。在大多數(shù)兩級存儲層次中，若訪問的字不在M1中，就必須從M2把所請求的字的信息塊傳送到M1，之后CPU才可在M1中訪問到這個字。假設(shè)傳遞一個信息塊所需的時間為TB,則不命中的訪問時間為 TA2+TB+TA1=TA1+TM其中，TM=TA2+TB，它是從向M2發(fā)出訪問請求到把整個數(shù)據(jù)塊調(diào)入M1中所需的時間。TM常稱為失效開銷。根據(jù)以上分析可知

TA＝HTA1＋(1－H)(TA1+TM)＝TA1＋(1－H)TM或TA＝TA1＋FTM

4.1存儲器的層次結(jié)構(gòu)4.1.3“Cache－主存”和“主存－輔存”層次從主存的角度來看

“Cache－主存”層次：彌補主存速度的不足

“主存－輔存”層次：彌補主存容量的不足1.“Cache－主存”層次

主存與CPU的速度差距4.1存儲器的層次結(jié)構(gòu)4.1存儲器的層次結(jié)構(gòu)4.1存儲器的層次結(jié)構(gòu)3.“主存－輔存”層次4.1存儲器的層次結(jié)構(gòu)存儲層次CPU對第二級的

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

訪問速度的比值

(第一級和第二級)典型的塊(頁)大小失效時CPU是否切換“Cache－主存”層次“主存－輔存”層次為了彌補主存速度的不足為了彌補主存容量的不足主要由專用硬件實現(xiàn)主要由軟件實現(xiàn)幾比一幾百比一幾十個字節(jié)幾百到幾千個字節(jié)可直接訪問均通過第一級不切換切換到其他進(jìn)程“Cache－主存”與“主存－輔存”層次的區(qū)別4.1存儲器的層次結(jié)構(gòu)4.1.4存儲層次的四個問題當(dāng)把一個塊調(diào)入高一層(靠近CPU)存儲器時，

可以放在哪些位置上?

(映象規(guī)則)當(dāng)所要訪問的塊在高一層存儲器中時，如何

找到該塊?

(查找算法)3.當(dāng)發(fā)生失效時，應(yīng)替換哪一塊？

(替換算法)4.當(dāng)進(jìn)行寫訪問時，應(yīng)進(jìn)行哪些操作?

(寫策略)1.2.第4章存儲層次4.2Cache基本知識Cache是按塊進(jìn)行管理的。Cache和主存均被分割成大小相同的塊。信息以塊為單位調(diào)入Cache。相應(yīng)地，CPU的訪存地址被分割成兩部分：塊地址和塊內(nèi)位移。主存地址：塊地址塊內(nèi)位移主存塊地址用于查找該塊在Cache中的位置，塊內(nèi)位移用于確定所訪問的數(shù)據(jù)在該塊中的位置。4.2Cache基本知識5.2.1映象規(guī)則映象規(guī)則主要有全相聯(lián)映象，直接映象和組相聯(lián)映象三種。1.全相聯(lián)映象全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個位置。特點：空間利用率最高，沖突概率最低，實現(xiàn)最復(fù)雜。4.2Cache基本知識4.2Cache基本知識2.直接映象直接映象：主存中的每一塊只能被放置到Cache中唯一的一個位置。(循環(huán)分配)◆特點：空間利用率最低，沖突概率最高，實現(xiàn)最簡單?！魧τ谥鞔娴牡趇塊，若它映象到Cache的第j塊，則:

j＝imod(M)（M為Cache的塊數(shù)）

4.2Cache基本知識4.2Cache基本知識◆

組相聯(lián)：主存中的每一塊可以被放置到Cache

中唯一的一個組中的任何一個位置。（Cache等分為若干組，每組由若干個塊構(gòu)成）◆組相聯(lián)是直接映象和全相聯(lián)的一種折中?！粼O(shè)M＝2m，則當(dāng)表示為二進(jìn)制數(shù)時，j實際

上就是i的低m位：3.組相聯(lián)映象m位j主存塊地址i：4.2Cache基本知識4.2Cache基本知識◆上述的m和k通常稱為索引◆組的選擇常采用位選擇算法若主存第i塊映象到第k組，則:

k＝imod（G）（G為Cache的組數(shù)）設(shè)G＝2g，則當(dāng)表示為二進(jìn)制數(shù)時，k實

際上就是i的低g位：g位k主存塊地址i：4.2Cache基本知識◆絕大多數(shù)計算機的Cache:n≤4

想一想：相聯(lián)度一定是越大越好？◆n路組相聯(lián)：每組中有n個塊(n＝M/G)

n稱為相聯(lián)度。

相聯(lián)度越高，Cache空間的利用率就越高，

塊沖突概率就越低，失效率也就越低。全相聯(lián)直接映象組相聯(lián)n(路數(shù))G(組數(shù))MM111＜n＜M1＜G＜M4.2Cache基本知識塊沖突是指一個主存塊要進(jìn)入已被占用的Cache塊位置。顯然，全相聯(lián)的失效率最低，直接映象的失效率最高。雖然從降低失效率的角度來看，n的值越大越好，但在后面我們將看到，增大n值并不一定能使整個計算機系統(tǒng)的性能提高，而且還會使Cache的實現(xiàn)復(fù)雜度和代價增大。因此，絕大多數(shù)計算機都采用直接映象、兩路組相聯(lián)或4路組相聯(lián)。特別是直接映象，采用得最多。4.2Cache基本知識4.2.2查找方法1.如何確定Cache中是否有所要訪問的塊？若有的話如何確定其位置？

設(shè)置查找目錄表。目錄表共有M項，每一項對應(yīng)于Cache中的一個塊，用于指出當(dāng)前該塊中存放的信息是哪一個主存塊的（可能有多個主存塊映象到該Cache塊）。它實際上是記錄了該主存塊的塊地址的高位部分，稱為標(biāo)識（tag）。每個主存塊能唯一的由其標(biāo)識來確定。4.2Cache基本知識為了指出Cache中的塊是否包含有效信息，一般是在目錄表中給每一項設(shè)置一個有效位。例如，當(dāng)該位為“1”時表示該目錄表項有效，Cache中相應(yīng)塊所包含的信息有效。當(dāng)一個主存塊被調(diào)入Cache中某一個塊位置時，它的標(biāo)識就被填入到目錄表中與該Cache塊相對應(yīng)的項中，并且該項的有效位被置“1”。4.2Cache基本知識根據(jù)映象規(guī)則不同，一個主存塊可能映象到Cache中的一個或多個Cache塊位置。為便于討論，我們把它們稱為候選位置。當(dāng)CPU訪問該主存塊時，必須且只需查找它的候選位置所對應(yīng)的目錄表項（標(biāo)識）。如果有與所訪問的主存塊相同的標(biāo)識，且其有效位為“1”，則它所對應(yīng)的Cache塊即是所要找的塊。4.2Cache基本知識直接映象Cache的候選位置最少，只有一個；全相聯(lián)Cache的候選位置最多，為M個；而n路組相聯(lián)則介于兩者之間，為n個。4.2Cache基本知識◆并行查找與順序查找4.2Cache基本知識◆順序查找提高性能的方法：主候選位置(MRU塊)

前瞻執(zhí)行4.2Cache基本知識◆并行查找的實現(xiàn)方法：舉例：４路組相聯(lián)并行標(biāo)識比較（比較器的個數(shù)及位數(shù)）

相聯(lián)存儲器單體多字存儲器＋比較器4.2Cache基本知識主存塊地址：目錄表（標(biāo)識存儲器）4.2Cache基本知識4.2Cache基本知識4.2Cache基本知識4.2.3替換算法

所要解決的問題：當(dāng)要從主存調(diào)入一個塊到Cache中時，會出現(xiàn)該塊所映象到的一組（或一個）Cache塊已全被占用的情況。這時需強迫騰出其中的某一塊，以接納新調(diào)入的塊。那么應(yīng)該替換哪一塊？1.隨機法

為了均勻使用一組中的各塊，隨機地選擇被替換的塊。有些系統(tǒng)采用偽隨機數(shù)法產(chǎn)生塊號。

特點：實現(xiàn)簡單，但反映不了程序的局部性。2.先進(jìn)先出法（FIFO）

選擇最早調(diào)入的塊作為被替換的塊。

特點：容易實現(xiàn)。還是不能正確地反映程序的局部性。4.2Cache基本知識3.最近最少使用法（LRU）

選擇近期最少被訪問的塊作為被替換的塊。實際應(yīng)用中通常是選擇最久沒有被訪問過的塊作為被替換的塊。

特點：失效率低。能較好地反映程序的局部性原理。但LRU比較復(fù)雜，硬件實現(xiàn)比較困難，特別是當(dāng)組的大小增加時，LRU的實現(xiàn)代價會越來越高，而且經(jīng)常只能是近似的實現(xiàn)。4.2Cache基本知識表中的數(shù)據(jù)是對于一個VAX地址流（既包括用戶程序也包括操作系統(tǒng)程序）在塊大小為16B的情況下統(tǒng)計的。在這個例子中，對于大容量Cache，LRU和隨機法的失效率幾乎沒什么差別。4.2Cache基本知識4.2.4寫策略處理器對Cache的訪問主要是讀訪問，因此設(shè)計Cache要針對最經(jīng)常發(fā)生的“讀”進(jìn)行優(yōu)化。幸運的是，最經(jīng)常發(fā)生的“讀”也是最容易提高速度的。訪問Cache時，在讀出標(biāo)識進(jìn)行比較的同時，可以把相應(yīng)的Cache塊也讀出。如果命中，則把該塊中請求的數(shù)據(jù)立即送給CPU；若為失效，則所讀出的塊沒什么用處，但也沒什么壞處，置之不理就是了。4.2Cache基本知識“寫”在所有訪存操作中所占的比例統(tǒng)計結(jié)果表明，對于一組給定的程序：load指令：26％store指令：9％“寫”在所有訪存操作中所占的比例：

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

9％/(26％＋9％)≈25％取指令讀數(shù)據(jù)寫數(shù)據(jù)4.2Cache基本知識然而，對于“寫”卻不是如此。只有在讀出標(biāo)識并進(jìn)行比較，確認(rèn)是命中后，才可對Cache塊進(jìn)行寫入。由于檢查標(biāo)識不能與寫入Cache并行進(jìn)行，“寫”一般比“讀”花費更多的時間。另一個比較麻煩的地方是，處理器要寫入的數(shù)據(jù)的寬度不是定長的（通常為1~8B）。寫入時，只能修改Cache塊中相應(yīng)的部分，而“讀”則可以多讀出幾個字節(jié)也沒關(guān)系?！皩憽痹L問有可能導(dǎo)致Cache和主存內(nèi)容的不一致。顯然，為了保證正確性，主存的內(nèi)容也必須更新。至于何時更新，這正是寫策略要解決的問題。4.2Cache基本知識兩種寫策略寫策略是區(qū)分不同Cache設(shè)計方案的一個重要標(biāo)志。

◆寫直達(dá)法執(zhí)行“寫”操作時，不僅寫入Cache，而且

也寫入下一級存儲器。

◆寫回法執(zhí)行“寫”操作時，只寫入Cache。僅當(dāng)

Cache中相應(yīng)的塊被替換時，才寫回主存。

(設(shè)置“污染位”)4.2Cache基本知識兩種寫策略的比較

◆寫直達(dá)法的優(yōu)點：易于實現(xiàn)，一致性好。

◆寫回法的優(yōu)點：速度快，而且對于同一單元的多個寫最后只需一次寫回下一級存儲器，有些“寫”只到達(dá)Cache不到達(dá)主存，因而所使用的存儲器頻帶較低；4.2Cache基本知識寫緩沖器：采用寫直達(dá)法時，若在進(jìn)行“寫”操作的過程中CPU必須等待，直到“寫”操作結(jié)束，則稱CPU寫等待。減少寫等待的一種常用優(yōu)化技術(shù)是采用寫緩沖器，從而使下一級存儲器的更新和CPU的執(zhí)行重疊起來。4.2Cache基本知識寫策略與調(diào)塊

寫直達(dá)法──不按寫分配

寫回法──按寫分配“寫”操作時的調(diào)塊：由于“寫”訪問并不需要用到所訪問單元中原有的數(shù)據(jù)。所以，當(dāng)發(fā)生寫失效時，是否調(diào)入相應(yīng)的塊，有兩種選擇：◆按寫分配(寫時取)

寫失效時，先把所寫單元所在的塊調(diào)入

Cache，再行寫入。◆不按寫分配(繞寫法)

寫失效時，直接寫入下一級存儲器而不調(diào)塊。4.2Cache基本知識4.2.5Cache的結(jié)構(gòu)例子：DEC的AlphaAXP21064中的內(nèi)部數(shù)據(jù)Cache1.簡介

容量：8KB

塊大?。?2B

塊數(shù)：256

映象方法：直接映象

“寫”策略：寫直達(dá)采用不按寫分配寫緩沖器大?。?個塊4.2Cache基本知識2.結(jié)構(gòu)圖4.2Cache基本知識3.工作過程

◆

“讀”訪問命中4.2Cache基本知識◆

“寫”訪問命中4.2Cache基本知識◆失效情況下的操作發(fā)生讀失效時，Cache向CPU發(fā)出一個暫停信號，通知它等待，并從下一級存儲器中讀入32B數(shù)據(jù)。21064的Cache和它的下一級存儲器之間的數(shù)據(jù)通路為16B，每次數(shù)據(jù)傳送需5個時鐘周期，傳送全部32B數(shù)據(jù)要花10個時鐘周期。因為21064的數(shù)據(jù)Cache是直接映象的，所以被替換的塊只有一個，別無選擇。替換一個塊意味著更新該塊的數(shù)據(jù)、標(biāo)識和有效位。發(fā)生寫失效時，21064采用不按寫分配規(guī)則。也就是說Cache使數(shù)據(jù)“繞過”Cache，直接寫入主存。4.2Cache基本知識4.混合Cache與分離Cache

混合Cache：指令和數(shù)據(jù)混合Cache。 若流水線中同時請求一個數(shù)據(jù)字和一個指令字，會出現(xiàn)沖突，導(dǎo)致CPU等待。

分離Cache：分為指令Cache和數(shù)據(jù)Cache兩個Cache。 AlphaAXP21064有一個8KB的指令Cache，其結(jié)構(gòu)與8KB的數(shù)據(jù)Cache幾乎一樣。 CPU知道它發(fā)出的地址是指令地址還是數(shù)據(jù)地址，因此可以為它們設(shè)置不同的端口，這樣就會加倍對存儲系統(tǒng)和CPU之間數(shù)據(jù)通道帶寬的要求。由于系統(tǒng)對指令和數(shù)據(jù)的操作特性不同，獨立的指令Cache和數(shù)據(jù)Cache使我們能分別對它們進(jìn)行優(yōu)化，它們各自采用不同的容量、塊大小和相聯(lián)度時的性能可能會更好。4.2Cache基本知識16KB容量1KB2KB4KB8KB32KB指令Cache3.06%失效率的比較64KB128KB數(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%以上數(shù)據(jù)是在塊大小為32B、映象方法為直接映象的條件下，針對SPEC92典型程序，在DECstation5000上測出的平均值。對指令的訪問約占所有訪問的75%.4.2Cache基本知識分離Cache平均失效率的計算：訪問指令Cache的百分比×指令Cache的失效率＋訪問數(shù)據(jù)Cache的百分比×數(shù)據(jù)Cache的失效率4.2.6Cache性能分析失效率與硬件速度無關(guān)，用它來評價存儲系統(tǒng)的性能非常方便,所以經(jīng)常會用到它。容易產(chǎn)生一些誤導(dǎo)：一種更好的評測存儲系統(tǒng)性能的指標(biāo)是平均訪存時間。平均訪存時間平均訪存時間＝命中時間＋失效率×失效開銷4.2Cache基本知識例5.1

假設(shè)Cache的命中時間為1個時鐘周期，失效開銷為50個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期(因為混合Cache只有一個端口，無法同時滿足兩個請求。流水線中，混合Cache會導(dǎo)致結(jié)構(gòu)沖突)，根據(jù)上表所列的失效率，試問指令Cache和數(shù)據(jù)Cache容量均為16KB的分離Cache和容量為32KB的混合Cache相比，哪種Cache的失效率更低？又假設(shè)采用寫直達(dá)策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。請問上述兩種情況下平均訪存時間各是多少？4.2Cache基本知識解：

如前所述，約75%的訪存為取指令。因此，分離Cache的總體失效率為：(75%×0.64%)＋(25%×6.47%)＝2.10%根據(jù)前表，容量為32KB的混合Cache的失效率略低一些，只有1.99%.100%/（100%+26%+9%）=75%LoadStore4.2Cache基本知識平均訪存時間公式可以分為指令訪問和數(shù)據(jù)訪問兩部分：平均訪存時間＝指令所占的百分比×(指令命中時間＋指令失效率×失效開銷＋數(shù)據(jù)所占的百分比×(數(shù)據(jù)命中時間＋數(shù)據(jù)失效率×失效開銷)所以，兩種結(jié)構(gòu)的平均訪存時間分別為：平均訪存時間分離

＝75%×(1＋0.64%×50)＋25%×(1＋6.47%×50)

＝(75%×1.32)＋(25%×4.325)＝0.990＋1.059＝2.05平均訪存時間混合

＝75%×(1＋1.99%×50)＋25%×(1＋1＋1.99%×50)

＝(75%×1.995)＋(25%×2.995)＝1.496＋0.749＝2.24因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存時間反而較低。分離Cache提供了兩個端口，消除了結(jié)構(gòu)沖突。執(zhí)行一個程序所需要的CPU時間與Cache的性能密切相關(guān)。4.2Cache基本知識程序執(zhí)行時間CPU時間＝（CPU執(zhí)行周期數(shù)+存儲器停頓周期數(shù)）×?xí)r鐘周期時間其中：存儲器停頓時鐘周期數(shù)＝“讀”的次數(shù)×讀失效率×讀失效開銷＋“寫”的次數(shù)×寫失效率×寫失效開銷將讀/寫合并，并求出“讀”和“寫”的平均失效率和平均失效開銷，上式可化簡：存儲器停頓時鐘周期數(shù)＝訪存次數(shù)×失效率×失效開銷

4.2Cache基本知識例5.2我們用一個和AlphaAXP類似的機器作為第一個例子。假設(shè)Cache失效開銷為50個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期，訪問Cache失效率為2%，平均每條指令訪存1.33次。試分析Cache對性能的影響。解CPU時間＝IC×(CPIexe＋────────)

×?xí)r鐘周期時間存儲器停頓周期數(shù)指令數(shù)4.2Cache基本知識考慮Cache的失效后，性能為：

CPU時間有cache＝IC×（2.0＋1.33×2%×50）×?xí)r鐘周期時間＝IC×3.33×?xí)r鐘周期時間實際CPI：3.33

3.33/2.0=1.67(倍)

CPU時間也增加為原來的1.67倍。但若不采用Cache,則：

CPI＝2.0＋50×1.33＝68.54.2Cache基本知識Cache失效對于一個CPI較小而時鐘頻率較高的CPU來說，影響是雙重的：CPIexecution越低，固定周期數(shù)的Cache失效開銷的相對影響就越大。在計算CPI時，失效開銷的單位是時鐘周期數(shù)。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的失效開銷較大，其CPI中存儲器停頓這部分也就較大。因此Cache對于低CPI、高時鐘頻率的CPU來說更加重要。

4.2Cache基本知識例5.3考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象Cache和2路組相聯(lián)Cache，試問它們對CPU的性能有何影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設(shè)：(1)理想Cache（命中率為100%）情況下的CPI為2.0，時鐘周期為2ns，平均每條指令訪存1.3次。(2)兩種Cache容量均為64KB，塊大小都是32字節(jié)。(3)下圖說明，在組相聯(lián)Cache中，必須增加一個多路選擇器，用于根據(jù)標(biāo)識匹配結(jié)果從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。因為CPU的速度直接與Cache命中的速度緊密相關(guān)，所以對于組相聯(lián)Cache，由于多路選擇器的存在而使CPU的時鐘周期增加到原來的1.10倍。4.2Cache基本知識 (4)這兩種結(jié)構(gòu)Cache的失效開銷都是70ns。（在實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期）(5)命中時間為1個時鐘周期，64KB直接映象Cache的失效率為1.4%，相同容量的2路組相聯(lián)Cache的失效率為1.0%。4.2Cache基本知識4.2Cache基本知識

解

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

平均訪存時間1路＝2＋（0.014×70）＝2.98ns平均訪存時間2路＝2×1.10＋（0.010×70）＝2.90ns2路組相聯(lián)Cache的平均訪存時間比較低。

CPU時間＝IC×(CPIexe＋每條指令的平均存儲器

停頓周期數(shù))×?xí)r鐘周期時間

＝IC×(CPIexe×?xí)r鐘周期時間＋

每條指令的平均存儲器停頓時間)4.2Cache基本知識因此：CPU時間1路＝IC×(2.0×2＋(1.3×0.014×70))

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

＝5.31×IC5.31×ICCPU時間1路─────＝─────＝1.015.27×ICCPU時間2路和平均訪存時間的比較結(jié)果相反，直接映象Cache的平均性能好一些，這是因為在兩路組相聯(lián)的情況下，雖然失效次數(shù)減少了，但所有指令的時鐘周期時間都增加了10%。由于CPU時間是我們進(jìn)行評價的基準(zhǔn)，而且直接映象Cache實現(xiàn)更簡單，所以本例中直接映象Cache是較好的選擇。4.2Cache基本知識4.2.7改進(jìn)Cache的性能平均訪存時間＝命中時間＋失效率×失效開銷可以從三個方面改進(jìn)Cache的性能：降低失效率減少失效開銷減少Cache命中時間下面介紹17種Cache優(yōu)化技術(shù)8種用于降低失效率5種用于減少失效開銷4種用于減少命中時間4.2Cache基本知識寫緩沖合并第4章存儲層次4.3降低Cache失效率的方法三種失效(3C)強制性失效(Compulsorymiss)當(dāng)?shù)谝淮卧L問一個塊時，該塊不在Cache中，需從下一級存儲器中調(diào)入Cache，這就是強制性失效。

(冷啟動失效，首次訪問失效)容量失效(Capacitymiss)如果程序執(zhí)行時所需的塊不能全部調(diào)入Cache中，則當(dāng)某些塊被替換后，若又重新被訪問，就會發(fā)生失效。這種失效稱為容量失效。4.3降低Cache失效率的方法沖突失效(Conflictmiss)在組相聯(lián)或直接映象Cache中，若太多的塊映象到同一組(塊)中，則會出現(xiàn)該組中某個塊被別的塊替換(即使別的組或塊有空閑位置)，然后又被重新訪問的情況。這就是發(fā)生了沖突失效。(碰撞失效，干擾失效)三種失效所占的比例圖示I(絕對值)圖示Ⅱ(相對值)4.3降低Cache失效率的方法4.3降低Cache失效率的方法4.3降低Cache失效率的方法可以看出：相聯(lián)度越高，沖突失效就越少；強制性失效和容量失效不受相聯(lián)度的影響；強制性失效不受Cache容量的影響，但容量失效卻隨著容量的增加而減少；表中的數(shù)據(jù)符合2:1的Cache經(jīng)驗規(guī)則，即大小為N的直接映象Cache的失效率約等于大小為N/2的2路組相聯(lián)Cache的失效率。4.3降低Cache失效率的方法減少三種失效的方法強制性失效：增加塊大小，預(yù)?。ū旧砗苌伲┤萘渴В涸黾尤萘?/p>

（抖動現(xiàn)象）沖突失效：提高相聯(lián)度（理想情況：全相聯(lián)）許多降低失效率的方法會增加命中時間或失效開銷4.3降低Cache失效率的方法4.3.1增加Cache的容量降低cache失效率最直接的方法是增加Cache的容量缺點:增加成本可能增加命中時間這種方法在片外Cache中用得比較多

4.3降低Cache失效率的方法4.3.2增加Cache塊大小失效率與塊大小的關(guān)系對于給定的Cache容量，當(dāng)塊大小增加時，失效率開始是下降，后來反而上升了。原因：一方面它減少了強制性失效；另一方面，由于增加塊大小會減少Cache中塊的數(shù)目，所以有可能會增加沖突失效。

Cache容量越大，使失效率達(dá)到最低的塊大小就越大。4.3降低Cache失效率的方法4.3降低Cache失效率的方法各種塊大小情況下Cache的失效率

4.3降低Cache失效率的方法增加塊大小會增加失效開銷

例5.4假定存儲系統(tǒng)在延遲40個時鐘周期后，每2個時鐘周期能送出16個字節(jié)。即，經(jīng)過42個時鐘周期，它可提供16個字節(jié)；經(jīng)過44個時鐘周期，可提供32個字節(jié)；依此類推。請問對于上表中列出的各種容量的Cache，在塊大小分別為多少時，平均訪存時間最??？解：平均訪存時間=命中時間+失效率×失效開銷

假設(shè)命中時間與塊大小無關(guān)，為1個時鐘周期，那么對于一個塊大小為16B、容量為1KB的cache來說，平均訪存時間=1+（15.05%×42)=7.321

對于一個塊大小為256B、容量為256KB的cache來說，平均訪存時間=1+（0.49%×72)=1.3534.3降低Cache失效率的方法各種塊大小情況下Cache的平均訪存時間

4.3降低Cache失效率的方法Cache設(shè)計者一直在努力同時減少失效率和失效開銷。從失效開銷的角度來講，塊大小的選擇取決于下一級存儲器的延遲和帶寬兩個方面。高延遲和高帶寬時，宜采用較大的Cache塊，因為這時每次失效時，稍微增加一點失效開銷，就可以獲得許多數(shù)據(jù)。與之相反，低延遲和低帶寬時，宜采用較小的Cache塊，因為采用大Cache塊所能節(jié)省的時間不多。4.3降低Cache失效率的方法4.3.3提高相聯(lián)度采用相聯(lián)度超過8的方案的實際意義不大。2:1Cache經(jīng)驗規(guī)則容量為N的直接映象Cache的失效率和容量為N/2的2路組相聯(lián)Cache的失效率差不多相同。提高相聯(lián)度是以增加命中時間為代價。例如：2路組相聯(lián)比直接映像，采用TTL（晶體管-晶體管邏輯電路）或ECL（射極耦合邏輯電路）板級Cache命中時間增加10％，若采用定制的CMOS（互補型金屬氧化物半導(dǎo)體電路）Cache,增加2％4.3降低Cache失效率的方法例5.5假定提高相聯(lián)度會按下列比例增大處理器時鐘周期：時鐘周期2路＝1.10×?xí)r鐘周期1路時鐘周期4路＝1.12×?xí)r鐘周期1路時鐘周期8路＝1.14×?xí)r鐘周期1路假定命中時間為一個時鐘周期，失效開銷為50個時鐘周期，使用表5.5中的失效率，試問當(dāng)Cache為多大時，以下不等式成立？平均訪存時間8路<平均訪存時間4路平均訪存時間4路<平均訪存時間2路平均訪存時間2路<平均訪存時間1路

4.3降低Cache失效率的方法解在各種相聯(lián)度的情況下，平均訪存時間分別為：平均訪存時間8路=命中時間8路+失效率8路×失效開銷8路

=1.14＋失效率8路×50平均訪存時間4路=1.12＋失效率4路×50平均訪存時間2路=1.10＋失效率2路×50平均訪存時間1路=1.00＋失效率1路×50把相應(yīng)的失效率代入上式，即可得平均訪存時間。例如，1KB的直接映象Cache的平均訪存時間為：平均訪存時間1路=1.00＋0.133×50＝7.65

128KB的8路組相聯(lián)Cache的平均訪存時間為：

平均訪存時間8路＝1.14＋0.006×50＝1.444.3降低Cache失效率的方法在各種容量和相聯(lián)度情況下Cache的平均訪存時間4.3降低Cache失效率的方法當(dāng)Cache容量不超過16KB時，上述三個不等式成立。從32KB開始，對于平均訪存時間有：4路組相聯(lián)的平均訪存時間小于2路組相聯(lián)的;2路組相聯(lián)的小于直接映象的;但8路組相聯(lián)的卻比4路組相聯(lián)的大。4.3降低Cache失效率的方法4.3.4VictimCache一種能減少沖突失效次數(shù)而又不影響時鐘頻率的方法。基本思想在Cache和它從下一級存儲器調(diào)數(shù)據(jù)的通路之間設(shè)置一個全相聯(lián)的小Cache，用于存放被替換出去的塊(稱為Victim)，以備重用。4.3降低Cache失效率的方法每當(dāng)發(fā)生失效時，在訪問下一級存儲器之前，先檢查VictimCache中是否含有所需的塊。如果有，就將該塊與Cache中某個塊做交換。VictimCache在存儲層次中的位置

4.3降低Cache失效率的方法作用對于減小沖突失效很有效，特別是對于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。例如項數(shù)為4的VictimCache:能使4

KB

Cache的沖突失效減少20%～90%874.3降低Cache失效率的方法4.3.5偽相聯(lián)Cache多路組相聯(lián)的低失效率和直接映象的命中速度優(yōu)點缺點直接映象組相聯(lián)命中時間小命中時間大失效率高失效率低偽相聯(lián)Cache的優(yōu)點命中時間小失效率低4.3降低Cache失效率的方法基本思想及工作原理在邏輯上把直接映象Cache的空間上下平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián)Cache先按直接映象Cache的方式去處理。若命中，則其訪問過程與直接映象Cache的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下一級存儲器。快速命中與慢速命中要保證絕大多數(shù)命中都是快速命中。4.3降低Cache失效率的方法4.3降低Cache失效率的方法例5.6假設(shè)當(dāng)在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配，而在另一個位置才找到數(shù)據(jù)（偽命中）需要2個額外的周期。仍用上個例子中的數(shù)據(jù)，問：當(dāng)Cache容量分別為2KB和128KB時，直接映象、2路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度最快？解首先考慮標(biāo)準(zhǔn)的平均訪存時間公式：

平均訪存時間偽相聯(lián)

＝命中時間偽相聯(lián)＋失效率偽相聯(lián)×失效開銷偽相聯(lián)4.3降低Cache失效率的方法由于：

失效率偽相聯(lián)＝失效率2路命中時間偽相聯(lián)＝命中時間1路＋偽命中率偽相聯(lián)×2偽相聯(lián)查找的命中率等于2路組相聯(lián)Cache的命中率和直接映象Cache命中率之差。

偽命中率偽相聯(lián)＝命中率2路－命中率1路＝（1－失效率2路）－（1－失效率1路）＝失效率1路－失效率2路綜合上述分析，有：平均訪存時間偽相聯(lián)＝命中時間1路＋（失效率1路－失效率2路）×2＋失效率2路×失效開銷1路4.3降低Cache失效率的方法將前面表中的數(shù)據(jù)代入上面的公式，得：

平均訪存時間偽相聯(lián)，2KB

＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844平均訪存時間偽相聯(lián)，128KB

＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356根據(jù)上一個例子中的表，對于2KBCache，可得：

平均訪存時間1路＝5.90個時鐘平均訪存時間2路＝4.90個時鐘4.3降低Cache失效率的方法對于128KB的Cache有，可得：

平均訪存時間1路＝1.50個時鐘平均訪存時間2路＝1.45個時鐘可見，對于這兩種Cache容量，偽相聯(lián)Cache都是速度最快的。缺點：多種命中時間使流水線設(shè)計更復(fù)雜化。4.3降低Cache失效率的方法4.3.6硬件預(yù)取指令和數(shù)據(jù)都可以預(yù)取預(yù)取內(nèi)容既可放入Cache，也可放在速度比主存快的外緩沖器中。例如：指令流緩沖器指令預(yù)取通常由Cache之外的硬件完成4.3降低Cache失效率的方法以AlphaAXP21064為例，在發(fā)生指令失效時取兩個塊：被請求指令塊和順序的下一指令塊。被請求指令塊返回時放入Cache，而預(yù)取指令塊則放在緩沖器中；如果某次被請求的指令塊正好在緩沖器里，則取消對該塊的訪存請求，直接從緩沖器中讀出這一塊，同時發(fā)出對下一指令塊的預(yù)取方寸請求。Joppi的研究結(jié)果指令預(yù)取(4KB，直接映象Cache，塊大?。?6B)1個塊的指令流緩沖器：捕獲15％～25％的失效4個塊的指令流緩沖器：捕獲50％16個塊的指令流緩沖器：捕獲72％4.3降低Cache失效率的方法數(shù)據(jù)預(yù)取(4KB,直接映象Cache)1個數(shù)據(jù)流緩沖器：捕獲25％的失效還可以采用多個數(shù)據(jù)流緩沖器，分別從不同的地址預(yù)取數(shù)據(jù)。Jouppi發(fā)現(xiàn)，用4個數(shù)據(jù)流緩沖器可以將命中率提高到43%Palacharla和Kessler的研究結(jié)果流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)對于兩個64KB四路組相聯(lián)Cache來說：8個流緩沖器能捕獲50％～70％的失效4.3降低Cache失效率的方法例5.7AlphaAXP21064采用指令預(yù)取技術(shù)，其實際失效率是多少？若不采用指令預(yù)取技術(shù)，AlphaAXP21064的指令Cache必須為多大才能保持平均訪存時間不變？

解

假設(shè)當(dāng)指令不在指令Cache里，而在預(yù)取緩沖器中找到時，需要多花一個時鐘周期。下面是修改后的公式：平均訪存時間預(yù)?。矫袝r間＋失效率×預(yù)取命中率×1＋失效率×（1－預(yù)取命中率）×失效開銷4.3降低Cache失效率的方法假設(shè)預(yù)取命中率為25%，命中時間為2個時鐘周期，失效開銷為50個時鐘周期。查表可知8KB指令Cache的失效率為1.10%。則：

平均訪存時間預(yù)取

＝2＋（1.10%×25%×1）＋1.10%×（1－25%）×50＝2＋0.00275＋0.413＝2.415為了得到相同性能下的實際失效率，由原始公式得：

平均訪存時間＝命中時間＋失效率×失效開銷失效率＝（平均訪存時間－命中時間）/失效開銷＝（2.415－2）/50＝0.83%介于普通8KBcache的失效率1.10%和16KBcache的失效率0.63%之間。4.3降低Cache失效率的方法4.3.7編譯器控制的預(yù)取在編譯時加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請求。預(yù)取有以下幾種類型：寄存器預(yù)取：把數(shù)據(jù)取到寄存器中。Cache預(yù)取：只將數(shù)據(jù)取到Cache中。這兩種預(yù)取可以是故障性的,也可是非故障性的。故障性預(yù)?。涸陬A(yù)取時，若出現(xiàn)虛地址故障或違反保護(hù)權(quán)限，就會發(fā)生異常。非故障性預(yù)?。涸谟龅竭@種情況時則不會發(fā)生異常，因為這時它會放棄預(yù)取，轉(zhuǎn)變?yōu)榭詹僮鳌?.3降低Cache失效率的方法本節(jié)假定Cache預(yù)取都是非故障性的，也稱非綁定預(yù)取。在預(yù)取數(shù)據(jù)的同時，處理器應(yīng)能繼續(xù)執(zhí)行。只有這樣，預(yù)取才有意義。非阻塞Cache(非鎖定Cache)：要求cache在等待預(yù)取數(shù)據(jù)返回的同時,還能繼續(xù)提供指令和數(shù)據(jù)。

編譯器控制預(yù)取的目的使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。循環(huán)是預(yù)取優(yōu)化的主要對象，因為它易于進(jìn)行預(yù)取優(yōu)化。失效開銷小時：循環(huán)體展開1～2次，并調(diào)度好預(yù)取和執(zhí)行的重疊失效開銷大時：循環(huán)體展開許多次4.3降低Cache失效率的方法

例5.8對于下面的程序，首先判斷哪些訪問可能會導(dǎo)致數(shù)據(jù)Cache失效。然后，加入預(yù)取指令以減少失效。最后，計算所執(zhí)行的預(yù)取指令的條數(shù)以及通過預(yù)取避免的失效次數(shù)。假定：(1)我們用的是一個容量為8KB、塊大小為16

B的直接映象Cache，它采用寫回法并且按寫分配。(2)a、b分別為3×100（3行100列）和101×3的雙精度浮點數(shù)組，每個元素都是8

B。當(dāng)程序開始執(zhí)行時，這些數(shù)據(jù)都不在Cache內(nèi)。for（i=0;i<3;i=i+1） for（j=0;j<100;j=j+1）a[i][j]=b[j][0]*b[j+1][0];

4.3降低Cache失效率的方法4.3降低Cache失效率的方法當(dāng)沒有預(yù)取功能時，對數(shù)組a中元素的寫操作是按照他們在主存中的存放順序進(jìn)行的。由于每一塊含兩個元素，當(dāng)j為偶數(shù)是第一次訪問一個塊，為奇數(shù)時是第二次，因此j為偶數(shù)失效，j為奇數(shù)命中。4.3降低Cache失效率的方法4.3降低Cache失效率的方法因此，在沒有預(yù)取功能時，這個循環(huán)一共將引起150+101=251次數(shù)據(jù)Cache失效。優(yōu)化措施：將循環(huán)分解，使得在第一次循環(huán)中不僅預(yù)取a，而且預(yù)取b，而在第二次循環(huán)中只預(yù)取a，因為此時b早已經(jīng)被預(yù)取了。假設(shè)失效開銷很大，預(yù)取必須至少提前7次循環(huán)進(jìn)行。4.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）*/

a[0][j]=b[j][0]*b[j+1][0];}for（i=1;i<3;i=i+1）{for（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];}4.3降低Cache失效率的方法優(yōu)化后的程序預(yù)取了數(shù)據(jù)：a[i][7]~a[i][99],[7][0]~b[100][0]。失效情況為：第一次循環(huán)中訪問a[0][0]~a[0][6]時失效[7/2]=4，訪問b[0][0]~b[6][0]時失效7次；第二、三次循環(huán)中訪問a[i][0]~a[i][6]時失效[7/2]×2=8次。故，總的失效次數(shù)減少為：4+7+8=19次由此結(jié)果可知，避免232次失效，其代價是執(zhí)行了400條預(yù)取指令，這可能是一個很好的折中。4.3降低Cache失效率的方法例5.9在以下條件下，計算例5.8中所節(jié)約的時間：(1)忽略指令Cache失效，并假設(shè)數(shù)據(jù)Cache無沖突失效和容量失效。(2)假設(shè)預(yù)取可以被重疊或與Cache失效重疊執(zhí)行，從而能以最大的存儲帶寬傳送數(shù)據(jù)。(3)不考慮Cache失效時，修改前的循環(huán)每7個時鐘周期循環(huán)一次。修改后的程序中，第一個預(yù)取循環(huán)每9個時鐘周期循環(huán)一次，而第二個預(yù)取循環(huán)每8個時鐘周期循環(huán)一次（包括外層for循環(huán)的開銷）。(4)一次失效需50個時鐘周期。4.3降低Cache失效率的方法解修改前：雙重循環(huán)一共執(zhí)行了3×100次循環(huán)，每次用7個時鐘周期，循環(huán)時間＝300×7＝2100失效開銷＝251×50＝125502100＋12550＝14650修改后：循環(huán)時間＝100×9＋200×8＝2500失效時間＝19×50＝9502500＋950＝3450

加速比＝14650/3450＝4.24.3降低Cache失效率的方法4.3.8編譯器變化基本思想在編譯時，對程序中的指令和數(shù)據(jù)進(jìn)行重新組織，以降低Cache失效率。McFaring發(fā)現(xiàn)：通過對指令進(jìn)行重新排序，可有效地降低指令Cache的失效率。2KBCache:降低50％8KBCache：降低75%數(shù)據(jù)對存儲位置的限制比指令的少，因此更便于優(yōu)化。通過把數(shù)據(jù)重新組織，使得一塊數(shù)據(jù)在被從Cache替換出去之前，能最大限度利用其中的數(shù)據(jù)(訪問次數(shù)最多)。4.3降低Cache失效率的方法數(shù)組合并這種技術(shù)通過提高空間局部性來減少失效次數(shù)。有些程序同時用相同的索引來訪問若干數(shù)組的同一維。這些訪問可能會相互干擾，導(dǎo)致沖突失效?？梢酝ㄟ^組成復(fù)合數(shù)組，使得一個Cache塊中能包含全部所需的元素。舉例：

/*修改前*/

int

val[SIZE];

intkey[SIZE];/*修改后*/structmerge{intval;intkey;};structmergemerged_array[SIZE];4.3降低Cache失效率的方法內(nèi)外循環(huán)交換

只要簡單地交換循環(huán)的嵌套關(guān)系就能使程序按數(shù)據(jù)在存儲器中存儲的順序進(jìn)行訪問。也是通過提高空間局部性來減少失效次數(shù)。

舉例：

/*修改前*/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];4.3降低Cache失效率的方法循環(huán)融合

將多個獨立的循環(huán)融合為單一的循環(huán)，能使讀入Cache的數(shù)據(jù)在被替換出去之前，得到反復(fù)的使用。這是通過改進(jìn)時間局部性來減少失效次數(shù)。

/*修改前*/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=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];}4.3降低Cache失效率的方法分塊這種優(yōu)化可能是cache優(yōu)化技術(shù)中最著名的一種,它也是通過改進(jìn)時間局部性來減少失效。分塊算法不是對數(shù)組的整行或整列進(jìn)行訪問，而是對子矩陣或塊進(jìn)行操作。把對數(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;}（失效次數(shù)—最壞的情況下：2N3＋N2）4.3降低Cache失效率的方法兩個內(nèi)部循環(huán)讀取了數(shù)組z的全部N×N個元素，并反復(fù)讀取數(shù)組y的某一行的N個元素，所產(chǎn)生的N個結(jié)果被寫入數(shù)組x的某一行。4.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,N）;j=j+1）{ r=0; for（k=kk;k<min（kk+B,N）;k=k+1） {r=r+y[i][k]*z[k][j];} x[i][j]=x[i][j]+r; }

(失效次數(shù)：2N3/B＋N2)為了保證正在訪問的元素能在Cache中命中，把原程序改為只對大小為B×B的子數(shù)組進(jìn)行計算，B稱為分塊因子。4.3降低Cache失效率的方法第4章存儲層次4.4減少Cache失效開銷隨著技術(shù)的發(fā)展，處理器速度的提高要快于DRAM速度的提高，這使得Cache失效開銷的相對代價隨時間不斷增加。讓讀失效優(yōu)先于寫寫緩沖合并請求字處理技術(shù)非阻塞Cache技術(shù)采用兩級Cache4.4減少Cache失效開銷4.4.1讓讀失效優(yōu)先于寫提高寫直達(dá)Cache性能最重要的方法是使用一個大小適中的寫緩沖器。然而，寫緩沖器卻導(dǎo)致對存儲器的訪問復(fù)雜化了，因為在讀失效時，寫緩沖器中可能保存所讀單元的最新值。例5.10

考慮以下指令序列：

SWR3,512（R0）；M[512]←R3（Cache索引為0）

LWR1,1024（R0）；R1←M[1024]（Cache索引為0）

LWR2,512（R0）；R2←M[512]（Cache索引為0）

假設(shè)cache采用寫直達(dá)法和直接映象，并且地址512和1024映射到同一塊，寫緩沖器為4個字，試問寄存器R2的值總是等于R3的值嗎？4.4減少Cache失效開銷在執(zhí)行Store指令之后，R3的值被寫入緩沖器，接下來的第一條Load指令使用相同的Cache索引，因而產(chǎn)生一次失效。第二條Load指令欲把地址為512的存儲單元的值讀入寄存器R2中，這也會造成失效。如果此時寫緩沖器還未將數(shù)據(jù)寫入存儲單元512中，第二條Load指令讀入錯誤值。如果不采取適當(dāng)?shù)念A(yù)防措施，R2的值不會等于R3的值。4.4減少Cache失效開銷解決問題的方法(讀失效的處理)推遲對讀失效的處理，直到寫緩沖器清空。（缺點：讀失效的開銷增加，如50％）在讀失效時檢查寫緩沖器中的內(nèi)容，如果沒有沖突而且存儲器可訪問就可繼續(xù)處理讀失效。在寫回法Cache中，也可采用寫緩沖器。假定讀失效將替換一個“臟”的存儲塊，我們可以不像往常那樣先把“臟”塊寫回存儲器，然后在讀存儲器，而是先把被替換的“臟”塊拷入一個緩沖器，然后讀存儲器，最后再寫存儲器。這樣CPU的讀訪問就能更快地完成。和上面的情況類似，發(fā)生讀失效時，處理器既可以采用等待緩沖區(qū)清空的方法，也可以采用檢查緩沖區(qū)中各字的地址是否有沖突的方法。4.4減少Cache失效開銷4.4.2寫緩沖合并該項技術(shù)是提高寫緩沖器的效率寫直達(dá)Cache是依靠寫緩沖來提高完成對下一級存儲器的寫操作的時間。如果寫緩沖器為空，就把數(shù)據(jù)和相應(yīng)地址寫入該緩沖器。從CPU的角度來看，該寫操作就算完成了。4.4減少Cache失效開銷如果寫緩沖器中已經(jīng)有了待寫入的數(shù)據(jù)，就要把這次的寫入地址與寫緩沖器中已有的所有地址進(jìn)行比較，看是否有匹配的項。如果有地址匹配而對應(yīng)的位置又是空閑的，就把這次要寫入的數(shù)據(jù)與該項合并。這就叫寫緩沖合并。如果寫緩沖器滿且又沒有能進(jìn)行寫合并的項，就必須等待。

提高了寫緩沖器的空間利用率，而且還能減少因?qū)懢彌_器滿而要進(jìn)行的等待時間。4.4減少Cache失效開銷4.4減少Cache失效開銷4.4.3請求字處理技術(shù)請求字

從下一級存儲器調(diào)入Cache的塊中，往往只有一個字是立即需要的。這個字稱為請求字。應(yīng)盡早把請求字發(fā)送給CPU盡早重啟動：調(diào)塊時，從塊的起始位置開始讀起。一旦請求字到達(dá)，就立即發(fā)送給CPU，讓CPU繼續(xù)執(zhí)行。請求字優(yōu)先：調(diào)塊時，從請求字所在的位置讀起。這樣，第一個讀出的字便是請求字。將之立即發(fā)送給CPU。4.4減少Cache失效開銷一般說來，這些技術(shù)僅當(dāng)Cache塊很大時才有效。因為，Cache塊較小時，用不用這些技術(shù)，失效開銷差別不大。此外，在采用請求字優(yōu)先時，若下一條指令正好訪問Cache塊的另一部分（以請求字為界，Cache被分為上下兩部分。請求字屬于其中一部分），則只能節(jié)省一個時鐘周期，因為只有得到請求字的指令在流水線中可以前進(jìn)，下一條指令必須停下來等待所需的數(shù)據(jù)。4.4減少Cache失效開銷4.4.4非阻塞Cache技術(shù)采用盡早重啟動技術(shù)時，CPU在繼續(xù)執(zhí)行之前，仍需等待請求字到達(dá)。有些流水方式的機器允許指令亂序執(zhí)行（后面的指令可以跨越前面的指令先執(zhí)行），CPU無須在Cache失效時停頓。非阻塞Cache：Cache失效時仍允許CPU進(jìn)行其他的命中訪問。即允許“失效下命中”。這種“失效下命中”的優(yōu)化措施在Cache失效時，不是完全拒絕CPU的訪問，而是能處理部分訪問，從而減少了實際失效開銷。4.4減少Cache失效開銷如果更進(jìn)一步，讓Cache允許多個失效重疊，即支持“多重失效下的命中”和“失效下的失效”，則可進(jìn)一步減少實際失效開銷。（此種方法的前提是：存儲器必須能夠處理多個失效）可以同時處理的失效個數(shù)越多，所能帶來的性能上的提高就越大。下圖給出了對于不同的重疊失效個數(shù)，數(shù)據(jù)Cache的平均存儲器等待時間（以周期為單位）與阻塞Cache平均存儲器等待時間的比值。所考慮的Cache采用直接映像，容量為8kB，塊大小為32B。測試程序為18個SPEC92程序。前14個測試程序為浮點程序，后4個為整數(shù)程序。4.4減少Cache失效開銷4.4減少Cache失效開銷例5.11對于上圖描述的Cache，在2路組相聯(lián)和“一次失效下命中”這兩種措施中，哪一種對浮點程序更重要？對整數(shù)程序的情況如何？假設(shè)8KB數(shù)據(jù)Cache的平均失效率為：對于浮點程序，直接映象Cache為11.4%，而2路組相聯(lián)Cache為10.7%；對于整數(shù)程序，直接映象Cache為7.4%，2路組相聯(lián)Cache為6.0%。并且假設(shè)平均存儲器等待時間是失效率和失效開銷的積，失效開銷為16個時鐘周期。4.4減少Cache失效開銷解對于浮點程序，平均存儲器等待時間為：失效率直接映象×失效開銷＝11.4%×16＝1.84失效率2路組相聯(lián)×失效開銷＝10.7%×16＝1.71

1.71/1.84≈0.93即2路組相聯(lián)映像cache的平均存儲器等待時間是直接映像Cache的93%，而支持“一次失效下命中”技術(shù)的直接映像Cache的平均存儲器等待時間是直接映像Cache的76%。4.4減少Cache失效開銷對于整數(shù)程序：失效率直接映象×失效開銷＝7.4%×16＝1.18失效率2路組相聯(lián)×失效開銷＝6.0%×16＝0.96

0.96/1.18≈0.81“一次失效下的命中”也是81%，二者一樣。失效下命中”方法有一個潛在優(yōu)點：它不會影響命中時間，而組相聯(lián)卻會。4.4減少Cache失效開銷4.4.5采用兩級Cache應(yīng)把Cache做得更快？還是更大？答案：二者兼顧，再增加一級Cache第一級Cache(L1)小而快第二級Cache(L2)容量大性能分析平均訪存時間＝命中時間L1＋失效率L1×失效開銷L1失效開銷L1

＝命中時間L2＋失效率L2×失效開銷L2平均訪存時間＝命中時間L1＋失效率L1×

（命中時間L2＋失效率L2×失效開銷L2）在這個公式里，第二級Cache的失效率是以在第一級Cache中不命中而到達(dá)第二級Cache的訪存次數(shù)為分母來計算的。為避免二義性，對于二級Cache系統(tǒng)的失效率分兩種：4.4減少Cache失效開銷局部失效率與全局失效率局部失效率＝該級Cache的失效次數(shù)/到達(dá)該級

Cache的訪問次數(shù)例如：上述式子中的失效率L2全局失效率＝該級Cache的失效次數(shù)/CPU發(fā)出的訪存的總次數(shù)全局失效率L2＝失效率L1×失效率L2

評價第二級Cache時，應(yīng)使用全局失效率這個指標(biāo)。它指出了在CPU發(fā)出的訪存中，究竟有多大比例是穿過各級Cache，最終到達(dá)存儲器的。4.4減少Cache失效開銷例5.12假設(shè)在1000次訪存中，第一級Cache失效40次，第二級Cache失效20次。試問：在這種情況下，該Cache系統(tǒng)的局部失效率和全局失效率各是多少？

解第一級Cache的失效率（全局和局部）是40/1000，即4%；第二級Cache的局部失效率是20/40，即50%；第二級Cache的全局失效率是20/1000，即2%。4.4減少Cache失效開銷對于第二級Cache，我們有以下結(jié)論：在第二級Cache比第一級Cache大得多的情況下，兩級Cache的全局失效率和容量與第二級Cache相同的單級Cache的失效率非常接近。局部失效率不是衡量第二級Cache的一個好指標(biāo)，因此，在評價第二級Cache時，應(yīng)用全局失效率這個指標(biāo)。4.4減少Cache失效開銷第一級Cache和第二級Cache之間的首要區(qū)別是第一級Cache的速度會影響CPU的時鐘頻率，而第二級Cache的速度只影響第一級Cache的失效開銷。第二級Cache不會影響CPU的時鐘頻率，因此其設(shè)計有更大的考慮空間。第二級Cache設(shè)計時有兩個問題：它能否降低CPI中的平均訪存時間部分？它的成本是多少？4.4減少Cache失效開銷第二級Cache的參數(shù)容量因為第一級Cache中的所有信息都會出現(xiàn)在第二級Cache中，第二級Cache的容量一般比第一級的大許多。如果第二級Cache只是稍大一點，局部失效率將很高。如512KB，1024KB相聯(lián)度第二級Cache可采用較高的相聯(lián)度或偽相聯(lián)方法。4.4減少Cache失效開銷例5.13給出有關(guān)第二級Cache的以下數(shù)據(jù)：（1）2路組相聯(lián)使命中時間增加10%×CPU時鐘周期