記錄式分支預測器的硬體實現方法

2023-12-03 19:53:36 4

專利名稱：記錄式分支預測器的硬體實現方法
技術領域：
本發明涉及分支預測技術，尤其涉及一種記錄式分支預測器的硬體實現方法。
背景技術：
分支指令是程序中頻繁出現的指令，C語言中平均每9條指令就會出現一條分支 指令，分支指令帶來了程序行為的多樣性，在單發射順序執行處理器中，分支指令不影響程 序性能。但是在具有流水的處理器中，分支指令導致流水級中需要插入氣泡(Bubble)，影響 處理器性能。因此分支預測應運而生，分支預測指的是在計算出分支跳轉結果之前，預測分 支的跳轉方向，提前執行預測結果處的指令，如果分支結果和預測結果相同，那麼提前執行 的指令為有效指令，否則回滾提前執行的指令。
隨著處理器技術的發展，分支預測技術對處理器性能具有非常大的影響，準確的 分支預測和高效的錯誤預測結果回滾能夠使處理器性能更加強勁。Intel奔騰4處理器為 了能夠達到更高的頻率，採用了非常深的流水結構，使得流水級的每一步能夠在更短的時 間內完成。但是這樣設計使分支預測付出了更大的代價，由於深度的流水，當預測器錯誤預 測分支結果時，處理器需要回滾更多周期的錯誤結果，導致處理器性能低下，被人詬病。下 面幾個部分將詳細敘述分支預測技術的發展、先進的分支預測器以及多核時代下分支預測 面臨的挑戰。在指令級流水處理器發展的初始階段，分支點之後的指令需要等到計算出分支條 件以後才能夠進入流水，剛進入分支指令到計算出分支結果的時間間隔內，指令流水級中 插入氣泡(Bubble)，這樣的方式造成了處理器資源的浪費。於是提出了一種最簡單的分支 預測方法，就是當處理器在執行過程中遇到分支指令，則總認為分支指令是跳轉的(Taken) 或者不跳轉的(Not Taken)。這樣分支點之後的指令就可以提前進入流水，等到計算出分支 的結果以後判斷預測是否正確。這種方式對沒有固定跳轉模式的程序，預測的準確率相對 較高。靜態分支預測在程序運行階段缺乏靈活性，使得預測性能底下，於是人們就提出 了動態預測的方法。首先是一位計數器動態預測器，它記錄分支指令的執行結果，以0和 1分別表示分支的不跳轉和跳轉，當下次再次執行到這些分支指令的時候，就可以根據預測 位來預測分支。如果是0則預測不跳轉，如果是1則預測跳轉。每次分支在得到實際跳轉 結果以後更新預測位。和一位預測器原理相同，後來又提出了多位計數器預測器，用來記錄該分支以前 的跳轉情況。如果當前預測位的值大於等於預測位最大值的一半，那麼預測該分支跳轉，否 則就預測該分支不跳轉。如果實際結果是分支跳轉，那麼預測位的值更新為原來的值加1， 否則減1。多位預測器能夠比一位預測器取得更好的性能，因為多位預測器能夠容忍分支跳 轉的波動。但實驗結果表名，二位計數器的預測器最適合動態分支預測，它存儲空間較小而 且狀態轉換更快。在二位預測器中，0、1表示分支不跳轉，2、3表示分支跳轉。在程序的執行過程中，當前分支的跳轉與否又與該分支之前的分支跳轉結果有關，所以又通過一個全局歷史寄存器(GHR，Global History Register)記錄了當前分支之前的k條分支跳轉結果，然後用GHR去索引和更新模式歷史表(PHT，Pattern History Table), PHT是由二位計數器組成的一個表。這種結構也是以後GshanGselect等預測器 的基礎結構。而後發現由於只有一個獨立的PHT，不同地址的分支共同讀取和更新PHT，導致 了嚴重的相互幹擾，於是為了取得更高的預測效率，預測器又為不同的地址設立了不同的 PHT，一方面由PC的地址去決定索引哪個PHT，另外一方面又由GHR去索引PHT裡面的內容。 這樣的預測器被叫做全局分支預測器，因為不同地址的分支雖然分離的PHT，但還是共同使 用一個GHR。所以繼而又提出了局部分支預測器，也就是說不同地址的分支分別維護各自的 GHR。預測過程中，首先由PC索引決定使用哪個PHT和GHR，然後再由該GHR去索引PHT的 內容作為預測。更新的過程中則只更新相應的PHT和GHR。根據GHR和PHT進行分支預測的分支預測器被稱為兩級模式分支預測器，這類預 測器存在三個方面的性能缺陷。首先是分支別名，分支別名指的是在分支預測的過程中，存 在PHT表項的衝突問題。即不同的分支訪問相同的表項，這使得PHT的某些表項經常未被 使用，而某些表項被不同地址的分支同時使用。其次是分支歷史信息幹擾，它是由歷史分支 與當前分支的無關性引起的，具有幹擾作用的分支歷史信息也被稱作「噪音」，即那些分支 的結果對當前分支的結果不相關。最後是多路存取，即相同分支在預測時使用了不同的GHR 值，這導致同一分支需要訪問和修改PHT中的多各項，有些時候訪問多各項是必要的，而很 多時候訪問多個項是由於「噪音」引起的，這將降低分支預測的效率。

發明內容
為了能夠減少分支噪音帶來的多路存取對分支預測的性能影響，避免在分支預測 過程中通過訪問其他分支修改的PHT進行預測的冒險行為，提高分支預測效率，進而改進 處理器性能，本發明的目的在於提供一種記錄式分支預測器的硬體實現方法。本發明解決技術問題所採用的技術方案是1)記錄式分支預測器的工作過程記錄式分支預測器是記錄式結構在分支預測器上的運用，記錄式結構具有GHR、 GHR組、PC記錄、多路選擇器和兩個比較器；在預測時，分支的PC值和PC記錄中的PC值比 較，把相關的GHR存入GHR組中，再比較當前GHR較低幾位與GHR組中的值，最後決定用於 預測的GHR值，然後使用該GHR索引PHT，預測分支結果，記錄式分支預測器對PHT的更新保 持原來分支預測器的更新方法；2) PC記錄和GHR維護記錄式分支預測器中GHR較長，其維護過程如下當得到分支結果時GHR左移，新 得到的分支結果存入GHR的最低位，PC記錄是修改GHR對應位的PC值的記錄，GHR左移，那 麼PC記錄也會左移，PC記錄中的項始終與GHR中的位相對應；3) GHR組和多路選擇決定由於預測的GHR GHR組用於存放臨時的GHR值，通過第一比較器，將當前PC與PC記錄比較以後，可 能得到多個相等的值，那麼GHR組中就有多個項來存放當前PC和PC記錄比較後得到的相等的值，而這些相等的值的最終使用由第二比較器控制多路選擇器進行選擇；4)保持原來分支預測器的更新方法記錄式分支預測器在預測過程中具有和原來分支預測器不同的GHR使用方法，但是在對PHT的更新過程中，和原來分支預測器使用相同的GHR值，這個GHR值是記錄式結構 中較長GHR值的較低幾位。所述的預測時的三條原則1)如果某分支將要使用一個從來沒有對該分支預測過的GHR值進行預測，那麼採 用該分支上一次使用的GHR值進行預測，即使用上一次修改的PHT項進行預測；2)如果某分支將要使用的GHR值在該分支之前的預測中被使用過，那麼使用該 GHR進行分支預測；3)如果一個分支從來沒有被預測過，那麼使用默認GHR進行預測。本發明具有的有益效果是記錄式分支預測器能夠有效消除原來預測器中分支歷史噪音和多路存取的問題。


圖1是記錄式分支預測器在Gshare上的運用實例。圖2是一個改進預測器預測準確率的例子。
具體實施例方式下面結合附圖和實施例對本發明作進一步的說明。1)記錄式分支預測器的工作過程記錄式分支預測器是記錄式結構在分支預測器上的運用，如圖1所示，記錄式結 構具有GHR、GHR組、PC記錄、多路選擇器和兩個比較器；在預測時，分支的PC值和PC記錄 中的PC值比較，把相關的GHR存入GHR組中，再比較當前GHR較低幾位與GHR組中的值，最 後決定用於預測的GHR值，然後使用該GHR索引PHT，預測分支結果，記錄式分支預測器對 PHT的更新保持原來分支預測器的更新方法；2) PC記錄和GHR維護記錄式分支預測器中GHR較長，其維護過程如下當得到分支結果時GHR左移，新 得到的分支結果存入GHR的最低位，PC記錄是修改GHR對應位的PC值的記錄，GHR左移，那 麼PC記錄也會左移，PC記錄中的項始終與GHR中的位相對應；3) GHR組和多路選擇決定由於預測的GHR GHR組用於存放臨時的GHR值，通過第一比較器1，將當前PC與PC記錄比較以後， 可能得到多個相等的值，那麼GHR組中就有多個項來存放當前PC和PC記錄比較後得到的 相等的值，而這些相等的值的最終使用由第二比較器2控制多路選擇器進行選擇；4)保持原來分支預測器的更新方法記錄式分支預測器在預測過程中具有和原來分支預測器不同的GHR使用方法，但 是在對PHT的更新過程中，和原來分支預測器使用相同的GHR值，這個GHR值是記錄式結構 中較長GHR值的較低幾位。所述的預測時的三條原則
1)如果某分支將要使用一個從來沒有對該分支預測過的GHR值進行預測，那麼採用該分支上一次使用的GHR值進行預測，即使用上一次修改的PHT項進行預測；2)如果某分支將要使用的GHR值在該分支之前的預測中被使用過，那麼使用該 GHR進行分支預測；3)如果一個分支從來沒有被預測過，那麼使用默認GHR進行預測。記錄式分支預測器是記錄式結構在兩級模式分支預測器上的運用實施例，為了便 於表述，在下面的說明中使用記錄式結構在Gshare分支預測器上的運用實例。通過記錄式Gshare分支預測器來說明記錄式結構。Gshare是一個兩級模式分支 預測器，它使用全局GHR，對PHT的索引函數為GHR和PC的異或值。記錄式Gshare是便於 說明記錄式分支預測器的一個實例，並不代表記錄式結構器只能夠運用在Gshare預測器 上，記錄式結構是一個維護是使用GHR值的結構，用於改善運用它的分支預測器的預測性 能，能夠被利用在任何兩級模式分支預測器和其他使用GHR的分支預測器上。記錄式分支 預測器的理論依據是同一分支訪問相同的PHT項能夠比訪問其他分支修改過的PHT項取得 更好的預測準確率。首先通過例子說明改進分支預測器預測準確率的方法，假如a、b兩個分支(a分支 在b分支之前)與分支c的結果關聯，那麼a、b兩個分支的分支結果有4種組合00、01、10、 11，現假設a、b分支的00、01、11結果使得c分支跳轉，10結果使得c分支不跳轉。現又假 設GHR的長度為4位，而a、b的結果體現在GHR中的某兩個位，如圖2中為第2、第0位，另 外兩個位為與分支c結果無關的噪音。這兩位噪音也可以產生4種組合，而這兩位噪音使 得a、b分支的某一結果(如a、b都不跳轉，結果為00)有4個對應的GHR值，也就使得預測 器有可能索引PHT的4個項。相比本來只應該有1個PHT項，4個項需要更多的預熱時間， 訪問4各項產生的預測錯誤概率也越大。現在假設第一次預測分支c時GHR的值為1000，其中第2位和第0位代表分支a、 b的結果，第3和第1位為分支噪音。而第二次預測分支c的GHR變成了 0000，分支a、b還 是為00，而噪音位產生變化了，那麼如果能夠根據GHR為1000的項預測分支c，預測結果可 能會更加準確，因為GHR為0000的PHT項從來沒有被分支c存取過。這樣做沒有區分GHR 中具體的噪音位在哪裡，但是本質上相當於設置了 GHR中的兩個噪音位為1和0。然而當第三次預測時，GHR為0011，此時GHR中的有效位也發生了變化，但是當有 效位第一次變為01時，預測器中沒有任何線索判斷分支a、b為01時分支c將會跳轉或者 不跳轉，此時仍然使用GHR為0000時的結果進行分支預測。原因在於分支預測器如果使用 0011，那麼分支c就會使用一個其他分支修改的PHT作為預測，這是一種冒險。雖然在這裡， 有效位發生了變化，訪問以前GHR修改的PHT項也是冒險，但是這種情況裡包含了可能只是 噪音位變化的情況。當第四次預測分支c時，GHR為1000，這個GHR值以前被預測過，所以此時應當使 用GHR為1000的PHT項對分支c進行預測。採用這些策略的目的在於避免當分支產生多 路時，通過訪問其他分支修改的PHT項進行預測的冒險。所以記錄式結構遵循如下原則1.如果某分支將要使用一個從來沒有對該分支預測過的GHR值進行預測，那麼採 用該分支上一次使用的GHR值進行預測，即使用上一次修改的PHT項進行預測；
2.如果某分支將要使用的GHR值在該分支之前的預測中被使用過，那麼使用該 GHR進行分支預測；3.如果一個分支從來沒有被預測過，那麼使用默認GHR進行預測。上面三條對應的是分支的預測過程，即讀PHT的策略，因此相應的還有寫PHT的策 略，而不同的寫策略直接影響將來PHT讀取的內容，記錄式結構測試了不同的寫PHT策略， 結果表名遵循原來預測器的寫策略能夠使得預測 更加準確，所以在記錄式結構中，遵循的 第4條原則是4.使用原來預測器的更新策略更新PHT。記錄式分支預測結構如圖1所示，總共由7個部分組成，它們分別是PC記錄、GHR、 GHR組、比較器1、比較器2、多路選擇器、預測與更新。在這7個部分中，PC記錄和比較器 1與棧式結構中的PC記錄和比較器結構和功能類似，下面首先描述記錄式預測結構的工作 過程，然後詳細描述各個部分。記錄式結構的工作過程即是以上4條原則的實現過程。記錄式結構的GHR的更新 過程和原來分支預測器的更新過程相同，當得到新的分支結果以後，GHR左移，新的結果存 入GHR的最低位。PC記錄用於記錄更新GHR對應位的PC值，因此當GHR左移以後，PC記錄 也將左移，而且得到結果的分支PC值將被存入PC記錄的最右邊項。在預測過程中，第一步，PC值會與PC記錄中的所有記錄值進行比較，比較的結果 決定GHR組的內容。例如如果比較發現PC記錄中第5、9兩項與PC值相同，那麼GHR的 第5 12位、第9 16位將被映射到GHR組的第1、2兩個單元中(假設用於計算索引值 的GHR長度為8)；第二步，比較GHR組中是否有與GHR低8位(第0到7位)相等的值，如 果有相等的，那麼就用相等的那個值(即GHR的低8位)與PC值運算，索引PHT進行預測 (對應第2條原則)，如果沒有一個值相等，那麼就用GHR組中的第一個值與PC值運算，索 弓IPHT進行預測(對應第1條原則)；如果PC值和PC記錄中的值沒有一個相等，說明該分 支從來沒有被預測過，那麼就使用GHR的低8位進行索引計算(對應第3條原則)；在預測 器的更新時，採用GHR的低8位與PC值運算，把分支的實際結果更新到運算結果對應的PHT 項中(對應第4條原則)。記錄式結構中，GHR較長，而預測和更新過程中使用的GHR則較短，如圖1中GHR長 23位，而參與索引計算的GHR長度為8位。這樣設計的目的在於記錄相同分支以前被使用 過的GHR值，它與PC記錄配合使用，如果預測器中參與PHT索引計算的GHR長度為η位，而 PC記錄中第m項與當前需要預測分支的PC值相等，那麼就說明超長GHR中第m到(m+n-1) 位為該分支以前使用過的GHR值。超長GHR的長度比PC記錄的長度總是長n_l個單元，這 是因為最左邊的n-1個單元不能完整的保存一個η位的GHR。GHR組的作用在於臨時存儲分支以前訪問過的GHR值，當前PC值和PC記錄中的 值比較以後，有可能使用GHR中間的某一段值作為計算預測索引的GHR值，所以需要將那段 值進行臨時的存儲。而與當前分支PC值相等的PC記錄項有可能不止一項，所以需要有不 止一個的GHR臨時記錄，這樣就構成了一個GHR組。GHR轉存到GHR組中的原則是先存儲 較低位的GHR，例如PC記錄中有兩項與PC值相等，這兩項分別是第5、9項，那麼轉存到GHR 組中時，第5項PC記錄對應的GHR被存儲在GHR組的第0項，第9項PC記錄對應的GHR被 存儲在GHR組的第1項。多路選擇的原因在於既然GHR組中有可能不止一項，那麼就需要有一個選擇的邏輯結構判斷到底使用GHR組中的哪一項作為預測索引的GHR。在記錄式結構中，有兩個比較器，比較器1的作用是比較PC值與PC記錄中的項是否相等，如果PC記錄中存在和PC值相等的項，那麼這些項對應的GHR中的位需要被存放到 GHR組中。如果GHR組中的所有項沒有被填滿，那麼通過標記位標記該項未被填寫，這些標 記將被比較器2使用。比較器2的作用是比較GHR組中是否存在與GHR中低η位(假設參 與索引計算的GHR長度為η位，用陰影表示的那幾位)相同的項，如果存在相同的項，說明 那項GHR以前被當前預測的分支使用過，在多路選擇器選擇的時候，就選擇那個相同的項； 如果不存在相同的項，那麼就使用GHR組中的第一項；如果GHR組中一項也沒有，也就是說 這個分支以前沒有被預測過，那麼就使GHR中的低η位。比較器2的輸出是多路選擇器的 選擇信號，決定多路選擇器使用哪個GHR用於預測。在記錄式分支預測結構中，預測器對PHT讀取和對PHT更新採用了不同的索引計 算方法，使得PHT的讀取和更新可能為PHT的不同項。在進行預測的時候，遵循記錄式分支 預測的第1、2、3三條原則，所以在預測的時候，預測器根據前3條原則選取一個合適的GHR 用來計算預測的索引值。在進行PHT更新的時候，不同的更新策略使預測器產生不同的預 測行為，本發明保持原來分支預測器的更新策略。
權利要求
一種記錄式分支預測器的硬體實現方法，其特徵在於1)記錄式分支預測器的工作過程記錄式分支預測器是記錄式結構在分支預測器上的運用，記錄式結構具有GHR、GHR組、PC記錄、多路選擇器和兩個比較器；在預測時，分支的PC值和PC記錄中的PC值比較，把相關的GHR存入GHR組中，再比較當前GHR較低幾位與GHR組中的值，最後決定用於預測的GHR值，然後使用該GHR索引PHT，預測分支結果，記錄式分支預測器對PHT的更新保持原來分支預測器的更新方法；2)PC記錄和GHR維護記錄式分支預測器中GHR較長，其維護過程如下當得到分支結果時GHR左移，新得到的分支結果存入GHR的最低位，PC記錄是修改GHR對應位的PC值的記錄，GHR左移，那麼PC記錄也會左移，PC記錄中的項始終與GHR中的位相對應；3)GHR組和多路選擇決定由於預測的GHRGHR組用於存放臨時的GHR值，通過第一比較器(1)，將當前PC與PC記錄比較以後，可能得到多個相等的值，那麼GHR組中就有多個項來存放當前PC和PC記錄比較後得到的相等的值，而這些相等的值的最終使用由第二比較器(2)控制多路選擇器進行選擇；4)保持原來分支預測器的更新方法記錄式分支預測器在預測過程中具有和原來分支預測器不同的GHR使用方法，但是在對PHT的更新過程中，和原來分支預測器使用相同的GHR值，這個GHR值是記錄式結構中較長GHR值的較低幾位。
2.根據權利要求1所述的一種記錄式分支預測器的硬體實現方法，其特徵在於，所述 的預測時的三條原則1)如果某分支將要使用一個從來沒有對該分支預測過的GHR值進行預測，那麼採用該 分支上一次使用的GHR值進行預測，即使用上一次修改的PHT項進行預測；2)如果某分支將要使用的GHR值在該分支之前的預測中被使用過，那麼使用該GHR進 行分支預測；3)如果一個分支從來沒有被預測過，那麼使用默認GHR進行預測。
全文摘要
本發明公開了一種記錄式分支預測器的硬體實現方法。記錄式分支預測器是一個記錄式結構在兩級模式分支預測器上的運用，該記錄式結構記錄分支預測的一些信息，並且在將來的預測過程中，這些信息按一定的規則被使用，使記錄式分支預測器能夠比原來預測器取得更好的性能。記錄式分支預測器的理論依據是同一分支訪問相同的PHT項能夠比訪問其他分支修改過的PHT項取得更好的預測準確率，記錄式分支預測器的更新原則和原來預測器的更新原則相同。記錄式結構是對分支預測過程中對GHR進行維護和使用的一個硬體結構，能夠被運用在兩級模式分支預測器和其他使用GHR的分支預測器中。本發明能夠有效消除原來預測器中分支歷史噪音和多路存取的問題。
文檔編號G06F9/38GK101826002SQ20101014850
公開日2010年9月8日 申請日期2010年4月16日 優先權日2010年4月16日
發明者施青松, 胡威, 蔣冠軍, 袁輝, 陳天洲 申請人:浙江大學