【轉(zhuǎn)】轉(zhuǎn)移猜測(cè)-CA
轉(zhuǎn)移猜測(cè)-CA
? ? 2021-04-20
文章目錄
前景
提高流水線效率的技術(shù)
龍芯2號(hào)處理器核結(jié)構(gòu)圖
轉(zhuǎn)移指令
控制相關(guān)
轉(zhuǎn)移指令對(duì)性能的影響
轉(zhuǎn)移指令的屬性
MIPS指令系統(tǒng)的轉(zhuǎn)移指令
程序的轉(zhuǎn)移行為
各統(tǒng)計(jì)結(jié)果
分支的可預(yù)測(cè)性
總結(jié)
解決轉(zhuǎn)移條件相關(guān)的方法
方法綜述
軟件方法解決控制相關(guān)
硬件動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)
動(dòng)態(tài)轉(zhuǎn)移猜測(cè)小結(jié)
常見(jiàn)處理器的轉(zhuǎn)移預(yù)測(cè)
一些典型商品處理器的分支預(yù)測(cè)機(jī)制
Alpha 21264的分支預(yù)測(cè)器
Pentium IV的轉(zhuǎn)移預(yù)測(cè)器
Power4轉(zhuǎn)移預(yù)測(cè)器
MIPS R10000的轉(zhuǎn)移預(yù)測(cè)器
龍芯2號(hào)分支預(yù)測(cè)器
常見(jiàn)處理器的分支預(yù)測(cè)（最近）
分支預(yù)測(cè)未來(lái)
前景
提高流水線效率的技術(shù)
（1）指令流水線：
? 多發(fā)射：多車(chē)道
? 動(dòng)態(tài)調(diào)度：允許超車(chē)
（2）喂飽“饑餓”的運(yùn)算器：
? 轉(zhuǎn)移猜測(cè)：提供足夠的指令
? 存儲(chǔ)管理：提供足夠的數(shù)據(jù)
? 馮諾依曼結(jié)構(gòu)：存儲(chǔ)程序和順序執(zhí)行
龍芯2號(hào)處理器核結(jié)構(gòu)圖
轉(zhuǎn)移指令
控制相關(guān)
如果轉(zhuǎn)移指令計(jì)算下一條指令地址在EX階段計(jì)算，下一條指令等2拍 ；
解決方法：
①使用專門(mén)的地址運(yùn)算部件把地址計(jì)算提前到譯碼階段可以少等一拍：
②使用一個(gè)delay slot可以不用等待，但是多發(fā)射情況下延遲槽成為需要專門(mén)照顧的負(fù)擔(dān)：
轉(zhuǎn)移指令對(duì)性能的影響
（1）分支指令的影響是開(kāi)發(fā)指令級(jí)并行性的重要障礙：
? 一條指令流中，平均每5-7條指令中就有一條是分支指令，也即基本塊大小為5-7條指令
（2）增大發(fā)射寬度：
? 在發(fā)射寬度為n的處理器中，遇到分支指令的速度也快了n倍
（3）增加流水線深度：
? 流水線越深，處理分支指令所需要的時(shí)鐘周期數(shù)就越多
（4）例子：
假設(shè)平均每8條指令中有一條轉(zhuǎn)移指令，某處理器采用4發(fā)射結(jié)構(gòu)，第10級(jí)流水解決轉(zhuǎn)移地址相關(guān)（即第10級(jí)流水算出轉(zhuǎn)移方向和目標(biāo)）：
（每次轉(zhuǎn)移出問(wèn)題，流水線停頓9拍，這9拍可發(fā)射36條指令，即浪費(fèi)的指令帶寬）
①在A系統(tǒng)中不進(jìn)行轉(zhuǎn)移預(yù)測(cè)，遇到轉(zhuǎn)移指令就等待：
-指令帶寬浪費(fèi)36/(36+8)=82%； //相當(dāng)于沒(méi)發(fā)射8條指令，浪費(fèi)一次
②在B系統(tǒng)中進(jìn)行簡(jiǎn)單的轉(zhuǎn)移預(yù)測(cè)，轉(zhuǎn)移猜錯(cuò)率為50%，那么平均每16條指令預(yù)測(cè)錯(cuò)誤一次:
-指令帶寬浪費(fèi)36/(36+16)=75%
③在C系統(tǒng)中，轉(zhuǎn)移指令猜錯(cuò)率為10%，那么平均每80條指令預(yù)測(cè)錯(cuò)誤一次:
-指令帶寬浪費(fèi)36/(36+80)=31%；
④在D系統(tǒng)中，轉(zhuǎn)移指令猜錯(cuò)率為4%，平均每200條指令預(yù)測(cè)錯(cuò)誤一次:
-取指令帶寬浪費(fèi)36/(36+200)=15%。
轉(zhuǎn)移指令的屬性
（1）條件轉(zhuǎn)移與無(wú)條件轉(zhuǎn)移：
? 條件轉(zhuǎn)移：需等待條件確定后才能取指，程序中多數(shù)轉(zhuǎn)移指令是條件轉(zhuǎn)移指令
? 無(wú)條件轉(zhuǎn)移：不用判斷條件就轉(zhuǎn)移，如call/return
（2）直接轉(zhuǎn)移與間接轉(zhuǎn)移：
? 直接轉(zhuǎn)移：轉(zhuǎn)移目標(biāo)根據(jù)指令內(nèi)容直接得出
? 間接轉(zhuǎn)移：轉(zhuǎn)移目標(biāo)在寄存器中
（3）相對(duì)轉(zhuǎn)移與絕對(duì)轉(zhuǎn)移：
? 相對(duì)轉(zhuǎn)移：轉(zhuǎn)移目標(biāo)為當(dāng)前PC值加上偏移量
? 絕對(duì)轉(zhuǎn)移：轉(zhuǎn)移目標(biāo)由指令或寄存器內(nèi)容直接給出
由上可知：理論上有8種組合：實(shí)際上不實(shí)現(xiàn)所有組合
MIPS指令系統(tǒng)的轉(zhuǎn)移指令
程序的轉(zhuǎn)移行為
各統(tǒng)計(jì)結(jié)果
（1）SPEC CPU2000轉(zhuǎn)移指令統(tǒng)計(jì)—龍芯2號(hào)統(tǒng)計(jì)結(jié)果
（2）轉(zhuǎn)移指令間距離統(tǒng)計(jì)：
發(fā)射寬度增加，分支間的動(dòng)態(tài)距離就會(huì)越小，分支預(yù)測(cè)的延遲對(duì)性能的影響就越大，當(dāng)要求更高的發(fā)射寬度時(shí)，需要每個(gè)周期做不止一個(gè)預(yù)測(cè)；
例：Inter-branch distance(cycles) ，模擬環(huán)境：4發(fā)射亂序機(jī)器 @SPECint2000
（3）不同類型轉(zhuǎn)移指令分布：
龍芯2號(hào)上部分SPEC CPU2000程序中轉(zhuǎn)移指令分布：
? 1％是間接分支指令，采用BTB預(yù)測(cè)
? 5％是返回指令，返回地址棧RAS預(yù)測(cè)
? 29％是無(wú)條件立即跳轉(zhuǎn)指令，跳轉(zhuǎn)地址在指令中
? 65%是條件分支，大量的工作是進(jìn)行條件分支預(yù)測(cè)
（4）轉(zhuǎn)移指令的執(zhí)行頻率分布：
龍芯2號(hào)上部分SPEC CPU2000程序轉(zhuǎn)移指令執(zhí)行頻率分布：
? 所有轉(zhuǎn)移指令的44%僅僅執(zhí)行99次或者更少，這44%的轉(zhuǎn)移指令占所有轉(zhuǎn)移指令總執(zhí)行次數(shù)的0.03%；
? 只有4.2%的轉(zhuǎn)移指令執(zhí)行了超過(guò)100000次或者更多，占所有轉(zhuǎn)移指令總執(zhí)行次數(shù)的87%（或者說(shuō)，只有14.7%的轉(zhuǎn)移指令超過(guò)了10000次，占所有轉(zhuǎn)移指令總執(zhí)行次數(shù)的97%）。
（5）轉(zhuǎn)移成功率分布：
龍芯2號(hào)上部分SPEC CPU2000程序轉(zhuǎn)移指令的跳轉(zhuǎn)成功率：
? 45%的指令總是跳轉(zhuǎn)，15%的指令總是不跳轉(zhuǎn)；
? 20%的指令跳轉(zhuǎn)的幾率小于5%或者大于95%；（80%的轉(zhuǎn)移指令具有強(qiáng)烈的一個(gè)跳轉(zhuǎn)方向，具有挑戰(zhàn)性的工作是預(yù)測(cè)其余20%轉(zhuǎn)移指令的跳轉(zhuǎn)方向）
分支的可預(yù)測(cè)性
（1）利用單個(gè)轉(zhuǎn)移指令的重復(fù)性：
基于模式的預(yù)測(cè)方法
循環(huán)型分支：
? for型循環(huán)：TT…TN（成功n次后跟一次不成功 ）
? while型循環(huán)：NN…NT（不成功n次后跟一次成功）周期重復(fù)模式型分支：
? 定長(zhǎng)重復(fù)模式類分支：{pat}^q , |pat|=k （每隔k個(gè)分支模式就重復(fù)一次）
? 塊模式類分支：{T^n Nm}q， 成功n次，不成功m次，如此循環(huán)
（2）利用不同轉(zhuǎn)移指令之間的關(guān)系：
基于相關(guān)的預(yù)測(cè)方法
利用指令間的方向相關(guān)
? 兩個(gè)分支的條件（完全或部分）基于相同或相關(guān)的信息
? 第二個(gè)分支的結(jié)果基于第一個(gè)分支的結(jié)果產(chǎn)生利用指令間的路徑相關(guān)
? 如果一個(gè)分支是通向當(dāng)前分支的前n條分支之一，則稱該分支處在當(dāng)前分支的路徑之上（Y和Z在通往X的路徑上）
? 處在當(dāng)前分支路徑上的分支與當(dāng)前分支結(jié)果之間的相關(guān)稱為路徑相關(guān)；
（3）利?函數(shù)調(diào)?的遞歸性：
總結(jié)
分支指令是很頻繁的
分支指令有較好的局部性
分支指令具有可預(yù)測(cè)性
解決轉(zhuǎn)移條件相關(guān)的方法
方法綜述
（1）阻塞：
- 等待直到轉(zhuǎn)移條件確定
（2）用延遲槽容忍延遲：
- 延遲槽指令來(lái)源
（3）編譯器優(yōu)化：
- 循環(huán)：循環(huán)展開(kāi)減少轉(zhuǎn)移指令、軟流水減少阻塞
- 分支：全局代碼調(diào)度（越過(guò)分支調(diào)度指令）
- 函數(shù)調(diào)用：inline
（4）轉(zhuǎn)換為數(shù)據(jù)相關(guān)：
- 條件指令、謂詞
（5）硬件轉(zhuǎn)移預(yù)測(cè)：
- 轉(zhuǎn)移條件未確定時(shí)預(yù)測(cè)轉(zhuǎn)移是否成功
- 靜態(tài)與動(dòng)態(tài)預(yù)測(cè)
軟件方法解決控制相關(guān)
（1）利用延遲槽：
延遲槽指令的來(lái)源：
- 來(lái)自轉(zhuǎn)移指令前：肯定執(zhí)行
- 來(lái)自轉(zhuǎn)移目標(biāo)地址：轉(zhuǎn)移成功才執(zhí)行
- 來(lái)自轉(zhuǎn)移不成功地址：轉(zhuǎn)移不成功才執(zhí)行單延遲槽的編譯效果：
- 能為 60% 左右的轉(zhuǎn)移延遲槽找到有效操作
- 大約80%的延遲槽指令用于有效計(jì)算
- 因此大約50% (60% x 80%) 的延遲槽操作用于有效計(jì)算延遲槽的限制：
- 超流水情況下一條延遲槽不夠
- 多發(fā)射情況下延遲槽反而成為需要特殊照顧的兼容負(fù)擔(dān)
（2）軟件循環(huán)展開(kāi)消除控制相關(guān)
方法：軟件展開(kāi)兩個(gè)循環(huán)
①. 循環(huán)展開(kāi)
②. 寄存器重命名
③. 變換次序軟件循環(huán)展開(kāi)的不足：
- 有些循環(huán)不好展開(kāi)（如循環(huán)次數(shù)不定的循環(huán)）
- 增加指令CACHE的負(fù)擔(dān)循環(huán)的數(shù)據(jù)相關(guān)：
- 循環(huán)內(nèi)相關(guān)：
-S2使用同一次循環(huán)中S1計(jì)算的A[i+1]。
-導(dǎo)致一個(gè)循環(huán)體內(nèi)的多條指令不能并行執(zhí)行；
- 循環(huán)間（loop-carried）相關(guān)：
-本次循環(huán)計(jì)算的A[i+1]/B[i+1]將被下一次循環(huán)使用。
-導(dǎo)致多個(gè)循環(huán)體不能并行執(zhí)行
把循環(huán)間相關(guān)轉(zhuǎn)換為循環(huán)內(nèi)相關(guān)循環(huán)展開(kāi)的條件：
- 數(shù)組元素相關(guān)的判斷：
數(shù)組元素兩種類型：
- 名字相關(guān)的消除：重命名技術(shù)
- 指針相關(guān)的判斷：只有一些經(jīng)驗(yàn)的方法循環(huán)間相關(guān)的解決—軟流水：
? 新循環(huán)體的每個(gè)操作來(lái)自不同的循環(huán)體，以分開(kāi)數(shù)據(jù)相關(guān)的指令，相當(dāng)于軟件的Tomasulo算法；
? 符號(hào)級(jí)循環(huán)展開(kāi)，比真正循環(huán)展開(kāi)代碼開(kāi)銷(xiāo)小；
（3）把控制相關(guān)轉(zhuǎn)換成數(shù)據(jù)相關(guān)：
把條件轉(zhuǎn)移指令轉(zhuǎn)換為條件執(zhí)行：
（條件指令的條件作為指令執(zhí)?階段的?個(gè)輸?,實(shí)際上把控制相關(guān)轉(zhuǎn)化為數(shù)據(jù)相關(guān)）
- if (x) then A = B op C else NOP （在執(zhí)行階段判斷x是否為0） //CMOV A ,B , X
- 只有條件為真時(shí)才寫(xiě)結(jié)果，為假時(shí)不寫(xiě)結(jié)果也不發(fā)生例外
- RISC系統(tǒng)如Alpha, MIPS, PowerPC, SPARC都增加了條件MOVE指令; PA-RISC的nullification
- EPIC: 使用64個(gè)1位的謂詞寄存器來(lái)選擇是否寫(xiě)執(zhí)行結(jié)果條件指令的缺點(diǎn)：
- 條件為假時(shí)仍需要1拍，占用發(fā)射槽和功能部件
- 條件未確定仍需要在執(zhí)行前等待，轉(zhuǎn)移猜測(cè)反而在執(zhí)行后
- 條件復(fù)雜時(shí)會(huì)降低效率，因?yàn)闂l件在執(zhí)行時(shí)才確定條件指令舉例：
- 假設(shè)轉(zhuǎn)移指令沒(méi)有延遲槽
- 條件指令可消除簡(jiǎn)單的條件轉(zhuǎn)移，對(duì)取絕對(duì)值等操作有用
- 條件指令仍要在執(zhí)行前等待條件，注意例外的處理
硬件動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)
（1）基本思路：
在取指或譯碼階段預(yù)測(cè)轉(zhuǎn)移是否成功以及轉(zhuǎn)移目標(biāo)進(jìn)行后續(xù)指令的取指
? 以減少指令流水線由于控制相關(guān)而堵塞在執(zhí)行階段判斷轉(zhuǎn)移預(yù)測(cè)是否正確
? 如果猜測(cè)正確，則正常提交
? 如果猜測(cè)錯(cuò)誤，則取消該轉(zhuǎn)移指令及其后續(xù)指令
（2）基本原理：
1）猜測(cè)依據(jù)：
? 當(dāng)前指令的地址（PC）和性質(zhì)（是否轉(zhuǎn)移指令）
? 過(guò)去轉(zhuǎn)移指令歷史記錄
2）猜測(cè)內(nèi)容：
? 轉(zhuǎn)移方向、轉(zhuǎn)移目標(biāo)地址
3）原理圖示：
（3）分支處理機(jī)制的性能取決于：
預(yù)測(cè)精度（BPA）=> 設(shè)計(jì)好的預(yù)測(cè)器
? 預(yù)測(cè)精度越高，能抽取的并行性就越多預(yù)測(cè)正確所付的代價(jià)：轉(zhuǎn)到目標(biāo)地址處執(zhí)行所需的延遲
? 譯碼時(shí)根據(jù)IR內(nèi)容預(yù)測(cè)：有一拍的延遲槽，在4發(fā)射情況下有4條指令的延遲槽
? 取指時(shí)根據(jù)PC預(yù)測(cè)：沒(méi)有延遲槽，需要BTB/Trace Cache等機(jī)制
? MIPS R10000無(wú)BTAC，MIPS R12000有32項(xiàng)BTAC預(yù)測(cè)錯(cuò)所付的代價(jià)：
? 盡量提前執(zhí)行轉(zhuǎn)移操作
? Pentium II/III和Alpha 21264重新刷新流水線需要11周期以上
（4）轉(zhuǎn)移預(yù)測(cè)關(guān)鍵技術(shù)：
1）如何保證準(zhǔn)確的預(yù)測(cè)：根據(jù)記錄的歷史進(jìn)行預(yù)測(cè)
? 如何記錄轉(zhuǎn)移歷史，記錄哪些轉(zhuǎn)移歷史
? 記錄多少轉(zhuǎn)移歷史
? 何時(shí)更新：更新太早，轉(zhuǎn)移指令也可能被取消；更新太晚，導(dǎo)致轉(zhuǎn)移歷史不準(zhǔn)確
2）如何在取消猜測(cè)執(zhí)行的操作時(shí)保證現(xiàn)場(chǎng)精確性
? 增加提交流水級(jí)，在提交時(shí)修改寄存器（寄存器重命名）和內(nèi)存（write buffer機(jī)制）
? I/O指令的猜測(cè)執(zhí)行難以取消
3）如何識(shí)別流水線中的指令哪些需要取消，哪些不要取消
? 例外取消一般在提交時(shí)，取消所有后續(xù)指令
? 轉(zhuǎn)移取消一般在執(zhí)行后，只取消部分指令
要求有?種機(jī)制來(lái)判斷指令流?線中的每?條指令和錯(cuò)誤預(yù)測(cè)的轉(zhuǎn)移指令的先后關(guān)系。
4）延遲槽指令的處理
5）每個(gè)周期多個(gè)分支預(yù)測(cè)
? 每周期1個(gè)預(yù)測(cè)，基本可滿足4-6 發(fā)射需要的取指帶寬
（5）高性能性能轉(zhuǎn)移預(yù)測(cè)機(jī)制特征：
① 減少預(yù)測(cè)延遲槽 (如?根據(jù)PC預(yù)測(cè)的BTB/BTAC等機(jī)制）；
② 在執(zhí)?階段盡早確定轉(zhuǎn)移結(jié)果,降低錯(cuò)誤預(yù)測(cè)的開(kāi)銷(xiāo)；
③ 在轉(zhuǎn)移預(yù)測(cè)錯(cuò)誤時(shí)要有?效的流?線刷新機(jī)制；
④具有?預(yù)測(cè)精度的轉(zhuǎn)移預(yù)測(cè)機(jī)制；
（6）靜態(tài)/動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)：
靜態(tài)預(yù)測(cè)：總是預(yù)測(cè)轉(zhuǎn)移成功或總是預(yù)測(cè)轉(zhuǎn)移不成功
? 預(yù)測(cè)轉(zhuǎn)移成功：較精確，計(jì)算轉(zhuǎn)移地址需要delay slot
? 預(yù)測(cè)轉(zhuǎn)移不成功：直接用PC+4動(dòng)態(tài)預(yù)測(cè)：根據(jù)轉(zhuǎn)移指令執(zhí)行歷史進(jìn)行預(yù)測(cè)
? 復(fù)雜預(yù)測(cè)技術(shù)：精確、控制復(fù)雜混合預(yù)測(cè)：利用編譯器的提示，結(jié)合動(dòng)態(tài)和靜態(tài)預(yù)測(cè)
（7）局部轉(zhuǎn)移預(yù)測(cè)：
- 獨(dú)立考慮單個(gè)循環(huán)的歷史記錄，尋找其中的重復(fù)性規(guī)律，并根據(jù)該規(guī)律預(yù)測(cè)未來(lái)的轉(zhuǎn)移行為；
- 對(duì)于重復(fù)性特征明顯的轉(zhuǎn)移指令（如循環(huán)）效果好；
- 例子：
?? for (I=0, I<10; I++){ }
?? 轉(zhuǎn)移模式為(1111111110)^n
（8）利用單個(gè)分支的重復(fù)性—BHT
1）轉(zhuǎn)移歷史表BHT（Branch History Table）：
? 用PC的低位索引，每項(xiàng)1位 （可能兩條轉(zhuǎn)移指令的PC低位相同 ,從?引起沖突）
? 記錄同一項(xiàng)上次轉(zhuǎn)移是否成功，表示是否轉(zhuǎn)移成功
（具有上述兩項(xiàng)特征的BHT表，1位，稱為PHT表）
? 不進(jìn)行地址比較檢查（cache，tag用于地址比較檢查）(因?yàn)榧词诡A(yù)測(cè)錯(cuò)誤也還有糾正措施)
2）問(wèn)題：
對(duì)循環(huán)進(jìn)行猜測(cè)時(shí)，1位BHT（PHT）引起兩次猜錯(cuò)：
（1位PHT表預(yù)測(cè)時(shí)僅看該轉(zhuǎn)移指令上次跳轉(zhuǎn)是否成功）
①循環(huán)退出時(shí)，轉(zhuǎn)移方向不一致
②進(jìn)入循環(huán)時(shí)，和上次退出時(shí)的轉(zhuǎn)移方向不一致
3）改進(jìn)：兩位BHT表—轉(zhuǎn)移歷史表
特點(diǎn)：只有連續(xù)兩次猜錯(cuò)，才會(huì)改變猜測(cè)方向
要求：
- 12位PC索引：4096項(xiàng)已經(jīng)足夠，和無(wú)窮項(xiàng)效果差不多；
- BHT表2位已經(jīng)足夠, n位 (n>2)與2位效果差不多；預(yù)測(cè)機(jī)制：
- 執(zhí)行動(dòng)作：轉(zhuǎn)移指令每次轉(zhuǎn)移成功（這里的轉(zhuǎn)移成功是指：分支真是的跳轉(zhuǎn)情況）加1，加到3為止；轉(zhuǎn)移不成功減1，減到0為止；
- 預(yù)測(cè)方向：轉(zhuǎn)移預(yù)測(cè)時(shí)，若相應(yīng)PHT表項(xiàng)的高位為1（計(jì)數(shù)器的值為2或3）就預(yù)測(cè)跳轉(zhuǎn)；高位為0（計(jì)數(shù)器的值為1或0）就預(yù)測(cè)不跳轉(zhuǎn)；功能結(jié)構(gòu)：
缺點(diǎn)：
①僅能預(yù)測(cè)轉(zhuǎn)移指令?向,?法預(yù)測(cè)跳轉(zhuǎn)?標(biāo)；
②僅在譯碼階段使? ,僅只使?PC低位索引 ,可能把普通指令也當(dāng)作轉(zhuǎn)移指令進(jìn)?預(yù)測(cè)；例子說(shuō)明：
在前述兩重循環(huán)的例子中，循環(huán)預(yù)測(cè)準(zhǔn)確率從：
（8+80）/（10+100）= 80% //“8”外層循環(huán)錯(cuò)兩次；“80”內(nèi)層循環(huán)錯(cuò)20次
提高到：
（7+88）/（10+100）= 87.2%
（9）減少猜測(cè)延遲—轉(zhuǎn)移目標(biāo)緩沖器BTB
使用CAM結(jié)構(gòu)，在取指階段根據(jù)當(dāng)前PC值預(yù)測(cè)轉(zhuǎn)移方向和轉(zhuǎn)移地址：
- 需要進(jìn)行地址全相等比較；
- 直接預(yù)測(cè)PC值而不是根據(jù)指令內(nèi)容計(jì)算；
- 失效時(shí)進(jìn)行替換；硬件結(jié)構(gòu)：
缺點(diǎn)：
①表項(xiàng)復(fù)雜 ,需全相聯(lián)查找，不能做?；
②BTB需配合PHT；
（10）RAS：返回地址棧
- 返回地址棧（Return Addresses Stack）預(yù)測(cè)返回地址
- 函數(shù)調(diào)用時(shí)壓棧，返回時(shí)從棧頂彈出作為返回地址
- 針對(duì)函數(shù)調(diào)用有很高的預(yù)測(cè)準(zhǔn)確率
（11）BHR轉(zhuǎn)移歷史寄存器—轉(zhuǎn)移指令的相關(guān)性
1）作用：記錄所有轉(zhuǎn)移指令的歷史
2）實(shí)現(xiàn)方式：
移位寄存器：處理器執(zhí)行轉(zhuǎn)移指令，就把BHR左移1位，左移時(shí)最高位扔掉，最低位如果轉(zhuǎn)移成功就填1，否則填0；
3）m位的BHR記錄了處理器M次的轉(zhuǎn)移歷史;
4）BHR表：為每條轉(zhuǎn)移指令單獨(dú)記錄 BHR ,再把多個(gè)BHR組織在?起的表
5）2位分支預(yù)測(cè)之后，預(yù)測(cè)正確率難以提高，主要原因是分支指令的相關(guān)性
（12）Yeh和Patt分類：
1）當(dāng)前的轉(zhuǎn)移依賴于兩種情況：
? 該指令的過(guò)去m次轉(zhuǎn)移記錄：PHT（Pattern History Table）
? 程序中所有轉(zhuǎn)移指令過(guò)去m次的轉(zhuǎn)移記錄：BHR（Branch History Register）
BHR的組織：
- “PA”表示per address BHR // 每條轉(zhuǎn)移指令都有自己的BHR，用PC索引BHR；
- “GA”表示global address BHR //所有轉(zhuǎn)移指令共用一個(gè)BHR；
- “SA”表示set address BHR // 用PC的低位索引BHRPHT的組織：
- 只用歷史記錄索引PHT表，用“g”表示
- 用全地址和歷史記錄一起索引PHT表，用“p”表示
- 使用部分地址和歷史記錄一起索引PHT表，用“s”表示
2）兩層自適應(yīng)預(yù)測(cè)器組合情況：
? BHR: Branch History Register
? PHT: Pattern History Table
①GAg結(jié)構(gòu)：
- BHR和PHT都是全局的，全局的BHR又稱為GHR（Global History Rigster）。
- 其中GHR存儲(chǔ)過(guò)去k次轉(zhuǎn)移歷史，并用GHR的k位值去索引2k個(gè)入口的PHT，
- PHT每項(xiàng)利用2位飽和計(jì)數(shù)器進(jìn)行預(yù)測(cè)。
②GAs結(jié)構(gòu)：
- 其中BHR表還是全局的，只有k位；
- PHT表用k位的GHR和PC的低n位進(jìn)行索引，因此一共有2^（k+n）項(xiàng)。
③SAg(k)的結(jié)構(gòu)：
- PHT是全局的，BHR寄存器一共有2^n個(gè)，每個(gè)BHR為 k位。
- 先用PC的低n位索引GHR，然后再用GHR的值索引PHT表。
④PAp(4)結(jié)構(gòu)：
- 每個(gè)PC值一個(gè)BHR寄存器，每個(gè)BHR為k位。
- 先用PC索 引BHR，然后再用BHR的值和PC一起索引PHT表。
（13）分支別名干擾問(wèn)題：
1）模式：
- 無(wú)論BHR和PHT表如何增大，效果也不是很明顯
- 主要原因是不同分支地址訪問(wèn)同一個(gè)PHT，造成分支干擾
- ?從?級(jí)轉(zhuǎn)移預(yù)測(cè)器出現(xiàn)來(lái) ,預(yù)測(cè)精度?般在92%左右 。
2）分支別名干擾的消除：
①Gselect:全局歷史m位和地址n位組合尋址
②Gshare: 部分地址和全局歷史異或?qū)ぶ?br>
性能分析結(jié)果表明：gshare稍微好于gselect
（14）Agree分支預(yù)測(cè)：
分支預(yù)測(cè)緩沖區(qū)BTB：在指令Cache或轉(zhuǎn)移目的地址緩存（BTB）中為每一個(gè)轉(zhuǎn)移都加上一個(gè)偏向位，偏向位中保存的是這條指令最常見(jiàn)的轉(zhuǎn)移方向。
（偏向位依據(jù)：前面分析的多數(shù)轉(zhuǎn)移指令具有強(qiáng)烈跳轉(zhuǎn)或者不跳轉(zhuǎn)傾向性）Gshare預(yù)測(cè)器：2位計(jì)數(shù)器不是用來(lái)預(yù)測(cè)轉(zhuǎn)移方向的，而是用來(lái)決定是否按照偏向位來(lái)轉(zhuǎn)移的。
當(dāng)轉(zhuǎn)移的實(shí)際結(jié)果與偏向位一致時(shí)，計(jì)數(shù)器加一，否則減一
1）舉例計(jì)算說(shuō)明：
2條分支預(yù)測(cè)正確率分別為 85%和15%，使用同一項(xiàng)PHT
傳統(tǒng)方法 - 兩條分支結(jié)果相反（分支沖突）的概率:
(br1taken, br2nottaken) + (br1nottaken, br2taken) = (85% * 85%) + (15% * 15%) = 74.5%Agree 方法–兩條分支結(jié)果相反（分支沖突）的概率:
(br1agree, br2disagree) + (br1disagree, br2agree)= (85% * 15%) + (15% * 85%) = 25.5%
2）優(yōu)點(diǎn)：
? 2條不同方向的分支可以映射到同一表項(xiàng)
? 偏向位不變，只改變 PHT
? gcc誤預(yù)測(cè)在64k的PHT下減少8.6%, 1K的PHT誤預(yù)測(cè)減少33.3%
3）應(yīng)用：HP的PA-8700處理器
（15）Bi-Mode預(yù)測(cè)器：
Bi-mode 和Agree 分支預(yù)測(cè)的思想一致，不過(guò)它是把容易發(fā)生跳轉(zhuǎn)和不跳轉(zhuǎn)的分支放入不同的PHT。
它由3 部分組成，一部分用來(lái)選擇PHT，另外兩部分表示PHT 的方向，分別為跳轉(zhuǎn)和不跳轉(zhuǎn)，PHT 的方向被全局歷史索引。
由于對(duì)預(yù)測(cè)器的選擇，達(dá)到了針對(duì)每條轉(zhuǎn)移的程度，因此命中率又有所提高。
（16）組合分支預(yù)測(cè)器：
不同的分支預(yù)測(cè)只能對(duì)某類的分支行為有效
不同分支預(yù)測(cè)組合起來(lái)，根據(jù)分支行為選不同分支預(yù)測(cè)器
動(dòng)態(tài)轉(zhuǎn)移猜測(cè)小結(jié)
轉(zhuǎn)移的重復(fù)性和偏向性：BHT
轉(zhuǎn)移指令的相關(guān)性問(wèn)題：兩層轉(zhuǎn)移預(yù)測(cè)
分支別名干擾問(wèn)題：Gshare等
混合預(yù)測(cè)器：不同的分支預(yù)測(cè)只能對(duì)某類的分支行為有效
不要執(zhí)著于具體辦法，關(guān)鍵是抓住應(yīng)用程序的特點(diǎn)
常見(jiàn)處理器的轉(zhuǎn)移預(yù)測(cè)
一些典型商品處理器的分支預(yù)測(cè)機(jī)制
Alpha 21264的分支預(yù)測(cè)器
舉例：
Pentium IV的轉(zhuǎn)移預(yù)測(cè)器
兩個(gè)動(dòng)態(tài)預(yù)測(cè)器（BTB）和靜態(tài)預(yù)測(cè)混合預(yù)測(cè)：
靜態(tài)預(yù)測(cè)：跳轉(zhuǎn)方向是backward時(shí)則預(yù)測(cè)taken，反之nottaken
BTB：記錄歷史信息和目標(biāo)地址
選擇：當(dāng)BTB中沒(méi)有該跳轉(zhuǎn)指令時(shí)采用靜態(tài)預(yù)測(cè)
Power4轉(zhuǎn)移預(yù)測(cè)器
靜態(tài)預(yù)測(cè)：
- 每條轉(zhuǎn)移指令保留兩位，一位表示是否用靜態(tài)預(yù)測(cè)，若用則動(dòng)態(tài)預(yù)測(cè)失效，另一位表示是否跳轉(zhuǎn)動(dòng)態(tài)預(yù)測(cè)器由3個(gè)16K*1的表組成：
- 局部預(yù)測(cè)器由指令地址來(lái)索引；
- 全局預(yù)測(cè)器由一個(gè)11位的歷史向量與地址異或來(lái)索引，歷史向量記錄；
- 前11組指令是否連續(xù)的信息（Power4將指令分組，1組指令為5條）；
- 選擇器的索引同全局預(yù)測(cè)器；返回地址棧Link stack：
- 遇到branch and link指令預(yù)測(cè)taken，同時(shí)將link地址壓棧，由編譯器對(duì)branch to link指令作上標(biāo)記（hint bit），從棧中彈出地址；計(jì)數(shù)緩存（Count cache）：
- 32項(xiàng)，直接相聯(lián)，軟件標(biāo)志該指令會(huì)多次重復(fù)跳轉(zhuǎn)，則將其目標(biāo)地址寫(xiě)入計(jì)數(shù)緩存，計(jì)數(shù)緩存的每一項(xiàng)保存62位地址
-
MIPS R10000的轉(zhuǎn)移預(yù)測(cè)器
R10000：
? 512-entry, 2-bit BHT
? Branch stackR12000：
? 2048-entry, 2-bit BHT
? 32-entry BTB
龍芯2號(hào)分支預(yù)測(cè)器
靜態(tài)預(yù)測(cè)和動(dòng)態(tài)預(yù)測(cè)結(jié)合的轉(zhuǎn)移預(yù)測(cè)方法：
? “l(fā)ikely”類的轉(zhuǎn)移直接預(yù)測(cè)跳轉(zhuǎn)
? 其它轉(zhuǎn)移指令采用動(dòng)態(tài)預(yù)測(cè)方法。采用Gshare結(jié)構(gòu)進(jìn)行條件指令的轉(zhuǎn)移預(yù)測(cè)：
? BHR共9位，PHT表有4096項(xiàng)16項(xiàng)BTB預(yù)測(cè)普通JR指令：
? 在譯碼階段訪問(wèn)4項(xiàng)RAS預(yù)測(cè)函數(shù)返回指令：
? 目標(biāo)寄存器為31號(hào)寄存器的JR指令
常見(jiàn)處理器的分支預(yù)測(cè)（最近）
分支預(yù)測(cè)未來(lái)
進(jìn)一步提高很難：
? 95%－98％左右
? 工業(yè)界分支預(yù)測(cè)越做越大，Alpha21464有48KB進(jìn)一步提高很有意義：
? 預(yù)測(cè)精度提高0.5%，10000條分支指令就能減少50次流水線刷新新應(yīng)用及新結(jié)構(gòu)需要新的預(yù)測(cè)機(jī)制：
? Power-aware分支預(yù)測(cè)
? SMT結(jié)構(gòu)分支預(yù)測(cè)
? 神經(jīng)網(wǎng)絡(luò)分支預(yù)測(cè)器分支預(yù)測(cè)大賽：
? 工業(yè)界支持，2年一次
來(lái)源網(wǎng)絡(luò)
