第十講(cache存儲(chǔ)器)要點(diǎn)

1、第3章內(nèi)部存儲(chǔ)器iuosfiao6in201 q163. com(phone： 83#,辨主要內(nèi)容 cache基本原理cache存儲(chǔ)器組織替換策略與寫操作策略 奔騰pc機(jī)的cache,ccache基本原理根據(jù)訪存局部性原理，可以在主存和cpu之間設(shè)置一個(gè)高 速的容量相對較小的存儲(chǔ)器，如果當(dāng)前正在執(zhí)行的程序和數(shù)據(jù) 存放在這個(gè)存儲(chǔ)器中，在程序運(yùn)行時(shí)，不必從主存儲(chǔ)器取指令 和取數(shù)據(jù)，只需訪問這個(gè)高速存儲(chǔ)器，以提高程序運(yùn)行速度。 這個(gè)存儲(chǔ)器稱作高速緩沖存儲(chǔ)器cache。cache由高速的sram組成，它的工作速度數(shù)倍于主存， 全部功能由硬件實(shí)現(xiàn)，并且對程序員是透明的。cach

2、e的基本結(jié)構(gòu)它由cache存儲(chǔ)體、地址映象變換機(jī)構(gòu)、cache替換機(jī)構(gòu)cache概念:(1) cpu與主存儲(chǔ)器之間的一種高速緩沖裝置(2) cache-主存層次結(jié)構(gòu)：由硬件變換地址和控制調(diào)度。cache具有如下特點(diǎn)： 位于cpu與主存之間，是存儲(chǔ)器層次結(jié)構(gòu)中級別最高的一 級； 容量比主存小，目前一般有數(shù)kb到數(shù)mb；it 速度一般比主存快5-10倍,通常由存儲(chǔ)速度高的sram組成； 其內(nèi)容是主存的部分副本； 其用途可用來存放指令，也可用來存放數(shù)據(jù)； 快存的功能全部由硬件實(shí)現(xiàn)，并對程序員透明。任何時(shí)候都有一些主存塊處在cache中。當(dāng)cpu發(fā)出讀請求時(shí)，將主存地址s位(或s位中的一部分) 與ca

3、che某塊的標(biāo)記相比較，根據(jù)其比較結(jié)果是否相等而區(qū)分 出兩種情況： (1)當(dāng)比較結(jié)果相等時(shí)，說明需要的數(shù)據(jù)已在cache中，那么 直接訪問cache就行了，在cpu與cache之間，通常一次傳送 一個(gè)字； 當(dāng)比較結(jié)果不相等時(shí)，說明需要的數(shù)據(jù)尚未調(diào)入cache,那么就要把該數(shù)據(jù)所在的整個(gè)字塊從主存一次調(diào)進(jìn)來。前一種情況稱為訪問cache命中，后一種情況稱為訪問?!?!cache不命中。cache的命中率命中率指cpu所要訪問的信息在cache中的比率； 而將所要訪問的信息不在cache中的比率稱為失效率。增加cache的目的，就是在性能上使主存的平均讀出 時(shí)間盡可能接近c(diǎn)ache的讀出時(shí)間。因此

4、,cache的命中率應(yīng) 接近于1。由于程序訪問的局部性，這是可能的。在一個(gè)程序執(zhí)行期間：設(shè)m表示cache完成存取的總次數(shù)， nm表示主存完成存取的總次數(shù)， h定義為命中率，則有：h=nc/nc+nm若l表示命中時(shí)的cache訪問時(shí)間，上表示未命中時(shí)的主存訪問時(shí)間，lh表示不命中率，則cache/主存系統(tǒng)的平均訪問時(shí)間為：ta=htc+(l-h)tm我們追求的目標(biāo)是:以較小的硬件代價(jià)使cache/主存系統(tǒng)的平均訪問時(shí)間越接近l越好。設(shè)r=tn/tc表示主存慢于cache的倍率， e表示訪問效率，則有：e=tc/ta=tc/htc+(l-h)tm=l/r+(l-r)h=l/h+(l-h)rit為

5、提高訪問效率：命中率h越接近1越好，r值以510為宜，不宜太大。ev命中率h與程序的行為、cache的容量、組織方式、 塊的大小有關(guān)。e3ea例cpu執(zhí)行一段程序時(shí)，cache完成存取的次數(shù)為1900次，主 存完成存取的次數(shù)為100次，已知cache存取周期為50ns,主存 存取周期為250ns,求cache/主存系統(tǒng)的效率和平均訪問時(shí)間。解：h=nc/(nc+nm)=1900/(1900+100)=0.95r=tm/t =250ns/50ns=5in ce=u(r+(l-r)h)=l/(5+(l-5) x 0.95)=83.3%sata=tje=50ns/0.833=60ns例:已知cach

6、e存儲(chǔ)周期為40ns,主存存儲(chǔ)周期為200ns, cache / 主存系統(tǒng)平均訪問時(shí)間為50ns,求cache的命中率是多少？解：因?yàn)?ta=htc+(l-h)tm所以 h=(ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16cache結(jié)構(gòu)設(shè)計(jì)必須解決的問題:如何存放，如何訪問，如何替換，如何改寫?111（1）數(shù)據(jù)塊在cache中存放在哪個(gè)位置？即定位問題（地址 映象）o如果一個(gè)塊存放在某一cache中，怎樣確定并找到該 塊，即尋址問題（地址變換）。（2）不命中時(shí)將從主存儲(chǔ)器中訪問，并將該塊調(diào)入cache中，即替換問題。但是如果cache中已無空閑空間，則勢必將cac

7、he中的某一塊 調(diào)出，但應(yīng)調(diào)出那一塊（3）在寫訪問時(shí)，寫入cache必須在適當(dāng)?shù)臅r(shí)候?qū)懟刂鞔鎯?chǔ) 器，何時(shí)寫？寫操作時(shí)釆用什么策略保證兩級存儲(chǔ)器間的數(shù)據(jù) 一致性。寫操作失配時(shí)是否將訪問塊取入高層存儲(chǔ)器。本講主要內(nèi)容 cache基本原理cache存儲(chǔ)器組織替換策略與寫操作策略 奔騰pc機(jī)的cache,c地址映象（映射）與地址變換地址映象把主存塊按照某種規(guī)則（函數(shù)或方法）裝入或定位到 cache中的過程稱地址映象。地址變換ci信息按這種映象關(guān)系裝入cache后，執(zhí)行程序時(shí)，將主存 地址變換成cache地址的變換過程叫做地址變換。地址映象和變換密切相關(guān)。使用cache的動(dòng)力在于它的高速，因此也要求這個(gè)

8、地址變 換過程盡可能地快，故此過程是以硬件完成的。這帶來的另一 好處是cache的透明性，除了程序運(yùn)行速度提高之外，用戶包 括系統(tǒng)軟件編制人員，絲毫未感覺到cache的存在?；镜牡刂酚诚蠓绞剑褐苯佑诚螅蝗噙B映象；組相連映象在高速緩沖存儲(chǔ)器中，把cache和主存機(jī)械等分為相同大小的塊,每一塊是由若干個(gè)字（或字節(jié)）組成o例：某機(jī)主存容量為1mb,劃分為2048塊，每塊512b;cache容量為kb,劃分為16塊,每塊512b。cache標(biāo)記標(biāo)記塊15塊jsz.字 511主存由于cache的塊數(shù)遠(yuǎn)小于主存的塊數(shù)，因此一個(gè)cache不能 唯一地、永久地只對應(yīng)一個(gè)貯存塊，在cache中，每一塊外加有

9、 一個(gè)標(biāo)記，指明它是主存的哪一塊的副本（拷貝）。標(biāo)記的有效位每個(gè)標(biāo)記設(shè)置有一個(gè)有效位。機(jī) 器加電啟動(dòng)時(shí)，reset信號(hào)將所有標(biāo)記 的有效位置即無效。程序執(zhí)行 過程中，cache不命申時(shí)，逐步輜指 令塊或數(shù)據(jù)塊從主存調(diào)入cache中的 某一塊，并將這一塊標(biāo)記的有效位置 “1”，當(dāng)再次用到這一塊中的指令或 數(shù)據(jù)時(shí)，可直接從cache中取指令或 數(shù)據(jù)。標(biāo)記 cache0 u_ zt, v牙-口字塊0字塊1ew因剛加電時(shí)所有標(biāo)記位都為開始執(zhí)行程序時(shí), 命中率較低。另外cache的命中率還與程序本身有關(guān)，即 不同的程序，其命中率可能不同。直接映射方式這是一種多對一的映射關(guān)系，但一個(gè)主存塊只能映象到 ca

10、che的一個(gè)特定塊位置上去。cache的第i塊和主存的第j塊有如下函數(shù)關(guān)系：i = j mod mi =0,l,2,.,mlj=0,l,2,.,nl（m為cache的總塊數(shù)）在這種映象方式中：主存的第0塊，第16塊，第32塊，只能映象到 cache的第0塊；iii主存的第1塊，第17塊，第33塊，只能映象到 cache的第1塊；塊15tag cache主存地址cache地址cache塊號(hào)塊內(nèi)地址主存地址主存標(biāo)記包a號(hào)）cache塊號(hào)塊內(nèi)地址iii直接映象的地址變換方法 9位主存標(biāo)記（組號(hào)）cache塊號(hào)塊內(nèi)地址主存地址主存塊31不命中塊15塊16塊17比較塊 2047優(yōu)點(diǎn):硬件簡單,成本低缺點(diǎn)

11、:塊沖突率很高ill優(yōu)點(diǎn):實(shí)現(xiàn)簡單，只需利用主存地址按某些字段直接判斷，即可確定所需字塊是否已在cache中。缺點(diǎn):不夠靈活，主存的多個(gè)字塊只能對應(yīng)唯一的cache字塊，因此，即使cache別的地址空著也不 能占用。cache存儲(chǔ)空間得不到充分利用，降低 了命中率。例上設(shè)有一個(gè)cache的容量為2k字，每個(gè)塊為項(xiàng)字,求(1) 該cache可容納多少個(gè)塊？(2) 如果主存的容量是256k字，則有多少個(gè)塊？(3) 主存的地址有多少位？ cache地址有多少位？ha(4) 在直接映象方式下，主存中的第i塊映象到cache中哪一個(gè)塊 中？(5) 進(jìn)行地址映象時(shí)，存儲(chǔ)器的地址分成哪幾段？各段分別有 多少

12、位？ 解：(1) cache中有2048/16=128個(gè)塊。(2) 主存有256k/16=16384個(gè)塊。(3) cache容量為2k=2n字，所以cache字地址為11位。(4) 主存中的第i塊映象到cache中第imod 128個(gè)塊中。(5) 存儲(chǔ)器的字地址分成三段：區(qū)號(hào)、塊號(hào)、塊內(nèi)字地址。區(qū)號(hào)的長度為18.11=7位，塊號(hào)為7位。塊內(nèi)字地址為4位。允許主存中的每一個(gè)字塊映象到cache的任何一個(gè)字塊位置上:靈活但成本】:高的一種方式。31!全相聯(lián)映象的地址變換方法11位主存塊號(hào)塊內(nèi)地址主存地址不命中有效位塊。有效位塊1111有效位塊15主存塊0塊 1.塊15塊16塊17塊31. . .塊

13、 2047命中這只是一個(gè)理想的方案。兩個(gè)原因使其實(shí)際上很少釆用: 標(biāo)記位數(shù)從7位增加到11位，使cache標(biāo)記容量加大。=1 訪問cache時(shí)，需要和cache的全部標(biāo)記進(jìn)行“比較”才 能判斷出所訪主存地址的內(nèi)容是否已在cache中。由于cache 速度要求高，通常由“按內(nèi)容尋址”的相聯(lián)存儲(chǔ)器完成，所 需硬件邏輯電路很多，以至于無法用于cache中。實(shí)際的 cache組織則是釆取各種措施來減少所需比較的地址數(shù)目。優(yōu)點(diǎn)：靈活，塊沖突概率小。只有當(dāng)cache中全部裝滿后，才 有可能出現(xiàn)塊沖突；1=缺點(diǎn)：要作相聯(lián)搜索，速度慢，代價(jià)高。組相聯(lián)映射方式1、組間全相聯(lián)，組內(nèi)直接映像直接 映象和全 相聯(lián)映象

14、 方袞的一 種折衷方 案。tag標(biāo)記cache標(biāo)記塊0標(biāo)記塊11.標(biāo)記塊7標(biāo)記標(biāo)記塊71組v塊0塊1 塊7塊8塊9 塊15.塊 2032塊 2033 塊 2039塊 2040 塊 2046塊 2047。組, 1組、254組255組cache組號(hào)塊號(hào)塊內(nèi)地址1位3位9主存組號(hào)塊號(hào)塊內(nèi)地址注意：當(dāng)只有一個(gè)組并且每組16塊時(shí)，此時(shí)為直接映像; 當(dāng)有16組并且每組一個(gè)塊時(shí)，則為全相聯(lián)映像。內(nèi)存tv塊0tv塊1tv塊2tv塊3tvtv塊5tv塊6tv塊7塊0塊8塊1塊9 xx 6塊7塊15 塊2040 塊2047組相聯(lián)的地址變換方法8位 3位 9位主存中的一塊能對應(yīng)到cache中一個(gè)特定組中的任意一 行

15、上。若組中有n個(gè)塊，則稱其為n路組關(guān)聯(lián)。n個(gè)直接映射cache并行工作。直接映象和全相聯(lián)映象是組相聯(lián)的特例：直接映象是：1路組相聯(lián) 全相聯(lián)是：m路組相聯(lián)另外一種組相聯(lián)映射方式2、組內(nèi)全相聯(lián)，組間直接映像all!cache與主存均分組，主存中一個(gè)組內(nèi)的塊數(shù)與cache的分 組數(shù)相同，主存中的各塊與cache的組號(hào)有固定的映象關(guān)系，但可自由映象到對應(yīng)的cache組中任一塊。注意：當(dāng)只有一個(gè)組并且每組16塊時(shí)，此時(shí)為全相聯(lián)映像;當(dāng)有16組并且每組一個(gè)塊時(shí)，則為直接映像。組相聯(lián)的地址變換方法主存組號(hào)塊號(hào)塊內(nèi)地址tv組0tv組1tv組2tv組3tv組4tv組5tv組6tv組7組0vt組1vt組2vt組3

16、vt組4vt組5vt組6vt組7vt1不命中比較=命中比較選擇器例:設(shè)一個(gè)cache中有8個(gè)塊,訪問主存進(jìn)行讀操作的塊地址序列 為22、26、22、26、16、4、16、18,求每次訪問后cache中的 內(nèi)容解:直接映象下cache訪問情況地址22命中與否不命中地址轉(zhuǎn)換關(guān)系22 mod 8=62622261616182不命中命中命中不命中不命中命中不命中26 mod 8=222 mod 8=626 mod 8=216 mod 8=04 mod 8=416 mod 8=018 mod直接映象的塊分配情況訪問順序12345678操作 調(diào)調(diào)命命調(diào) 調(diào)命替狀態(tài)進(jìn)進(jìn)中中進(jìn)進(jìn)中換cache容量與命中率ca

17、che的容量和塊的大小是影響cache的效率的重要因素。 一般來說，cache的存儲(chǔ)容量比主存的容量小得多；twfis容量超過但不能太小，太小會(huì)使命中率太低；建離必辭如礬盈髓課畑順量超過 魂觥將卿颱將髀容量不斷增大已由幾k 因此，cache容量是總成本價(jià)與命中率的折衷值。如：80386的主存最大容量為4g,與其配套的cache容量為 16kb或32kb,其命中率為95%。塊長與命中率塊長與命中率的關(guān)系更為復(fù)雜，它取決于程序的局部特 性。塊長的最優(yōu)值很難確定，通常：a每塊取4至8個(gè)可編址單位（字或字節(jié)）較好；也可取一個(gè)主存周期所能調(diào)出主存的信息長度。例如，cary-1的主存是16個(gè)交叉體，每個(gè)體

18、為單字寬，其指令cache的塊長為16個(gè)字；ibm 370/168機(jī)主存是4體交叉，每個(gè)體寬為64位（8個(gè)字），其cache塊長為32個(gè)字。本講主要內(nèi)容 cache基本原理cache存儲(chǔ)器組織替換策略與寫操作策略 奔騰pc機(jī)的cache,c替換策略當(dāng)一個(gè)新的主存塊要調(diào)入到cache,而允許存放此塊的行位 置都被其它主存塊占滿時(shí)，就要產(chǎn)生替換，因?yàn)閏ache工作原理 要求它應(yīng)盡量保存最新的數(shù)據(jù)。替換問題與cache的組織方式緊密相關(guān)對于釆用直接映射方式的cache來說： 因一個(gè)主存塊只有一個(gè)特定的行位置可存放，所以問題 解決很簡單，把此特定行位置上的原主存塊妥善處理后，換 出cache即可。(2

19、)對于全相聯(lián)的cache來說，它的全部行都是可被替換的特 定行；而組相聯(lián)的cache中同組各路的行都是可被替換的特定 行：這樣就要從允許存放新主存塊的若干特定行中選取一行 換出。2!如何選取就涉及到替換策略或稱替換算法的釆用。以硬件 實(shí)現(xiàn)的常用算法主要有以下三種o(1)先進(jìn)先出(fifo)算法1=1fifo (first in first out)算法是把一組中最先調(diào)入 cache的字塊替換出去，不需要隨時(shí)記錄各個(gè)字塊的使用情 況,所以實(shí)現(xiàn)容易，開銷小。(2) lru與lfu算法lru (least recently used)算法是將最近最少使用的行 換出。需要二維計(jì)數(shù)，實(shí)現(xiàn)復(fù)雜，速度慢。r

20、=lfu (least frequently used)算法是將最久未被訪問過 的行換出。方法：每行設(shè)置一個(gè)計(jì)數(shù)器，cache每命中一次，命中行計(jì)數(shù)器 清零，其它各行計(jì)數(shù)器增1,因此它是未訪問次數(shù)計(jì)數(shù)器。當(dāng) 需要替換時(shí)，比較各特定行的計(jì)數(shù)值，將計(jì)數(shù)值最大的行換出。 這種算法顯然保護(hù)了剛拷貝進(jìn)新數(shù)據(jù)的行，符合cache工作原 因而使cache有較高的命中率。(3)隨機(jī)替換ii隨機(jī)替換(random replacement)策略實(shí)際上是不要 什么算法，從特定的行位置中隨機(jī)地選取一行換出即可。這種策略以硬件實(shí)現(xiàn)最容易，而且速度也比前兩種策 略快。缺點(diǎn)是隨意換出的數(shù)據(jù)很可能馬上又要用，從而增加 了映射

21、次數(shù)，降低了命中率和cache的工作效率。但這個(gè)缺 點(diǎn)可以用增大cache的容量來克服，實(shí)驗(yàn)統(tǒng)計(jì)表明，隨機(jī)替 換策略的功效只是稍遜于前兩種策略。例：一訪cache的地址流為：23215245325 2,假設(shè)cache只有3塊(?)時(shí)間：123456789101112塊地址流：2321524532522222555旦333fifo33332225531114444替2調(diào)調(diào)命調(diào)替替替命命替222222223333lfu33旦5555旦551 ,1444222調(diào)調(diào)命調(diào)替命替命替替命命先進(jìn)先出替換策略訪問順序12345678地址塊號(hào)2h297643先進(jìn)先出替換方式下的cache內(nèi)容變化情況近期最久未使

22、用替換策略訪問順序地址塊號(hào)塊分配情況操作狀態(tài)調(diào)進(jìn)調(diào)進(jìn)命中調(diào)進(jìn)調(diào)進(jìn)替換替換替換最久未使用替換方式下的cache內(nèi)容變化情況寫操作策略 因?yàn)閏ache的內(nèi)容是部分主存內(nèi)容的副本，應(yīng)該與主存內(nèi) 容保持一致。而cpu對cache的寫入更改了cache內(nèi)容，如何 與主存內(nèi)容保持一致就有幾種寫操作工作方式可供選擇，統(tǒng) 稱為寫策略。寫回法(write.back)(1) cpu對cache寫命中時(shí)當(dāng)cpu對cache寫命中時(shí)，只修改cache的內(nèi)容不立即寫入 主存，只當(dāng)此行被換出時(shí)才寫回主存。對一cache行的多次寫命中都在cache中快速完成修改，只 是需被替換時(shí)才寫回速度較慢的主存，減少了訪問主存的次 數(shù)

23、從而提高了效率。方法：每個(gè)cache行必須配置一個(gè)修改位，以反映此行是否被 cpu修改過。當(dāng)某行被換出時(shí)，根據(jù)此行修改位為1還是為0, 決定是將該行內(nèi)容寫回主存還是簡單地棄之而不顧。(2) cpu對cache寫未命中時(shí)對于cache寫未命中，寫回法的處理是為包含欲寫字的主存 塊在cache分配一行,將此塊整個(gè)拷貝到cache后在cache中對其 進(jìn)行修改；拷貝主存塊時(shí)雖已讀訪問到主存，但此時(shí)并不對主 存塊修改，統(tǒng)一地將主存寫修改操作留待換出時(shí)進(jìn)行。(3)優(yōu)缺點(diǎn):寫cache與寫主存分開進(jìn)行方式可顯著減少寫主存次數(shù)，但 寫回法存在cache/主存不一致性的隱患。寫直達(dá)法(write-throug

24、h )也稱全寫法。當(dāng)cache寫命中時(shí)：cache與主存同時(shí)發(fā)生寫修改。這種策 略顯然較好地維護(hù)了 cache與主存的內(nèi)容一致性； (2)當(dāng)cache寫未命中時(shí)：直接向主存寫。但此時(shí)是否將修改過的主存塊取到cache,寫直達(dá)法有兩種選 擇： 一種是取主存塊到cache并為它分配一個(gè)行位置，稱為wtwa法(writethroughwithwriteallocate )；另一種是不取主存塊到cache,稱為wtnwa法(write-through-with. no-write-allocate )。(3)優(yōu)缺點(diǎn):寫直達(dá)法是寫cache與寫主存同步進(jìn)行，優(yōu)點(diǎn)是：cache每行無需設(shè)置一個(gè)修改位以及相

25、應(yīng)的判測邏輯； 缺點(diǎn)是：cachextcpu向主存的寫操作無高速緩存功能，降低了 cache的功效。80486處理器片內(nèi)cache釆用的就是寫直達(dá)法。寫一次法(writeonce)策略：寫一次法是一種基于寫回法又結(jié)合了寫直達(dá)法的寫策略, 即寫命中和寫未命中的處理與寫回法基本相同，只是第一次寫 命中時(shí)要同時(shí)寫入主存。應(yīng)用: ii這種策略主要用于某些處理器的片內(nèi)cache,例如pentium 處理器的片內(nèi)數(shù)據(jù)cache就釆用的是寫一次法。因?yàn)槠瑑?nèi)cache 寫命中時(shí)，寫操作就在cpu內(nèi)部高速完成，若沒有內(nèi)存地址 及其它指示信號(hào)送出，就不便于系統(tǒng)中的其它c(diǎn)ache監(jiān)聽(snoop) o在第一次片內(nèi)cache寫命中時(shí)，cpu要在總線 上啟動(dòng)一個(gè)存儲(chǔ)器寫周期。其它c(diǎn)ache監(jiān)聽到此主存塊地址及寫信號(hào)后，即可把它們各自保存可能有 的該塊拷貝及時(shí)作廢（無效處理）。爾后若有對片 內(nèi)cache此行的再次或多次寫命中，則按回寫法處理，無需再送出信號(hào)了。這樣雖然第一次寫命中時(shí)花費(fèi)了一個(gè)存儲(chǔ)周期，但對維護(hù)系統(tǒng)全部cache的一致性有利。而大多的cache寫操作不涉及到片外,對指令流水執(zhí)行有利。本講主要內(nèi)容 cache基本原理cache存儲(chǔ)器組織替換策略與寫操作策略ii奔騰pc機(jī)的cache奔騰pc機(jī)的cachepentium pc釆用兩級cache結(jié)構(gòu)m3m2安裝在主板上，其容量