動態(tài)調(diào)度（Cont）,推斷執(zhí)行和ILP

1、計算機體系結(jié)構 Chapter4_3.1動態(tài)調(diào)度動態(tài)調(diào)度 ( (Cont), Cont), 推斷執(zhí)行推斷執(zhí)行和和ILPILP計算機體系結(jié)構 Chapter4_3.2Review TomasuloTomasulo 引入動態(tài)調(diào)度的動機引入動態(tài)調(diào)度的動機 在沒有專用編譯器的情況下，提高系統(tǒng)性能 解決編譯時無法判定的部分相關問題 Scoreboard 和Tomasula Tomasula 主要貢獻主要貢獻 Dynamic scheduling Register renaming-消除了WAW，WAR相關 Load/store disambiguation 算法的主要缺陷算法的主要缺陷 復雜 要求高速C

2、DB 性能受限于Common Data Bus 動態(tài)硬件方案可以用硬件進行循環(huán)展開 如何處理分支? 我們可以用硬件做循環(huán)展開必須可以解決分支指令問題 如何處理精確中斷? Out-of-order execution out-of-order completion!計算機體系結(jié)構 Chapter4_3.3為什么順序發(fā)射為什么順序發(fā)射? 順序發(fā)射使我們可以進行程序的數(shù)據(jù)流分析 我們可以知道某條指令的結(jié)果會流向哪些指令 如果我們亂序發(fā)射，可能會混淆RAW和WAR相關 每一周期發(fā)射多條指令也使用該原則將會正確地工作: 需要多端口的 “rename table” ,以便同時對一組指令所用的寄存器重命名

3、需要在單周期內(nèi)發(fā)射到多個RS中. 寄存器文件需要有2x 個讀端口和x個寫端口.計算機體系結(jié)構 Chapter4_3.4關于異常處理關于異常處理? 亂序完成加大了實現(xiàn)精確中斷的難度 在前面指令還沒有完成時，寄存器文件中可能會有后面指令的運行結(jié)果. 如果這些前面的指令執(zhí)行時有中斷產(chǎn)生，怎么辦？ 例如：DIVD F10, F0, F2SUBD F4, F6, F8ADDD F12, F14, F16 需要“rollback” 寄存器文件到原來的狀態(tài): 精確中斷的含義是其返回地址為：-該地址之前的所有指令都已完成-其后的指令還都沒有完成 實現(xiàn)精確中斷的技術：順序完成（或提交） 即提交指令完成的順序必須

4、與指令發(fā)射的順序相同計算機體系結(jié)構 Chapter4_3.5進行循環(huán)重疊執(zhí)行需要盡快解決分支問題進行循環(huán)重疊執(zhí)行需要盡快解決分支問題! 在循環(huán)展開的例子中，我們假設整數(shù)部件可以快速解決分支問題，以便進行循環(huán)重疊執(zhí)行! Loop:LDF00R1MULTDF4F0F2SDF40R1SUBIR1R1#8BNEZR1Loop 如果分支依賴于multd,怎么辦? 需要能預測分支方向 如果分支成功，我們就可以重疊執(zhí)行循環(huán) 對于superscalar機器這一問題更加突出計算機體系結(jié)構 Chapter4_3.6控制相關的動態(tài)解決技術控制相關的動態(tài)解決技術 控制相關：由條件轉(zhuǎn)移或程序中斷引起的相關，也稱全局相關

5、?？刂葡嚓P對流水線的吞吐率和效率影響相對于數(shù)據(jù)相關要大得多 條件指令在一般程序中所占的比例相當大 中斷雖然在程序中所占的比例不大，但中斷發(fā)生在程序中的哪一條指令，發(fā)生在一條指令執(zhí)行過程中的哪一個功能段都是不確定的 處理好條件轉(zhuǎn)移和中斷引起的控制相關是很重要的。 關鍵問題： 要確保流水線能夠正常工作 減少因斷流引起的吞吐率和效率的下降計算機體系結(jié)構 Chapter4_3.7分支對性能的影響分支對性能的影響 假設在一條有K段的流水線中，在最后一段才能確定目標地址i-1ii+1i+2i+k-3p+1p+2p+k-3i+k-2p+k-2OutputOutput當分支方向預測錯誤時，不僅流水線中有多個功

6、能段要浪費，更嚴重的是可能造成程序執(zhí)行結(jié)果發(fā)生錯誤，因此當程序沿著錯誤方向運行后，作廢這些程序時，一定不能破壞通用寄存器和主存儲器的內(nèi)容。計算機體系結(jié)構 Chapter4_3.8條件轉(zhuǎn)移指令對流水線性能的影響條件轉(zhuǎn)移指令對流水線性能的影響 假設對于一條有K段的流水線，由于條件分支的影響，在最壞情況下，每次條件轉(zhuǎn)移將造成k-1個時鐘周期的斷流。假設條件分支在一般程序中所占的比例為p, 條件成功的概率為q。試分析分支對流水線的影響。 結(jié)論：條件轉(zhuǎn)移指令對流水線的影響很大，必須采取相關措施來減少這種影響。 預測可以是靜態(tài)預測“Static” (at compile time) 或動態(tài)預測 “Dyna

7、mic” (at runtime) 動態(tài)分支預測 vs. 靜態(tài)分支預測，哪個好？計算機體系結(jié)構 Chapter4_3.9Dynamic Branch Prediction 動態(tài)分支預測：預測分支的方向在程序運行時刻動態(tài)確定 需解決的關鍵問題是： 如何記錄轉(zhuǎn)移歷史信息 如何根據(jù)所記錄的轉(zhuǎn)移歷史信息，預測轉(zhuǎn)移的方向 主要方法 基于BPB(Branch Prediction Buffer)或BHT(Branch History Table)的方法-1-bit BHT和2-bit BHT-Correlating Branch Predictors-Tournament Predictors: Adap

8、tively Combining Local and Global Predictors High Performance Instruction Delivery-BTB-Integrated Instruction Fetch Units-Return Address Predictors Performance = (accuracy, cost of misprediction) Misprediction Flush Reorder Buffer計算機體系結(jié)構 Chapter4_3.101-bit BHT Branch History Table: 分支指令的PC的低位索引1-bit

9、 BHT 該表記錄上一次轉(zhuǎn)移是否成功 不做地址檢查 例題：一個循環(huán)供循環(huán)10次，它將分支成功9次，1次不成功，假設此分支的預測位始終在緩沖區(qū)中，那么分支預測的準確性是多少？ 靜態(tài)預測 vs. 動態(tài)預測 問題: 在一個循環(huán)中, 1-bit BHT 將導致2次分支預測錯誤(avg is 9 iteratios before exit): 最后一次循環(huán), 前面都是預測成功，而這次需要退出循環(huán) 第一次循環(huán)，由于前面預測為失敗，而這次實際上為成功計算機體系結(jié)構 Chapter4_3.11 解決辦法解決辦法: 2位記錄分支歷史位記錄分支歷史 Red: stop, not taken Green: go,

10、taken2-bit BHTNTTTNTPredict TakenPredict Not TakenPredict TakenPredict Not TakenTNTTNT計算機體系結(jié)構 Chapter4_3.12計算機體系結(jié)構 Chapter4_3.13計算機體系結(jié)構 Chapter4_3.14BHT Accuracy 分支預測錯誤的原因: 預測錯誤 由于使用PC的低位查找BHT表，可能得到錯誤的分支歷史記錄 BHT表的大小問題 4096 項的表分支預測錯誤的比例為1% (nasa7, tomcatv) to 18% (eqntott), spice at 9% and gcc at 12%

11、 再增加項數(shù)，對提高預測準確率幾乎沒有效果(in Alpha 21164)計算機體系結(jié)構 Chapter4_3.15Correlating Branch Predicator 例如： if (aa=2) aa=0; if (bb=2) bb=0; if (aa!=bb) 翻譯為DLX SUBI R3,R1,#2 BNEZ R3,L1 ; branch b1 (aa!=2) ADDI R1,R0,R0 ;aa=0 L1: SUBI R3,R2,#2 BNEZ R3,L2 ;branch b2(bb!=2) ADDI R2,R0,R0 ; bb=0 L2: SUBI R3,R1,R2 ;R3=aa

12、-bb BEQZ R3,L3 ;branch b3 (aa=bb)計算機體系結(jié)構 Chapter4_3.16Correlating Branches 觀察結(jié)果：b3 與分支b2 和b1相關。如果b1和b2都分支失敗，則b3一定成功。 Correlating predictors 或 兩級預測器：分支預測器根據(jù)其他分支的行為來進行預測。 工作原理：根據(jù)一個簡單的例子我們來看其基本原理 if (d=0)d=1; if (d=1) d=0; 翻譯為DLX BNEZ R1,L1 ;branch b1(d!=0) ADDI R1,R0,#1 ;d=0, so d=1 L1: ADDI R3,R1,#-1

13、 BNEZ R3,L2 ;branch b2(d!=1) . L2:計算機體系結(jié)構 Chapter4_3.17兩級預測器基本工作原理兩級預測器基本工作原理 假設d的初始值序列為0，1，2 b1 如果分支失敗，b2一定也分支失敗。 前面的兩位標準的預測方案就沒法利用這一點，而兩級預測方案就可以。計算機體系結(jié)構 Chapter4_3.18 假設d的初始值在2和0之間切換。 用1-bit預測器，初始設置為預測失敗，T表示預測成功，NT表示預測失敗。 結(jié)論：這樣的序列每次預測都錯，預測錯誤率100計算機體系結(jié)構 Chapter4_3.19Correlating Branches 基本思想：用1位作為c

14、orrelation位。即每個分支都有兩個相互獨立的預測位：一個預測位假設最近一次執(zhí)行的分支失敗時的預測位，另一個預測位是假設最近一次執(zhí)行的分支成功時的預測位。 最近一次執(zhí)行的分支通常與要預測的分支不是同一條指令 記為 （1，1）前一位表示最近一次分支失敗時的預測位，后一位表示最近一次分支成功時的預測位計算機體系結(jié)構 Chapter4_3.20 Correlating 預測器的預測和執(zhí)行情況， 顯然只有在第一次d=2時，預測錯誤，其他都預測正確 記為（1，1）預測器，即根據(jù)最近一次分支的行為來選擇一對1-bit預測器中的一個。 更一般的表示為（m, n)，即根據(jù)最近的m個分支，從2m個分支預測

15、器中選擇預測器，每個預測器的位數(shù)為n計算機體系結(jié)構 Chapter4_3.21Correlating Branches (2,2) predictor: 2-bit global, 2-bit localBranch address (4 bits)2-bits per branch local predictorsPrediction2-bit recent global branch history(01 = not taken then taken)計算機體系結(jié)構 Chapter4_3.22計算機體系結(jié)構 Chapter4_3.23Tournament Predictors Tourna

16、ment predictors: 使用兩個預測器 一個基于全局信息 一個基于局部信息 再加一個選擇器 Use the predictor that tends to guess correctlyaddrhistoryPredictor APredictor B計算機體系結(jié)構 Chapter4_3.24Tournament Predictor in Alpha 21264 Selector：4K 2-bit 計數(shù)器用來選擇全局預測器還是局部預測器 Global predictor： 使用4K項，根據(jù)最近的12個分支的執(zhí)行情況來索引，每項為標準的2-bit預測器 12-bit pattern:

17、ith bit 0 = ith prior branch not taken; ith bit 1 = ith prior branch taken; Local predictor ：兩級預測器 Top level ：1024個10-bit 項構成，每個10-bit項對應最近10次分支的轉(zhuǎn)移方向 Next level ：由Top level所選項中的10-bit索引找到1K 項中的對應項，每項由3-bit saturating counter 作為局部預測器 Total size: 4K*2 + 4K*2 + 1K*10 + 1K*3 = 29K bits!(180,000 transist

18、ors)計算機體系結(jié)構 Chapter4_3.25% of predictions from local predictor in Tournament Scheme98%100%94%90%55%76%72%63%37%69%0%20%40%60%80%100%nasa7matrix300tomcatvdoducspicefppppgccespressoeqntottli計算機體系結(jié)構 Chapter4_3.26Accuracy of Branch Prediction Profile: branch profile from last execution(static in that in

19、 encoded in instruction, but profile)fig 3.40計算機體系結(jié)構 Chapter4_3.27Accuracy v. Size (SPEC89)0%1%2%3%4%5%6%7%8%9%10%081624324048566472808896104112120128Total predictor size (Kbits)Conditional branch misprediction rateLocalCorrelatingTournament計算機體系結(jié)構 Chapter4_3.28 分支指令的地址作為BTB的索引，以得到分支預測地址 必須檢測分支指令的地址

20、是否匹配，以免用錯誤的分支地址 從表中得到預測地址分支方向確定后，更新預測的PCSimple dynamic prediction: Branch Target Buffer (BTB)Branch PCPredicted PC=?PC of instructionFETCHExtra prediction statebitsYes: instruction is branch and use predicted PC as next PCNo: branch not predicted, proceed normally (Next PC = PC+4)計算機體系結(jié)構 Chapter4_3.

21、29計算機體系結(jié)構 Chapter4_3.30 Determine the total branch penalty for a branch-target buffer assuming the penalty cycles for individual mispredictions from figure 2.24. Make the following assumptions about the prediction accuracy and hit rate: Prediction accuracy is 90% (for instructions in the butter) Hit

22、 rate in the buffer is 90% (for branches predicted taken)Ans. P1 = 90%*10% P2= 10% BP = (0.09+0.1)*2 = 0.38計算機體系結(jié)構 Chapter4_3.31Review 控制相關的動態(tài)解決技術控制相關的動態(tài)解決技術 動態(tài)分支預測：預測分支的方向在程序運行時刻動態(tài)確定 需解決的關鍵問題： 如何記錄轉(zhuǎn)移歷史信息 如何根據(jù)所記錄的轉(zhuǎn)移歷史信息，預測轉(zhuǎn)移的方向 主要方法 1-bit BHT和2-bit BHT Correlating Branch Predictors Tournament Predic

23、tors: Adaptively Combining Local and Global Predictors High Performance Instruction Delivery-BTB-Integrated Instruction Fetch Units-Return Address Predictors Performance = (accuracy, cost of misprediction) Misprediction Flush Reorder Buffer計算機體系結(jié)構 Chapter4_3.32Accuracy of Different SchemesFrequency

24、of MispredictionsFrequency of Mispredictions0%2%4%6%8%10%12%14%16%18%nasa7matrix300tomcatvdoducdspicefppppgccespressoeqntottli0%1%5%6%6%11%4%6%5%1%4,096 entries: 2-bits per entryUnlimited entries: 2-bits/entry1,024 entries (2,2)4096 Entries 2-bit BHTUnlimited Entries 2-bit BHT1024 Entries (2,2) BHT0

25、%18%Frequency of Mispredictions計算機體系結(jié)構 Chapter4_3.33HW support for More ILP 避免分支預測：將分支預測轉(zhuǎn)換為有條件的執(zhí)行指令: if (x) then A = B op C else NOP 如果條件不成立，即不寫結(jié)果，也不引起異常 擴展ISA, Alpha, MIPS, PowerPC, SPARC 的ISA , 存在條件傳送指令; PA-RISC 的“取消”分支指令 EPIC: 64 1-bit 條件位選擇有條件的執(zhí)行 帶條件的指令（conditional instructions）的缺陷： 如果取消該指令執(zhí)行，仍然

26、需要花費時間 如果檢測條件較晚，仍然要Stall 復雜條件將降低其有效性，條件是否成立要在流水線較后段才能知道計算機體系結(jié)構 Chapter4_3.34 需要硬件緩存沒有提交的指令結(jié)果: reorder buffer （ROB） 3 個域: 指令類型,目的地址, 值 Reorder buffer 可以作為操作數(shù)源 = 就像有更多的寄存器（與RS類似） 當程序執(zhí)行階段完成后，用ROB的編號代替RS中的值 增加指令提交階段 ROB提供執(zhí)行完成階段和提交階段的操作數(shù) 一旦操作數(shù)提交，結(jié)果就寫入寄存器 這樣，在預測失敗時，容易恢復推斷執(zhí)行的指令，或發(fā)生異常時，容易恢復狀態(tài)ReorderBufferFP

27、OpQueueFP AdderFP AdderRes StationsRes StationsFP Regs硬件支持精確中斷硬件支持精確中斷計算機體系結(jié)構 Chapter4_3.351. Issueget instruction from FP Op Queue 如果RS和ROB有空閑單元就發(fā)射指令。如果寄存器或ROB中源操作數(shù)可用，就將其發(fā)送到RS，目的地址的ROB編號也發(fā)送給RS (this stage sometimes called “dispatch”)2. Executionoperate on operands (EX) 當操作數(shù)就緒后，開始執(zhí)行。如果沒有就緒，監(jiān)測CDB，檢查R

28、AW相關3. Write resultfinish execution (WB) 將運算結(jié)果通過CDB傳送給所有等待結(jié)果的FU以及ROB單元，標識RS可用4. Commitupdate register with reorder result 按ROB表中順序，如果結(jié)果已有，就更新寄存器（或存儲器），并將該指令從ROB表中刪除 預測失敗或有中斷時，刷新ROB支持推斷執(zhí)行的支持推斷執(zhí)行的 Tomasulo 算法的四階段算法的四階段計算機體系結(jié)構 Chapter4_3.36LD F6, 34(R2)LD F2, 45(R3)MULT F0, F2, F4SUBD F8, F6, F2DIVD F1

29、0, F0, F6ADDD F6, F8, F2計算機體系結(jié)構 Chapter4_3.37計算機體系結(jié)構 Chapter4_3.38計算機體系結(jié)構 Chapter4_3.39計算機體系結(jié)構 Chapter4_3.40計算機體系結(jié)構 Chapter4_3.41v計算機體系結(jié)構 Chapter4_3.42計算機體系結(jié)構 Chapter4_3.43計算機體系結(jié)構 Chapter4_3.44計算機體系結(jié)構 Chapter4_3.45計算機體系結(jié)構 Chapter4_3.46計算機體系結(jié)構 Chapter4_3.47計算機體系結(jié)構 Chapter4_3.48計算機體系結(jié)構 Chapter4_3.49計算

30、機體系結(jié)構 Chapter4_3.50計算機體系結(jié)構 Chapter4_3.51計算機體系結(jié)構 Chapter4_3.52計算機體系結(jié)構 Chapter4_3.53計算機體系結(jié)構 Chapter4_3.54計算機體系結(jié)構 Chapter4_3.55計算機體系結(jié)構 Chapter4_3.56計算機體系結(jié)構 Chapter4_3.57消除存儲器的二義性消除存儲器的二義性 : 處理對存儲器引用的處理對存儲器引用的RAW相關相關 Question: 給定一個指令序列，store，load 這兩個操作是否有關？ 即下列代碼是否有相關問題?Eg:st0(R2),R5 ldR6,0(R3) 我們是否可以較早

31、啟動ld? Store的地址可能會延遲很長時間才能得到. 我們也許想在同一個周期開始這兩個操作的執(zhí)行. 兩種方法: No Speculation: 不進行l(wèi)oad操作，直到我們確信地址 0(R2) 0(R3) Speculation: 我們可以假設他們相關還是不相關 (called “dependence speculation”) ，如果推測錯誤通過ROB來修正計算機體系結(jié)構 Chapter4_3.58 需要緩沖區(qū)以程序序保存所有對存儲器的寫操作 保存地址（地址可用時）和值（值可用時） FIFO ordering: 以程序序確認和刪除store 當發(fā)射一個load操作時，記錄當前store隊

32、列的頭指針. 當load的地址可用時，檢查store隊列: 如果在load前存在正等待該地址的store操作，則stall該load操作 如果load地址與前面的store地址匹配，則有 memory-induced RAW hazard:-存儲的值可用 返回值-存儲的值還沒有準備好 返回該store指令的ROB編號 否則發(fā)出存儲器請求 由于實際的store操作順序提交，所以不會有WAW 相關.Hardware Support for Memory Disambiguation計算機體系結(jié)構 Chapter4_3.59-LD F4, 10(R3)NMemory Disambiguation:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F2F0- ST 10(R3), F5 LD F0,32(R2)ST 0(R3), F4NNYDone?DestDestOldestNewestfrom Memory2 32+R24 ROB3DestReorder BufferRegisters計算機體系結(jié)構 Chapter4_3.60Relationship betw