分支預測器
 | 此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2012年4月29日) |
在電腦架構中，分支預測器（英語：Branch predictor）是一種數碼電路，在分支指令執行結束之前猜測哪一路分支將會被執行，以提高處理器的指令管線化的效能。使用分支預測器的目的，在於改善指令管線化的流程，就像一家公司的員工提前預測公司所需要的東西，即交付不同單位進行準備工作，而那各個部門之間的等待交辦的時間大大地縮短，整個公司的效率就會提高了。現代使用指令管線化處理器的效能能夠提高，分支預測器對於現今的指令管線化微處理器獲得高效能是非常關鍵的技術。
簡介
[編輯]條件分支指令通常具有兩路後續執行分支。即不採取（not taken）跳轉，順序執行後面緊挨JMP的指令；以及採取（taken）跳轉到另一塊程式主記憶體去執行那裏的指令。
是否條件跳轉，只有在該分支指令在指令管線化中通過了執行階段（execution stage）才能確定下來。
如果沒有分支預測器，處理器將會等待分支指令通過了指令管線化的執行階段，才把下一條指令送入管線化的第一個階段—取指令階段（fetch stage）。這種技術叫做管線化停頓（pipeline stalled）或者管線化冒泡（pipeline bubbling）或者分支延遲間隙。這是早期的RISC體系結構處理器採用的應對分支指令的管線化執行的辦法。
分支預測器猜測條件運算式兩路分支中哪一路最可能發生，然後推測執行這一路的指令，來避免管線化停頓造成的時間浪費。如果後來發現分支預測錯誤，那麼管線化中推測執行的那些中間結果全部放棄，重新取得正確的分支路線上的指令開始執行，這招致了程式執行的延遲。
在分支預測失敗時浪費的時間是從取指令到執行完指令（但還沒有寫回結果）的管線化的級數。現代微處理器趨向採用非常長的管線化，因此分支預測失敗可能會損失10-20個時鐘周期。越長的管線化就需要越好的分支預測。
一條條件跳轉指令第一次遇到，還沒有任何資訊可以去預測分支。此後保持這條指令是採取還是不採取跳轉的歷史記錄，就可以作為再遇到這條指令時猜測最可能的分支。
分支預測不同於「分支目標預測」（Branch target predictor）。後者是指對指令高速緩衝記憶體中的內容，檢測出其中的條件跳轉指令與無條件跳轉指令，然後為指令高速緩衝記憶體預裝入（prefetch）相應的跳轉目標碼塊。
實現
[編輯]靜態預測
[編輯]靜態預測（Static prediction）是最簡單的分支預測技術，因為它不依賴於代碼執行的動態歷史資訊。相反，它僅依賴於分支指令自身。[1]
SPARC與MIPS的最早實現（作為第一代商用RISC體系結構處理器）使用單方向靜態分支預測：總是預測條件跳轉不發生，因此總是順序取下一條指令推測執行。僅當條件跳轉指令被求值確實發生了跳轉，則非順序的代碼地址被載入執行。兩種CPU都是在解碼階段評價分支指令，取指令佔用1個周期。因此分支目標需要兩個周期（即經過了取指令、解碼兩個周期）才能確定。兩種處理器都會在分支指令進入管線化的執行階段時，插入一個分支延遲間隙。分支指令完成管線化的執行階段，就已經能確定是否跳轉，這時就可以決定是後續的順序出現的指令被繼續執行還是跳轉到的新指令進入流水。
更複雜的靜態預測假定向後分支將會發生，向前的分支不會發生。向後分支，是指跳轉到的新地址比當前地址要低。這有助於配合經常出現的程式的迴圈控制結構。
一些處理器允許分支預測提示出現在代碼中。Intel Pentium 4就是如此。但這一特徵在Intel此後的處理器中不再支援。[2]
靜態預測也用於某些處理器分支動態預測沒有任何可用資訊時的一個最後的辦法。Motorola MPC7450 (G4e)與Intel Pentium 4都是如此。[3]
動態預測
[編輯]動態預測利用分支指令發生轉移的歷史來進行預測，並根據實際執行情況動態調整預測位，準確率可達90%，現在幾乎所有處理器都採用動態預測。
下一行預測
[編輯]一些超純量處理器(MIPS R8000, Alpha 21264 and Alpha 21464 (EV8))使用此種技術。
飽和計數
[編輯]飽和計數器（saturating counter）或者稱雙模態預測器（bimodal predictor）是一種有4個狀態的狀態機：
- 強不選擇（Strongly not taken）
- 弱不選擇（Weakly not taken）
- 弱選擇（Weakly taken）
- 強選擇（Strongly taken）
當一個分支命令被求值，對應的狀態機被修改。分支不採納，則向「強不選擇」方向降低狀態值；如果分支被採納，則向「強選擇」方向提高狀態值。這種方法的優點是，該條件分支指令必須連續選擇某條分支兩次，才能從強狀態翻轉，從而改變了預測的分支。
最初的不具有MMX的Intel Pentium處理器使用了這種飽和計數器。雖然實現不夠完美。[2]
在SPEC'89 benchmark測評中, 飽和預測達到了93.5%正確率，如果每條條件分支指令都對映了自己的計數器。[4]
預測器表使用條件分支指令的地址作為索引。因此處理器可以在分支指令解碼前就給它分配一個預測器。
兩級自適應預測器
[編輯]
對於一條分支指令，如果每2次執行發生一次條件跳轉，或者其它的規則發生模式，那麼用上文提到的飽和計數器就很難預測了。如圖所示，一種二級自適應預測器可以記住過去n次執行該指令時的分支情況的歷史，可能的2n種歷史模式的每一種都有1個專用的飽和計數器，用來表示如果剛剛過去的n次執行歷史是此種情況，那麼根據這個飽和計數器應該預測為跳轉還是不跳轉。
例如，n = 2。這意味着過去的2次分支情況被儲存在一個2位的移位暫存器中。因此可能有4種不同的分支歷史情況：00, 01, 10, 11。其中0表示未發生跳轉，1表示發生了分支跳轉。現在，設計一個模式歷史表（pattern history table），有4個條目，對應於2n = 4種可能的分支歷史情況。4種歷史情況的每一種都在模式歷史表對應於一個2位飽和計數器。分支歷史暫存器用於選擇哪個飽和計數器供現在使用。如果分支歷史暫存器是00，那麼選擇第一個飽和計數器；如果分支歷史暫存器是11，那麼選擇第4個飽和計數器。
假定，例如條件跳轉每隔2次執行就發生一次，即分支情況的歷史序列是001001001...。在這種情況下，00對應的飽和計數器將是狀態「強選擇」（strongly taken），表明在兩個0之後必然是出現一個1。01對應的飽和計數器將是狀態「強不選擇」（strongly not taken），表示在01之後必然是出現一個0。這也同樣適用於10狀態。而11狀態從未使用，因為不可能出現連續兩個1。
2級自適應預測器的一般規則是n位分支歷史暫存器，可以預測在所有n周期以內出現的所有的重複序列的模式。[2]
2級自適應預測器的優點是能快速學會預測任意的重複模式。此方法1991年被提出。[5] 已經變得非常流行。以此為基礎很多變種方法被用於現代微處理器。
局部分支預測
[編輯]局部分支預測（local branch predictor）對於每個條件跳轉指令都有專用的分支歷史情況緩衝區；模式歷史表可以是專用的，也可以是所有條件分支指令共用。
Intel Pentium MMX, Pentium II, Pentium III使用局部分支預測器，記錄4位元的歷史情況，每條條件跳轉指令使用專用的局部模式歷史表，當然是包含24 = 16個條目。
對SPEC'89 benchmark測評，非常大的本地預測器的正確率達到97.1%[6]。
全域分支預測
[編輯]全域分支預測器（global branch predictor）並不為每條條件跳轉指令保持專用的歷史記錄。相反，它保持一份所有條件跳轉指令的共用的歷史記錄。優點是能辨識出不同的跳轉指令之間的相關性。缺點是歷史記錄被不相關的不同的條件跳轉指令的執行情況稀釋了（diluted）；甚至歷史記錄沒有一位是來自同一個分支指令，如果有太多的不同的分支指令。
這種方法只有在歷史緩衝區足夠長，才能發揮出效能。但是模式歷史表的條目數是歷史緩衝區位數的指數量級。因此只能是在所有的條件跳轉指令間共用這個大的模式歷史表。
AMD的CPU，以及Intel的Pentium M, Core，Core 2使用了此種方法。
SPEC'89 benchmark評測，非常大的gshare預測器達到了96.6%正確率，略低於局部分支預測。
融合分支預測
[編輯]融合分支預測器（alloyed branch predictor）[7]組合了本地與全域預測原理，把本地與全域的分支歷史情況連接（concatenating）起來。VIA Nano處理器可能採用此方法。[2]
Agree預測器
[編輯]Agree預測器是一種兩級自適應全域預測器，但是附加了一個bias飽和計數器，用來記錄歷次預期的準確度。最終輸出結果是全域預測與bias飽和計數器的異或[8]。Intel Pentium 4使用了此種方法，但此後的Intel處理器放棄了此種方法。
迴圈預測器
[編輯]程式迴圈的控制部分所對應的條件跳轉指令最好用專門的迴圈控制器來預測分支。將要重複N次的迴圈的底部的條件跳轉指令，前N-1次選擇跳轉，只有一次不跳轉而是順序執行。條件跳轉指令有很多次選擇了一條分支，只有一次選擇另一分支，這種行為將被作為迴圈行為被檢測。這種條件跳轉指令可以用簡單的計數器很容易地檢測出來。迴圈預測器是一種混合預測器，其中元預測器判斷該條件跳轉指令是否具有迴圈行為。許多微處理器現在都有迴圈預測器。[2]
間接跳轉預測
[編輯]間接跳轉指令（indirect jump）是指運算元不是要轉去的下一條指令地址（這是直接跳轉），而是一個儲存位置（暫存器或者主記憶體），這個儲存位置的內容才是要轉去的下一條指令地址。例如je EAX，表示在ZF標誌暫存器為1情況下，跳轉到暫存器EAX所儲存的主記憶體地址開始的代碼快。
間接跳轉指令可以選擇多於兩條分支的執行路線。Intel與AMD的更新的處理器使用兩級自適應預測器能預測間接跳轉。間接跳轉指令在歷史緩衝區貢獻了超過1位的表示。沒有這種預測機制的處理器，就簡單地預測間接跳轉指令是否會如同上次一樣選擇同一目標。[2]
函數返回的預測
[編輯]許多處理器有專門用於表示函數呼叫返回地址的return stack buffer。[2]
overriding分支預測
[編輯]快速與精確，是分支預測需要平衡的兩個效能指標。有時就設置兩個分支預測器。第一個是簡單且快速。第二個是更慢、更複雜、表更大、可以覆蓋第一個預測器作出的預測。
Alpha 21264與Alpha EV8處理器使用一個快速的、單周期的下一行（next line）預測器處理分支目標，提供一個簡單快速的分支預測。兩個微處理器都有更複雜的、兩個周期的分支預測期，可以覆蓋下一行預測器的不準確的結果。
Intel Core i7有兩個分支目標預測器（Branch target predictor），可能有兩個或更多分支預測器。[9]
神經分支預測器
[編輯]1999年提出的神經分支預測器（neural branch predictor）[10]。突出優點是能夠利用很長的歷史記錄，僅導致了資源的線性增長。而傳統預測器的資源需要量與歷史長度是指數增長關係。這種方法主要缺點是高延遲。
神經分支預測器的準確度非常突出。（參見Intel's "Championship Branch Prediction Competition" [11]）。Intel在IA-64的模擬器 (2003)中實現了這一方法。
歷史
[編輯]分支預測對於指令管線化、超純量的處理器是非常重要的，如Intel Pentium, DEC Alpha 21064, MIPS R8000, IBM POWER等處理器。這些處理器依賴於1位或2位預測器。
參考文獻
[編輯]- ^ P. Shen, John; Lipasti, Mikko. Modern processor design: fundamentals of superscalar processors. Boston: McGraw-Hill Higher Education. 2005: 455. ISBN 0-07-057064-7.
- ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 Fog, Agner. The microarchitecture of Intel, AMD and VIA CPUs. 2009 [2009-10-01]. （原始內容存檔於2020-12-07）.
- ^ The Pentium 4 and the G4e: an Architectural Comparison （頁面存檔備份，存於互聯網檔案館）, Ars Technica
- ^ S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993
- ^ Yeh, T.-Y.; Patt, Y. N. Two-Level Adaptive Training Branch Prediction. Proceedings of the 24th annual international symposium on Microarchitecture. Albuquerque, New Mexico, Puerto Rico: ACM: 51–61. 1991.
- ^ S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993:8
- ^ Skadron, K.; Martonosi, M; and Clark, D.W. A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions. Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Philadelphia. Oct 2000.
- ^ Sprangle, E.; et. al. The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference. Proceedings of the 24th International Symposium on Computer Architecture. Denver. June 1997.
- ^ WO 2000/014628,Yeh, Tse-Yu & H P Sharangpani,「A method and apparatus for branch prediction using a second level branch prediction table」,發表於16.03.2000
- ^ Towards a High Performance Neural Branch Predictor, Proceedings of The International Joint Conference on Neural Networks - IJCNN '99, Washington DC, USA, 1999. (PDF). [2012-09-09]. （原始內容存檔 (PDF)於2019-07-13）.
- ^ Championship Branch Prediction. [2012-09-09]. （原始內容存檔於2008-05-28）.
外部連結
[編輯]- Seznec et al. (1996). "Multiple-Block Ahead Branch Predictors（頁面存檔備份，存於互聯網檔案館）" — demonstrates prediction accuracy is not impaired by indexing with previous branch address.
- Seznec et al. (2002). "Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor（頁面存檔備份，存於互聯網檔案館）" — describes the Alpha EV8 branch predictor. This paper does an excellent job discussing how they arrived at their design from various hardware constraints and simulation studies.
- Jimenez (2003). "Reconsidering Complex Branch Predictors（頁面存檔備份，存於互聯網檔案館）" — describes the EV6 and K8 branch predictors, and pipelining considerations.
- Fog, Agner. The microarchitecture of Intel, AMD and VIA CPUs. 2009 [2009-10-01]. （原始內容存檔於2020-12-07）.
- Andrews, Jeff. Branch and Loop Reorganization to Prevent Mispredicts. Intel Software Network. 2007-10-30 [2008-08-20]. （原始內容存檔於2008-04-17）.
- Yee, Alexander. What is Branch Prediction? - Stack Overflow Example. [2012-09-09]. （原始內容存檔於2016-06-22）.