沒有幻燈片標(biāo)題-北京大學(xué)微處理器研究開發(fā)中心

1、高等計算機系統(tǒng)結(jié)構(gòu),高速緩沖存儲器,（第七講）,2011年4月25日,程 旭,微處理器-DRAM的延遲差距,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

2、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,10,100,1000,1980,1981,1983,1984,1985,1986,1987,1988,1989,1990,1991,1992,1993,1994,1995,1996,1997,1998,1999,2000

3、,1982,Performance,Time,1980: no cache in µproc; 1995 2-level cache on chip(1989 first Intel µproc with a cache on chip),削減 處理器-存儲器性能差距,處理器 面積比 晶體管數(shù)比 (成本)(功率)Alpha 2116437%77%StrongArm SA11061%94%

4、Pentium Pro64%88%每個封裝體 兩個2芯片(dies)：Proc/I$/D$ + L2$Cache本身并沒有特殊的內(nèi)在意義，它僅是縮小處理器-存儲器之間性能差距的一種手段,Alpha微處理器,Time of a full cache miss in instructions executed:1st Alpha : 340 ns/5.0 ns = 68 clks x 2 or1362nd Alpha :

5、266 ns/3.3 ns = 80 clks x 4 or3203rd Alpha :180 ns/1.7 ns =108 clks x 6 or 6481/2X latency x 3X clock rate x 3X Instr/clock ? ?X,存儲層次設(shè)計的四個問題,Q1: 信息塊可以放在高層的哪里？ (Block placement)全相聯(lián)、組相聯(lián)、直接映射Q2: 如果信息塊在高層，那么如何找到它？ (Bl

6、ock identification)標(biāo)記/信息塊Q3: 在失效時，應(yīng)該替換掉哪個信息塊？(Block replacement)隨機、 LRU、FIFOQ4: 在寫操作時，會發(fā)生什么情況 (Write strategy)回寫（Write Back）或 直寫（Write Through） (使用寫緩沖器),Cache性能,CPU time = (CPU execution clock cycles + Memory stall

7、clock cycles) ? clock cycle timeMemory stall clock cycles = (Reads ? Read miss rate ? Read miss penalty + Writes ? Write miss rate ? Write miss penalty)Memory stall clock cycles = Memory accesses ? Miss rate ? Miss

8、 penalty,Cache 性能（續(xù)）,CPUtime = Instruction Count ? (CPIexecution + Mem accesses per instruction ? Miss rate ? Miss penalty) ? Clock cycle timeMisses per instruction = Memory accesses per instruction ? Miss rateCPUtim

9、e = IC ? (CPIexecution + Misses per instruction ? Miss penalty) ? Clock cycle timeMemory stall cycles per instruction = Misses per instruction ? (Total miss latency – Overlapped miss latency)Average Memory access tim

10、e = Hit time + Miss rate ? Miss penalty,改進Cache性能,Average Memory access time = Hit time + Miss rate ? Miss penalty1. 降低失效率 2. 降低失效損失，或者3. 減少在cache中命中的時間,降低失效,對失效進行分類： 3 CsCompulsory 第一次訪問一個不在cache中的數(shù)據(jù)塊，該塊必須被調(diào)入。也稱為 c

11、old start misses o或 first reference misses。 (即使Cache無窮大，也會失效)Capacity在程序執(zhí)行中，cache不能存放其所需的所有數(shù)據(jù)塊，就會先放棄一些塊然后再找回，這就出現(xiàn)了 capacity misses。（有限大小的全相聯(lián)Cache也會出現(xiàn)的失效)Conflict 如果采用組相聯(lián)或直接映射的策略，除了義務(wù)失效和容量失效，還會因為有太多塊要同時映射到同一組中，就會先放棄一些塊然

12、后再找回，這就出現(xiàn)了 conflict misses 。也稱為 collision misses 或 interference misses。(有限大小的 N路組相聯(lián)Cache中出現(xiàn)的失效),3Cs的絕對失效率 (SPEC92),Conflict,,,義務(wù)失效率非常低,2:1 Cache規(guī)律,Conflict,,,,,miss rate 1-way associative cache size X = miss rate 2-way

13、associative cache size X/2,3Cs 的相對失效率,Conflict,Flaws: for fixed block sizeGood: insight => invention,如何能減少失效?,3 Cs: Compulsory, Capacity, Conflict在所有情況，假設(shè)總的cache大小不變：在下列情況，會發(fā)生什么變化：1) 改變塊大?。?3Cs中哪些失效會受到明顯影響?2) 改

14、變相聯(lián)度： 3Cs中哪些失效會受到明顯影響? 3) 改變編譯器: 3Cs中哪些失效會受到明顯影響?,1. 通過增大塊大小來減少失效,2. 通過增大相聯(lián)度來減少失效,8路組相聯(lián)實際上在減少Miss rate方面與全相效果接近。2:1 Cache規(guī)律： Miss Rate DM cache size N = Miss Rate 2-way cache size N/2小心：執(zhí)行時間是唯一最終度量標(biāo)準(zhǔn)！是否時鐘周期時間會增

15、加?Hill [1988]的研究表明2-way cache的命中時間比1-way 外部cache的時間會 +10%, 比內(nèi)部cache的時間會 + 2% 通過增加Cache容量來減少失效。,示例：平均存儲器訪問時間 與 失效率,假設(shè)與直接映射的時鐘周期時間相比 對2路cache為1.10、對4路1.12、對8路 1.14Cache SizeAssociativity (KB)1-way2-way

16、4-way8-way 12.332.152.072.01 21.981.861.761.68 41.721.671.611.53 81.461.481.471.43 161.291.321.321.32 321.201.241.251.27 641.141.201.211.23 1281.101.171.181.20

17、(紅 表示 平均存儲器訪問時間 沒有 被更高的相聯(lián)度減少),假設(shè)失效損失為10周期,3. 使用Victim Cache來減少失效,如何結(jié)合直接映射的高速命中時間，而又避免沖突失效? 增加一個存放從cache中放棄數(shù)據(jù)的緩沖器（全相聯(lián)cache）Jouppi [1990]: 對于4KB的直接映射數(shù)據(jù)cache，4-entry victim cache可以消除 20% 至95%的沖突。 在Alpha、HP等中使用,,,Victim C

18、ache,4. 通過偽相聯(lián)減少失效,如何結(jié)合直接映射的快速命中時間和兩路組相聯(lián)cache的低沖突失效的優(yōu)勢? 分解cache: 在失效時，檢查cache的另一半看是否有所需信息，如果有稱為 偽命中（pseudo-hit） (慢命中)缺點：如果命中需要1或2個周期，那么CPU難以流水適用于不與處理器直接連接的cache（二級cache）用于MIPS R1000和UltraSPARC的二級cache。路預(yù)測(Way Pr

19、ediction),命中時間,偽命中時間,失效損失,時間,,,,,,,,,5. 通過 硬件 預(yù)取指令和數(shù)據(jù)減少失效,例如，指令預(yù)取Alpha 21064在失效時取2個信息塊額外的塊放置在 流緩沖器（stream buffer）中失效時，檢測流緩沖器對于數(shù)據(jù)塊也可使用上述策略Jouppi [1990] 對于4KB cache，1個數(shù)據(jù)流緩沖器可以減少25%的損失；4個流緩沖器，減少43%Palacharla & Kes

20、sler [1994] 對于科學(xué)計算程序，對于兩個64KB，四路組相聯(lián)cache，8個流緩沖器減少 50%至70%的失效 采用預(yù)測策略的前提是具有額外的存儲帶寬，它的使用沒有“其他破壞”代價,6. 通過 軟件 預(yù)取數(shù)據(jù)減少失效,數(shù)據(jù)預(yù)取將數(shù)據(jù)裝入寄存器 (HP PA-RISC loads)Cache預(yù)取: 裝入cache (MIPS IV, PowerPC, SPARC v. 9)不會產(chǎn)生故障的特殊預(yù)取指令；一種推測式執(zhí)行發(fā)

21、射預(yù)取指令需要時間發(fā)射預(yù)取指令的開銷 是否小于 減少失效的收益？超標(biāo)量的能力越強 越可以減小 發(fā)射帶寬的難度,7. 通過編譯優(yōu)化減少失效,McFarling [1989] 對于塊大小為4字節(jié)的8KB直接映射cache，軟件可以75% 的失效指令對存儲訪問重排序，因而可以減少沖突失效進行剖視（Profiling）來觀測沖突(使用他們開發(fā)的工具)數(shù)據(jù)合并數(shù)組(data merge)：通過將兩個獨立數(shù)組合并為一個復(fù)合元素的數(shù)組來

22、改進空間局部性循環(huán)交換(loop interchange): 通過改變循環(huán)嵌套來按序訪問存儲器中存儲的數(shù)據(jù)循環(huán)合并(loop fusion): 將兩個具有相同循環(huán)類型且有一些變量重疊的獨立循環(huán)合并塊化(blocking): 通過不斷使用一些數(shù)據(jù)塊（而不是完整地遍歷一行和一列）來改進時間局部性,合并數(shù)據(jù)的示例,/* Before: 2 sequential arrays */int val[SIZE];int key[SIZE]

23、;/* After: 1 array of stuctures */struct merge {int val;int key;};struct merge merged_array[SIZE];減少 val和 key之間的沖突 改進空間局部性,循環(huán)交換示例,/* Before */for (k = 0; k < 100; k = k+1)for (j = 0; j < 100; j = j+1)

24、for (i = 0; i < 5000; i = i+1)x[i][j] = 2 * x[i][j];/* After */for (k = 0; k < 100; k = k+1)for (i = 0; i < 5000; i = i+1)for (j = 0; j < 100; j = j+1)x[i][j] = 2 * x[i][j];用順序訪問代替跳步（100個存

25、儲字）訪問存儲器改進空間局部性,,循環(huán)合并示例,/* Before */for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1)a[i][j] = 1/b[i][j] * c[i][j];for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1)d[i][j] = a[i][j] + c

26、[i][j];,/* After */for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1){a[i][j] = 1/b[i][j] * c[i][j];d[i][j] = a[i][j] + c[i][j];},每次對a & c 訪問兩次失效 與 每次訪問一次失效; 改進空間局部性,分塊示例,兩個內(nèi)層循環(huán):讀取z[]的所有 N?N個元素分

27、別讀取y[]一行的N個元素寫x[]一行的N個元素容量失效是 N和Cache容量的函數(shù)：3 N ? N ? 4 => 無容量失效；否則 ...思路：計算滿足條件的 B ? B子陣,,,,,,,,,/* Before */for (i = 0; i < N; i = i+1)for (j = 0; j < N; j = j+1){r = 0; for (k = 0; k < N; k = k

28、+1){r = r + y[i][k]*z[k][j];}; x[i][j] = r;};,分塊示例（續(xù)）,/* After */for (jj = 0; jj < N; jj = jj+B)for (kk = 0; kk < N; kk = kk+B)for (i = 0; i < N; i = i+1) for (j = jj; j < min(jj+B-1,N); j =

29、j+1){r = 0; for (k = kk; k < min(kk+B-1,N); k = k+1) {r = r + y[i][k]*z[k][j];}; x[i][j] = x[i][j] + r;};B 稱為 塊化因子（Blocking Factor）容量失效從2N3 + N2 減至 2N3/B +N2是否也會降低沖突失效?,通過分塊減少沖突失效,沒有全相聯(lián)的cache的沖突失效

30、與 塊化大小Lam et al [1991] a blocking factor of 24 had a fifth the misses vs. 48 despite both fit in cache,MISS RATIO,編譯優(yōu)化減少cache失效 小結(jié),總 結(jié),,3 Cs: Compulsory, Capacity, Conflict降低失效率1. 通過增大塊大小減少失效2.通過增大相聯(lián)度減少失效3.通過Victim

31、 Cache減少失效4.通過偽-相聯(lián)減少失效5.通過硬件預(yù)取指令或數(shù)據(jù)減少失效6.通過軟件預(yù)取數(shù)據(jù)減少失效7.通過編譯優(yōu)化減少失效注意：在評價性能時僅僅側(cè)重于某一個參數(shù)是危險的,改進cache性能（續(xù)）,Average Memory access time = Hit time + Miss rate ? Miss penalty1. 降低失效率 2. 降低失效損失，或者3. 減少在cache中命中的時間,1. 減少失

32、效損失: 在失效時讀比寫優(yōu)先,Write through with write buffers offer RAW conflicts with main memory reads on cache missesIf simply wait for write buffer to empty, might increase read miss penalty (old MIPS 1000 by 50% )Check write bu

33、ffer contents before read; if no conflicts, let the memory access continueWrite Back?Read miss replacing dirty blockNormal: Write dirty block to memory, and then do the readInstead copy the dirty block to a write bu

34、ffer, then do the read, and then do the writeCPU stall less since restarts as soon as do read,1.1 在失效時讀比寫優(yōu)先1.2 Merging Write Buffer,,,,Write Buffer,,2. 減少失效損失: 子塊放置,Don’t have to load full block on a missHave valid bi

35、ts per subblock to indicate valid(Originally invented to reduce tag storage),Valid Bits,,,,,Subblocks,,,,,3. 減少失效損失: 提前重啟和關(guān)鍵字先送,Don’t wait for full block to be loaded before restarting CPUEarly restartAs soon as the re

36、quested word of the block arrives, send it to the CPU and let the CPU continue executionCritical Word FirstRequest the missed word first from memory and send it to the CPU as soon as it arrives; let the CPU continue exe

37、cution while filling the rest of the words in the block. Also called wrapped fetch and requested word firstGenerally useful only in large blocks, Spatial locality a problem; tend to want next sequential word, so not c

38、lear if benefit by early restart,,,block,4. 減少失效損失: 用Non-blocking Caches來減少失效時暫停,Non-blocking cache or lockup-free cache allow data cache to continue to supply cache hits during a missrequires out-of-order executuion C

39、PU hit under miss reduces the effective miss penalty by working during miss vs. ignoring CPU requestshit under multiple miss or miss under miss? may further lower the effective miss penalty by overlapping multiple miss

40、esSignificantly increases the complexity of the cache controller as there can be multiple outstanding memory accessesRequires muliple memory banks (otherwise cannot support)Penium Pro allows 4 outstanding memory misse

41、s,對SPEC，失效下命中的情況,浮點程序的平均: AMAT= 0.68 ? 0.52 ? 0.34 ? 0.26整數(shù)程序的平均: AMAT= 0.24 ? 0.20 ? 0.19 ? 0.198 KB Data Cache、直接映射、32B 數(shù)據(jù)塊、 失效需要16周期,Integer,Floating Point,,n次失效下命中,0->11->22->64Base,5.二級cache,二級cache的計算

42、公式AMAT = Hit TimeL1 + Miss RateL1 x Miss PenaltyL1Miss PenaltyL1 = Hit TimeL2 + Miss RateL2 x Miss PenaltyL2AMAT = Hit TimeL1 + Miss RateL1 x (Hit TimeL2 + Miss RateL2 + Miss PenaltyL2)定義:局部失效率 該cache的失效次數(shù)除以

43、對 該級cache 進行的總的存儲訪問次數(shù) (Miss rateL2)總失效率 該cache的失效次數(shù)除以 CPU產(chǎn)生的 總的存儲器訪問次數(shù) (Miss RateL1 x Miss RateL2) 總失效率是我們真正關(guān)心的,局部和全局失效率的比較,一級cache:32 KByte;增加二級cache總失效率接近于二級Cache的單級cache失效率 使得 二級 >> 一級（大?。Χ塁ache不要使用局部失

44、效率二級cache與CPU時鐘周期無關(guān)!成本 和 平均存儲訪問時間通常，快命中時間 和 更少的失效由于命中增多，目標(biāo)失效減少,Linear,Log,Cache Size,Cache Size,減少失效損失:哪些適用于二級 Cache?,降低失效率1. 通過增大塊大小減少失效2.通過增大相聯(lián)度減少失效3.通過Victim Cache減少失效4.通過偽-相聯(lián)減少失效5.通過硬件預(yù)取指令或數(shù)據(jù)減少失效6.通過軟件預(yù)取數(shù)據(jù)減

45、少失效7.通過編譯優(yōu)化減少失效,二級cache 塊大小 和平均存儲器訪問時間,第一級32KB , 與存儲器的通路8字節(jié)寬,減少失效損失小結(jié),,五種技術(shù)失效時，讀比寫優(yōu)先；合并寫緩存子塊放置失效時，提前重啟和關(guān)鍵存儲字先送非阻塞Cache (Hit under Miss, Miss under Miss)二級Cache可適用于多級cache問題：到DRAM的時間可能隨著cache的級數(shù)而增長亂序執(zhí)行CPU可以隱藏第一級數(shù)

46、據(jù)cache的失效，但在第二級cache失效時會暫停,Cache優(yōu)化小結(jié),技術(shù)MRMPHTComplexity增大塊大小+-0增高相聯(lián)度+-2淘汰塊Cache+2偽相聯(lián)Cache+2指令/數(shù)據(jù)的硬件預(yù)取+2編譯控制的預(yù)取+3編譯減少失效+0讀失效優(yōu)先+1子塊放置 ++1提前重啟和關(guān)鍵存儲字優(yōu)先 +2非阻塞Cache+3

47、二級Cache+2,,失效率,失效損失,改進Cache性能,,Average Memory access time = Hit time + Miss rate ? Miss penalty1. 降低失效率 2. 降低失效損失，或者3. 減少在cache中命中的時間,1. 通過小、簡單的Cache來加快命中時間,為什么Alpha 21164設(shè)置8KB指令cache和 8KB數(shù)據(jù)cache + 96KB二級cache?小

48、數(shù)據(jù)cache和時鐘頻率片載cache直接映射,2. 通過避免地址變換加快命中,將虛擬地址送給cache? 稱為 虛擬地址cache（Virtually Addressed Cache） 或者 虛擬Cache（Virtual Cache） 性對于 物理cache（Physical Cache）每次進程間的邏輯切換都必須沖洗cache; 否則將會發(fā)生錯誤命中代價是 沖洗時間 + 空cache的義務(wù)失效需要處理處理 別名(alia

49、ses) (也稱為 化名(synonyms)); 兩個不同的虛擬地址映射到同一物理地址I/O必然與cache相互影響，因而需要虛擬地址處理別名的策略硬件保證 Index域和直接映射，它們都是唯一的。稱為“頁面染色（page coloring)”沖洗cache的解決策略增加 進程標(biāo)識符（process identifier tag） ：與進程內(nèi)的地址一起還標(biāo)識進程本身：如果進程錯誤就不會命中,虛擬地址Caches,CPU,T

50、B,$,MEM,,,,VA,PA,PA,常規(guī)組織,CPU,$,TB,MEM,,,,VA,VA,PA,虛擬地址cache只在失效時才變換別名問題,CPU,$,TB,MEM,,,,VA,PATags,PA,,,,,Cache訪問與虛擬地址變換重疊：需要cahe索引來保持變換間的不變性,VATags,L2 $,2.通過避免地址變化加快cache命中: 進程標(biāo)識符的效果,黑色為單進程淺灰為沖洗cache時的多進程深灰為使用進程標(biāo)識符

51、的多進程Y軸：失效率達20%X軸：Cache大小從2 KB到 1024 KB,,2.通過避免地址變化加快cache命中: 利用地址的物理部分進行索引,限制cache不能超過頁面大小: 那么，需要更大的 cache時，怎么辦？增大相聯(lián)度將會使TAG和INDEX之間的界限右移頁面染色,Page Address,Page Offset,Address Tag,Index,Block Offset,如果索引就是地址的某一物理部分，就可以

52、與變換并行開始標(biāo)志訪問，因而就可以與物理標(biāo)志進行比較,將標(biāo)簽檢測和更改cache分為不同流水級；當(dāng)前寫操作的標(biāo)簽檢測 & 上一次寫操作的cache更改 流水線中只有 STORES；失效時清空Store r2, (r1)Check r1Add--Sub--Store r4, (r3) M[r1]<-r2&check r3陰影部分為 延遲寫緩沖器（Delayed Write Buffer）

53、 在讀操作中必須被檢測；,3. 通過流水化寫操作來加快命中時間,,4. Trace Cache in Pentium 4,How to supply enough instructions every cycle without dependencies?Instead of limiting the instructions in a static cache block to spatial localityA trace ca

54、che finds a dynamic sequence of instructions including taken branches to load into a cache block.Much more complicated address mapping mechanisms.Trace cache store the same instructions multiple times in the instructi

55、on cache.,,,Cache 優(yōu)化小結(jié),技術(shù)MRMPHTComplexityLarger Block Size+-0Higher Associativity+-1Victim Caches++2Pseudo-Associative Caches +2HW Prefetching of Instr/Data++2Compiler Controlled Prefetching

56、++3Compiler Reduce Misses+0Priority to Read Misses+1Subblock Placement ++1Early Restart & Critical Word 1st +2Non-Blocking Caches+3Second Level Caches+2Small & Simple Caches-

57、+0Avoiding Address Translation+2Pipelining Writes+1Trace Cache+3,,,miss rate,hit time,misspenalty,Cache 優(yōu)化小結(jié),技術(shù)MRMPHTComplexityLarger Block Size+-0Higher Associativity+-1Victim Caches++

58、2Pseudo-Associative Caches +2HW Prefetching of Instr/Data++2Compiler Controlled Prefetching++3Compiler Reduce Misses+0Priority to Read Misses+1Subblock Placement ++1Early Restart & Cr

59、itical Word 1st +2Non-Blocking Caches+3Second Level Caches+2Small & Simple Caches-+0Avoiding Address Translation+2Pipelining Writes+1Trace Cache+3,,,miss rate,hit time,misspenalty,

60、所學(xué)知識對Caches性能的影響,這對以下領(lǐng)域意味著什么？編譯技術(shù)、操作系統(tǒng)、算法、數(shù)據(jù)結(jié)構(gòu),1960-1985: Speed = f(no. operations)1990Pipelined Execution & Fast Clock RateOut-of-Order executionSuperscalar Instruction Issue1998: Speed = f(non-cached me