第4章存儲(chǔ)層次

1、n第第4章章 存儲(chǔ)層次存儲(chǔ)層次n4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)n4.2 Cache基本知識(shí)基本知識(shí)n4.3 降低降低Cache失效率的方法失效率的方法n4.4 減少減少Cache失效開銷失效開銷n4.5 減少命中時(shí)間減少命中時(shí)間n4.6 主存主存n4.7 虛擬存儲(chǔ)器虛擬存儲(chǔ)器n4.8 進(jìn)程保護(hù)進(jìn)程保護(hù)n4.9 Intel Core i7中的存儲(chǔ)器層次結(jié)構(gòu)中的存儲(chǔ)器層次結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第第4章章 存儲(chǔ)層次存儲(chǔ)層次n4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)n4.1.1 從單級(jí)存儲(chǔ)器到多級(jí)存儲(chǔ)器從單級(jí)存儲(chǔ)器到多級(jí)存儲(chǔ)器1. 1. 從用戶的角度來看，存儲(chǔ)器的三個(gè)主要指標(biāo)是：從

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

3、離CPU最近，容量最小，每位價(jià)格最高。lMn離CPU最遠(yuǎn)，容量最大，每位價(jià)格最低。l考慮相鄰的兩級(jí)，靠近CPU的一級(jí)總是容量小一些，速度快一些，價(jià)格高一些。4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)n整個(gè)系統(tǒng)的目標(biāo)：從整個(gè)系統(tǒng)的目標(biāo)：從CPU看去，這個(gè)存儲(chǔ)器系統(tǒng)的速度看去，這個(gè)存儲(chǔ)器系統(tǒng)的速度接近于接近于M1的，而容量和價(jià)格則接近于的，而容量和價(jià)格則接近于Mn。n須做到：存儲(chǔ)器越靠近須做到：存儲(chǔ)器越靠近CPU，CPU對(duì)它的訪問頻率越高對(duì)它的訪問頻率越高。大多數(shù)訪問都能在。大多數(shù)訪問都能在M1完成（根據(jù)局部性原理）。完成（根據(jù)局部性原理）。n任何一級(jí)存儲(chǔ)器中的內(nèi)容一般都是其下一層存儲(chǔ)器中內(nèi)任何一級(jí)

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

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

6、 S 容量容量 T TA A 訪問時(shí)間訪問時(shí)間 C C 每位價(jià)格每位價(jià)格下面僅考慮由下面僅考慮由M M1 1和和M M2 2構(gòu)成的兩級(jí)存儲(chǔ)層次：構(gòu)成的兩級(jí)存儲(chǔ)層次：M M1 1的參數(shù)：的參數(shù)：S S1 1，T TA1A1，C C1 1 M M2 2的參數(shù)：的參數(shù)：S S2 2，T TA2A2，C C2 21.1. 每位價(jià)格每位價(jià)格C C C CC C1 1S S1 1C C2 2S S2 2S S1 1S S2 2顯然，當(dāng)顯然，當(dāng)S1 S2時(shí)，時(shí)，C C24.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)2. 2. 命中率命中率 H H 和失效率和失效率 F F命中率為命中率為CPU訪問存儲(chǔ)系統(tǒng)時(shí)，在訪

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

8、慮CPUCPU的一次訪存：的一次訪存：n當(dāng)命中時(shí)，訪問時(shí)間即為當(dāng)命中時(shí)，訪問時(shí)間即為T TA1A1，所以，所以T TA1A1常稱為命中時(shí)間。常稱為命中時(shí)間。n不命中時(shí)，情況比較復(fù)雜。在大多數(shù)兩級(jí)存儲(chǔ)層次中，若不命中時(shí)，情況比較復(fù)雜。在大多數(shù)兩級(jí)存儲(chǔ)層次中，若訪問的字不在訪問的字不在M M1 1中，就必須從中，就必須從M M2 2把所請(qǐng)求的字的信息塊傳把所請(qǐng)求的字的信息塊傳送到送到M M1 1，之后，之后CPUCPU才可在才可在M M1 1中訪問到這個(gè)字。假設(shè)傳遞一中訪問到這個(gè)字。假設(shè)傳遞一個(gè)信息塊所需的時(shí)間為個(gè)信息塊所需的時(shí)間為T TB B, ,則不命中的訪問時(shí)間為則不命中的訪問時(shí)間為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發(fā)出訪問請(qǐng)求到把整個(gè)數(shù)據(jù)塊調(diào)發(fā)出訪問請(qǐng)求到把整個(gè)數(shù)據(jù)塊調(diào)入入M M1 1中所需的時(shí)間。中所需的時(shí)間。T TM M常稱為常稱為失效開銷失效開銷。根據(jù)以上分析可知根據(jù)以上分析可知 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 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)n4.1.3 “Cache主存主存”和和“主存輔

10、存主存輔存”層次層次n從主存的角度來看從主存的角度來看 “CacheCache主存主存”層次：彌補(bǔ)主存速度的不足層次：彌補(bǔ)主存速度的不足 “主存輔存主存輔存”層次：層次： 彌補(bǔ)主存容量的不足彌補(bǔ)主存容量的不足1. 1. “CacheCache主存主存”層次層次 主存與主存與CPUCPU的速度差距的速度差距4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)3. “3. “主存輔存主存輔存”層次層次4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)層次存儲(chǔ)層次CPU對(duì)第二級(jí)的對(duì)第二級(jí)的訪問方式訪問方式比較項(xiàng)目比較項(xiàng)目目的目的存儲(chǔ)管理實(shí)

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

12、.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.1.4 存儲(chǔ)層次的四個(gè)問題存儲(chǔ)層次的四個(gè)問題當(dāng)把一個(gè)塊調(diào)入高一層當(dāng)把一個(gè)塊調(diào)入高一層(靠近靠近CPU)存儲(chǔ)器時(shí)，存儲(chǔ)器時(shí)，可以放在哪些位置上可以放在哪些位置上? (映象規(guī)則映象規(guī)則)當(dāng)所要訪問的塊在高一層存儲(chǔ)器中時(shí)，如何當(dāng)所要訪問的塊在高一層存儲(chǔ)器中時(shí)，如何找到該塊找到該塊? (查找算法查找算法)3. 當(dāng)發(fā)生失效時(shí)，應(yīng)替換哪一塊？當(dāng)發(fā)生失效時(shí)，應(yīng)替換哪一塊？ (替換算法替換算法)4. 當(dāng)進(jìn)行寫訪問時(shí)，應(yīng)進(jìn)行哪些操作當(dāng)進(jìn)行寫訪問時(shí)，應(yīng)進(jìn)行哪些操作? (寫策略寫策略)1. 2.第第4章章 存儲(chǔ)層次存儲(chǔ)層次n4.2 Cache基本知識(shí)基本知識(shí)nCache是按

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

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

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

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

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

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

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

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

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

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

23、2 Cache基本知識(shí)基本知識(shí) 并行查找的實(shí)現(xiàn)方法：并行查找的實(shí)現(xiàn)方法：舉例：舉例： 路組相聯(lián)并行標(biāo)識(shí)比較路組相聯(lián)并行標(biāo)識(shí)比較 （比較器的個(gè)數(shù)及位數(shù)）（比較器的個(gè)數(shù)及位數(shù)）l 相聯(lián)存儲(chǔ)器相聯(lián)存儲(chǔ)器l 單體多字存儲(chǔ)器比較器單體多字存儲(chǔ)器比較器 4.2 Cache基本知識(shí)基本知識(shí)主存塊地址： 目錄表（標(biāo)識(shí)存儲(chǔ)器）4.2 Cache基本知識(shí)基本知識(shí)4.2 Cache基本知識(shí)基本知識(shí)4.2 Cache基本知識(shí)基本知識(shí)4.2.3 替換算法替換算法 所要解決的問題：當(dāng)要從主存調(diào)入一個(gè)塊到所要解決的問題：當(dāng)要從主存調(diào)入一個(gè)塊到Cache中時(shí)，中時(shí)，會(huì)出現(xiàn)該塊所映象到的一組（或一個(gè)）會(huì)出現(xiàn)該塊所映象到的一組（

24、或一個(gè)）Cache塊已全被占?jí)K已全被占用的情況。這時(shí)需強(qiáng)迫騰出其中的某一塊，以接納新調(diào)入用的情況。這時(shí)需強(qiáng)迫騰出其中的某一塊，以接納新調(diào)入的塊。那么應(yīng)該替換哪一塊？的塊。那么應(yīng)該替換哪一塊？1. 隨機(jī)法隨機(jī)法為了均勻使用一組中的各塊，隨機(jī)地選擇被替為了均勻使用一組中的各塊，隨機(jī)地選擇被替換的塊。有些系統(tǒng)采用偽隨機(jī)數(shù)法產(chǎn)生塊號(hào)。換的塊。有些系統(tǒng)采用偽隨機(jī)數(shù)法產(chǎn)生塊號(hào)。特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，但反映不了程序的局部性。特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，但反映不了程序的局部性。2. 先進(jìn)先出法（先進(jìn)先出法（FIFO）選擇最早調(diào)入的塊作為被替換的塊。選擇最早調(diào)入的塊作為被替換的塊。特點(diǎn)：容易實(shí)現(xiàn)。還是不能正確地反映程序的特點(diǎn)：容

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

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

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

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

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

30、解決的問題。至于何時(shí)更新，這正是寫策略要解決的問題。4.2 Cache基本知識(shí)基本知識(shí)兩種寫策略兩種寫策略寫策略是區(qū)分不同Cache設(shè)計(jì)方案的一個(gè)重要標(biāo)志。 寫直達(dá)法寫直達(dá)法 執(zhí)行執(zhí)行“寫寫”操作時(shí)，不僅寫入操作時(shí)，不僅寫入Cache，而且，而且 也寫入下一級(jí)存儲(chǔ)器。也寫入下一級(jí)存儲(chǔ)器。 寫回法寫回法 執(zhí)行執(zhí)行“寫寫”操作時(shí)，只寫入操作時(shí)，只寫入Cache。僅當(dāng)。僅當(dāng) Cache中相應(yīng)的塊被替換時(shí)，才寫回主存。中相應(yīng)的塊被替換時(shí)，才寫回主存。 (設(shè)置設(shè)置“污染位污染位”)4.2 Cache基本知識(shí)基本知識(shí)兩種寫策略的比較兩種寫策略的比較 寫直達(dá)法的優(yōu)點(diǎn)：寫直達(dá)法的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，一致性好。易于

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

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

33、 不按寫分配不按寫分配(繞寫法繞寫法) 寫失效時(shí)，直接寫入下一級(jí)存儲(chǔ)器而不調(diào)塊。寫失效時(shí)，直接寫入下一級(jí)存儲(chǔ)器而不調(diào)塊。4.2 Cache基本知識(shí)基本知識(shí)n4.2.5 Cache的結(jié)構(gòu)的結(jié)構(gòu) 例子：例子：DECDEC的的Alpha AXP21064Alpha AXP21064中的內(nèi)部數(shù)據(jù)中的內(nèi)部數(shù)據(jù)CacheCache1. 簡(jiǎn)介 容量：容量：8KB8KB 塊大小：塊大?。?2B32B 塊數(shù)：塊數(shù)：256256 映象方法：映象方法：直接映象直接映象 “寫寫”策略：策略：寫直達(dá)寫直達(dá) 采用采用不按寫分配不按寫分配 寫緩沖器大?。簩懢彌_器大小：4 4個(gè)塊個(gè)塊4.2 Cache基本知識(shí)基本知識(shí)2. 結(jié)

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

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

36、eCache：指令和數(shù)據(jù)混合指令和數(shù)據(jù)混合CacheCache。若流水線中同時(shí)請(qǐng)求一個(gè)數(shù)據(jù)字和一個(gè)指令字，會(huì)出若流水線中同時(shí)請(qǐng)求一個(gè)數(shù)據(jù)字和一個(gè)指令字，會(huì)出現(xiàn)沖突，導(dǎo)致現(xiàn)沖突，導(dǎo)致CPUCPU等待。等待。分離分離CacheCache：分為指令分為指令CacheCache和數(shù)據(jù)和數(shù)據(jù)CacheCache兩個(gè)兩個(gè)CacheCache。Alpha AXP21064Alpha AXP21064有一個(gè)有一個(gè)8KB8KB的指令的指令CacheCache，其結(jié)構(gòu)與，其結(jié)構(gòu)與8KB8KB的數(shù)據(jù)的數(shù)據(jù)CacheCache幾乎一樣。幾乎一樣。CPUCPU知道它發(fā)出的地址是指令地址還是數(shù)據(jù)地址，因此知道它發(fā)出的地址

37、是指令地址還是數(shù)據(jù)地址，因此可以為它們?cè)O(shè)置不同的端口，這樣就會(huì)加倍對(duì)存儲(chǔ)系可以為它們?cè)O(shè)置不同的端口，這樣就會(huì)加倍對(duì)存儲(chǔ)系統(tǒng)和統(tǒng)和CPUCPU之間數(shù)據(jù)通道帶寬的要求。由于系統(tǒng)對(duì)指令和之間數(shù)據(jù)通道帶寬的要求。由于系統(tǒng)對(duì)指令和數(shù)據(jù)的操作特性不同，獨(dú)立的指令數(shù)據(jù)的操作特性不同，獨(dú)立的指令CacheCache和數(shù)據(jù)和數(shù)據(jù)CacheCache使我們能分別對(duì)它們進(jìn)行優(yōu)化，它們各自采用不同的使我們能分別對(duì)它們進(jìn)行優(yōu)化，它們各自采用不同的容量、塊大小和相聯(lián)度時(shí)的性能可能會(huì)更好。容量、塊大小和相聯(lián)度時(shí)的性能可能會(huì)更好。4.2 Cache基本知識(shí)基本知識(shí)16 KB16 KB容量容量1 KB1 KB2 KB2 KB4

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

39、4.2 Cache基本知識(shí)基本知識(shí)分離分離Cache平均失效率的計(jì)算：平均失效率的計(jì)算：訪問指令訪問指令Cache的百分比的百分比指令指令Cache的失效率的失效率訪問數(shù)據(jù)訪問數(shù)據(jù)Cache的百分比的百分比數(shù)據(jù)數(shù)據(jù)Cache的失效率的失效率4.2.6 Cache性能分析性能分析失效率失效率n與硬件速度無關(guān)，用它來評(píng)價(jià)存儲(chǔ)系統(tǒng)的性能非常與硬件速度無關(guān)，用它來評(píng)價(jià)存儲(chǔ)系統(tǒng)的性能非常方便方便,所以經(jīng)常會(huì)用到它。所以經(jīng)常會(huì)用到它。n容易產(chǎn)生一些誤導(dǎo)：一種更好的評(píng)測(cè)存儲(chǔ)系統(tǒng)性能容易產(chǎn)生一些誤導(dǎo)：一種更好的評(píng)測(cè)存儲(chǔ)系統(tǒng)性能的指標(biāo)是平均訪存時(shí)間。的指標(biāo)是平均訪存時(shí)間。平均訪存時(shí)間平均訪存時(shí)間 平均訪存時(shí)間平

40、均訪存時(shí)間 命中時(shí)間失效率命中時(shí)間失效率失效開銷失效開銷4.2 Cache基本知識(shí)基本知識(shí)n例例5.15.1 假設(shè)假設(shè)CacheCache的命中時(shí)間為的命中時(shí)間為1 1個(gè)時(shí)鐘周期，失效開銷個(gè)時(shí)鐘周期，失效開銷為為50 50 個(gè)時(shí)鐘周期，在混合個(gè)時(shí)鐘周期，在混合CacheCache中一次中一次loadload或或storestore操操作訪問作訪問CacheCache的命中時(shí)間都要增加一個(gè)時(shí)鐘周期的命中時(shí)間都要增加一個(gè)時(shí)鐘周期( (因?yàn)橐驗(yàn)榛旌匣旌螩acheCache只有一個(gè)端口，無法同時(shí)滿足兩個(gè)請(qǐng)求。流只有一個(gè)端口，無法同時(shí)滿足兩個(gè)請(qǐng)求。流水線中，混合水線中，混合CacheCache會(huì)導(dǎo)致結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

50、以下假設(shè)： (1) (1)理想理想CacheCache（命中率為（命中率為100%100%）情況下的）情況下的CPICPI為為2.02.0，時(shí)鐘周期為時(shí)鐘周期為2ns2ns，平均每條指令訪存，平均每條指令訪存1.31.3次。次。 (2) (2)兩種兩種CacheCache容量均為容量均為64KB64KB，塊大小都是，塊大小都是3232字節(jié)。字節(jié)。 (3) (3)下圖說明，在組相聯(lián)下圖說明，在組相聯(lián)CacheCache中，必須增加一個(gè)多路中，必須增加一個(gè)多路選擇器，用于根據(jù)標(biāo)識(shí)匹配結(jié)果從相應(yīng)組的塊中選擇所需選擇器，用于根據(jù)標(biāo)識(shí)匹配結(jié)果從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。因?yàn)榈臄?shù)據(jù)。因?yàn)镃PUCPU的速

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

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

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

54、 2路路 ICIC(2.0(2.02 21.101.10(1.3(1.30.0100.01070)70) 5.315.31ICIC5.315.31ICICCPUCPU時(shí)間時(shí)間1 1路路 1.011.015.275.27ICICCPUCPU時(shí)間時(shí)間2 2路路和平均訪存時(shí)間的比較結(jié)果相反，直接映象和平均訪存時(shí)間的比較結(jié)果相反，直接映象CacheCache的的平均性能好一些，這是因?yàn)樵趦陕方M相聯(lián)的情況下，平均性能好一些，這是因?yàn)樵趦陕方M相聯(lián)的情況下，雖然失效次數(shù)減少了，但所有指令的時(shí)鐘周期時(shí)間都雖然失效次數(shù)減少了，但所有指令的時(shí)鐘周期時(shí)間都增加了增加了10%10%。由于。由于CPUCPU時(shí)間是我們進(jìn)

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

56、用于降低失效率n5 5種種用于減少失效開銷用于減少失效開銷n4 4種種用于減少命中時(shí)間用于減少命中時(shí)間 4.2 Cache基本知識(shí)基本知識(shí)寫緩沖合并寫緩沖合并第第4章章 存儲(chǔ)層次存儲(chǔ)層次n4.3 降低降低Cache失效率的方法失效率的方法n三種失效三種失效(3C C)n強(qiáng)制性失效強(qiáng)制性失效( (C Compulsory miss)ompulsory miss)n當(dāng)?shù)谝淮卧L問一個(gè)塊時(shí)，該塊不在當(dāng)?shù)谝淮卧L問一個(gè)塊時(shí)，該塊不在CacheCache中，需從中，需從下一級(jí)存儲(chǔ)器中調(diào)入下一級(jí)存儲(chǔ)器中調(diào)入CacheCache，這就是強(qiáng)制性失效。，這就是強(qiáng)制性失效。 ( (冷啟動(dòng)冷啟動(dòng)失效，首次訪問失效失效，

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

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

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

60、失效：強(qiáng)制性失效：增加塊大小，預(yù)取增加塊大小，預(yù)?。ū旧砗苌伲ū旧砗苌伲﹏容量失效：容量失效：增加容量增加容量 （抖動(dòng)現(xiàn)象）（抖動(dòng)現(xiàn)象）n沖突失效：沖突失效：提高相聯(lián)度提高相聯(lián)度（理想情況：全相聯(lián)）（理想情況：全相聯(lián)）n許多降低失效率的方法會(huì)增加命中時(shí)間或失效開銷許多降低失效率的方法會(huì)增加命中時(shí)間或失效開銷4.3 降低降低Cache失效率的方法失效率的方法n4.3.1 增加增加Cache的容量的容量n降低降低cachecache失效率最直接的方法是增加失效率最直接的方法是增加CacheCache的容量的容量n缺點(diǎn)缺點(diǎn):n增加成本增加成本n可能增加命中時(shí)間可能增加命中時(shí)間n這種方法在片外這種方