高等計算機系統(tǒng)結(jié)構(gòu)微處理器-DRAM的延遲差距1101001000198019811983198419851986198719881989199019911992199319941995199619971998199920001982Processor-MemoryPerformanceGap:

(grows50%/year)PerformanceTimeProc60%/yr.CPUDRAM7%/yr.DRAM1980:nocacheinμproc;19952-levelcacheonchip

(1989firstIntelμprocwithacacheonchip)

削減處理器-存儲器性能差距

處理器 面積比 晶體管數(shù)比

(成本) (功率)Alpha21164 37% 77%StrongArmSA110 61% 94%PentiumPro 64% 88%每個封裝體兩個2芯片(dies)：Proc/I$/D$+L2$Cache本身并沒有特殊的內(nèi)在意義，它僅是縮小處理器-存儲器之間性能差距的一種手段Alpha微處理器Timeofafullcachemissininstructionsexecuted:1stAlpha: 340ns/5.0ns=68clksx2or 1362ndAlpha: 266ns/3.3ns=80clksx4or 3203rdAlpha: 180ns/1.7ns=108clksx6or 6481/2Xlatencyx3Xclockratex3XInstr/clock?X存儲層次設(shè)計的四個問題Q1:信息塊可以放在高層的哪里？(Blockplacement)全相聯(lián)、組相聯(lián)、直接映射Q2:如果信息塊在高層，那么如何找到它？

(Blockidentification)標(biāo)記/信息塊Q3:在失效時，應(yīng)該替換掉哪個信息塊？(Blockreplacement)隨機、LRU、FIFOQ4:在寫操作時，會發(fā)生什么情況(Writestrategy)回寫（WriteBack）或直寫（WriteThrough）(使用寫緩沖器)Cache性能CPUtime=(CPUexecutionclockcycles+Memorystallclockcycles)clockcycletime

Memorystallclockcycles=(ReadsReadmissrateReadmisspenalty+WritesWritemissrateWritemisspenalty)

Memorystallclockcycles=

MemoryaccessesMissrateMisspenaltyCache性能（續(xù)）CPUtime=InstructionCount(CPIexecution+MemaccessesperinstructionMissrateMisspenalty)Clockcycletime

Missesperinstruction=MemoryaccessesperinstructionMissrate

CPUtime=IC(CPIexecution+MissesperinstructionMisspenalty)ClockcycletimeMemorystallcyclesperinstruction=Missesperinstruction(Totalmisslatency–Overlappedmisslatency)AverageMemoryaccesstime=Hittime+MissrateMisspenalty改進Cache性能AverageMemoryaccesstime=Hittime+MissrateMisspenalty1.降低失效率

2.降低失效損失，或者3.減少在cache中命中的時間降低失效對失效進行分類：3CsCompulsory第一次訪問一個不在cache中的數(shù)據(jù)塊，該塊必須被調(diào)入。也稱為coldstartmisses

o或

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

或interferencemisses。(有限大小的N路組相聯(lián)Cache中出現(xiàn)的失效)3Cs的絕對失效率(SPEC92)Conflict義務(wù)失效率非常低2:1Cache規(guī)律Conflictmissrate1-wayassociativecachesizeX

=missrate2-wayassociativecachesizeX/23Cs的相對失效率ConflictFlaws:forfixedblocksizeGood:insight=>invention如何能減少失效?3Cs:Compulsory,Capacity,Conflict在所有情況，假設(shè)總的cache大小不變：在下列情況，會發(fā)生什么變化：1)改變塊大?。?/p>

3Cs中哪些失效會受到明顯影響?

2)改變相聯(lián)度：

3Cs中哪些失效會受到明顯影響?

3)改變編譯器:

3Cs中哪些失效會受到明顯影響?1.通過增大塊大小來減少失效2.通過增大相聯(lián)度來減少失效8路組相聯(lián)實際上在減少Missrate方面與全相效果接近。2:1Cache規(guī)律：MissRateDMcachesizeN=MissRate2-waycachesizeN/2小心：執(zhí)行時間是唯一最終度量標(biāo)準(zhǔn)！是否時鐘周期時間會增加?Hill[1988]的研究表明2-waycache的命中時間比1-way外部cache的時間會+10%,比內(nèi)部cache的時間會+2%通過增加Cache容量來減少失效。示例：平均存儲器訪問時間與失效率假設(shè)與直接映射的時鐘周期時間相比對2路cache為、對4路、對8路 CacheSize Associativity (KB) 1-way 2-way 4-way 8-way 8 1.46

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

分解cache:在失效時，檢查cache的另一半看是否有所需信息，如果有稱為偽命中（pseudo-hit）

(慢命中)缺點：如果命中需要1或2個周期，那么CPU難以流水適用于不與處理器直接連接的cache（二級cache）用于MIPSR1000和UltraSPARC的二級cache。路預(yù)測(WayPrediction)命中時間偽命中時間失效損失時間5.通過硬件預(yù)取指令和數(shù)據(jù)減少失效例如，指令預(yù)取Alpha21064在失效時取2個信息塊額外的塊放置在流緩沖器（streambuffer）中失效時，檢測流緩沖器對于數(shù)據(jù)塊也可使用上述策略Jouppi[1990]對于4KBcache，1個數(shù)據(jù)流緩沖器可以減少25%的損失；4個流緩沖器，減少43%Palacharla&Kessler[1994]對于科學(xué)計算程序，對于兩個64KB，四路組相聯(lián)cache，8個流緩沖器減少50%至70%的失效采用預(yù)測策略的前提是具有額外的存儲帶寬，它的使用沒有“其他破壞”代價6.通過軟件預(yù)取數(shù)據(jù)減少失效數(shù)據(jù)預(yù)取將數(shù)據(jù)裝入寄存器(HPPA-RISCloads)Cache預(yù)取:裝入cache

(MIPSIV,PowerPC,SPARCv.9)不會產(chǎn)生故障的特殊預(yù)取指令；一種推測式執(zhí)行發(fā)射預(yù)取指令需要時間發(fā)射預(yù)取指令的開銷是否小于減少失效的收益？超標(biāo)量的能力越強越可以減小發(fā)射帶寬的難度7.通過編譯優(yōu)化減少失效McFarling[1989]對于塊大小為4字節(jié)的8KB直接映射cache，軟件可以75%的失效指令對存儲訪問重排序，因而可以減少沖突失效進行剖視（Profiling）來觀測沖突(使用他們開發(fā)的工具)數(shù)據(jù)合并數(shù)組(datamerge)：通過將兩個獨立數(shù)組合并為一個復(fù)合元素的數(shù)組來改進空間局部性循環(huán)交換(loopinterchange):通過改變循環(huán)嵌套來按序訪問存儲器中存儲的數(shù)據(jù)循環(huán)合并(loopfusion):將兩個具有相同循環(huán)類型且有一些變量重疊的獨立循環(huán)合并塊化(blocking):

通過不斷使用一些數(shù)據(jù)塊（而不是完整地遍歷一行和一列）來改進時間局部性合并數(shù)據(jù)的示例/*Before:2sequentialarrays*/intval[SIZE];intkey[SIZE];/*After:1arrayofstuctures*/structmerge{ intval; intkey;};structmergemerged_array[SIZE];

減少val和key之間的沖突

改進空間局部性循環(huán)交換示例/*Before*/for(k=0;k<100;k=k+1)

for(j=0;j<100;j=j+1) 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個存儲字）訪問存儲器改進空間局部性循環(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[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[]的所有NN個元素分別讀取y[]一行的N個元素寫x[]一行的N個元素容量失效是N和Cache容量的函數(shù)：3NN4=>無容量失效；否則...思路：計算滿足條件的BB子陣/*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+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=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稱為塊化因子（BlockingFactor）容量失效從2N3+N2

減至2N3/B+N2是否也會降低沖突失效?通過分塊減少沖突失效沒有全相聯(lián)的cache的沖突失效與塊化大小Lametal[1991]ablockingfactorof24hadafifththemissesvs.48despitebothfitincacheMISSRATIO編譯優(yōu)化減少cache失效小結(jié)總結(jié)3Cs:Compulsory,Capacity,Conflict降低失效率1.通過增大塊大小減少失效2.通過增大相聯(lián)度減少失效3.通過VictimCache減少失效4.通過偽-相聯(lián)減少失效5.通過硬件預(yù)取指令或數(shù)據(jù)減少失效6.通過軟件預(yù)取數(shù)據(jù)減少失效7.通過編譯優(yōu)化減少失效注意：在評價性能時僅僅側(cè)重于某一個參數(shù)是危險的改進cache性能（續(xù)）AverageMemoryaccesstime=Hittime+MissrateMisspenalty1.降低失效率

2.降低失效損失，或者3.減少在cache中命中的時間1.減少失效損失:在失效時讀比寫優(yōu)先WritethroughwithwritebuffersofferRAWconflictswithmainmemoryreadsoncachemissesIfsimplywaitforwritebuffertoempty,mightincreasereadmisspenalty(oldMIPS1000by50%)Checkwritebuffercontentsbeforeread;

ifnoconflicts,letthememoryaccesscontinueWriteBack?ReadmissreplacingdirtyblockNormal:Writedirtyblocktomemory,andthendothereadInsteadcopythedirtyblocktoawritebuffer,thendotheread,andthendothewriteCPUstalllesssincerestartsassoonasdoread1.1在失效時讀比寫優(yōu)先1.2MergingWriteBufferwritebufferCPUinoutDRAM(orlowermem)WriteBuffer2.減少失效損失:子塊放置Don’thavetoloadfullblockonamissHavevalidbits

persubblocktoindicatevalid(Originallyinventedtoreducetagstorage)ValidBitsSubblocks3.減少失效損失:提前重啟和關(guān)鍵字先送Don’twaitforfullblocktobeloadedbeforerestartingCPUEarlyrestartAssoonastherequestedwordoftheblockarrives,sendittotheCPUandlettheCPUcontinueexecutionCriticalWordFirstRequestthemissedwordfirstfrommemoryandsendittotheCPUassoonasitarrives;lettheCPUcontinueexecutionwhilefillingtherestofthewordsintheblock.AlsocalledwrappedfetchandrequestedwordfirstGenerallyusefulonlyinlargeblocks,Spatiallocalityaproblem;tendtowantnextsequentialword,sonotclearifbenefitbyearlyrestartblock4.減少失效損失:用Non-blockingCaches來減少失效時暫停Non-blockingcache

orlockup-freecache

allowdatacachetocontinuetosupplycachehitsduringamissrequiresout-of-orderexecutuionCPUhitundermissreducestheeffectivemisspenaltybyworkingduringmissvs.ignoringCPUrequestshitundermultiplemissormissundermiss?mayfurtherlowertheeffectivemisspenaltybyoverlappingmultiplemissesSignificantlyincreasesthecomplexityofthecachecontrollerastherecanbemultipleoutstandingmemoryaccessesRequiresmuliplememorybanks(otherwisecannotsupport)PeniumProallows4outstandingmemorymisses對SPEC，失效下命中的情況浮點程序的平均:AMAT=0.680.520.34整數(shù)程序的平均:AMAT=0.240.200.198KBDataCache、直接映射、32B數(shù)據(jù)塊、失效需要16周期IntegerFloatingPointn次失效下命中0->11->22->64Base5.二級cache二級cache的計算公式

AMAT=HitTimeL1+MissRateL1xMissPenaltyL1

MissPenaltyL1=HitTimeL2+MissRateL2xMissPenaltyL2 AMAT=HitTimeL1+

MissRateL1

x(HitTimeL2+

MissRateL2

+ MissPenaltyL2)定義:局部失效率該cache的失效次數(shù)除以對該級cache

進行的總的存儲訪問次數(shù)(MissrateL2)總失效率該cache的失效次數(shù)除以CPU產(chǎn)生的總的存儲器訪問次數(shù)

(MissRateL1xMissRateL2)總失效率是我們真正關(guān)心的局部和全局失效率的比較一級cache:32KByte;

增加二級cache總失效率接近于二級Cache的單級cache失效率 使得二級>>一級（大小）對二級Cache不要使用局部失效率二級cache與CPU時鐘周期無關(guān)!成本和平均存儲訪問時間通常，快命中時間和更少的失效由于命中增多，目標(biāo)失效減少LinearLogCacheSizeCacheSize減少失效損失:哪些適用于二級Cache?降低失效率1.通過增大塊大小減少失效2.通過增大相聯(lián)度減少失效3.通過VictimCache減少失效4.通過偽-相聯(lián)減少失效5.通過硬件預(yù)取指令或數(shù)據(jù)減少失效6.通過軟件預(yù)取數(shù)據(jù)減少失效7.通過編譯優(yōu)化減少失效二級cache塊大小和平均存儲器訪問時間第一級32KB,與存儲器的通路8字節(jié)寬減少失效損失小結(jié)五種技術(shù)失效時，讀比寫優(yōu)先；合并寫緩存子塊放置失效時，提前重啟和關(guān)鍵存儲字先送非阻塞Cache(HitunderMiss,MissunderMiss)二級Cache可適用于多級cache問題：到DRAM的時間可能隨著cache的級數(shù)而增長亂序執(zhí)行CPU可以隱藏第一級數(shù)據(jù)cache的失效，但在第二級cache失效時會暫停Cache優(yōu)化小結(jié)技術(shù) MR MP HT Complexity增大塊大小 + - 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

二級Cache + 2失效率失效損失改進Cache性能AverageMemoryaccesstime=Hittime+MissrateMisspenalty1.降低失效率

2.降低失效損失，或者3.減少在cache中命中的時間1.通過小、簡單的Cache來加快命中時間為什么Alpha21164設(shè)置8KB指令cache和8KB數(shù)據(jù)cache+96KB二級cache?小數(shù)據(jù)cache和時鐘頻率片載cache直接映射2.通過避免地址變換加快命中將虛擬地址送給cache?稱為虛擬地址cache（VirtuallyAddressedCache）

或者虛擬Cache（VirtualCache）

性對于物理cache（PhysicalCache）每次進程間的邏輯切換都必須沖洗cache;否則將會發(fā)生錯誤命中代價是沖洗時間+空cache的義務(wù)失效需要處理處理別名(aliases)

(也稱為化名(synonyms));

兩個不同的虛擬地址映射到同一物理地址I/O必然與cache相互影響，因而需要虛擬地址處理別名的策略硬件保證Index域和直接映射，它們都是唯一的。稱為“頁面染色（pagecoloring)”沖洗cache的解決策略增加

進程標(biāo)識符（processidentifiertag）

：與進程內(nèi)的地址一起還標(biāo)識進程本身：如果進程錯誤就不會命中虛擬地址CachesCPUTB$MEMVAPAPA常規(guī)組織CPU$TBMEMVAVAPA虛擬地址cache只在失效時才變換別名問題CPU$TBMEMVAPATagsPACache訪問與虛擬地址變換重疊：需要cahe索引來保持變換間的不變性VATagsL2$2.通過避免地址變化加快cache命中:進程標(biāo)識符的效果黑色為單進程淺灰為沖洗cache時的多進程深灰為使用進程標(biāo)識符的多進程Y軸：失效率達20%X軸：Cache大小從2KB到1024KB2.通過避免地址變化加快cache命中:利用地址的物理部分進行索引限制cache不能超過頁面大小:那么，需要更大的cache時，怎么辦？增大相聯(lián)度將會使TAG和INDEX之間的界限右移頁面染色PageAddressPageOffsetAddressTagIndexBlockOffset如果索引就是地址的某一物理部分，就可以與變換并行開始標(biāo)志訪問，因而就可以與物理標(biāo)志進行比較

將標(biāo)簽檢測和更改cache分為不同流水級；當(dāng)前寫操作的標(biāo)簽檢測&上一次寫操作的cache更改流水線中只有STORES；失效時清空

Storer2,(r1) Checkr1

Add --

Sub --

Storer4,(r3) M[r1]<-r2& checkr3

陰影部分為延遲寫緩沖器（DelayedWriteBuffer）在讀操作中必須被檢測；3.通過流水化寫操作來加快命中時間4.TraceCacheinPentium4Howtosupplyenoughinstructionseverycyclewithoutdependencies?InsteadoflimitingtheinstructionsinastaticcacheblocktospatiallocalityAtracecachefindsadynamicsequenceofinstructionsincludingtakenbranchestoloadintoacacheblock.Muchmorecomplicatedaddressmappingmechanisms.Tracecachestorethesameinstructions