高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

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

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

(1989firstIntelμprocwithacacheonchip)

削減處理器-存儲(chǔ)器性能差距

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

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

(Blockidentification)標(biāo)記/信息塊Q3:在失效時(shí)，應(yīng)該替換掉哪個(gè)信息塊？(Blockreplacement)隨機(jī)、LRU、FIFOQ4:在寫(xiě)操作時(shí)，會(huì)發(fā)生什么情況(Writestrategy)回寫(xiě)（WriteBack）或直寫(xiě)（WriteThrough）(使用寫(xiě)緩沖器)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改進(jìn)Cache性能AverageMemoryaccesstime=Hittime+MissrateMisspenalty1.降低失效率

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

o或

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

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

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

3Cs中哪些失效會(huì)受到明顯影響?

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

3Cs中哪些失效會(huì)受到明顯影響?

3)改變編譯器:

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

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

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

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

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

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

減少val和key之間的沖突

改進(jìn)空間局部性循環(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];

用順序訪問(wèn)代替跳步（100個(gè)存儲(chǔ)字）訪問(wèn)存儲(chǔ)器改進(jìn)空間局部性循環(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];}

每次對(duì)a&c

訪問(wèn)兩次失效與每次訪問(wèn)一次失效;改進(jìn)空間局部性分塊示例兩個(gè)內(nèi)層循環(huán):讀取z[]的所有NN個(gè)元素分別讀取y[]一行的N個(gè)元素寫(xiě)x[]一行的N個(gè)元素容量失效是N和Cache容量的函數(shù)：3NN4=>無(wú)容量失效；否則...思路：計(jì)算滿(mǎn)足條件的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稱(chēng)為塊化因子（BlockingFactor）容量失效從2N3+N2

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

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

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

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

orlockup-freecache

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

AMAT=HitTimeL1+MissRateL1xMissPenaltyL1

MissPenaltyL1=HitTimeL2+MissRateL2xMissPenaltyL2 AMAT=HitTimeL1+

MissRateL1

x(HitTimeL2+

MissRateL2

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

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

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

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

非阻塞Cache + 3

二級(jí)Cache + 2失效率失效損失改進(jìn)Cache性能AverageMemoryaccesstime=Hittime+MissrateMisspenalty1.降低失效率

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

或者虛擬Cache（VirtualCache）

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

(也稱(chēng)為化名(synonyms));

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

進(jìn)程標(biāo)識(shí)符（processidentifiertag）

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

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

Storer2,(r1) Checkr1

Add --

Sub --

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

陰影部分為延遲寫(xiě)緩沖器（DelayedWriteBuffer）在讀操作中必須被檢測(cè)；3.通過(guò)流水化寫(xiě)操作來(lái)加快命中時(shí)間4.TraceCacheinPentium4Howtosupplyenoughinstructionseverycyclewithoutdependencies?InsteadoflimitingtheinstructionsinastaticcacheblocktospatiallocalityAtracecachefindsadynamicsequenceofinstructionsincludingtakenbranchestoloadintoacacheblock.Muchmorecomplicatedaddressmappingmechanisms.Tracecachestorethesameinstructions