處理器分支預(yù)測研究的歷史和現(xiàn)狀.pdf

《處理器分支預(yù)測研究的歷史和現(xiàn)狀.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、處理器分支預(yù)測研究的歷史和現(xiàn)狀馮子軍肖俊華章隆兵摘要在過去十幾年中，分支預(yù)測技術(shù)一直是提高處理器性能的重要方法，工業(yè)界和學(xué)術(shù)界對之進(jìn)行了大量研究。分支預(yù)測的本質(zhì)是克服指令控制相關(guān)，提高指令并行度。隨著研究的不斷深入，當(dāng)前學(xué)術(shù)界認(rèn)為分支預(yù)測是一個指令學(xué)習(xí)的過程，這就使得對分支預(yù)測的研究出現(xiàn)了新的趨勢。本文對分支預(yù)測技術(shù)的歷史和研究現(xiàn)狀進(jìn)行了歸納，以便從總體上了解分支預(yù)測技術(shù)的發(fā)展過程。1引言過去的十幾年里，分支預(yù)測技術(shù)一直是提高通用處理器性能的重要方法。分支預(yù)測的本質(zhì)是克服指令控制相關(guān)，提高指令并行度，從而使得處理器的性能

2、得到提高。在這方面學(xué)術(shù)界和工業(yè)界都進(jìn)行了大量的研究和實踐，分支預(yù)測的重要性體現(xiàn)在以下幾個方面：首先，現(xiàn)在的通用處理器大多采用深度流水線和寬發(fā)射機(jī)制，分支預(yù)測是兩者的關(guān)鍵支撐技術(shù)。雖然前兩年英特爾（Intel）的奔騰4（Pentium4）靠深度流水提高主頻一直為人所詬病，但是同時應(yīng)該注意到?jīng)]有一定深度的流水，處理器頻率就不可能太高，也就不會有很高的性能。目前x86處理器一般都有20－30級的流水線。此外展望新世紀(jì)體系結(jié)構(gòu)時候，耶魯.帕特（Yale.Patt）[1]預(yù)測寬發(fā)射將成為單芯片集成10億晶體管主要解決方案之一，而且

3、寬發(fā)射也是提高單片處理器性能的重要手段之一，最近英特爾的新處理器Conroe就從原先奔騰的三發(fā)射提高到四發(fā)射，使得[2]處理器性能提高30％也是例證。簡單的分析表明：在當(dāng)前流行的深流水線寬發(fā)射體系結(jié)構(gòu)中，分支預(yù)測率會嚴(yán)重影響取指帶寬的利用率。在5發(fā)射10級流水線條件下，預(yù)測準(zhǔn)確率為90%時，帶寬會浪費(fèi)47%；而如果準(zhǔn)確率提高到96%則帶寬浪費(fèi)可降低到26%（一般處理器設(shè)計為2到8發(fā)射，此處為了計算方便假定5發(fā)射）。另外，分支預(yù)測技術(shù)不僅在高性能通用處理器中采用，而且在嵌入式處理器也廣泛采用，所以作為一個處理器設(shè)計者，我們

4、應(yīng)該知道當(dāng)前存在的分支預(yù)測的各種算法及其優(yōu)缺點，這樣才能對功耗和性能進(jìn)行權(quán)衡。事實上，一種分支預(yù)測機(jī)制可能在某些應(yīng)用中可以提高運(yùn)算效率，但在另一些應(yīng)用可能效果就不明顯，因此設(shè)計者需要對不同應(yīng)用采用不同的分支預(yù)測解決方案。還應(yīng)該指出，很好地理解分支指令對微處理器的設(shè)計至關(guān)重要，分支指令是計算機(jī)不同于計算器的最重要區(qū)別，使得計算機(jī)得以超越簡單的數(shù)字計算功能轉(zhuǎn)變?yōu)榭梢酝瓿筛鞣N復(fù)雜任務(wù)和運(yùn)算的信息處理裝置。分支指令決定了程序從取指令到執(zhí)行指令的路徑，對分支指令的特性和行為理解深刻就可以幫助處理器設(shè)計者來平衡處理器結(jié)構(gòu)。在程序里面

5、分支指令組合起來就形成了程序分支行為，后面的介紹將說明不同分支預(yù)測機(jī)制的提出就是根據(jù)這些程序行為來進(jìn)行設(shè)計和改進(jìn)的。分支行為是取指單元設(shè)計必須考慮的關(guān)鍵因素，而掌握更復(fù)雜的分支特性，比如分支相關(guān)，就能很好地幫助我們對不同應(yīng)用選擇和改進(jìn)分支預(yù)測。綜上所述，可以知道分支預(yù)測的重要性，本文就處理器的分支預(yù)測技術(shù)的過去、現(xiàn)在和將來做一下總結(jié)和展望。本文首先介紹分支指令的性質(zhì)和分支行為的一些屬性，其次介紹分支預(yù)測的發(fā)展歷程和主要的分支預(yù)測方法，然后介紹分支預(yù)測的最新進(jìn)展，最后預(yù)測未來處理器設(shè)計分支可能會出現(xiàn)的問題和發(fā)展趨勢。2分支

6、行為分支預(yù)測器設(shè)計的本質(zhì)是在對分支指令行為認(rèn)識的基礎(chǔ)上，提出分支指令的預(yù)測機(jī)制，從而減少分支懲罰，也就是分支預(yù)測誤預(yù)測導(dǎo)致的流水線等待。一組分支指令組合起來就成為程序的分支行為。程序分支行為非常復(fù)雜，國外學(xué)術(shù)界作了大量的研究。這里只介紹一些基本的特點，以便更好地了解后面重點說明的預(yù)測機(jī)制。下面我們就分別簡單介紹一下分支指令屬性和程序分支的行為。2.1分支指令的基本屬性分支指令總的來說有三個基本屬性：分支指令的類型、分支指令發(fā)生的頻率和分支指令的成功率。分支指令的類型可以分為條件分支指令和無條件分支指令，由于分支指令目標(biāo)地

7、址的不同，無條件分支又可以進(jìn)一步分為立即分支指令，間接分支指令和返回分支指令。立即分支指令就是分支的地址就在分支指令中，一般都是直接跳轉(zhuǎn)，比如跳轉(zhuǎn)（jump）這類指令；間接分支就是分支的目標(biāo)地址不在分支指令中，而是從其他寄存器中取得；返回型分支的分支目標(biāo)地址是從鏈接寄存器（Linkregister）或者堆棧中得到，一般是程序返回使用。圖1不同分支類型所占SPEC程序比例如圖1所示，統(tǒng)計分析SEPC程序結(jié)果表明，分支指令中72%是條件分支，17％是無條件立即跳轉(zhuǎn)指令，10％是返回指令，1％是間接分支指令。其中立即分支跳轉(zhuǎn)可

8、以采用BTB（BranchTarget1[5]Buffer，分支預(yù)測緩沖區(qū)）這種方式精確預(yù)測，返回型跳轉(zhuǎn)可以采用返回地址棧(RAS)精確預(yù)測，間接分支跳轉(zhuǎn)的預(yù)測一直沒什么好的辦法，在[6]中進(jìn)行了討論。所以分支預(yù)測大量的工作是進(jìn)行條件分支預(yù)測。圖2分支指令執(zhí)行的頻率分布圖2說明了SPEC程序條件分支預(yù)測執(zhí)行的頻率分布