第07章 72 高速緩沖存儲(chǔ)器

1、1/2917.2 7.2 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器cachecache 程序訪問(wèn)的局部性程序訪問(wèn)的局部性 對(duì)局部范圍的存儲(chǔ)器地址頻繁訪問(wèn)，而對(duì)對(duì)局部范圍的存儲(chǔ)器地址頻繁訪問(wèn)，而對(duì)此范圍以外的地址則訪問(wèn)甚少的現(xiàn)象。此范圍以外的地址則訪問(wèn)甚少的現(xiàn)象。 程序地址的分布本來(lái)就是連續(xù)的，再加上循環(huán)程序地址的分布本來(lái)就是連續(xù)的，再加上循環(huán) 程序段和子程序段要重復(fù)執(zhí)行多次，因此，對(duì)程序段和子程序段要重復(fù)執(zhí)行多次，因此，對(duì) 程序地址的訪問(wèn)自然地具有相對(duì)集中的傾向。程序地址的訪問(wèn)自然地具有相對(duì)集中的傾向。 cache cache存儲(chǔ)器工作原理存儲(chǔ)器工作原理 2/292 根據(jù)局部性原理，可在主存和根據(jù)局部性原

2、理，可在主存和CPUCPU之間設(shè)置一個(gè)之間設(shè)置一個(gè) 高速的容量相對(duì)較小的存儲(chǔ)器，如果當(dāng)前正在高速的容量相對(duì)較小的存儲(chǔ)器，如果當(dāng)前正在 執(zhí)行的程序和數(shù)據(jù)存放在這個(gè)存儲(chǔ)器中，則當(dāng)執(zhí)行的程序和數(shù)據(jù)存放在這個(gè)存儲(chǔ)器中，則當(dāng) 程序運(yùn)行時(shí)，不必從主存取指令和取數(shù)據(jù)，而程序運(yùn)行時(shí)，不必從主存取指令和取數(shù)據(jù)，而 訪問(wèn)這個(gè)高速存儲(chǔ)器即可，所以提高了程序的訪問(wèn)這個(gè)高速存儲(chǔ)器即可，所以提高了程序的 運(yùn)行速度，這個(gè)存儲(chǔ)器稱作運(yùn)行速度，這個(gè)存儲(chǔ)器稱作高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器。 cachecache介于介于CPUCPU和主存之間，它的工作速度數(shù)倍和主存之間，它的工作速度數(shù)倍 于主存，全部功能由硬件實(shí)現(xiàn)，并且對(duì)程序員于

3、主存，全部功能由硬件實(shí)現(xiàn)，并且對(duì)程序員 是是透明透明的。的。3/293 命中率：命中率：CPUCPU所要訪問(wèn)的信息所要訪問(wèn)的信息在在cachecache中的比率。中的比率。 通常用通常用“命中率命中率”來(lái)測(cè)量來(lái)測(cè)量cachecache的效率。的效率。 失效率：失效率：CPUCPU要訪問(wèn)的信息要訪問(wèn)的信息不在不在cachecache中的比率。中的比率。 影響影響cachecache效率的因素：效率的因素：cachecache的容量、塊的大的容量、塊的大 小、塊替換算法、程序本身。小、塊替換算法、程序本身。4/294 cache容量比主存的容量小得多，但不能太小，容量比主存的容量小得多，但不能太小

4、， 太小會(huì)使命中率太低；也沒(méi)有必要過(guò)大，過(guò)大太小會(huì)使命中率太低；也沒(méi)有必要過(guò)大，過(guò)大 不僅會(huì)增加成本，而且當(dāng)容量超過(guò)一定值后，不僅會(huì)增加成本，而且當(dāng)容量超過(guò)一定值后， 命中率隨容量的增加將不會(huì)有明顯地增長(zhǎng)。命中率隨容量的增加將不會(huì)有明顯地增長(zhǎng)。 隨著芯片價(jià)格的下降，隨著芯片價(jià)格的下降，cachecache的容量不斷增大，的容量不斷增大， 由幾十由幾十K K發(fā)展到幾百發(fā)展到幾百K K，甚至達(dá)到幾，甚至達(dá)到幾M M字節(jié)。字節(jié)。5/295 讀操作讀操作 命中：直接讀即可。命中：直接讀即可。 失效：需要從主存讀取新字塊調(diào)入失效：需要從主存讀取新字塊調(diào)入cache。調(diào)入時(shí)，若調(diào)入時(shí)，若cache已滿，則

5、必須去掉一個(gè)舊字塊，已滿，則必須去掉一個(gè)舊字塊，讓位于一個(gè)新字塊。這種替換應(yīng)遵循一定的規(guī)則，讓位于一個(gè)新字塊。這種替換應(yīng)遵循一定的規(guī)則，最好能使被替換的字塊是下一段時(shí)間內(nèi)估計(jì)最少最好能使被替換的字塊是下一段時(shí)間內(nèi)估計(jì)最少使用的。這些規(guī)則稱為使用的。這些規(guī)則稱為替換策略替換策略或或替換算法替換算法，由，由替換部件加以實(shí)現(xiàn)。替換部件加以實(shí)現(xiàn)。6/296 寫操作（字塊已在寫操作（字塊已在cache中時(shí)）中時(shí)）cache中保存的字塊是主存相應(yīng)字塊的一個(gè)副本。中保存的字塊是主存相應(yīng)字塊的一個(gè)副本。若程序執(zhí)行過(guò)程中要對(duì)該字塊的某個(gè)單元進(jìn)行若程序執(zhí)行過(guò)程中要對(duì)該字塊的某個(gè)單元進(jìn)行寫操作，如何保持寫操作，如何

6、保持cache與主存的一致性？與主存的一致性？ 有兩種寫入方式有兩種寫入方式 標(biāo)志交換方式（寫回法）標(biāo)志交換方式（寫回法） 通過(guò)式寫（寫直達(dá)法）通過(guò)式寫（寫直達(dá)法）7/297 暫時(shí)只向暫時(shí)只向cachecache存儲(chǔ)器寫入，并用標(biāo)志加以注明，存儲(chǔ)器寫入，并用標(biāo)志加以注明， 直到經(jīng)過(guò)修改的字塊被從直到經(jīng)過(guò)修改的字塊被從cachecache中替換出來(lái)時(shí)才中替換出來(lái)時(shí)才 一次寫入主存。一次寫入主存。 只有寫標(biāo)志只有寫標(biāo)志“置位置位”的字塊才有必要最后從的字塊才有必要最后從cachecache 存儲(chǔ)器一次寫回主存。存儲(chǔ)器一次寫回主存。(1) (1) 標(biāo)志交換方式（寫回法）標(biāo)志交換方式（寫回法） 特點(diǎn)：

7、特點(diǎn)：寫操作速度快，但在寫回以前，主存中的寫操作速度快，但在寫回以前，主存中的 字塊未經(jīng)隨時(shí)修改而可能失效。字塊未經(jīng)隨時(shí)修改而可能失效。8/298 每次寫入每次寫入cachecache時(shí)也同時(shí)寫入主存，使時(shí)也同時(shí)寫入主存，使cachecache和和 主存保持一致。主存保持一致。(2) (2) 通過(guò)式寫（寫直達(dá)法）通過(guò)式寫（寫直達(dá)法） 特點(diǎn)：特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單且隨時(shí)保持主存數(shù)據(jù)的正確性。實(shí)現(xiàn)簡(jiǎn)單且隨時(shí)保持主存數(shù)據(jù)的正確性。 但有可能要增加多次不必要的向主存的寫入。但有可能要增加多次不必要的向主存的寫入。 寫操作（字塊不在寫操作（字塊不在cache中時(shí)）中時(shí)） 直接對(duì)主存進(jìn)行寫入，而不寫入直接對(duì)主存進(jìn)

8、行寫入，而不寫入cache存儲(chǔ)器。存儲(chǔ)器。9/299 具有具有cachecache的存儲(chǔ)器的平均存取時(shí)間：的存儲(chǔ)器的平均存取時(shí)間： 設(shè)設(shè)cachecache的存取時(shí)間為的存取時(shí)間為tctc，命中率為，命中率為h h， 主存的存取時(shí)間為主存的存取時(shí)間為tMtM，則：，則：平均存取時(shí)間平均存取時(shí)間htc+(1-h)(tc+tM)htc+(1-h)(tc+tM)10/2910(1) 地址映像地址映像 地址映像：地址映像：為了把信息放到為了把信息放到cachecache存儲(chǔ)器中，存儲(chǔ)器中， 必須應(yīng)用某種函數(shù)把主存地址映像到必須應(yīng)用某種函數(shù)把主存地址映像到cachecache。2. cache2. ca

9、che存儲(chǔ)器組織存儲(chǔ)器組織 地址變換：地址變換：信息按照映像關(guān)系裝入信息按照映像關(guān)系裝入cachecache后，后， 執(zhí)行程序時(shí)將主存地址變換成執(zhí)行程序時(shí)將主存地址變換成cachecache地址的地址的 變換過(guò)程。變換過(guò)程。 映像函數(shù)：映像函數(shù)：決定主存地址和決定主存地址和cachecache地址的對(duì)應(yīng)地址的對(duì)應(yīng) 關(guān)系。關(guān)系。11/2911 假設(shè)：假設(shè)：主存空間被分為主存空間被分為Mm(0)Mm(0)、Mm(1)Mm(1)、Mm(2Mm(2m m-1)-1)共共2 2m m個(gè)塊，字塊大小為個(gè)塊，字塊大小為2 2b b個(gè)字；個(gè)字；cachecache存儲(chǔ)空間被分為存儲(chǔ)空間被分為Mc(0)Mc(0

10、)、Mc(1)Mc(1)、Mc(2Mc(2c c-1)-1)共共2 2c c個(gè)同樣大小的塊。個(gè)同樣大小的塊。12/2912 直接映像直接映像 直接映像函數(shù)為：直接映像函數(shù)為： j=i mod 2j=i mod 2c c 其中：其中： j j cachecache的字塊號(hào)；的字塊號(hào)； i i 主存的字塊號(hào)；主存的字塊號(hào)； 2 2c c cachecache的塊數(shù)。的塊數(shù)。 主存的每一塊都對(duì)應(yīng)主存的每一塊都對(duì)應(yīng)cachecache的某一固定塊；的某一固定塊； cachecache的每一塊都對(duì)應(yīng)主存的若干塊。的每一塊都對(duì)應(yīng)主存的若干塊。13/2913 主存地址格式為：主存地址格式為： 標(biāo)記位：標(biāo)記位

11、：指明指明cachecache中的某塊對(duì)應(yīng)于主存的中的某塊對(duì)應(yīng)于主存的 哪一塊（緩存也需加哪一塊（緩存也需加t t位標(biāo)記位）。位標(biāo)記位）。 cachecache塊號(hào)：塊號(hào)：指明指明cachecache中的塊地址。中的塊地址。 塊內(nèi)字地址：塊內(nèi)字地址：確定塊內(nèi)的字地址。確定塊內(nèi)的字地址。標(biāo)記位標(biāo)記位cachecache塊號(hào)塊號(hào)塊內(nèi)字地址塊內(nèi)字地址t t位位c c位位b b位位m m位位14/2914圖圖 直接映像直接映像cachecache組織組織15/2915 直接映像的特點(diǎn)：直接映像的特點(diǎn)： 實(shí)現(xiàn)簡(jiǎn)單，只需利用主存地址按某些字段實(shí)現(xiàn)簡(jiǎn)單，只需利用主存地址按某些字段 直接判斷，即可確定所需的字

12、塊是否已在直接判斷，即可確定所需的字塊是否已在 cachecache存儲(chǔ)器中。成本較低。存儲(chǔ)器中。成本較低。 不靈活，沒(méi)有好的塊替換算法（為什么）。不靈活，沒(méi)有好的塊替換算法（為什么）。16/2916 全相聯(lián)映像全相聯(lián)映像 主存的任一塊可映像到主存的任一塊可映像到cachecache的任一塊。的任一塊。標(biāo)記位標(biāo)記位塊內(nèi)字地址塊內(nèi)字地址t tc c位位b b位位m m位位 主存地址格式為：主存地址格式為： 緩存也需加緩存也需加t+ct+c位標(biāo)記位。位標(biāo)記位。17/2917圖圖 全相聯(lián)映像全相聯(lián)映像cachecache組織組織18/2918 全相聯(lián)映像的特點(diǎn)：全相聯(lián)映像的特點(diǎn)： 最靈活（為什么？）

13、。最靈活（為什么？）。 但成本最高。但成本最高。19/2919 組相聯(lián)映像組相聯(lián)映像 把把cachecache中的塊分成若干組，每組包含若干中的塊分成若干組，每組包含若干 塊。主存塊與塊。主存塊與cachecache組之間是組之間是直接映像直接映像，而，而 與組內(nèi)各塊之間是與組內(nèi)各塊之間是全相聯(lián)映像全相聯(lián)映像。 即：主存塊可映像到即：主存塊可映像到cachecache中某固定組中的中某固定組中的 任意塊。任意塊。 組相聯(lián)映像方式是直接映像和全相聯(lián)映像組相聯(lián)映像方式是直接映像和全相聯(lián)映像 方式的一種折衷方案。方式的一種折衷方案。20/2920 主存地址格式為：主存地址格式為： cachecach

14、e共共2 2C C塊，被分成塊，被分成2 2CC組，每組組，每組2 2r r個(gè)塊。個(gè)塊。 則：則：c cc+rc+r標(biāo)記位標(biāo)記位組地址組地址塊內(nèi)字地址塊內(nèi)字地址t+rt+r位位CC位位b b位位m m位位 當(dāng)當(dāng)r=0r=0時(shí)，為直接映像方式；時(shí)，為直接映像方式； 當(dāng)當(dāng)r=cr=c時(shí)，為全相聯(lián)映像方式。時(shí)，為全相聯(lián)映像方式。21/2921圖圖 組相聯(lián)映像組相聯(lián)映像cachecache組織組織22/2922 組相聯(lián)映像的特點(diǎn)：組相聯(lián)映像的特點(diǎn)： 性能與復(fù)雜性介于直接映像與全相聯(lián)映像性能與復(fù)雜性介于直接映像與全相聯(lián)映像 兩種方式之間。兩種方式之間。 較靈活且不難實(shí)現(xiàn)，最常用。較靈活且不難實(shí)現(xiàn)，最常用

15、。23/2923(1) 先進(jìn)先出先進(jìn)先出(FIFO)(FIFO)算法算法 當(dāng)新的主存字塊需要調(diào)入當(dāng)新的主存字塊需要調(diào)入cachecache，而它的可用，而它的可用 位置又已被占滿時(shí)，就產(chǎn)生替換算法問(wèn)題。位置又已被占滿時(shí)，就產(chǎn)生替換算法問(wèn)題。3. 3. 替換算法替換算法 總是把一組中最先調(diào)入總是把一組中最先調(diào)入cachecache的字塊替換出去。的字塊替換出去。 容易實(shí)現(xiàn)，開銷小。容易實(shí)現(xiàn)，開銷小。24/2924 FIFO舉例舉例 設(shè)：設(shè)：CPU對(duì)字塊的訪問(wèn)順序?yàn)閷?duì)字塊的訪問(wèn)順序?yàn)?，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。 若若cache的大小為的大小為3個(gè)字塊，求失效

16、率。個(gè)字塊，求失效率。7 01203042303212017 77222244400000000000333222221111111100033333222 共有共有12次不命中，失效率為次不命中，失效率為12/17=70.5%。25/2925(2) 近期最少使用近期最少使用(LRU)(LRU)算法（最常用）算法（最常用） 把一組中近期最少使用的字塊替換出去。把一組中近期最少使用的字塊替換出去。 平均命中率比平均命中率比FIFOFIFO要高，并且當(dāng)分組容量要高，并且當(dāng)分組容量 加大時(shí)，能提高加大時(shí)，能提高LRULRU替換算法的命中率。替換算法的命中率。 需隨時(shí)記錄需隨時(shí)記錄cachecache中各個(gè)字塊的使用情況，中各個(gè)字塊的使用情況， 以便確定哪個(gè)字塊是近期最少使用的字塊。以便確定哪個(gè)字塊是近期最少使用的字塊。26/2926圖圖 LRULRU算法替換登記表算法替換登記表27/2927(3) 隨機(jī)替換法隨機(jī)替換法(RAND)(RAND) 在組內(nèi)隨機(jī)選擇一塊替換。在組內(nèi)隨機(jī)選擇一塊替換。 不考慮使用情況，性能比根據(jù)使用情況的不考慮使用情況，性能比根據(jù)使用情況的 替換算法要差些。替換算法要差些。28/2928圖圖 具有具有cachecache