1、1,高性能計算機系統(tǒng)結構,2,轉移預測,轉移指令 程序的轉移行為 軟件方法解決控制相關 硬件動態(tài)轉移預測 常見處理器的轉移猜測,3,轉移指令,4,轉移指令計算的下一條指令地址在EX階段計算，下一條指令等2拍 使用專門的地址運算部件把地址計算提前到譯碼階段可以少等一拍 使用一個delay slot可以不用等待 多發(fā)射情況下延遲槽成為需要專門照顧的負擔,控制相關,5,轉移指令對性能的影響,分支指令的影響是開發(fā)指令級并行性的重要障礙 一條指令流中，平均每5-7條指令中就有一條是分支指令，也即基本塊大小為5-7條指令。 增大發(fā)射寬度 在發(fā)射寬度為n的處理器中，遇到分支指令的速度也快了n倍 增加流水線深

2、度 流水線越深，處理分支指令所需要的時鐘周期數(shù)就越多,6,一個例子,假設平均每8條指令中有一條轉移指令，某處理器采用4發(fā)射結構，第10級流水解決轉移地址相關（即第10級流水算出轉移方向和目標） 在A系統(tǒng)中不進行轉移預測，遇到轉移指令就等待，指令帶寬浪費36/(36+8)=82%； 在B系統(tǒng)中進行簡單的轉移預測，轉移猜錯率為50%，那么平均每16條指令預測錯誤一次，指令帶寬浪費36/(36+16)=75% 在C系統(tǒng)中，轉移指令猜錯率為10%，那么平均每80條指令預測錯誤一次，指令帶寬浪費36/(36+80)=31%； 在D系統(tǒng)中，轉移指令猜錯率為4%，平均每200條指令預測錯誤一次，取指令帶寬浪

3、費36/(36+200)=15%。,7,轉移指令的屬性,條件轉移與無條件轉移 條件轉移：需等待條件的確定后才能取指，程序中多數(shù)轉移指令是條件轉移指令 無條件轉移：不用判斷條件就轉移，如call/return 直接轉移與間接轉移 直接轉移：轉移目標根據(jù)指令內(nèi)容直接得出 間接轉移：轉移目標在寄存器中 相對轉移與絕對轉移 相對轉移：轉移目標為當前PC值加上偏移量 絕對轉移：轉移目標由指令或寄存器內(nèi)容直接給出 理論上有8種組合 實際上不實現(xiàn)所有組合,8,MIPS指令系統(tǒng)的轉移指令,條件轉移 都是直接、相對轉移，如BEQ，BGEZ 無條件直接轉移 轉移目標為PC31:28,IR25:0,2b0 J與JA

4、L 無條件間接轉移 轉移目標為寄存器內(nèi)容 JR與JALR MIPS轉移指令特點 likely與非likely，如BEQL，BGEZL 沒有Call/Return，通過link類轉移指令實現(xiàn)call功能，如JAL,9,程序的轉移行為,10,SPEC CPU2000轉移指令統(tǒng)計（1）,龍芯2號統(tǒng)計結果,11,SPEC CPU2000轉移指令統(tǒng)計（2）,龍芯2號統(tǒng)計結果,12,發(fā)射寬度增加，分支間的動態(tài)距離就會越小，分支預測的延遲對性能的影響就越大，當要求更高的發(fā)射寬度時，需要每個周期做不止一個預測,轉移指令間距離統(tǒng)計（1）,13,Inter-branch distance(cycles) 模擬環(huán)境

5、：4發(fā)射亂序機器 SPECint2000,轉移指令間距離統(tǒng)計（2）,14,龍芯2號上部分SPEC CPU2000程序中不同類型轉移指令分布 1是間接分支指令，采用BTB預測 5是返回指令，返回地址棧RAS預測 29是無條件立即跳轉指令，跳轉地址在指令中 65%是條件分支，大量的工作是進行條件分支預測,不同類型轉移指令分布,15,轉移指令的執(zhí)行頻率分布,龍芯2號上部分SPEC CPU2000程序中轉移指令執(zhí)行頻率分布 左圖表示執(zhí)行一定次數(shù)的轉移指令在所有轉移指令中的靜態(tài)分布，右圖表示執(zhí)行一定次數(shù)的轉移指令在所有轉移指令中的動態(tài)分布 所有轉移指令的44%僅僅執(zhí)行99次或者更少，這53%的轉移指令占

6、所有轉移指令總執(zhí)行次數(shù)的0.03% 只有4.2%的轉移指令執(zhí)行了超過100000次或者更多，占所有轉移指令總執(zhí)行次數(shù)的87%（或者說，只有14.7%的轉移指令超過了10000次，占所有轉移指令總執(zhí)行次數(shù)的97%）。,16,轉移成功率分布,龍芯2號上部分SPEC CPU2000程序轉移指令的跳轉成功率 45%的指令總是跳轉，15%的指令總是不跳轉 20%的指令跳轉的幾率小于5%或者大于95%，也就是說，80%的轉移指令具有強烈的一個跳轉方向，具有挑戰(zhàn)性的工作是預測其余20%轉移指令的跳轉方向。,17,分支的可預測性,利用單個轉移指令的重復性 基于模式的預測方法 利用不同轉移指令之間的關系 基于相

7、關的預測方法 方向相關、路徑相關,18,利用單個轉移指令重復性,循環(huán)型分支 for型循環(huán)：TTTN（成功n次后跟一次不成功 ） while型循環(huán)：NNNT（不成功n次后跟一次成功） 周期重復模式型分支 定長重復模式類分支：patq , |pat|=k （每隔k個分支模式就重復一次） 塊模式類分支：Tn Nmq 成功n次，不成功m次，如此循環(huán),19,利用轉移指令之間的方向相關,兩個分支的條件（完全或部分）基于相同或相關的信息 第二個分支的結果基于第一個分支的結果產(chǎn)生,20,利用轉移指令之間的路徑相關,如果一個分支是通向當前分支的前n條分支之一，則稱該分支處在當前分支的路徑之上。 處在當前分支路徑

8、上的分支與當前分支結果之間的相關稱為路徑相關,21,分支指令行為小結,分支指令是很頻繁的 分支指令有較好的局部性 分支指令具有可預測性,22,軟件方法解決控制相關,23,阻塞 等待直到轉移條件確定 用延遲槽容忍延遲 延遲槽指令來源 編譯器優(yōu)化 循環(huán)：循環(huán)展開減少轉移指令、軟流水減少阻塞 分支：全局代碼調(diào)度（越過分支調(diào)度指令） 函數(shù)調(diào)用：inline 轉換為數(shù)據(jù)相關 條件指令、謂詞 硬件轉移預測 轉移條件未確定時預測轉移是否成功 靜態(tài)與動態(tài)預測,解決轉移條件相關的方法,24,延遲槽指令的來源 來自轉移指令前：肯定執(zhí)行 來自轉移目標地址：轉移成功才執(zhí)行 來自轉移不成功地址：轉移不成功才執(zhí)行 單延遲

9、槽的編譯效果 能為 60% 左右的轉移延遲槽找到有效操作 大約80%的延遲槽指令用于有效計算 因此大約50% (60% x 80%) 的延遲槽操作用于有效計算 延遲槽的限制 超流水情況下一條延遲槽不夠 多發(fā)射情況下延遲槽反而成為需要特殊照顧的兼容負擔,利用延遲槽,25,軟件循環(huán)展開消除控制相關,軟件展開兩個循環(huán) 循環(huán)展開 寄存器重命名 變換次序 軟件循環(huán)展開的不足 有些循環(huán)不好展開（如循環(huán)次數(shù)不定的循環(huán)） 增加指令CACHE的負擔,LDF00R1 MULTDF4F0F2 SDF40R1 LDF00R1 MULTDF4F0F2 SDF40R1,LDF00R1 MULTDF4F0F2 SDF40R

10、1 LDF60R1 MULTDF8F6F2 SDF80R1,LDF00R1 LDF60R1 MULTDF4F0F2 MULTDF8F6F2 SDF40R1 SDF80R1,26,循環(huán)的數(shù)據(jù)相關,循環(huán)內(nèi)相關：S2使用同一次循環(huán)中S1計算的Ai+1. 循環(huán)間（loop-carried）相關：本次循環(huán)計算的Ai+1/Bi+1將被下一次循環(huán)使用。 循環(huán)內(nèi)相關導致一個循環(huán)體內(nèi)的多條指令不能并行執(zhí)行，循環(huán)間相關導致多個循環(huán)體不能并行執(zhí)行,27,循環(huán)展開的條件,數(shù)組元素相關的判斷 仿射（Affine）和非仿射（nonaffine） Xa*i+b XYi 最大公約數(shù)法 Xa*j+b = Xc*k+d GCD(

11、a,c)整除(d-b)則有相關 名字相關的消除 重命名技術 指針相關的判斷 只有一些經(jīng)驗的方法,28,軟流水,新循環(huán)體的每個操作來自不同的循環(huán)體，以分開數(shù)據(jù)相關的指令，相當于軟件的Tomasulo算法 符號級循環(huán)展開，比真正循環(huán)展開代碼開銷小,29,把控制相關轉換成數(shù)據(jù)相關,把條件轉移指令轉換為條件執(zhí)行 if (x) then A = B op C else NOP 只有條件為真時才寫結果，為假時不寫結果也不發(fā)生例外 RISC系統(tǒng)如Alpha, MIPS, PowerPC, SPARC都增加了條件MOVE指令; PA-RISC的nullification EPIC: 使用64個1位的謂詞寄存器

12、來選擇是否寫執(zhí)行結果 條件指令的缺點 條件為假時仍需要1拍，占用發(fā)射槽和功能部件 條件未確定仍需要在執(zhí)行前等待，轉移猜測反而在執(zhí)行后 條件復雜時會降低效率，因為條件在執(zhí)行時才確定,30,條件指令舉例,假設轉移指令沒有延遲槽 條件指令可消除簡單的條件轉移，對取絕對值等操作有用 條件指令仍要在執(zhí)行前等待條件，注意例外的處理,/if (A=0) S=T; BNEZ R1,L ADDU R2,R3,R0 L:,CMOVZ R2,R3,R1,LW R1,40(R2) ADD R3,R4,R5 ADD R6,R3,R7 BEQZ R10,L LW R8,0(R10) LW R9,0(R8),LW R1,4

13、0(R2) ADD R3,R4,R5 LWC R8,0(R10),R10 ADD R6,R3,R7 BEQZ R10,L LW R9,0(R8),31,硬件轉移預測,32,在取指或譯碼階段預測轉移是否成功以及轉移目標進行后續(xù)指令的取指 以減少指令流水線由于控制相關而堵塞 在執(zhí)行階段判斷轉移預測是否正確 如果猜測正確，則正常提交 如果猜測錯誤，則取消該轉移指令及其后續(xù)指令,硬件轉移預測基本思路,33,猜測依據(jù) 當前指令的地址（PC）和性質(zhì)（是否轉移指令） 過去轉移指令歷史記錄 猜測內(nèi)容 轉移方向、轉移目標地址,硬件轉移預測基本原理,34,分支處理機制的性能取決于,預測精度（BPA）= 設計好的預

14、測器 預測精度越高，能抽取的并行性就越多 預測正確所付的代價：轉到目標地址處執(zhí)行所需的延遲 譯碼時根據(jù)IR內(nèi)容預測：有一拍的延遲槽，在4發(fā)射情況下有4條指令的延遲槽 取指時根據(jù)PC預測：沒有延遲槽，需要BTB/Trace Cache等機制 MIPS R10000無BTAC，MIPS R12000有32項BTAC 預測錯所付的代價 盡量提前執(zhí)行轉移操作 Pentium II/III和Alpha 21264重新刷新流水線需要11周期以上,35,轉移預測關鍵技術,如何保證準確的預測：根據(jù)記錄的歷史進行預測 如何記錄轉移歷史，記錄哪些轉移歷史 記錄多少轉移歷史 何時更新：更新太早，轉移指令也可能被取消

15、；更新太晚，導致轉移歷史不準確 如何在取消猜測執(zhí)行的操作時保證現(xiàn)場精確性 增加提交流水級，在提交時修改寄存器和內(nèi)存 I/O指令的猜測執(zhí)行難以取消 如何識別流水線中的指令哪些需要取消，哪些不要取消 例外取消一般在提交時，取消所有后續(xù)指令 轉移取消一般在執(zhí)行后，只取消部分指令 延遲槽指令的處理 每個周期多個分支預測 每周期1個預測，基本可滿足4-6 發(fā)射需要的取指帶寬,36,靜態(tài)/動態(tài)轉移預測,靜態(tài)預測：總是預測轉移成功或總是預測轉移不成功 預測轉移成功：較精確，計算轉移地址需要delay slot 預測轉移不成功：直接用PC+4 動態(tài)預測：根據(jù)轉移指令執(zhí)行歷史進行預測 復雜預測技術：精確、控制復

16、雜 混合預測：利用編譯器的提示，結合動態(tài)和靜態(tài)預測,37,局部轉移預測,獨立考慮單個循環(huán)的歷史記錄，尋找其中的重復性規(guī)律，并根據(jù)該規(guī)律預測未來的轉移行為 對于重復性特征明顯的轉移指令（如循環(huán)）效果好 例子 for (I=0, I10; I+) 轉移模式為(1111111110)n,38,轉移歷史表BHT（Branch History Table） 用PC的低位索引，每項1位 記錄同一項上次轉移是否成功，表示是否轉移成功 不進行地址比較檢查（cache tag用于地址比較檢查） 問題 對循環(huán)進行猜測時，1位 BHT引起兩次猜錯 循環(huán)退出時，轉移方向不一致 進入循環(huán)時，和上次退出時的轉移方向不一致

17、 for (i=0;i10;i+) for (j=0; j10; j+) ,利用單個分支的重復性-BHT,39,兩位BHT表,只有連續(xù)兩次猜錯，才會改變猜測方向 在前述兩重循環(huán)的例子中，內(nèi)循環(huán)預測準確率從80%提高到98% 4096項已經(jīng)足夠，和無窮項效果差不多 2位已經(jīng)足夠, n位 (n2)與2位效果差不多,40,在取指階段根據(jù)當前PC值預測轉移方向和轉移地址 需要進行地址全相等比較 直接預測PC值而不是根據(jù)指令內(nèi)容計算 失效時進行替換,減少猜測延遲-BTB,41,返回地址棧,返回地址棧（Return Addresses Stack）預測返回地址 函數(shù)調(diào)用時壓棧，返回時從棧頂彈出作為返回地址

18、 針對函數(shù)調(diào)用有很高的預測準確率,42,轉移指令的相關性,2位分支預測之后，預測正確率難以提高 主要原因是分支指令的相關性,43,Yeh和Patt分類,當前的轉移依賴于兩種情況： 該指令的過去m次轉移記錄：PHT（Pattern History Table） 程序中所有轉移指令過去m次的轉移記錄：BHR（Branch History Register） BHR的組織 “PA”表示per address BHR “GA”表示global address BHR “SA”表示set address BHR PHT的組織 只用歷史記錄索引PHT表，用“g”表示 用全地址和歷史記錄一起索引PHT表，用

19、“p”表示 使用部分地址和歷史記錄一起索引PHT表，用“s”表示,44,兩層自適應預測器組合情況,BHR: Branch History Register PHT: Pattern History Table,45,GAg結構,BHR和PHT都是全局的，全局的BHR又稱為GHR（Global History Rigster）。其中GHR存儲過去k次轉移歷史，并用GHR的k位值去索引2k個入口的PHT，PHT每項利用2位飽和計數(shù)器進行預測。,46,GAs結構,其中BHR表還是全局的，只有k位；PHT表用k位的GHR和PC的低n位進行索引，因此一共有2k+n項。,47,SAg(k)的結構,PHT是

20、全局的，BHR寄存器一共有2n個，每個BHR為k位。先用PC的低n位索引GHR，然后再用GHR的值索引PHT表。,48,PAp(4)結構,每個PC值一個BHR寄存器，每個BHR為k位。先用PC索引BHR，然后再用BHR的值和PC一起索引PHT表。,49,分支別名干擾問題,無論BHR和PHT表如何增大，效果也不是很明顯 主要原因是不同分支地址訪問同一個PHT，造成分支干擾,50,Gselect: 全局歷史m位和地址n位組合尋址 Gshare: 部分地址和全局歷史異或?qū)ぶ?性能分析結果表明：gshare稍微好于gselect,分支別名干擾的消除,51,Agree分支預測,在指令Cache或轉移目的

21、地址緩存（BTB）中為每一個轉移都加上一個偏向位，偏向位中保存的是這條指令最常見的轉移方向。 2位計數(shù)器不是用來預測轉移方向的，而是用來決定是否按照偏向位來轉移的。 當轉移的實際結果與偏向位一致時，計數(shù)器加一，否則減一,52,Agree分支預測,2條分支預測正確率分別為 85%和15%，使用同一項PHT 傳統(tǒng)方法 - 兩條分支結果相反（分支沖突）的概率: (br1taken, br2nottaken) + (br1nottaken, br2taken) = (85% * 85%) + (15% * 15%) = 74.5% Agree 方法兩條分支結果相反（分支沖突）的概率: (br1agre

22、e, br2disagree) + (br1disagree, br2disagree) = (85% * 15%) + (15% * 85%) = 25.5% 優(yōu)點 2條不同方向的分支可以映射倒同一表項 偏向位不變，只改變 PHT gcc誤預測在64k的PHT下減少8.6%, 1K的PHT誤預測減少33.3% HP的PA-8700處理器中得到應用,53,Bi-Mode預測器,Bi-mode 和Agree 分支預測的思想一致，不過它是把容易發(fā)生跳轉和不跳轉的分支放入不同的PHT。它由3 部分組成，一部分用來選擇PHT，另外兩部分表示PHT 的方向，分別為跳轉和不跳轉，PHT 的方向被全局歷史索

23、引。 由于對預測器的選擇，達到了針對每條轉移的程度，因此命中率又有所提高。,54,組合分支預測器,不同的分支預測只能對某類的分支行為有效 不同分支預測組合起來，根據(jù)分支行為選不同分支預測器,55,動態(tài)轉移猜測小結,轉移的重復性和偏向性 BHT 轉移指令的相關性問題 兩層轉移預測 分支別名干擾問題 Gshare等 混合預測器 不同的分支預測只能對某類的分支行為有效 不要執(zhí)著于具體辦法，關鍵是抓住應用程序的特點,56,常見處理器的轉移預測,57,一些典型商品處理器的分支預測機制,58,Alpha 21264的分支預測器,Global PHT,(112),Global BHR,per-set BHT

24、,global PHT,n=10,k =10,k = 12,Local history prediction,Global history prediction,SAg(10),GAg(12),Selector,59,程序（a）中，假設第一個條件語句的轉移模式為“TNTNTN”，第二個條件語句的轉移模式為“NNNNNN”。 簡單的PHT表就可以準確猜測第二個條件語句的跳轉方向，但對第一個條件語句的猜測就無能為力。Alpha 21264的兩級局部預測器中“局部歷史表”相應的表項有兩個可能的值“1010101010”和“0101010101”，這兩個值分別指向“局部預測表”中的兩個表項，前者預測跳轉，后者預測不跳轉。 程序段（b）中，第一個和第二個條件都成立時第三個條件也成立。 當全局轉移歷史為“xxxxxxxxxx11”時，全局預測表將預測“if (a=b)”指令跳轉。經(jīng)過訓練后的選擇預測表也會根據(jù)在全局轉移歷史最后兩位為“11”時選擇全局預測表而不是局部預測表的預測結果。,Alpha 21264分支預測器舉例,60,Pentium IV的轉移預測器,兩個動態(tài)預測器（BTB）和靜態(tài)預測混合預測 靜態(tài)預測：跳轉方向是backward時則預測taken，反之nottaken B