高速緩沖存儲(chǔ)器

（Cache）

高速緩沖存儲(chǔ)器(Cache)IntelPentium的CacheCorei7的Cache結(jié)構(gòu)32KL1I-cache32KL1D-cache256KL2Cache32KL1I-cache32KL1D-cache256KL2Cache32KL1I-cache32KL1D-cache256KL2Cache32KL1I-cache32KL1D-cache256KL2Cache8MBSharedL3Cache高速緩沖存儲(chǔ)器(Cache)硬盤(pán)上的cache磁盤(pán)CacheI/O總線(xiàn)主要內(nèi)容基本結(jié)構(gòu)與工作原理地址映像規(guī)則與地址變換替換算法與實(shí)現(xiàn)寫(xiě)策略Cache層次CPU-主存瓶頸高速計(jì)算機(jī)的性能通常受到主存帶寬和響應(yīng)時(shí)間的限制。

響應(yīng)時(shí)間(Latency)：一次訪(fǎng)存所需要的時(shí)間。

主存訪(fǎng)存時(shí)間>>處理器機(jī)器周期帶寬(bandwidth)：?jiǎn)挝粫r(shí)間內(nèi)的訪(fǎng)存次數(shù)。

假設(shè)每條指令需要一個(gè)機(jī)器周期，一條指令需要訪(fǎng)問(wèn)主存m次，意味著每個(gè)機(jī)器周期需要訪(fǎng)存m次。主存CPUCPU-主存瓶頸時(shí)間DRAM7%/年微處理器60%/年199919801981198319841985198619871988198919901991199219931994199519961997199820001982處理器-存儲(chǔ)器性能差距：50%/年擴(kuò)大1101001000性能CPU-主存瓶頸解決速度問(wèn)題方法：在CPU和主存之間設(shè)置速度快、容量小的高速緩沖存儲(chǔ)器(cache)。依據(jù)程序局部性原理，將未來(lái)要用到的指令或數(shù)據(jù)從低速主存預(yù)取到高速cache中，從而減少平均響應(yīng)時(shí)間，提高平均訪(fǎng)問(wèn)速度。程序局部性：程序在執(zhí)行時(shí)所用到的指令和數(shù)據(jù)的分布不是隨機(jī)的，而是相對(duì)簇聚的。它包括時(shí)間局部性和空間局部性。CPU-主存瓶頸時(shí)間局部性最近的未來(lái)要用到的信息可能就是當(dāng)前正在使用的信息——這是由程序的循環(huán)造成的?？臻g局部性最近的未來(lái)要用到的信息可能就是當(dāng)前信息的相鄰信息——這是由程序的順序執(zhí)行造成的?；窘Y(jié)構(gòu)和工作原理主存地址100中的數(shù)據(jù)副本主存地址101中的數(shù)據(jù)副本1004086848616數(shù)據(jù)字節(jié)數(shù)據(jù)字節(jié)數(shù)據(jù)字節(jié)…………塊行地址標(biāo)記Cache中緩存數(shù)據(jù)的基本結(jié)構(gòu)主存CPUCache主存地址主存地址數(shù)據(jù)數(shù)據(jù)基本結(jié)構(gòu)和工作原理Cache基本結(jié)構(gòu)主存/Cache

地址映象變換cache地址Cache替換策略替換塊裝入塊Cache已滿(mǎn)Cache未滿(mǎn)未命中命中數(shù)據(jù)送CPU主存地址，來(lái)自CPUCacheCPU儲(chǔ)器主存基本結(jié)構(gòu)和工作原理Cache工作原理：讀取將CPU給出的主存地址變換為cache地址，搜索cache在cache中找到（命中）在cache中未找到（未命中）1.從主存中讀取數(shù)據(jù)塊2.等待…3.向CPU返回?cái)?shù)據(jù),更新cache（滿(mǎn)時(shí)替換）訪(fǎng)問(wèn)cache，向CPU返回cache中的數(shù)據(jù)副本只要Cache的命中率足夠高，就能以接近于Cache的速度訪(fǎng)問(wèn)主存?；窘Y(jié)構(gòu)和工作原理Cache工作原理：寫(xiě)入將CPU給出的主存地址變換為cache地址，搜索cache在cache中找到（命中）在cache中未找到（未命中）寫(xiě)主存（與cache無(wú)關(guān)）寫(xiě)cache，寫(xiě)主存（存在一致性問(wèn)題）為保持cache與主存中的內(nèi)容一致，可以采取以下方法：寫(xiě)直達(dá)法寫(xiě)回法Cache特點(diǎn)Cache與CPU采用相同工藝；地址映象、變換、替換、調(diào)度等由專(zhuān)門(mén)的硬件實(shí)現(xiàn)；Cache靠近CPU或就放在CPU中，以減少與CPU之間的傳輸延遲；Cache—主存之間的信息交換對(duì)所有程序員都透明；Cache訪(fǎng)問(wèn)主存的優(yōu)先級(jí)高于其他系統(tǒng)訪(fǎng)問(wèn)主存的優(yōu)先級(jí)；除了Cache和CPU有直接的通路外，主存和CPU也有直接的通路，可以實(shí)現(xiàn)讀直達(dá)和寫(xiě)直達(dá)；Cache系統(tǒng)須解決的三個(gè)問(wèn)題1.定位問(wèn)題將主存中的數(shù)據(jù)裝入cache的哪個(gè)位置；如何知道主存中的數(shù)據(jù)已經(jīng)裝入cache（即是否命中）；如果命中，如何形成Cache地址并訪(fǎng)問(wèn)主存。2.替換問(wèn)題若未命中或失效，需將數(shù)據(jù)從主存調(diào)入Cache；若Cache滿(mǎn)，則按何種算法將Cache中的數(shù)據(jù)替換出去。3.數(shù)據(jù)一致性問(wèn)題如何保證Cache內(nèi)容與主存內(nèi)容的一致。地址映像規(guī)則與地址變換地址映像：

把主存中的數(shù)據(jù)按照某種規(guī)則裝入Cache中，并建立主存地址與Cache地址之間的對(duì)應(yīng)關(guān)系，進(jìn)而根據(jù)主存地址，判斷Cache有無(wú)命中并變換為Cache的地址。為便于進(jìn)行地址的映象和變換，也便于替換和管理，把Cache和主存等分成相同大小的塊，這樣，Cache—主存地址映像就演變?yōu)橹鞔嬷械膲K如何與Cache中的塊相對(duì)應(yīng)。地址映像規(guī)則與地址變換儲(chǔ)器主存當(dāng)cache和主存的字節(jié)數(shù)，以及塊數(shù)和塊內(nèi)字節(jié)數(shù)都是2的冪次時(shí)，地址好劃分。塊號(hào)b塊內(nèi)地址w塊號(hào)B塊內(nèi)地址WCache地址結(jié)構(gòu)塊0塊1塊2塊3Cache01234567891011121314151011101010011000111111101101110000110010000100000111011001010100地址124125126127主存0123456789101112131415……塊30塊31塊0塊1塊2塊3地址11111110001111000000000000010000010000001100100000000100…………主存地址結(jié)構(gòu)10111111111111100011110000000地址映像規(guī)則與地址變換可以采用的地址映象方法有很多。選擇依據(jù)：地址映象和變換硬件的速度是否高，價(jià)格是否低，實(shí)現(xiàn)是否容易；Cache空間的利用率是否高；塊沖突概率是否低；塊沖突：主存中的塊要調(diào)入Cache中的某個(gè)位置，但該位置已經(jīng)被其他主存塊所占用。地址映像規(guī)則與地址變換在Cache—主存存貯層次，典型的地址映象與變換方法主要有：1.全相聯(lián)映象與變換2.直接映象與變換3.組相聯(lián)映象與變換全相聯(lián)映像規(guī)則與變換映像規(guī)則：主存中的任意一塊都可以裝入到Cache中的任意一個(gè)塊位置。主存Cache0123塊號(hào)01234567塊號(hào)全相聯(lián)映像規(guī)則與變換地址變換：采用相聯(lián)存儲(chǔ)器構(gòu)成的目錄表，以硬件方式實(shí)現(xiàn)。主存地址Cache地址Cache…塊b…m塊Cache塊號(hào)…b…相聯(lián)比較=(命中)=?塊內(nèi)地址W塊號(hào)B塊內(nèi)地址w塊號(hào)b每塊一個(gè)表項(xiàng)目錄表(按內(nèi)容訪(fǎng)問(wèn))有效位1主存塊號(hào)…B…m行全相聯(lián)映像規(guī)則與變換優(yōu)點(diǎn)：塊沖突概率最低；Cache空間利用率最高。缺點(diǎn)：所需容量的相聯(lián)存貯器代價(jià)較高；Cache容量已經(jīng)很大，相聯(lián)查表速度難以提高。直接映像規(guī)則與變換映像規(guī)則：主存中的每一塊只能裝入到Cache內(nèi)唯一 一個(gè)指定的塊位置。主存Cache0123塊號(hào)01234567塊號(hào)為便于地址變換，設(shè)：Cache塊號(hào)b＝(主存塊號(hào)B)mod(cache塊數(shù))則：0=0|4mod4,1=1|5mod4,2=2|6mod4,3=3|7mod4一個(gè)Cache塊對(duì)應(yīng)多個(gè)主存塊直接映像規(guī)則與變換地址變換：若Cache塊號(hào)b＝(主存塊號(hào)B)mod(cache塊數(shù))，設(shè)cache塊數(shù)＝2k，當(dāng)表示為二進(jìn)制數(shù)時(shí)，Cache塊號(hào)b與主存塊號(hào)B的低k

位完全相同。塊內(nèi)地址主存地址Cache地址主存塊號(hào)Bk位塊內(nèi)地址塊號(hào)b區(qū)號(hào)區(qū)內(nèi)塊號(hào)意味著，只要從主存地址中取出低位部分，即可形成cache的地址。直接映像規(guī)則與變換地址變換：設(shè)置一個(gè)按地址訪(fǎng)問(wèn)的區(qū)表存貯器（稱(chēng)之為區(qū)號(hào)表），存放Cache中每一塊目前被主存中哪個(gè)區(qū)的對(duì)應(yīng)塊所占用。主存地址=(命中)Cache地址塊號(hào)b塊內(nèi)地址區(qū)號(hào)E塊內(nèi)地址區(qū)內(nèi)塊號(hào)Cache…塊b…m塊=?每塊一個(gè)表項(xiàng)區(qū)號(hào)表(按地址訪(fǎng)問(wèn))有效位1區(qū)號(hào)…E…m行直接映像規(guī)則與變換優(yōu)點(diǎn)所需硬件簡(jiǎn)單，成本較低；訪(fǎng)問(wèn)Cache可與訪(fǎng)問(wèn)區(qū)號(hào)表、比較區(qū)號(hào)等操作同時(shí)進(jìn)行，節(jié)省了地址變換時(shí)間。缺點(diǎn)塊沖突概率很高；Cache空間利用率很低。因此已經(jīng)很少使用。組相聯(lián)映像規(guī)則與變換映像規(guī)則：主存中的每一塊可以被裝入到Cache中 唯一一個(gè)組中的任何一個(gè)位置。為便于地址變換，可以采用如下映像算法：將整個(gè)Cache看成是一個(gè)區(qū)，將Cache分成G組（G=2g），每個(gè)組S塊（S=2s）；將主存分成2e個(gè)與Cache大小相同的區(qū)，每個(gè)區(qū)分成G組（G=2g），每個(gè)組S塊（S=2s）；Cache地址塊號(hào)(s位)塊內(nèi)地址組號(hào)(g位)主存地址塊號(hào)(s位)塊內(nèi)地址組號(hào)(g位)區(qū)號(hào)(e位)主存0123456789101112131415組0組1組2組3組0組1組2組3區(qū)0區(qū)1Cache01234567組0組1組2組3組間直接映像組內(nèi)全相聯(lián)映像主存塊可以裝入唯一cache組中的任何一個(gè)cache塊位置。組相聯(lián)映像規(guī)則與變換地址變換：組間直接映象采用按地址訪(fǎng)問(wèn)的區(qū)表存貯器（區(qū)號(hào)表），每組一行，共有G=2g行；區(qū)號(hào)表共G=2g行按地址訪(fǎng)問(wèn)…有效位區(qū)號(hào)+主存塊號(hào)…主存塊號(hào)區(qū)號(hào)組k組相聯(lián)映像規(guī)則與變換地址變換：組內(nèi)全相聯(lián)采用目錄表法，使用相聯(lián)存貯器每組都有一個(gè)目錄表，共有G=2g個(gè)目錄表；每個(gè)目錄表的行數(shù)為S=2s，每行對(duì)應(yīng)一個(gè)cache塊?！行粎^(qū)號(hào)+主存塊號(hào)…主存塊號(hào)區(qū)號(hào)區(qū)號(hào)表共G=2g行按地址訪(fǎng)問(wèn)組k目錄表共S=2s行按內(nèi)容訪(fǎng)問(wèn)組kS稱(chēng)為相聯(lián)度。每組有S塊的組相聯(lián)稱(chēng)為S路組相聯(lián)。組相聯(lián)映像規(guī)則與變換主存地址=(命中)Cache地址Cache…塊b…=?區(qū)號(hào)表(按地址訪(fǎng)問(wèn))有效位區(qū)號(hào)…目錄表…塊號(hào)(s位)塊內(nèi)地址組號(hào)(g位)塊號(hào)(s位)塊內(nèi)地址組號(hào)(g位)區(qū)號(hào)(e位)區(qū)號(hào)塊號(hào)……相聯(lián)比較01234567組0組1組2組3組相聯(lián)映像規(guī)則與變換實(shí)際上是全相聯(lián)映像和直接映像的折衷方案。當(dāng)S=Cache塊數(shù)，組相聯(lián)就變成了全相聯(lián)；當(dāng)S=1，組相聯(lián)變成了直接映象；S越大，沖突越少，地址變換就越復(fù)雜；S越小，沖突越多，地址變換就越容易。組相聯(lián)映像規(guī)則與變換012345670123Cache012345678911111111110123456789222222222201234567893301主存塊號(hào)組號(hào)全相聯(lián)2路組相聯(lián)直接相聯(lián)主存塊12可以裝入cache中的任意位置組2中的任意位置只能是塊4位置組相聯(lián)映像規(guī)則與變換優(yōu)點(diǎn)：塊沖突概率比直接映象低得多；Cache空間利用率也比直接映象提高；實(shí)現(xiàn)成本比全相聯(lián)映象要低得多；性能接近于全相聯(lián)映象。替換算法與實(shí)現(xiàn)所要解決的問(wèn)題：當(dāng)所要訪(fǎng)問(wèn)的主存塊不在cache中（稱(chēng)為塊失效），需新調(diào)入一個(gè)主存塊，而該塊能夠占用的Cache塊位置已被占滿(mǎn)時(shí)（稱(chēng)為塊沖突），將哪一個(gè)位置的主存塊替換出去。典型替換算法：1.隨機(jī)算法：隨機(jī)選取一塊進(jìn)行替換。2.FIFO算法：選取最早裝入的塊進(jìn)行替換。3.LRU算法：選取近期被CPU訪(fǎng)問(wèn)次數(shù)最少的塊進(jìn) 行替換。 優(yōu)點(diǎn)：比較正確地反映了程序的局部性，失效 率低。

常用替換算法與實(shí)現(xiàn)Cache容量相聯(lián)度2路4路8路LRU隨機(jī)LRU隨機(jī)LRU隨機(jī)16KB5.18%5.69%4.67%5.29%4.39%4.96%64KB1.88%2.01%1.54%1.66%1.39%1.53%256KB1.15%1.17%1.13%1.13%1.12%1.12%測(cè)試條件：塊大小=16字節(jié)，地址流=VAX流表LRU和隨機(jī)算法的失效率的比較從表中數(shù)據(jù)可以看出：LRU算法的失效率低于隨機(jī)算法。隨著Cache容量的增加，失效率降低。當(dāng)Cache容量較大時(shí)，LRU算法和隨機(jī)算法的失效率幾乎無(wú)差別。替換算法與實(shí)現(xiàn)LRU算法的實(shí)現(xiàn)：采用堆棧法，用硬件堆棧實(shí)現(xiàn)。被訪(fǎng)問(wèn)的塊(經(jīng)相聯(lián)比較找到)近期最近訪(fǎng)問(wèn)的塊近期最久未訪(fǎng)問(wèn)的塊將被替換的塊431526由寄存器構(gòu)成的堆?！?被訪(fǎng)問(wèn)的塊號(hào)70要訪(fǎng)問(wèn)的主存塊7已在Cache中時(shí)的情況替換算法與實(shí)現(xiàn)LRU算法的實(shí)現(xiàn)：采用堆棧法，用硬件堆棧實(shí)現(xiàn)。近期最近訪(fǎng)問(wèn)的塊近期最久未訪(fǎng)問(wèn)的塊將被替換的塊431526由寄存器構(gòu)成的堆棧…780要訪(fǎng)問(wèn)的主存塊8不在Cache中時(shí)的情況4寫(xiě)策略Cache－主存存貯層次對(duì)所有程序員透明。Cache內(nèi)容是主存內(nèi)容的一小部分副本，但Cache內(nèi)容有可能與主存內(nèi)容不一致。例如：CPU更新（寫(xiě)入）了Cache，但未更新主存；I/O更新（寫(xiě)入）了主存，但未更新Cache；CPUX’I/OXCache主存儲(chǔ)器(a)CPU寫(xiě)CacheCacheCPUX’I/OX主存儲(chǔ)器(b)I/O寫(xiě)Cache寫(xiě)策略?xún)煞N寫(xiě)策略：寫(xiě)直達(dá)法（Write-through）CPU在執(zhí)行寫(xiě)操作時(shí)，利用直接通路，把數(shù)據(jù)同時(shí)寫(xiě)入Cache和主存。寫(xiě)回法（Write-Back）CPU數(shù)據(jù)只寫(xiě)入Cache，不寫(xiě)入主存；為每個(gè)Cache塊設(shè)置“修改位”；僅當(dāng)替換時(shí)，才把修改過(guò)的Cache塊寫(xiě)回到主存。解決一致性問(wèn)題的關(guān)鍵：CPU寫(xiě)入Cache時(shí)如何更新主存的內(nèi)容。寫(xiě)策略CPUCacheRAMCache控制器主存RAM主存控制器外設(shè)I/O控制器系統(tǒng)總線(xiàn)寫(xiě)直達(dá)法：數(shù)據(jù)同時(shí)寫(xiě)入Cache和主存寫(xiě)策略CPUCacheRAMCache控制器主存RAM主存控制器外設(shè)I/O控制器系統(tǒng)總線(xiàn)寫(xiě)回法：數(shù)據(jù)只寫(xiě)入Cache，替換時(shí)才寫(xiě)入主存替換時(shí)寫(xiě)策略寫(xiě)回法和寫(xiě)直達(dá)法都需要少量緩沖器：寫(xiě)直達(dá)法中存放要寫(xiě)回主存的內(nèi)容，以減少CPU等待寫(xiě)主存的時(shí)間。寫(xiě)回法中存放將要寫(xiě)回的塊，不必等待寫(xiě)回主存后才進(jìn)行Cache取。緩沖器對(duì)Cache－主存透明。寫(xiě)策略寫(xiě)直達(dá)法寫(xiě)回法可靠性好于寫(xiě)回法塊替換前仍存在一致性問(wèn)題與主存的通信量少于寫(xiě)直達(dá)法控制復(fù)雜性比寫(xiě)回法簡(jiǎn)單硬件實(shí)現(xiàn)代價(jià)比寫(xiě)直達(dá)法低得多表寫(xiě)直達(dá)發(fā)與寫(xiě)回法的比較Cache層次1.統(tǒng)一Cache和分離Cache統(tǒng)一Cache：只有一個(gè)Cache，指令和數(shù)據(jù)混放。分離Cache：分為指令Cache和數(shù)據(jù)Cache。 它消除了流水線(xiàn)中指令處理器和執(zhí)行單元間的競(jìng)爭(zhēng)，因此特別適用于超標(biāo)量流水線(xiàn)；是Cache結(jié)構(gòu)發(fā)展的趨勢(shì)。2.單級(jí)Cache與多級(jí)CacheL1Cache，L2Cache，L3Cache 采用多級(jí)Cache結(jié)構(gòu)可以提高性能。寄存器L1CacheL2Cache主存CPUCache層次80%16%4%Cache層次(20/80規(guī)則)Cache層次數(shù)據(jù)L1Cache