動(dòng)態(tài)調(diào)度(Cont)-推斷執(zhí)行和ILP

動(dòng)態(tài)調(diào)度(Cont),推斷執(zhí)行和ILPReviewTomasulo引入動(dòng)態(tài)調(diào)度的動(dòng)機(jī)在沒(méi)有專(zhuān)用編譯器的情況下，提高系統(tǒng)性能解決編譯時(shí)無(wú)法判定的部分相關(guān)問(wèn)題Scoreboard和TomasulaTomasula

主要貢獻(xiàn)DynamicschedulingRegisterrenaming---消除了WAW，WAR相關(guān)Load/storedisambiguation算法的主要缺陷復(fù)雜要求高速CDB性能受限于CommonDataBus動(dòng)態(tài)硬件方案可以用硬件進(jìn)行循環(huán)展開(kāi)如何處理分支?我們可以用硬件做循環(huán)展開(kāi)必須可以解決分支指令問(wèn)題如何處理精確中斷?Out-of-orderexecutionout-of-ordercompletion!為什么順序發(fā)射?順序發(fā)射使我們可以進(jìn)行程序的數(shù)據(jù)流分析我們可以知道某條指令的結(jié)果會(huì)流向哪些指令如果我們亂序發(fā)射，可能會(huì)混淆RAW和WAR相關(guān)每一周期發(fā)射多條指令也使用該原則將會(huì)正確地工作:需要多端口的“renametable”,以便同時(shí)對(duì)一組指令所用的寄存器重命名需要在單周期內(nèi)發(fā)射到多個(gè)RS中.

寄存器文件需要有2x個(gè)讀端口和x個(gè)寫(xiě)端口.

關(guān)于異常處理???亂序完成加大了實(shí)現(xiàn)精確中斷的難度在前面指令還沒(méi)有完成時(shí)，寄存器文件中可能會(huì)有后面指令的運(yùn)行結(jié)果.如果這些前面的指令執(zhí)行時(shí)有中斷產(chǎn)生，怎么辦？例如：DIVDF10,F0,F2SUBDF4,F6,F8ADDDF12,F14,F16需要“rollback”寄存器文件到原來(lái)的狀態(tài):精確中斷的含義是其返回地址為：該地址之前的所有指令都已完成其后的指令還都沒(méi)有完成實(shí)現(xiàn)精確中斷的技術(shù)：順序完成（或提交）即提交指令完成的順序必須與指令發(fā)射的順序相同進(jìn)行循環(huán)重疊執(zhí)行需要盡快解決分支問(wèn)題!在循環(huán)展開(kāi)的例子中，我們假設(shè)整數(shù)部件可以快速解決分支問(wèn)題，以便進(jìn)行循環(huán)重疊執(zhí)行!

Loop: LD F0 0 R1

MULTD F4 F0 F2

SD F4 0 R1

SUBI R1 R1 #8

BNEZ R1 Loop如果分支依賴于multd,怎么辦??需要能預(yù)測(cè)分支方向如果分支成功，我們就可以重疊執(zhí)行循環(huán)對(duì)于superscalar機(jī)器這一問(wèn)題更加突出控制相關(guān)的動(dòng)態(tài)解決技術(shù)控制相關(guān)：由條件轉(zhuǎn)移或程序中斷引起的相關(guān)，也稱(chēng)全局相關(guān)。控制相關(guān)對(duì)流水線的吞吐率和效率影響相對(duì)于數(shù)據(jù)相關(guān)要大得多條件指令在一般程序中所占的比例相當(dāng)大中斷雖然在程序中所占的比例不大，但中斷發(fā)生在程序中的哪一條指令，發(fā)生在一條指令執(zhí)行過(guò)程中的哪一個(gè)功能段都是不確定的處理好條件轉(zhuǎn)移和中斷引起的控制相關(guān)是很重要的。關(guān)鍵問(wèn)題：要確保流水線能夠正常工作減少因斷流引起的吞吐率和效率的下降分支對(duì)性能的影響假設(shè)在一條有K段的流水線中，在最后一段才能確定目標(biāo)地址i-1ii+1i+2i+k-3p+1p+2p+k-3i+k-2p+k-2OutputOutput當(dāng)分支方向預(yù)測(cè)錯(cuò)誤時(shí)，不僅流水線中有多個(gè)功能段要浪費(fèi)，更嚴(yán)重的是可能造成程序執(zhí)行結(jié)果發(fā)生錯(cuò)誤，因此當(dāng)程序沿著錯(cuò)誤方向運(yùn)行后，作廢這些程序時(shí)，一定不能破壞通用寄存器和主存儲(chǔ)器的內(nèi)容。條件轉(zhuǎn)移指令對(duì)流水線性能的影響假設(shè)對(duì)于一條有K段的流水線，由于條件分支的影響，在最壞情況下，每次條件轉(zhuǎn)移將造成k-1個(gè)時(shí)鐘周期的斷流。假設(shè)條件分支在一般程序中所占的比例為p,條件成功的概率為q。試分析分支對(duì)流水線的影響。結(jié)論：條件轉(zhuǎn)移指令對(duì)流水線的影響很大，必須采取相關(guān)措施來(lái)減少這種影響。預(yù)測(cè)可以是靜態(tài)預(yù)測(cè)“Static”(atcompiletime)或動(dòng)態(tài)預(yù)測(cè)“Dynamic”(atruntime)動(dòng)態(tài)分支預(yù)測(cè)vs.靜態(tài)分支預(yù)測(cè)，哪個(gè)好？DynamicBranchPrediction動(dòng)態(tài)分支預(yù)測(cè)：預(yù)測(cè)分支的方向在程序運(yùn)行時(shí)刻動(dòng)態(tài)確定需解決的關(guān)鍵問(wèn)題是：如何記錄轉(zhuǎn)移歷史信息如何根據(jù)所記錄的轉(zhuǎn)移歷史信息，預(yù)測(cè)轉(zhuǎn)移的方向主要方法基于BPB(BranchPredictionBuffer)或BHT(BranchHistoryTable)的方法1-bitBHT和2-bitBHTCorrelatingBranchPredictorsTournamentPredictors:AdaptivelyCombiningLocalandGlobalPredictorsHighPerformanceInstructionDeliveryBTBIntegratedInstructionFetchUnitsReturnAddressPredictorsPerformance=?(accuracy,costofmisprediction)Misprediction

FlushReorderBuffer1-bitBHTBranchHistoryTable:分支指令的PC的低位索引1-bitBHT該表記錄上一次轉(zhuǎn)移是否成功不做地址檢查例題：一個(gè)循環(huán)供循環(huán)10次，它將分支成功9次，1次不成功，假設(shè)此分支的預(yù)測(cè)位始終在緩沖區(qū)中，那么分支預(yù)測(cè)的準(zhǔn)確性是多少？靜態(tài)預(yù)測(cè)vs.動(dòng)態(tài)預(yù)測(cè)問(wèn)題:在一個(gè)循環(huán)中,1-bitBHT將導(dǎo)致2次分支預(yù)測(cè)錯(cuò)誤(avgis9iteratiosbeforeexit):最后一次循環(huán),前面都是預(yù)測(cè)成功，而這次需要退出循環(huán)第一次循環(huán)，由于前面預(yù)測(cè)為失敗，而這次實(shí)際上為成功解決辦法:2位記錄分支歷史Red:stop,nottakenGreen:go,taken2-bitBHTNTTTNTPredictTakenPredictNotTakenPredictTakenPredictNotTakenTNTTNTBHTAccuracy分支預(yù)測(cè)錯(cuò)誤的原因:預(yù)測(cè)錯(cuò)誤由于使用PC的低位查找BHT表，可能得到錯(cuò)誤的分支歷史記錄BHT表的大小問(wèn)題4096項(xiàng)的表分支預(yù)測(cè)錯(cuò)誤的比例為1%(nasa7,tomcatv)to18%(eqntott),spiceat9%andgccat12%再增加項(xiàng)數(shù)，對(duì)提高預(yù)測(cè)準(zhǔn)確率幾乎沒(méi)有效果

(inAlpha21164)CorrelatingBranchPredicator例如：

if(aa==2)aa=0;if(bb==2)bb=0;if(aa!=bb){翻譯為DLX

SUBIR3,R1,#2BNEZR3,L1;branchb1(aa!=2)ADDIR1,R0,R0;aa=0L1:SUBIR3,R2,#2BNEZR3,L2;branchb2(bb!=2)ADDIR2,R0,R0;bb=0L2:SUBIR3,R1,R2;R3=aa-bbBEQZR3,L3;branchb3(aa==bb)CorrelatingBranches觀察結(jié)果：b3與分支b2和b1相關(guān)。如果b1和b2都分支失敗，則b3一定成功。Correlatingpredictors或兩級(jí)預(yù)測(cè)器：分支預(yù)測(cè)器根據(jù)其他分支的行為來(lái)進(jìn)行預(yù)測(cè)。工作原理：根據(jù)一個(gè)簡(jiǎn)單的例子我們來(lái)看其基本原理

if(d==0)d=1;if(d==1)d=0;翻譯為DLXBNEZR1,L1;branchb1(d!=0)ADDIR1,R0,#1;d==0,sod=1L1:ADDIR3,R1,#-1BNEZR3,L2;branchb2(d!=1)...

L2:兩級(jí)預(yù)測(cè)器基本工作原理假設(shè)d的初始值序列為0，1，2b1如果分支失敗，b2一定也分支失敗。前面的兩位標(biāo)準(zhǔn)的預(yù)測(cè)方案就沒(méi)法利用這一點(diǎn)，而兩級(jí)預(yù)測(cè)方案就可以。假設(shè)d的初始值在2和0之間切換。用1-bit預(yù)測(cè)器，初始設(shè)置為預(yù)測(cè)失敗，T表示預(yù)測(cè)成功，NT表示預(yù)測(cè)失敗。結(jié)論：這樣的序列每次預(yù)測(cè)都錯(cuò)，預(yù)測(cè)錯(cuò)誤率100％CorrelatingBranches基本思想：用1位作為correlation位。即每個(gè)分支都有兩個(gè)相互獨(dú)立的預(yù)測(cè)位：一個(gè)預(yù)測(cè)位假設(shè)最近一次執(zhí)行的分支失敗時(shí)的預(yù)測(cè)位，另一個(gè)預(yù)測(cè)位是假設(shè)最近一次執(zhí)行的分支成功時(shí)的預(yù)測(cè)位。最近一次執(zhí)行的分支通常與要預(yù)測(cè)的分支不是同一條指令記為（1，1）前一位表示最近一次分支失敗時(shí)的預(yù)測(cè)位，后一位表示最近一次分支成功時(shí)的預(yù)測(cè)位Correlating預(yù)測(cè)器的預(yù)測(cè)和執(zhí)行情況，顯然只有在第一次d=2時(shí)，預(yù)測(cè)錯(cuò)誤，其他都預(yù)測(cè)正確記為（1，1）預(yù)測(cè)器，即根據(jù)最近一次分支的行為來(lái)選擇一對(duì)1-bit預(yù)測(cè)器中的一個(gè)。更一般的表示為（m,n)，即根據(jù)最近的m個(gè)分支，從2m個(gè)分支預(yù)測(cè)器中選擇預(yù)測(cè)器，每個(gè)預(yù)測(cè)器的位數(shù)為nCorrelatingBranches

(2,2)predictor:2-bitglobal,2-bitlocalBranchaddress(4bits)2-bitsperbranch

localpredictorsPrediction2-bitrecentglobalbranchhistory(01=nottakenthentaken)TournamentPredictorsTournamentpredictors:使用兩個(gè)預(yù)測(cè)器一個(gè)基于全局信息一個(gè)基于局部信息再加一個(gè)選擇器UsethepredictorthattendstoguesscorrectlyaddrhistoryPredictorAPredictorBTournamentPredictorinAlpha21264Selector：4K2-bit計(jì)數(shù)器用來(lái)選擇全局預(yù)測(cè)器還是局部預(yù)測(cè)器Globalpredictor：

使用4K項(xiàng)，根據(jù)最近的12個(gè)分支的執(zhí)行情況來(lái)索引，每項(xiàng)為標(biāo)準(zhǔn)的2-bit預(yù)測(cè)器12-bitpattern:ithbit0=>ithpriorbranchnottaken;

ithbit1=>ithpriorbranchtaken;Localpredictor

：兩級(jí)預(yù)測(cè)器Toplevel

：1024個(gè)10-bit項(xiàng)構(gòu)成，每個(gè)10-bit項(xiàng)對(duì)應(yīng)最近10次分支的轉(zhuǎn)移方向Nextlevel

：由Toplevel所選項(xiàng)中的10-bit索引找到1K項(xiàng)中的對(duì)應(yīng)項(xiàng)，每項(xiàng)由3-bitsaturatingcounter作為局部預(yù)測(cè)器Totalsize:4K*2+4K*2+1K*10+1K*3=29Kbits! (~180,000transistors)%ofpredictionsfromlocalpredictorinTournamentSchemeAccuracyofBranchPredictionProfile:branchprofilefromlastexecution

(staticinthatinencodedininstruction,butprofile)fig3.40Accuracyv.Size(SPEC89)分支指令的地址作為BTB的索引，以得到分支預(yù)測(cè)地址必須檢測(cè)分支指令的地址是否匹配，以免用錯(cuò)誤的分支地址從表中得到預(yù)測(cè)地址

分支方向確定后，更新預(yù)測(cè)的PCSimpledynamicprediction:BranchTargetBuffer(BTB)BranchPCPredictedPC=?PCofinstructionFETCHExtrapredictionstatebitsYes:instructionisbranchandusepredictedPCasnextPCNo:branchnotpredicted,proceednormally(NextPC=PC+4)Determinethetotalbranchpenaltyforabranch-targetbufferassumingthepenaltycyclesforindividualmispredictionsfromfigure2.24.Makethefollowingassumptionsaboutthepredictionaccuracyandhitrate:Predictionaccuracyis90%(forinstructionsinthebutter)Hitrateinthebufferis90%(forbranchespredictedtaken)Ans.P1=90%*10%P2=10%BP=(0.09+0.1)*2=0.38Review–

控制相關(guān)的動(dòng)態(tài)解決技術(shù)

動(dòng)態(tài)分支預(yù)測(cè)：預(yù)測(cè)分支的方向在程序運(yùn)行時(shí)刻動(dòng)態(tài)確定需解決的關(guān)鍵問(wèn)題：如何記錄轉(zhuǎn)移歷史信息如何根據(jù)所記錄的轉(zhuǎn)移歷史信息，預(yù)測(cè)轉(zhuǎn)移的方向主要方法1-bitBHT和2-bitBHTCorrelatingBranchPredictorsTournamentPredictors:AdaptivelyCombiningLocalandGlobalPredictorsHighPerformanceInstructionDeliveryBTBIntegratedInstructionFetchUnitsReturnAddressPredictorsPerformance=?(accuracy,costofmisprediction)Misprediction

FlushReorderBufferAccuracyofDifferentSchemes4096Entries2-bitBHTUnlimitedEntries2-bitBHT1024Entries(2,2)BHT0%18%FrequencyofMispredictionsHWsupportforMoreILP避免分支預(yù)測(cè)：將分支預(yù)測(cè)轉(zhuǎn)換為有條件的執(zhí)行指令:

if(x)thenA=BopCelseNOP如果條件不成立，即不寫(xiě)結(jié)果，也不引起異常擴(kuò)展ISA,Alpha,MIPS,PowerPC,SPARC的ISA,存在條件傳送指令;PA-RISC的“取消”分支指令EPIC:641-bit條件位選擇有條件的執(zhí)行帶條件的指令（conditionalinstructions）的缺陷：如果取消該指令執(zhí)行，仍然需要花費(fèi)時(shí)間如果檢測(cè)條件較晚，仍然要Stall復(fù)雜條件將降低其有效性，條件是否成立要在流水線較后段才能知道

需要硬件緩存沒(méi)有提交的指令結(jié)果:reorderbuffer（ROB）3個(gè)域:指令類(lèi)型,目的地址,值Reorderbuffer可以作為操作數(shù)源=>就像有更多的寄存器（與RS類(lèi)似）當(dāng)程序執(zhí)行階段完成后，用ROB的編號(hào)代替RS中的值增加指令提交階段ROB提供執(zhí)行完成階段和提交階段的操作數(shù)一旦操作數(shù)提交，結(jié)果就寫(xiě)入寄存器這樣，在預(yù)測(cè)失敗時(shí)，容易恢復(fù)推斷執(zhí)行的指令，或發(fā)生異常時(shí)，容易恢復(fù)狀態(tài)ReorderBufferFPOpQueueFPAdderFPAdderResStationsResStationsFPRegs硬件支持精確中斷1.Issue—getinstructionfromFPOpQueue如果RS和ROB有空閑單元就發(fā)射指令。如果寄存器或ROB中源操作數(shù)可用，就將其發(fā)送到RS，目的地址的ROB編號(hào)也發(fā)送給RS(thisstagesometimescalled“dispatch”)2.Execution—operateonoperands(EX)當(dāng)操作數(shù)就緒后，開(kāi)始執(zhí)行。如果沒(méi)有就緒，監(jiān)測(cè)CDB，檢查RAW相關(guān)3.Writeresult—finishexecution(WB)將運(yùn)算結(jié)果通過(guò)CDB傳送給所有等待結(jié)果的FU以及ROB單元，標(biāo)識(shí)RS可用4.Commit—updateregisterwithreorderresult按ROB表中順序，如果結(jié)果已有，就更新寄存器（或存儲(chǔ)器），并將該指令從ROB表中刪除預(yù)測(cè)失敗或有中斷時(shí)，刷新ROB支持推斷執(zhí)行的

Tomasulo

算法的四階段 LDF6,34(R2) LDF2,45(R3) MULTF0,F2,F4 SUBDF8,F6,F2 DIVDF10,F0,F6 ADDDF6,F8,F2v消除存儲(chǔ)器的二義性:

處理對(duì)存儲(chǔ)器引用的RAW相關(guān)Question:給定一個(gè)指令序列，store，load這兩個(gè)操作是否有關(guān)？即下列代碼是否有相關(guān)問(wèn)題?

Eg: st 0(R2),R5

ld R6,0(R3)我們是否可以較早啟動(dòng)ld?Store的地址可能會(huì)延遲很長(zhǎng)時(shí)間才能得到.我們也許想在同一個(gè)周期開(kāi)始這兩個(gè)操作的執(zhí)行.兩種方法:NoSpeculation:

不進(jìn)行l(wèi)oad操作，直到我們確信地址0(R2)0(R3)Speculation:

我們可以假設(shè)他們相關(guān)還是不相關(guān)(called“dependencespeculation”)，如果推測(cè)錯(cuò)誤通過(guò)ROB來(lái)修正需要緩沖區(qū)以程序序保存所有對(duì)存儲(chǔ)器的寫(xiě)操作保存地址（地址可用時(shí)）和值（值可用時(shí)）FIFOordering:以程序序確認(rèn)和刪除store當(dāng)發(fā)射一個(gè)load操作時(shí)，記錄當(dāng)前store隊(duì)列的頭指針.當(dāng)load的地址可用時(shí)，檢查store隊(duì)列:如果在load前存在正等待該地址的store操作，則stall該load操作如果load地址與前面的store地址匹配，則有

memory-inducedRAWhazard:存儲(chǔ)的值可用

返回值存儲(chǔ)的值還沒(méi)有準(zhǔn)備好

返回該store指令的ROB編號(hào)否則發(fā)出存儲(chǔ)器請(qǐng)求由于實(shí)際的store操作順序提交，所以不會(huì)有WAW相關(guān).HardwareSupportforMemoryDisambiguation--LDF4,10(R3)NMemoryDisambiguation:ToMemoryFPaddersFPmultipliersReservationStationsFPOpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F2F0--<val1>ST10(R3),F5LDF0,32(R2)ST0(R3),F4NNYDone?DestDestOldestNewestfromMemory232+R24

ROB3DestReorderBufferRegistersRelationshipbetweenpreciseinterruptsandspeculation:推斷是猜測(cè)的一種形式Branchpredicti