1、Lecture 10: Cache III1有效位（Valid Bit）通常為操作系統(tǒng)設置“cache沖刷”指令因此cache對操作系統(tǒng)程序員不是透明的！裝入新塊時 使V=1開機或復位時使V=0第一次被替換時使V=1通過使V=0沖刷Cache舉例假定計算機系統(tǒng)有一個容量為32KB的主存，且有一個4KB的4路組相聯(lián)Cache，主存和Cache之間的塊的大小為64B。假定Cache單元0、1、4351中取一個Byte，開始為空，處理器順序地從一共重復10次。設Cache比主存快10倍。采用LRU算法。試分析Cache的結構和主存地址的劃分。說明采用Cache后速度提高了多少？答：主存按字節(jié)（B）編

2、址。主存：32KB=512塊 x 64B / 塊Cache：4KB=16組 x 4路 / 組 x 64 B / 路主存地址劃分為：6544352/64=68，所以過程實際上是對前68塊連續(xù)10次。標志位組號字節(jié)號舉例第1 路第2 路第3 路第0 路16/0/6417/1/6518/2/6619/3/6720310/64/481/65/492/66/503/67/5141532/1633/1734/1835/19364748/3249/3350/3451/355263第0組第1組第2組第3組第4組第15組LRU算法：第一次循環(huán),對于每一塊只有第一字未命中,其余都命中;以后9次循環(huán),有20塊的第一

3、字未命中,其余都命中.所以,p為 (43520-68-9x20)/43520=99.43%m/(tc+(1-p)tm)=10/(1+10 x(1-p)=9.5倍速度提高：tm/寫策略（Cache一致性問題）為何要保持在Cache和主存中數(shù)據(jù)的一致？因為Cache中的內容是主存塊副本，當對Cache新時，就存在Cache和主存如何保持一致以下情況也會出現(xiàn)“Cache一致性問題”。當多個設備都允許主存時例如：I/O設備可直接讀寫內存時，如果Cache中的內容被修改，則I/O設備讀出的對應主存單元的內容無效；若I/O設備修改了主存單元的內容，則Cache中對應的內容無效。當多個CPU都帶有各自的Ca

4、che而共享主存時某個CPU修改了自身Cache中的內容，則對應的主存單元和其他CPU中對應的內容都變?yōu)闊o效。有兩種情況寫命中（Write Hit）：要寫的單元已經在Cache中寫不命中（Write Miss）：要寫的單元不在Cache基本的Cache處理算法問問有題題么題：題問題？如什如果需題需頻問么頻繁怎寫樣，會會怎么樣？么？怎樣會有沒有其他方法？寫分配方式Write Policy: Write Through versus Write Back處理Cache讀比Cache寫更容易，故指令Cache比數(shù)據(jù)Cache容易設計對于寫命中，有兩種處理方式Write Through (通過式寫、寫

5、直達、直寫)同時寫Cache和主存單元What! How can this be? Memory is too slow(100Cycles)?10%的指令使CPI增加到：1.0+100 x10%=11使用寫緩沖（Write Buffer）Write Back (寫、寫回、回寫)在缺失時一次寫回Cache塊，每塊有個修改位（“dirty bit-臟位”）大大降低主存帶寬需求，控制可能很復雜對于寫不命中，有兩種處理方式 Write Allocate (寫分配)直寫Cache可用非寫分配或寫分配寫回Cache通常用寫分配為什么？將主存塊裝入Cache，然后更新相應單元試圖利用空間局部性，但每次都要

6、從主存讀一個塊Not Write Allocate (非寫分配)直接寫主存單元，不裝入主存塊到CacheSKIPWrite ThroughWrite BufferMemory ControllerWrite Buffer在 Cache 和 Memory之間加一個Write BufferCPU: 同時寫數(shù)據(jù)到Cache和Write BufferMemory controller（存控）: 將緩沖內容寫主存Write buffer (寫緩沖) 是一個FIFO隊列一般有4項在存數(shù)頻率1 / DRAM write cycle(頻繁寫)時，使Write buffer 飽和(溢出)，會發(fā)生阻塞DRAMCa

7、cheCPUWrite Buffer Saturation（寫緩沖飽和）CPUDRAMWrite Buffer發(fā)生寫緩沖飽和的可能性 CPU時鐘周期 1/ DRAM寫周期 (發(fā)生頻繁寫)如何解決寫緩沖飽和？ 加一個二級CacheCPUWrite Buffer 使用Write Back方式的CacheBACKDRAML2CacheCacheCache寫策略（Cache一致性問題）問題1：以下描述的是哪種寫策略？Write Through 、Write Allocate！問題2：如果用非寫分配，則如何修改算法？BACK寫策略2：Write Back算法問題：以下算法描述的是哪種寫策略？Write

8、Back 、Write Allocate！寫策略2：Write Back中的修改（“臟”）位BACKCache大小、Block大小和缺失率的關系Cache大?。篊ache越大，Miss率越低，但成本越高！Block大小：Block大小與Cache大小有關，且不能太大，也不能太?。ache性能由缺失率確定，而缺失率與Cache大小、Block大小、Cache級數(shù)等有關Block Size Tradeoff (塊大小的選擇)塊大能很好利用 spatial locality， BUT: 塊大，則需花時間讀塊，缺失損失變大 塊大，則Cache行數(shù)變少，缺失率上升Average Acs Time:=

9、Hit Time x (1 - Miss Rate)+Miss Penalty x Miss RateAverageMiss PenaltyMiss RateAc TimesExploits Spatial LocalityFewer blocks: compromises temporal localityIncreased Miss Penalty & Miss RateBlock SizeBlock SizeBlock Size所以，塊大小必須適中！系統(tǒng)中的Cache數(shù)目剛引入Cache時只有一個Cache。近年來多Cache系統(tǒng)成為主流多Cache系統(tǒng)中，需考慮兩個方面：單級/多級？片

10、內(On-chip)Cache: 將Cache和CPU作在一個上外部(Off-chip)Cache:不做在CPU內而是獨立設置一個Cache單級Cache：只用一個片內Cache多級Cache：同時使用L1 Cache和L2 Cache，有些高端系統(tǒng)甚至有L3 Cache，L1 Cache更靠近CPU，其速度比L2快，其容量比L2大2 聯(lián)合/分立？分立：指數(shù)據(jù)和指令分開存放在各自的數(shù)據(jù)和指令Cache中一般L1 Cache都是分立Cache，為什么？L1 Cache中時間比更重要！為什么？聯(lián)合：指數(shù)據(jù)和指令都放在一個Cache一般L2 Cache都是聯(lián)合Cache，為什么？L2 Cache中率

11、比命中時間更重要！為什么？因為缺失時需從主存取數(shù)，并要送L1和L2cache，損失大！多核處理器中的多級Cache多級cache的性能采用L2 Cache的系統(tǒng)，其缺失損失的計算如下：若L2 Cache包含所請求信息，則缺失損失為L2 Cache時間主存，并取到L1 Cache和L2 Cache（缺失損失更大）否則例子：某處理器在無cache缺失時CPI為1，時鐘頻率為5GHz。假定訪問一次主存的時間（包括所有的缺失處理）為100ns，平均每條指令在L1 Cache中的缺失率為2%。若增加一個L2 Cache，其時間為5ns，而且容量足夠大到使全局缺失率減為0.5%，問處理器執(zhí)行指令的速度提高

12、了多少？解：如果只有一級Cache，則缺失只有一種。即L1缺失(需主存)，其缺失損失為：100nsx5GHz=500個時鐘，CPI=1+500 x2%=11.0。如果有二級Cache，則有兩種缺失：L1缺失(需L2 Cache)：5nsx5GHz=25個時鐘L1和L2都缺失(需主存)：500個時鐘因此，CPI=1+25x2%+500 x0.5%=4.0二者的性能比為11.0/4.0=2.8倍！Cache性能評估與改善CPU時間：CPU執(zhí)行時間 + 等待內存時間。即：CPU時間=(CPU時鐘數(shù)+Cache缺失引起阻塞的時鐘數(shù)) X 時鐘周期Cache缺失引起阻塞的時鐘數(shù)=讀操作阻塞時鐘數(shù)+寫操作

13、阻塞時鐘數(shù)讀操作阻塞時鐘數(shù)=(讀的次數(shù) / 程序) x 讀缺失率 x 讀缺失損失寫操作的情況較復雜：回寫（write back）:替換時，需要回寫一個塊，故會產生一些附加回寫阻塞寫操作阻塞時鐘數(shù)=(寫次數(shù)/ 程序) x 寫缺失率 x 寫缺失損失+回寫阻塞直寫（write through）:包括寫缺失和write buffer阻塞兩部分寫操作阻塞時鐘數(shù)=(寫次數(shù)/ 程序) x 寫缺失率 x 寫缺失損失+寫緩沖阻塞假定回寫阻塞或寫緩沖阻塞可以忽略不計，則可將讀和寫綜合考慮：內存阻塞時鐘數(shù)=(訪存次數(shù) / 程序) x 缺失率 x 缺失損失內存阻塞時鐘數(shù)=(指令條數(shù) / 程序) x (缺失數(shù)/ 指令)

14、 x缺失損失舉例: 缺失帶來的損失到底多大？設代碼Cache缺失率為2%，數(shù)據(jù)Cache缺失率為4%。假定一個CPU在沒有任何SPEC2000衡量，則使用無缺失Cache時CPU速度會快多少？分析過程如下：指令的缺失時鐘數(shù)為：Ix2%x100=2.0 xISPEC2000的訪存指令(Load和Store)頻度為：36%，所以數(shù)據(jù)的缺失時鐘數(shù)為：Ix36%x4%x100=1.44xI指令和數(shù)據(jù)總的缺失時鐘數(shù)為：2xI+1.44xI=3.44I，也即：平均每條指令要有3.44個時鐘處在器阻塞狀態(tài)器阻塞而使得CPI數(shù)增大到2+3.44=5.44. 故：因此，因為IxCPIstallxClock cy

15、cleCPU time with stalls5.44=IxCPIperfectxClock cycleCPU time with perfect cache2如果Cache不發(fā)生缺失，則CPU速度會快2.72倍。阻塞時CPI為2，缺失損失為100個時鐘。如果用舉例：處理器速度提高而器不變時的情況例1：假定上例中CPI減為1，時鐘寬度不變，則：器阻塞而使得CPI數(shù)增大到1+3.44=4.44. 故：因為IxCPIstallxClock cycleCPU time with stalls4.44=IxCPIperfectxClock cycleCPU time with perfect cach

16、e1由此可知：器阻塞所花時間占整個執(zhí)行時間的比例從：3.44 / 5.44=63% 上升到 3.44 / 4.44=77%結論：CPI越小，Cache阻塞的影響越大舉例：處理器速度提高而器不變時的情況例2：假定上例中時鐘頻率加倍， CPI不變，則：主存速度不會改變，故絕對時間不變，所以缺失損失為200個時鐘。每條指令發(fā)生的總缺失時鐘數(shù)為2%x200+36%x(4%x200)=6.88器阻塞使得CPI數(shù)增大到2+6.88=8.88故： IxCPIslow xClock cycleIxCPIfast xClock cycle/25.44時鐘快的機器的性能時鐘慢的機器的性能=1.23=8.88/2由

17、此可知：時鐘快的機器的性能只是較慢時鐘機器的1.2倍。如果沒有Cache缺失的話，應該是2倍！結論：CPU時鐘頻率越高，Cache缺失損失就越大上述兩個例子說明：處理器性能越高，高速緩存的性能就越重要！設計支持Cache的器系統(tǒng)指令執(zhí)行若發(fā)生Cache缺失，必須到DRAM中取數(shù)據(jù)或指令在DRAM和Cache之間傳輸?shù)氖荁lock器組織使得Block傳輸最快（缺失損失最小）？問題：怎樣的假定器過程：CPU發(fā)送地址到內存：1個總線時鐘內存的初始化時間：10個總線時鐘從總線上傳送一個字：1個總線時鐘可以有三種不同的組織形式！假定一個Block有4個字，則缺失損失各為多少時鐘？MMCPU支持Cache

18、的器系統(tǒng)假定器過程：CPU發(fā)送地址到內存：1個總線時鐘時間：10個總線時鐘內存從總線上傳送一個字：1個總線時鐘4x(1+10+1)=48缺失損失為48個時鐘周期代價小，但速度慢！假定器過程：CPU發(fā)送地址到內存：1個總線時鐘時間：10個總線時鐘內存從總線上傳送一個Block:1個總線時鐘Two-word: 2x(1+10+1)=24Four-word: 1+10+1=12缺失損失各為24或12個時鐘周期速度快，但代價大！假定器過程：CPU發(fā)送地址到內存：1個總線時鐘時間：10個總線時鐘內存從總線上傳送一個字：1個總線時鐘erleaved four bsord: 1+1x10+4x1=15缺失損

19、失為15個時鐘周期代價小，而且速度快！復習：SPARCsion 20s Memory Module512 cols8 bitsbitsMemory Bus512 8 SRAMbits行緩沖交叉編址方式！Cache行讀從內存讀一塊連續(xù)數(shù)據(jù)區(qū)。只要給定一個首地址，后續(xù)數(shù)據(jù)連續(xù)讀出，稱為突（猝）發(fā)傳輸方式。512 rows512 8 SRAMOne pageDRAM Chip 0256K x 8= 2 MbDRAM Chip 15256K x 8= 2 Mb28MB的DRAM復器交叉編址方式！8個同時讀出！若再構成多個模塊，則可輪流啟動每個模塊進行讀寫！地址Abits 56-63bits 48-55

20、bits 40-47bits 32-39bits 24-31bits 16-23bits 8-15bits 0-7控制器: 行、列地址為(i,j)的8個單元容量：16MB=4096X4096X8位64-bit 雙字6356 5548 4740 3932 3124 23 16 158 70主器地址 A 處的64-bit數(shù)據(jù)(行地址i, 列地址j)DRAM 0DRAM 74096行實例：奔騰機的Cache組織主存：4GB=220 x 27塊x 25B/塊Cache：8KB=128組x2行/組替換算法：LRU，每組一位LRU位。該位為0，下次淘汰第0路；該位為1，下次淘汰第1路。寫策略：默認為Write Back，可動態(tài)設置為Write Through。 Cache一致性：支持MESI協(xié)議實例：內置FastMATH處理器是MIPS結構的微處理器Memory Address31各Cache有：0Byte256(16K