1、n第第4章章 存儲層次存儲層次n4.1 存儲器的層次結構存儲器的層次結構n4.2 Cache基本知識基本知識n4.3 降低降低Cache失效率的方法失效率的方法n4.4 減少減少Cache失效開銷失效開銷n4.5 減少命中時間減少命中時間n4.6 主存主存n4.7 虛擬存儲器虛擬存儲器n4.8 進程保護進程保護n4.9 Intel Core i7中的存儲器層次結構中的存儲器層次結構計算機系統結構計算機系統結構第第4章章 存儲層次存儲層次n4.1 存儲器的層次結構存儲器的層次結構n4.1.1 從單級存儲器到多級存儲器從單級存儲器到多級存儲器1. 1. 從用戶的角度來看，存儲器的三個主要指標是：從

2、用戶的角度來看，存儲器的三個主要指標是： 容量，速度，價格容量，速度，價格( (每位價格每位價格) )2. 2. 人們對這三個指標的期望人們對這三個指標的期望: :容量大，速度快，價格低容量大，速度快，價格低3. 3. 這三個指標相互矛盾這三個指標相互矛盾如：如：速度越高，價格越高；容量越大，價格越低；速度越高，價格越高；容量越大，價格越低；容量越大，速度越慢。容量越大，速度越慢。4. 4. 解決方法解決方法 采用多種存儲器技術，構成存儲層次。采用多種存儲器技術，構成存儲層次。4.1 存儲器的層次結構存儲器的層次結構lM1-Mn：用不同技術實現的存儲器l它們之間以塊或頁面為單位傳送數據，lM1

3、離CPU最近，容量最小，每位價格最高。lMn離CPU最遠，容量最大，每位價格最低。l考慮相鄰的兩級，靠近CPU的一級總是容量小一些，速度快一些，價格高一些。4.1 存儲器的層次結構存儲器的層次結構n整個系統的目標：從整個系統的目標：從CPU看去，這個存儲器系統的速度看去，這個存儲器系統的速度接近于接近于M1的，而容量和價格則接近于的，而容量和價格則接近于Mn。n須做到：存儲器越靠近須做到：存儲器越靠近CPU，CPU對它的訪問頻率越高對它的訪問頻率越高。大多數訪問都能在。大多數訪問都能在M1完成（根據局部性原理）。完成（根據局部性原理）。n任何一級存儲器中的內容一般都是其下一層存儲器中內任何一級

4、存儲器中的內容一般都是其下一層存儲器中內容的子集。當容的子集。當CPU訪存時，首先是訪問訪存時，首先是訪問M1，若找到數據，若找到數據，則訪問結束。若沒有找到，就需要訪問，則訪問結束。若沒有找到，就需要訪問M2，將包含所，將包含所需數據的塊（或頁面）調入需數據的塊（或頁面）調入M1。若。若M2中還沒有找到，中還沒有找到，就需訪問就需訪問M3，以此類推。，以此類推。n小容量存儲器：速度高，價格也高。大容量存儲器：速小容量存儲器：速度高，價格也高。大容量存儲器：速度低，價格也低。度低，價格也低。n高性能要求存儲器速度高，實際應用要求存儲器容量大高性能要求存儲器速度高，實際應用要求存儲器容量大，互相

5、矛盾。怎么辦？現代計算機一般采用存儲層次。，互相矛盾。怎么辦？現代計算機一般采用存儲層次。4.1 存儲器的層次結構存儲器的層次結構n頂層包含最常用的信息。頂層包含最常用的信息。n任何一層中包含的信息，都是其下一層中信息的一個副本。任何一層中包含的信息，都是其下一層中信息的一個副本。nCPU訪問存儲器時，若在訪問存儲器時，若在Cache中沒找到所要的信息，就從中沒找到所要的信息，就從下一層中調入。下一層中調入。4.1 存儲器的層次結構存儲器的層次結構n4.1.2 存儲層次的性能參數存儲層次的性能參數每位價格每位價格C C，命中率，命中率H H，平均訪問時間，平均訪問時間T TA A假設：假設：S

6、 S 容量容量 T TA A 訪問時間訪問時間 C C 每位價格每位價格下面僅考慮由下面僅考慮由M M1 1和和M M2 2構成的兩級存儲層次：構成的兩級存儲層次：M M1 1的參數：的參數：S S1 1，T TA1A1，C C1 1 M M2 2的參數：的參數：S S2 2，T TA2A2，C C2 21.1. 每位價格每位價格C C C CC C1 1S S1 1C C2 2S S2 2S S1 1S S2 2顯然，當顯然，當S1 S2時，時，C C24.1 存儲器的層次結構存儲器的層次結構2. 2. 命中率命中率 H H 和失效率和失效率 F F命中率為命中率為CPU訪問存儲系統時，在訪

7、問存儲系統時，在M1中找到所需信息中找到所需信息的概率。的概率。 命中率一般用模擬的方法來確定，也就是通過模擬一命中率一般用模擬的方法來確定，也就是通過模擬一組有代表性的程序，分別記錄下訪問組有代表性的程序，分別記錄下訪問M M1 1和和M M2 2的次數的次數N N1 1和和N N2 2，則，則H HN N1 1/(/(N N1 1N N2 2) )N N1 1 訪問訪問M M1 1的次數的次數N N2 2 訪問訪問M M2 2的次數的次數 失效率失效率 F F1 1H H4.1 存儲器的層次結構存儲器的層次結構3. 3. 平均訪問時間平均訪問時間 T TA A分兩種情況來考慮分兩種情況來考

8、慮CPUCPU的一次訪存：的一次訪存：n當命中時，訪問時間即為當命中時，訪問時間即為T TA1A1，所以，所以T TA1A1常稱為命中時間。常稱為命中時間。n不命中時，情況比較復雜。在大多數兩級存儲層次中，若不命中時，情況比較復雜。在大多數兩級存儲層次中，若訪問的字不在訪問的字不在M M1 1中，就必須從中，就必須從M M2 2把所請求的字的信息塊傳把所請求的字的信息塊傳送到送到M M1 1，之后，之后CPUCPU才可在才可在M M1 1中訪問到這個字。假設傳遞一中訪問到這個字。假設傳遞一個信息塊所需的時間為個信息塊所需的時間為T TB B, ,則不命中的訪問時間為則不命中的訪問時間為T TA

9、2A2+T+TB B+T+TA1A1=T=TA1A1+T+TM M 其中，其中，T TM M=T=TA2A2+T+TB B，它是從向，它是從向M M2 2發出訪問請求到把整個數據塊調發出訪問請求到把整個數據塊調入入M M1 1中所需的時間。中所需的時間。T TM M常稱為常稱為失效開銷失效開銷。根據以上分析可知根據以上分析可知 T TA AHTHTA1A1(1(1H )(TA1+TH )(TA1+TM M) )T TA1A1(1(1H )TH )TM M 或或 T TA AT TA1A1F TF TM M 4.1 存儲器的層次結構存儲器的層次結構n4.1.3 “Cache主存主存”和和“主存輔

10、存主存輔存”層次層次n從主存的角度來看從主存的角度來看 “CacheCache主存主存”層次：彌補主存速度的不足層次：彌補主存速度的不足 “主存輔存主存輔存”層次：層次： 彌補主存容量的不足彌補主存容量的不足1. 1. “CacheCache主存主存”層次層次 主存與主存與CPUCPU的速度差距的速度差距4.1 存儲器的層次結構存儲器的層次結構4.1 存儲器的層次結構存儲器的層次結構4.1 存儲器的層次結構存儲器的層次結構3. “3. “主存輔存主存輔存”層次層次4.1 存儲器的層次結構存儲器的層次結構存儲層次存儲層次CPU對第二級的對第二級的訪問方式訪問方式比較項目比較項目目的目的存儲管理實

11、現存儲管理實現 訪問速度的比值訪問速度的比值(第一級和第二級第一級和第二級)典型的塊典型的塊(頁頁)大小大小失效時失效時CPU是否切換是否切換“Cache 主存主存”層次層次“主存輔存主存輔存”層次層次為了彌補主存速度的不足為了彌補主存速度的不足 為了彌補主存容量的不足為了彌補主存容量的不足主要由專用硬件實現主要由專用硬件實現主要由軟件實現主要由軟件實現幾比一幾比一幾百比一幾百比一幾十個字節幾十個字節幾百到幾千個字節幾百到幾千個字節可直接訪問可直接訪問均通過第一級均通過第一級不切換不切換切換到其他進程切換到其他進程“Cache“Cache主存主存”與與“主存輔存主存輔存”層次的區別層次的區別4

12、.1 存儲器的層次結構存儲器的層次結構4.1.4 存儲層次的四個問題存儲層次的四個問題當把一個塊調入高一層當把一個塊調入高一層(靠近靠近CPU)存儲器時，存儲器時，可以放在哪些位置上可以放在哪些位置上? (映象規則映象規則)當所要訪問的塊在高一層存儲器中時，如何當所要訪問的塊在高一層存儲器中時，如何找到該塊找到該塊? (查找算法查找算法)3. 當發生失效時，應替換哪一塊？當發生失效時，應替換哪一塊？ (替換算法替換算法)4. 當進行寫訪問時，應進行哪些操作當進行寫訪問時，應進行哪些操作? (寫策略寫策略)1. 2.第第4章章 存儲層次存儲層次n4.2 Cache基本知識基本知識nCache是按

13、塊進行管理的。是按塊進行管理的。Cache和主存均和主存均被分割成大小相同的塊。信息以塊為單位調被分割成大小相同的塊。信息以塊為單位調入入Cache。n相應地，相應地，CPU的訪存地址被分割成兩部分：的訪存地址被分割成兩部分：塊地址和塊內位移。塊地址和塊內位移。主存地址：塊地址塊地址 塊內位移塊內位移主存塊地址用于查找該塊在主存塊地址用于查找該塊在Cache中的位置，中的位置，塊內位移用于確定所訪問的數據在該塊中的位置。塊內位移用于確定所訪問的數據在該塊中的位置。4.2 Cache基本知識基本知識n5.2.1 映象規則映象規則n映象規則主要有全相聯映象，直接映象和組映象規則主要有全相聯映象，直

14、接映象和組相聯映象三種。相聯映象三種。n1.全相聯映象全相聯映象n全相聯：全相聯：主存中的任一塊可以被放置到主存中的任一塊可以被放置到CacheCache中中的任意一個位置。的任意一個位置。n特點：特點：空間利用率最高，沖突概率最低，實現最空間利用率最高，沖突概率最低，實現最復雜。復雜。4.2 Cache基本知識基本知識4.2 Cache基本知識基本知識n2.直接映象直接映象n直接映象：直接映象：主存中的每一塊只能被放置到主存中的每一塊只能被放置到CacheCache中唯一的一個位置。中唯一的一個位置。 ( (循環分配循環分配) ) 特點：特點：空間利用率最低，沖突概率最高，實現空間利用率最低

15、，沖突概率最高，實現最簡單。最簡單。 對于主存的第對于主存的第i i 塊，若它映象到塊，若它映象到CacheCache的第的第j j 塊，則塊，則: : j ji i mod ( mod (M M ) ) （M M為為CacheCache的塊數）的塊數）4.2 Cache基本知識基本知識4.2 Cache基本知識基本知識 組相聯：組相聯：主存中的每一塊可以被放置到主存中的每一塊可以被放置到Cache 中唯一的一個組中的任何一個位置。中唯一的一個組中的任何一個位置。 （Cache等分為若干組，每組由若干個塊構成）等分為若干組，每組由若干個塊構成） 組相聯是直接映象和全相聯的一種折中。組相聯是直接

16、映象和全相聯的一種折中。 設設M2m，則當表示為二進制數時，則當表示為二進制數時，j 實際實際 上就是上就是i 的低的低m 位：位：3. 組相聯映象組相聯映象m位位j主存塊地址主存塊地址 i：4.2 Cache基本知識基本知識4.2 Cache基本知識基本知識 上述的上述的m和和k 通常稱為通常稱為索引索引 組的選擇常采用位選擇算法組的選擇常采用位選擇算法 若主存第若主存第i 塊映象到第塊映象到第k 組，則組，則: ki mod（G） （G為為Cache的組數）的組數） 設設G2g，則當表示為二進制數時，則當表示為二進制數時，k 實實 際上就是際上就是i 的低的低 g 位：位：g位位k主存塊地

17、址主存塊地址 i：4.2 Cache基本知識基本知識 絕大多數計算機的絕大多數計算機的Cache: Cache: n n 44 想一想：相聯度一定是越大越好？想一想：相聯度一定是越大越好？ n n 路組相聯：路組相聯：每組中有每組中有n n 個塊個塊( (n nM M / /G G ) ) n n 稱為相聯度。稱為相聯度。 相聯度越高，相聯度越高，CacheCache空間的利用率就越高，空間的利用率就越高， 塊沖突概率就越低，失效率也就越低。塊沖突概率就越低，失效率也就越低。 全相聯全相聯直接映象直接映象組相聯組相聯n n ( (路數路數) )G G ( (組數組數) )M MM M1 11

18、11 1n nM M1 1G GM M4.2 Cache基本知識基本知識n塊沖突是指一個主存塊要進入已被占用的塊沖突是指一個主存塊要進入已被占用的Cache塊位置塊位置。n顯然，全相聯的失效率最低，直接映象的失效率最高顯然，全相聯的失效率最低，直接映象的失效率最高。雖然從降低失效率的角度來看，。雖然從降低失效率的角度來看，n的值越大越好，但的值越大越好，但在后面我們將看到，增大在后面我們將看到，增大n值并不一定能使整個計算機值并不一定能使整個計算機系統的性能提高，而且還會使系統的性能提高，而且還會使Cache的實現復雜度和代的實現復雜度和代價增大。價增大。n因此，絕大多數計算機都采用直接映象、

19、兩路組相聯因此，絕大多數計算機都采用直接映象、兩路組相聯或或4路組相聯。特別是直接映象，采用得最多。路組相聯。特別是直接映象，采用得最多。4.2 Cache基本知識基本知識4.2.2 查找方法查找方法1. 如何確定如何確定Cache中是否有所要訪問的塊？中是否有所要訪問的塊？ 若有的話如何確定其位置？若有的話如何確定其位置？ 設置查找目錄表。設置查找目錄表。目錄表共有目錄表共有M項，每一項對應于項，每一項對應于Cache中的一個塊，中的一個塊，用于指出當前該塊中存放的信息是哪一個主存塊的用于指出當前該塊中存放的信息是哪一個主存塊的（可能有多個主存塊映象到該（可能有多個主存塊映象到該Cache塊

20、）。它實際塊）。它實際上是記錄了該主存塊的塊地址的高位部分，稱為上是記錄了該主存塊的塊地址的高位部分，稱為標標識（識（tag）。每個主存塊能唯一的由其標識來確定。每個主存塊能唯一的由其標識來確定。4.2 Cache基本知識基本知識為了指出為了指出Cache中的塊是中的塊是否包含有效信息，一般是否包含有效信息，一般是在目錄表中給每一項設置在目錄表中給每一項設置一個一個有效位有效位。例如，當該。例如，當該位為位為“1”時表示該目錄時表示該目錄表項有效，表項有效，Cache中相應中相應塊所包含的信息有效。當塊所包含的信息有效。當一個主存塊被調入一個主存塊被調入Cache中某一個塊位置時，它的中某一個

21、塊位置時，它的標識就被填入到目錄表中標識就被填入到目錄表中與該與該Cache塊相對應的項塊相對應的項中，并且該項的有效位被中，并且該項的有效位被置置“1”。4.2 Cache基本知識基本知識n根據映象規則不同，一個主存塊可能映象到根據映象規則不同，一個主存塊可能映象到Cache中的中的一個或多個一個或多個Cache塊位置。為便于討論，我們把它們稱塊位置。為便于討論，我們把它們稱為為候選位置候選位置。n當當CPU訪問該主存塊時，必須且訪問該主存塊時，必須且只需查找它的候選位只需查找它的候選位置置所對應的目錄表項（標識）。如果有與所訪問的主所對應的目錄表項（標識）。如果有與所訪問的主存塊相同的標識

22、，且其有效位為存塊相同的標識，且其有效位為“1”，則它所對應的，則它所對應的Cache塊即是所要找的塊。塊即是所要找的塊。4.2 Cache基本知識基本知識n直接映象直接映象Cache的候選的候選位置最少，只位置最少，只有一個；有一個；n全相聯全相聯Cache的候選位置最的候選位置最多，為多，為M個；個；n而而n路組相聯路組相聯則介于兩者之則介于兩者之間，為間，為n個。個。4.2 Cache基本知識基本知識 并行查找與順序查找并行查找與順序查找4.2 Cache基本知識基本知識 順序查找順序查找提高性能的方法：提高性能的方法：主候選位置主候選位置(MRU(MRU塊塊) ) 前瞻執行前瞻執行4.

23、2 Cache基本知識基本知識 并行查找的實現方法：并行查找的實現方法：舉例：舉例： 路組相聯并行標識比較路組相聯并行標識比較 （比較器的個數及位數）（比較器的個數及位數）l 相聯存儲器相聯存儲器l 單體多字存儲器比較器單體多字存儲器比較器 4.2 Cache基本知識基本知識主存塊地址： 目錄表（標識存儲器）4.2 Cache基本知識基本知識4.2 Cache基本知識基本知識4.2 Cache基本知識基本知識4.2.3 替換算法替換算法 所要解決的問題：當要從主存調入一個塊到所要解決的問題：當要從主存調入一個塊到Cache中時，中時，會出現該塊所映象到的一組（或一個）會出現該塊所映象到的一組（

24、或一個）Cache塊已全被占塊已全被占用的情況。這時需強迫騰出其中的某一塊，以接納新調入用的情況。這時需強迫騰出其中的某一塊，以接納新調入的塊。那么應該替換哪一塊？的塊。那么應該替換哪一塊？1. 隨機法隨機法為了均勻使用一組中的各塊，隨機地選擇被替為了均勻使用一組中的各塊，隨機地選擇被替換的塊。有些系統采用偽隨機數法產生塊號。換的塊。有些系統采用偽隨機數法產生塊號。特點：實現簡單，但反映不了程序的局部性。特點：實現簡單，但反映不了程序的局部性。2. 先進先出法（先進先出法（FIFO）選擇最早調入的塊作為被替換的塊。選擇最早調入的塊作為被替換的塊。特點：容易實現。還是不能正確地反映程序的特點：容

25、易實現。還是不能正確地反映程序的局部性。局部性。4.2 Cache基本知識基本知識3. 最近最少使用法（最近最少使用法（LRU）選擇近期最少被訪問的塊作為被替換的塊。實選擇近期最少被訪問的塊作為被替換的塊。實際應用中通常是選擇最久沒有被訪問過的塊作為被替際應用中通常是選擇最久沒有被訪問過的塊作為被替換的塊。換的塊。特點：失效率低。能較好地反映程序的局部性特點：失效率低。能較好地反映程序的局部性原理。但原理。但LRU比較復雜，硬件實現比較困難，特別是比較復雜，硬件實現比較困難，特別是當組的大小增加時，當組的大小增加時，LRU的實現代價會越來越高，而的實現代價會越來越高，而且經常只能是近似的實現。

26、且經常只能是近似的實現。4.2 Cache基本知識基本知識n表中的數據是對于一個表中的數據是對于一個VAX地址流（既包括用戶程序地址流（既包括用戶程序也包括操作系統程序）在塊大小為也包括操作系統程序）在塊大小為16B的情況下統計的的情況下統計的。在這個例子中，對于大容量。在這個例子中，對于大容量Cache，LRU和隨機法和隨機法的失效率幾乎沒什么差別。的失效率幾乎沒什么差別。4.2 Cache基本知識基本知識n4.2.4 寫策略寫策略n處理器對處理器對Cache的訪問主要是讀訪問，因此設計的訪問主要是讀訪問，因此設計Cache要針對最經常發生的要針對最經常發生的“讀讀”進行優化。進行優化。n幸

27、運的是，最經常發生的幸運的是，最經常發生的“讀讀”也是最容易提高速度也是最容易提高速度的。訪問的。訪問Cache時，在讀出標識進行比較的同時，時，在讀出標識進行比較的同時，可以把相應的可以把相應的Cache塊也讀出。如果命中，則把該塊也讀出。如果命中，則把該塊中請求的數據立即送給塊中請求的數據立即送給CPU；若為失效，則所讀；若為失效，則所讀出的塊沒什么用處，但也沒什么壞處，置之不理就出的塊沒什么用處，但也沒什么壞處，置之不理就是了。是了。4.2 Cache基本知識基本知識n“寫寫”在所有訪存操作中所占的比例在所有訪存操作中所占的比例 n統計結果表明，對于一組給定的程序：統計結果表明，對于一組

28、給定的程序：nloadload指令：指令：2626nstorestore指令：指令：9 9n“寫寫”在所有訪存操作中所占的比例：在所有訪存操作中所占的比例：9 9/(100/(10026269 9)7)7n“寫寫”在訪問數據在訪問數據CacheCache操作中所占的比例：操作中所占的比例： 9 9/(26/(269 9)25)25取指令 讀數據 寫數據4.2 Cache基本知識基本知識n然而，對于然而，對于“寫寫”卻不是如此。只有在讀出標識并進卻不是如此。只有在讀出標識并進行比較，確認是命中后，才可對行比較，確認是命中后，才可對Cache塊進行寫入塊進行寫入。由于檢查標識不能與寫入。由于檢查標

29、識不能與寫入Cache并行進行，并行進行，“寫寫”一般比一般比“讀讀”花費更多的時間。花費更多的時間。n另一個比較麻煩的地方是，處理器要寫入的數據的另一個比較麻煩的地方是，處理器要寫入的數據的寬度不是定長的（通常為寬度不是定長的（通常為18B）。寫入時，只能修）。寫入時，只能修改改Cache塊中相應的部分，而塊中相應的部分，而“讀讀”則可以多讀出幾則可以多讀出幾個字節也沒關系。個字節也沒關系。n“寫寫”訪問有可能導致訪問有可能導致Cache和主存內容的不一致。和主存內容的不一致。顯然，為了保證正確性，主存的內容也必須更新。顯然，為了保證正確性，主存的內容也必須更新。至于何時更新，這正是寫策略要

30、解決的問題。至于何時更新，這正是寫策略要解決的問題。4.2 Cache基本知識基本知識兩種寫策略兩種寫策略寫策略是區分不同Cache設計方案的一個重要標志。 寫直達法寫直達法 執行執行“寫寫”操作時，不僅寫入操作時，不僅寫入Cache，而且，而且 也寫入下一級存儲器。也寫入下一級存儲器。 寫回法寫回法 執行執行“寫寫”操作時，只寫入操作時，只寫入Cache。僅當。僅當 Cache中相應的塊被替換時，才寫回主存。中相應的塊被替換時，才寫回主存。 (設置設置“污染位污染位”)4.2 Cache基本知識基本知識兩種寫策略的比較兩種寫策略的比較 寫直達法的優點：寫直達法的優點：易于實現，一致性好。易于

31、實現，一致性好。 寫回法的優點：寫回法的優點：速度快，而且對于同一單元速度快，而且對于同一單元的多個寫最后只需一次寫回下一級存儲器，有些的多個寫最后只需一次寫回下一級存儲器，有些“寫寫”只到達只到達Cache不到達主存，因而所使用的存不到達主存，因而所使用的存儲器頻帶較低；儲器頻帶較低；4.2 Cache基本知識基本知識寫緩沖器：寫緩沖器：n采用寫直達法時，若在進行采用寫直達法時，若在進行“寫寫”操作的過程中操作的過程中CPU必須等待，直到必須等待，直到“寫寫”操作結束，則稱操作結束，則稱CPU寫寫等待等待。減少寫等待的一種常用優化技術是采用。減少寫等待的一種常用優化技術是采用寫寫緩沖器緩沖器

32、，從而使下一級存儲器的更新和，從而使下一級存儲器的更新和CPU的執的執行重疊起來。行重疊起來。4.2 Cache基本知識基本知識寫策略與調塊寫策略與調塊 寫直達法寫直達法 不按寫分配不按寫分配 寫回法寫回法 按寫分配按寫分配“寫寫”操作時的調塊：操作時的調塊：由于由于“寫寫”訪問并不需要用到所訪問單元中原有的數據。訪問并不需要用到所訪問單元中原有的數據。所以，當發生寫失效時，是否調入相應的塊，有兩種選擇：所以，當發生寫失效時，是否調入相應的塊，有兩種選擇： 按寫分配按寫分配(寫時取寫時取) 寫失效時，先把所寫單元所在的塊調入寫失效時，先把所寫單元所在的塊調入 Cache，再行寫入。，再行寫入。

33、 不按寫分配不按寫分配(繞寫法繞寫法) 寫失效時，直接寫入下一級存儲器而不調塊。寫失效時，直接寫入下一級存儲器而不調塊。4.2 Cache基本知識基本知識n4.2.5 Cache的結構的結構 例子：例子：DECDEC的的Alpha AXP21064Alpha AXP21064中的內部數據中的內部數據CacheCache1. 簡介 容量：容量：8KB8KB 塊大小：塊大小：32B32B 塊數：塊數：256256 映象方法：映象方法：直接映象直接映象 “寫寫”策略：策略：寫直達寫直達 采用采用不按寫分配不按寫分配 寫緩沖器大小：寫緩沖器大小：4 4個塊個塊4.2 Cache基本知識基本知識2. 結

34、構圖4.2 Cache基本知識基本知識3. 工作過程 “讀讀”訪問命中訪問命中4.2 Cache基本知識基本知識 “寫寫”訪問命中訪問命中4.2 Cache基本知識基本知識 失效情況下的操作失效情況下的操作n發生發生讀失效讀失效時，時，CacheCache向向CPUCPU發出一個暫停信號，通發出一個暫停信號，通知它等待，并從下一級存儲器中讀入知它等待，并從下一級存儲器中讀入32B32B數據。數據。2106421064的的CacheCache和它的下一級存儲器之間的數據通路和它的下一級存儲器之間的數據通路為為16B16B，每次數據傳送需，每次數據傳送需5 5個時鐘周期，傳送全部個時鐘周期，傳送全

35、部32B32B數據要花數據要花1010個時鐘周期。因為個時鐘周期。因為2106421064的數據的數據CacheCache是直接映象的，所以被替換的塊只有一個，是直接映象的，所以被替換的塊只有一個，別無選擇。替換一個塊意味著更新該塊的數據、標別無選擇。替換一個塊意味著更新該塊的數據、標識和有效位。識和有效位。n發生發生寫失效寫失效時，時，2106421064采用不按寫分配規則。也就采用不按寫分配規則。也就是說是說CacheCache使數據使數據“繞過繞過”Cache”Cache，直接寫入主存。，直接寫入主存。4.2 Cache基本知識基本知識4. 混合Cache與分離Cache混合混合Cach

36、eCache：指令和數據混合指令和數據混合CacheCache。若流水線中同時請求一個數據字和一個指令字，會出若流水線中同時請求一個數據字和一個指令字，會出現沖突，導致現沖突，導致CPUCPU等待。等待。分離分離CacheCache：分為指令分為指令CacheCache和數據和數據CacheCache兩個兩個CacheCache。Alpha AXP21064Alpha AXP21064有一個有一個8KB8KB的指令的指令CacheCache，其結構與，其結構與8KB8KB的數據的數據CacheCache幾乎一樣。幾乎一樣。CPUCPU知道它發出的地址是指令地址還是數據地址，因此知道它發出的地址

37、是指令地址還是數據地址，因此可以為它們設置不同的端口，這樣就會加倍對存儲系可以為它們設置不同的端口，這樣就會加倍對存儲系統和統和CPUCPU之間數據通道帶寬的要求。由于系統對指令和之間數據通道帶寬的要求。由于系統對指令和數據的操作特性不同，獨立的指令數據的操作特性不同，獨立的指令CacheCache和數據和數據CacheCache使我們能分別對它們進行優化，它們各自采用不同的使我們能分別對它們進行優化，它們各自采用不同的容量、塊大小和相聯度時的性能可能會更好。容量、塊大小和相聯度時的性能可能會更好。4.2 Cache基本知識基本知識16 KB16 KB容量容量1 KB1 KB2 KB2 KB4

38、 KB4 KB8 KB8 KB32 KB32 KB指令指令 Cache3.06%失失 效效 率率 的的 比比 較較64 KB64 KB128 KB128 KB數據數據 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%以上數據是在塊大小為32B、映象方法為直接映象的條件下，針對SPEC92典型程序，在DECstation5000上測出的平均值。對指令的訪問約占所有訪問的75%.

39、4.2 Cache基本知識基本知識分離分離Cache平均失效率的計算：平均失效率的計算：訪問指令訪問指令Cache的百分比的百分比指令指令Cache的失效率的失效率訪問數據訪問數據Cache的百分比的百分比數據數據Cache的失效率的失效率4.2.6 Cache性能分析性能分析失效率失效率n與硬件速度無關，用它來評價存儲系統的性能非常與硬件速度無關，用它來評價存儲系統的性能非常方便方便,所以經常會用到它。所以經常會用到它。n容易產生一些誤導：一種更好的評測存儲系統性能容易產生一些誤導：一種更好的評測存儲系統性能的指標是平均訪存時間。的指標是平均訪存時間。平均訪存時間平均訪存時間 平均訪存時間平

40、均訪存時間 命中時間失效率命中時間失效率失效開銷失效開銷4.2 Cache基本知識基本知識n例例5.15.1 假設假設CacheCache的命中時間為的命中時間為1 1個時鐘周期，失效開銷個時鐘周期，失效開銷為為50 50 個時鐘周期，在混合個時鐘周期，在混合CacheCache中一次中一次loadload或或storestore操操作訪問作訪問CacheCache的命中時間都要增加一個時鐘周期的命中時間都要增加一個時鐘周期( (因為因為混合混合CacheCache只有一個端口，無法同時滿足兩個請求。流只有一個端口，無法同時滿足兩個請求。流水線中，混合水線中，混合CacheCache會導致結構

41、沖突會導致結構沖突) )，根據上表所列，根據上表所列的失效率，試問指令的失效率，試問指令CacheCache和數據和數據CacheCache容量均為容量均為16KB16KB的分離的分離CacheCache和容量為和容量為32KB32KB的混合的混合CacheCache相比，哪種相比，哪種CacheCache的失效率更低？又假設采用寫直達策略，且有一的失效率更低？又假設采用寫直達策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。請問上個寫緩沖器，并且忽略寫緩沖器引起的等待。請問上述兩種情況下平均訪存時間各是多少？述兩種情況下平均訪存時間各是多少？4.2 Cache基本知識基本知識解：解： 如前

42、所述，約如前所述，約75%75%的訪存為取指令。因此，分離的訪存為取指令。因此，分離CacheCache的總體失效率為：的總體失效率為： (75% (75%0.64%)0.64%)(25%(25%6.47%)6.47%)2.10%2.10% 根據前表，容量為根據前表，容量為32KB32KB的混合的混合CacheCache的失效率略低一的失效率略低一些，只有些，只有1.99%.1.99%.100%/（100%+26%+9%）=75% Load Store4.2 Cache基本知識基本知識平均訪存時間公式可以分為指令訪問和數據訪問兩部分：平均訪存時間公式可以分為指令訪問和數據訪問兩部分：平均訪存時

43、間平均訪存時間指令所占的百分比指令所占的百分比 (指令命中時間指令失效率指令命中時間指令失效率失效開銷失效開銷 數據所占的百分比數據所占的百分比 (數據命中時間數據失效率數據命中時間數據失效率失效開銷失效開銷)所以，兩種結構的平均訪存時間分別為：所以，兩種結構的平均訪存時間分別為：平均訪存時間平均訪存時間分離分離75%(10.64%50)25%(16.47%50) (75%1.32)(25%4.325)0.9901.0592.05平均訪存時間平均訪存時間混合混合75%(11.99%50)25%(111.99%50)(75%1.995)(25%2.995)1.4960.7492.24因此，盡管分

44、離因此，盡管分離CacheCache的實際失效率比混合的實際失效率比混合CacheCache的高，但其平均訪存時的高，但其平均訪存時間反而較低。分離間反而較低。分離CacheCache提供了兩個端口，消除了結構沖突。執行一個程提供了兩個端口，消除了結構沖突。執行一個程序所需要的序所需要的CPUCPU時間與時間與CacheCache的性能密切相關。的性能密切相關。4.2 Cache基本知識基本知識程序執行時間程序執行時間CPUCPU時間（時間（CPUCPU執行周期數執行周期數+ +存儲器停頓周期數）存儲器停頓周期數） 時鐘周期時間時鐘周期時間其中：其中： n存儲器停頓時鐘周期數存儲器停頓時鐘周期

45、數“讀讀”的次數的次數讀失效率讀失效率讀失效開銷讀失效開銷“寫寫”的次數的次數寫失效率寫失效率寫失效開銷寫失效開銷將讀將讀/ /寫合并，并求出寫合并，并求出“讀讀”和和“寫寫”的平均失效率和平均失效開銷，的平均失效率和平均失效開銷，上式可化簡：上式可化簡：n存儲器停頓時鐘周期數訪存次數存儲器停頓時鐘周期數訪存次數失效率失效率失效開銷失效開銷 時鐘周期時間失效開銷失效率指令數訪存次數時間executionCPIICCPU指令數 失效率 訪存次數 指令數 失效次數 每條指令的平均失效次數 時鐘周期時間指令數存儲器停頓周期數時間executionCPIICCPU4.2 Cache基本知識基本知識 例

46、例5.2 5.2 我們用一個和我們用一個和Alpha AXPAlpha AXP類似的機器作為第類似的機器作為第一個例子。假設一個例子。假設CacheCache失效開銷為失效開銷為5050個時鐘周期，當不個時鐘周期，當不考慮存儲器停頓時，所有指令的執行時間都是考慮存儲器停頓時，所有指令的執行時間都是2.02.0個時個時鐘周期，訪問鐘周期，訪問CacheCache失效率為失效率為2%2%，平均每條指令訪存，平均每條指令訪存1.331.33次。試分析次。試分析CacheCache對性能的影響。對性能的影響。 解解CPU CPU 時間時間ICIC( (CPICPIexeexe ) ) 時鐘周期時間時鐘

47、周期時間存儲器停頓周期數存儲器停頓周期數指令數指令數4.2 Cache基本知識基本知識考慮考慮CacheCache的失效后，性能為：的失效后，性能為： CPUCPU時間時間有有cachecacheICIC（2.02.01.331.332 %2 %5050）時鐘周期時間時鐘周期時間 ICIC3.333.33時鐘周期時間時鐘周期時間實際實際CPI CPI ：3.333.333.33/2.0 = 1.67(3.33/2.0 = 1.67(倍倍) ) CPUCPU時間也增加為原來的時間也增加為原來的1.671.67倍。倍。 但若不采用但若不采用Cache,Cache,則：則：CPICPI2.02.05

48、0501.331.3368.568.54.2 Cache基本知識基本知識nCacheCache失效對于一個失效對于一個CPICPI較小而時鐘頻率較高的較小而時鐘頻率較高的CPUCPU來來說，影響是雙重的：說，影響是雙重的：nCPICPIexecutionexecution越低，固定周期數的越低，固定周期數的CacheCache失效開銷的失效開銷的相對影響就越大。相對影響就越大。n在計算在計算CPICPI時，失效開銷的單位是時鐘周期數。時，失效開銷的單位是時鐘周期數。因此，即使兩臺計算機的存儲層次完全相同，時因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的鐘頻率較高的CPUCPU的失效開銷

49、較大，其的失效開銷較大，其CPICPI中存儲中存儲器停頓這部分也就較大。器停頓這部分也就較大。 因此因此CacheCache對于低對于低CPICPI、高時鐘頻率的、高時鐘頻率的CPUCPU來來說更加重要。說更加重要。 4.2 Cache基本知識基本知識 例例5.35.3 考慮兩種不同組織結構的考慮兩種不同組織結構的CacheCache：直接映象：直接映象CacheCache和和2 2路組相聯路組相聯CacheCache，試問它們對，試問它們對CPUCPU的性能有何影響？先求的性能有何影響？先求平均訪存時間，然后再計算平均訪存時間，然后再計算CPUCPU性能。分析時請用以下假設：性能。分析時請用

50、以下假設： (1) (1)理想理想CacheCache（命中率為（命中率為100%100%）情況下的）情況下的CPICPI為為2.02.0，時鐘周期為時鐘周期為2ns2ns，平均每條指令訪存，平均每條指令訪存1.31.3次。次。 (2) (2)兩種兩種CacheCache容量均為容量均為64KB64KB，塊大小都是，塊大小都是3232字節。字節。 (3) (3)下圖說明，在組相聯下圖說明，在組相聯CacheCache中，必須增加一個多路中，必須增加一個多路選擇器，用于根據標識匹配結果從相應組的塊中選擇所需選擇器，用于根據標識匹配結果從相應組的塊中選擇所需的數據。因為的數據。因為CPUCPU的速

51、度直接與的速度直接與CacheCache命中的速度緊密相關，命中的速度緊密相關，所以對于組相聯所以對于組相聯CacheCache，由于多路選擇器的存在而使，由于多路選擇器的存在而使CPUCPU的的時鐘周期增加到原來的時鐘周期增加到原來的1.101.10倍。倍。4.2 Cache基本知識基本知識 (4) (4) 這兩種結構這兩種結構CacheCache的失效開銷都是的失效開銷都是70 ns70 ns。（在實。（在實際應用中，應取整為整數個時鐘周期）際應用中，應取整為整數個時鐘周期） (5) (5) 命中時間為命中時間為1 1個時鐘周期，個時鐘周期，64 KB64 KB直接映象直接映象CacheC

52、ache的失效率為的失效率為1.4%1.4%，相同容量的，相同容量的2 2路組相聯路組相聯CacheCache的失效率為的失效率為1.0%1.0%。4.2 Cache基本知識基本知識4.2 Cache基本知識基本知識 解解 平均訪存時間為：平均訪存時間為： 平均訪存時間命中時間失效率失效開銷平均訪存時間命中時間失效率失效開銷 因此，兩種結構的平均訪存時間分別是：因此，兩種結構的平均訪存時間分別是： 平均訪存時間平均訪存時間1 1路路2 2（0.0140.0147070）2.98 ns2.98 ns 平均訪存時間平均訪存時間2 2路路2 21.101.10（0.0100.0107070）2.90

53、 ns2.90 ns 2 2路組相聯路組相聯CacheCache的平均訪存時間比較低。的平均訪存時間比較低。 CPU CPU 時間時間ICIC( (CPICPIexeexe每條指令的平均存儲器每條指令的平均存儲器 停頓周期數停頓周期數) )時鐘周期時間時鐘周期時間 IC IC ( (CPICPIexeexe時鐘周期時間時鐘周期時間 每條指令的平均存儲器停頓時間每條指令的平均存儲器停頓時間) )4.2 Cache基本知識基本知識因此：因此：CPUCPU時間時間1 1路路 ICIC(2.0(2.02 2(1.3(1.30.0140.01470)70) 5.275.27ICICCPUCPU時間時間2

54、 2路路 ICIC(2.0(2.02 21.101.10(1.3(1.30.0100.01070)70) 5.315.31ICIC5.315.31ICICCPUCPU時間時間1 1路路 1.011.015.275.27ICICCPUCPU時間時間2 2路路和平均訪存時間的比較結果相反，直接映象和平均訪存時間的比較結果相反，直接映象CacheCache的的平均性能好一些，這是因為在兩路組相聯的情況下，平均性能好一些，這是因為在兩路組相聯的情況下，雖然失效次數減少了，但所有指令的時鐘周期時間都雖然失效次數減少了，但所有指令的時鐘周期時間都增加了增加了10%10%。由于。由于CPUCPU時間是我們進

55、行評價的基準，而時間是我們進行評價的基準，而且直接映象且直接映象CacheCache實現更簡單，所以本例中直接映象實現更簡單，所以本例中直接映象CacheCache是較好的選擇。是較好的選擇。4.2 Cache基本知識基本知識n4.2.7 改進改進Cache的性能的性能n平均訪存時間命中時間失效率失效開銷平均訪存時間命中時間失效率失效開銷n可以從三個方面改進可以從三個方面改進CacheCache的性能：的性能：n降低失效率降低失效率n減少失效開銷減少失效開銷n減少減少CacheCache命中時間命中時間n下面介紹下面介紹1717種種CacheCache優化技術優化技術n8 8種種用于降低失效率

56、用于降低失效率n5 5種種用于減少失效開銷用于減少失效開銷n4 4種種用于減少命中時間用于減少命中時間 4.2 Cache基本知識基本知識寫緩沖合并寫緩沖合并第第4章章 存儲層次存儲層次n4.3 降低降低Cache失效率的方法失效率的方法n三種失效三種失效(3C C)n強制性失效強制性失效( (C Compulsory miss)ompulsory miss)n當第一次訪問一個塊時，該塊不在當第一次訪問一個塊時，該塊不在CacheCache中，需從中，需從下一級存儲器中調入下一級存儲器中調入CacheCache，這就是強制性失效。，這就是強制性失效。 ( (冷啟動冷啟動失效，首次訪問失效失效，

57、首次訪問失效)n容量失效容量失效( (C Capacity miss ) apacity miss ) n如果程序執行時所需的塊不能全部調入如果程序執行時所需的塊不能全部調入CacheCache中，中，則當某些塊被替換后，若又重新被訪問，就會發則當某些塊被替換后，若又重新被訪問，就會發生失效。這種失效稱為容量失效。生失效。這種失效稱為容量失效。4.3 降低降低Cache失效率的方法失效率的方法n沖突失效沖突失效( (C Conflict miss)onflict miss)n在組相聯或直接映象在組相聯或直接映象CacheCache中，若太多的塊映象中，若太多的塊映象到同一組到同一組( (塊塊)

58、 )中，則會出現該組中某個塊被別的中，則會出現該組中某個塊被別的塊替換塊替換( (即使別的組或塊有空閑位置即使別的組或塊有空閑位置) )，然后又被，然后又被重新訪問的情況。這就是發生了沖突失效。重新訪問的情況。這就是發生了沖突失效。 ( (碰撞失效，干擾失效碰撞失效，干擾失效) )n三種失效所占的比例三種失效所占的比例 n圖示圖示I(I(絕對值絕對值) )n圖示圖示(相對值相對值) )4.3 降低降低Cache失效率的方法失效率的方法4.3 降低降低Cache失效率的方法失效率的方法4.3 降低降低Cache失效率的方法失效率的方法n可以看出：可以看出：n相聯度越高，沖突失效就越少；相聯度越高

59、，沖突失效就越少；n強制性失效和容量失效不受相聯度的影響；強制性失效和容量失效不受相聯度的影響；n強制性失效不受強制性失效不受CacheCache容量的影響，但容量失效容量的影響，但容量失效卻隨著容量的增加而減少；卻隨著容量的增加而減少；n表中的數據符合表中的數據符合2:12:1的的CacheCache經驗規則經驗規則，即大小為，即大小為N N的直接映象的直接映象CacheCache的失效率約等于大小為的失效率約等于大小為N/2N/2的的2 2路組相聯路組相聯CacheCache的失效率。的失效率。4.3 降低降低Cache失效率的方法失效率的方法n減少三種失效的方法減少三種失效的方法n強制性

60、失效：強制性失效：增加塊大小，預取增加塊大小，預取（本身很少）（本身很少）n容量失效：容量失效：增加容量增加容量 （抖動現象）（抖動現象）n沖突失效：沖突失效：提高相聯度提高相聯度（理想情況：全相聯）（理想情況：全相聯）n許多降低失效率的方法會增加命中時間或失效開銷許多降低失效率的方法會增加命中時間或失效開銷4.3 降低降低Cache失效率的方法失效率的方法n4.3.1 增加增加Cache的容量的容量n降低降低cachecache失效率最直接的方法是增加失效率最直接的方法是增加CacheCache的容量的容量n缺點缺點:n增加成本增加成本n可能增加命中時間可能增加命中時間n這種方法在片外這種方