用於實現多態分支預測器的方法和裝置的製作方法

2023-04-24 22:39:16

專利名稱：用於實現多態分支預測器的方法和裝置的製作方法
技術領域：
本發明總體上涉及微處理器中分支指令的處理，並且更具體地， 涉及用於實現多態分支預測器的方法和裝置。
背景技術：
現代處理器通過應用預測技術來解決流水線分裂事件(諸如分支 操作)以此來實現性能。根據現有技術，已經提出了多種分支處理技 術。分支預測器是處理器的一部分，其確定程序指令流中的條件分支 是否有可能發生。這稱為分支預測。在當今的現代超標量處理器中， 分支預測器對於實現高性能至關重要。分支預測器允許處理器取回並 執行指令，而無需等待求解分支。
早期的RISC架構實現進行普通的分支預測例如，該架構總是 預測分支(或者無條件跳轉)將不會發生，因此其總是取回接下來的 連續指令。取指指針僅在對分支或者跳轉進行評估時被設置為非連續 地址。這些CPU在解碼階段評估分支，並且具有單周期的取指。因 此，分支目標循環的長度是兩個周期，並且機器將總是取回緊隨任意 發生分支之後的指令。 一些架構定義了分支延遲槽，以使用這些取回 的指令。
實現"靜態預測"的處理器預測向後指向的分支將發生(假設 該向後分支在程序循環的底部)，而向前指向的分支將不會發生(假 設其較早退出了循環或者其他處理代碼)。對於執行多次的循環而言， 這僅僅錯誤預測了循環的最後分支。在多數具有動態分支預測的處理 器中，靜態預測被用作回退(fall-back)技術(當沒有任何信息可供 動態預測器使用時)。
一些超標量處理器利用指令的每一行取回指向下一行的指針。該
5下 一行預測器不能直接與在此列出的其他預測器進行比較，因為該下 一行預測器處理分支目標預測以及分支方向預測。當下一行預測器指
向對齊的2、 4或8個指令的群組時，分支目標通常將不是被取回的 第一指令，並且因此浪費了取回的初始指令。為了筒化，假設分支目 標的均勻分布，分別丟棄取回的0.5、 1.5和3.5指令。
由於分支本身通常將不是對齊群組的最後指令，因此將丟棄發生 的分支(或者其延遲槽)之後的指令。再次，假設分支指令的放置均 勻分布，丟棄取回的0.5、 1.5、 3.5指令。即使對於單周期下一行預測 器而言，在分支處丟棄的指令和目的行總計也幾乎是整個取指周期。
雙峰分支預測器具有2位飽和計數器的表，由指令地址的最低有 效位索引。不同於指令緩存，雙峰預測器條目通常不具有標籤，並因 此可以將特定的計數器映射至不同的分支指令(這稱為分支幹擾或者 分支混淆)，在這種情況下，有可能不太準確。每個計數器具有以下 四個狀態之一l)強不發生，2)弱不發生，3)弱發生，以及4)強 發生。
在評估分支時，更新相應的計數器。被評估為不發生的分支朝著 "強不發生"降低狀態，而被預測為發生的分支朝著"強發生"提升 狀態。該2位飽和計數器方案的主要好處在於循環封閉分支總是被 預測發生。1位方案對於循環的第一分支和最後分支二者都會錯誤預 測。2位方案僅會錯誤預測最後分支。類似地，對於幾乎總是沿一個 方向執行的嚴重偏向的分支，1位方案對於每個奇數分支會錯誤預測 兩次，而2位方案錯誤預測一次。
由於雙峰計數器的表是通過指令地址位來索引的，因此超標量處 理器可以將該表劃分為用於每個取回指令的獨立SRAM,並且與取指 令並行地取回對於每個指令的預測，從而使分支預測在對分支解碼之 後立即可用。除了 2位預測器，基於使用n位的預測器的各種類似的 飽和計數器也是可能的。
雙峰分支預測錯誤預測每個循環的退出。對於傾向於每次具有相 同循環次數的循環而言(以及對於具有重複行為的很多其他分支而言)， 一些預測器可以做得更好。局部分支預測器保持兩個表。第一 表是局部分支歷史表。該表由分支指令的地址的低順序位索引，並且
記錄該分支的n次最近執行的發生/不發生歷史。另一表是模式歷史 表。此表包括實際的預測器；然而，其索引根據第一表中的分支歷史 生成。為了預測分支，查詢分支歷史，並且繼而使用該歷史來查詢預 測器以進行預測。該方法可以使用l位預測器，或者n位預測器(諸 如雙峰預測器)。
局部預測比雙峰預測慢，因為對於每次預測，局部預測需要兩個 連續的表查詢。快速實現將針對每個取回的指令使用獨立的雙峰計數 器陣列，從而使第二陣列訪問可以與取指令並行地進行。這些陣列不 是冗餘的，因為每個計數器意在存儲單個分支的行為。全局分支預測 器利用很多分支的行為都與其他最近發生的分支強相關這一事實。在 一種實現中，預測器可以保持通過每個執行分支的最近歷史來更新的 單個移位寄存器，並且使用該值來索引到預測器(例如，l位預測器 或者雙峰計數器預測器)的表。
gselect預測器利用與分支指令地址的幾個位級聯的最近歷史來 索引預測器的表。對於較小的表，gselect比局部預測做得更好；而對 於大於1KB的表存儲，局部預測僅僅略好。另一實現通過對分支指 令地址和全局歷史進行異或(XOR)而不是級聯，從而提供了更好的 預測準確性，其代價是用更昂貴的異或取代筒單的級聯。該預測器被 稱為gshare,對於大於256位元組的表而言，其略好於gselect。
gselect和gshare比局部預測更容易加快，因為它們每個分支需要 單次表查詢。對於雙峰預測，可以對表進行劃分，使得可以對每個取 回的指令進行並行查詢，從而可以與指令裝載並行地進行表查詢。 Scott McFarling在"Combining Branch Predictors", WRL Technical Note 36， 1993中提出了合併分支預測。在本說明書下文中將這種合併預測 器稱為多組件預測器。合併分支預測大約與局部預測一樣準確，並且 與全局預測一樣快速。
合併分支預測並行地使用三個預測器(例如，局部雙峰預測器、gshare預測器和類雙峰預測器)，以在逐個分支的基礎上挑選使用雙 峰或者gshare預測器中哪一個。選擇預測器可以是用於選擇要使用的 預測的1位預測器或者飽和n位計數器。在這種情況下，每當雙峰和 gshare預測不一致時就更新計數器，以選定要選擇哪個結果。另 一種 合併分支預測器的方法是具有例如3個不同的分支預測器，並且通過 多數表決來合併其結果。類似於gshare的預測器使用多個表條目來跟 蹤任意特定分支的行為。條目的增多使得兩個分支將有更大的可能映 射至相同的表條目(這種情況稱為混淆)，這繼而使得預測準確性更 有可能受到那些分支的影響。只要採用了多個預測器，則這樣布置是 有利的每個預測器具有不同的混淆模式，從而更有可能使至少一個 預測器將沒有混淆。對於不同預測器具有不同索引功能的合併預測器 稱為gskew預測器，並且其類似於用於數據和指令緩存的偏斜
(skewed)緩存器。
降低模式歷史表中的破壞性混淆的另 一種技術是一致預測器。一 種方法被用來建立針對分支的相對靜態預測，可能是雙峰預測器或者 分支指令中的提示位。另一預測器(例如，gskew預測器)進行預測， 但是不是預測發生/不發生，該預測器預測與基本預測的一致/不一致。 其意圖在於如果gskew預測器覆蓋的分支傾向於偏向一個方向l位
(可能是70%/30%),則可以對齊所有那些偏向，使得gskew模式歷 史表將傾向於具有多於不一致條目的一致條目。這降低了兩個混淆分 支將最好具有預測歷史表(PHT)中相對值的可能性。
一致預測器與合併預測器一起工作得很好，因為合併預測器通常 具有可以用作 一 致預測器基礎的預測器。 一 致預測器與不偏向 一 個方 向的分支一起工作得不是太好，如果一起工作，這使得基礎預測器給 出改變的預測。所以， 一致預測器作為三預測器方案的一部分可以最 好地工作，該三預測器方案中一個是一致預測器、另一個是非一致型 預測器。
幾乎所有的流水線處理器都進行某種形式的分支預測，因為其必 須猜測下一指令的地址，以便在當前指令執行完之前取回下一指令。設計分支預測技術的關鍵參數是分支預測條目的數目以及分支預測
算法(諸如，l位預測器或者飽和n位預測器)。這些決策必須適用 於針對局部預測器或者全局預測器的各種分支預觀'J方法。
儘管現有技術已經允許合併各種預測器，但是對於微處理器設計 者而言，關鍵的決策是選擇分支預測算法。根據現有技術，利用固定 的k位的存儲器分配，設計者能夠實現使每個預測表具有k個1位預 測器、或者k/2個雙峰預測器，或者更一般地，具有n位計數器的k/n 個預測器。這代表了一種權衡是提供通過每次預測使用較多的位而 允許單個預測的質量改進的預測器，還是提供構造較簡單的預測器。
在另一權衡中，設計者有可能選擇較長延遲的局部預測器，或者短延 遲的雙峰預測器或1位預測器。
最佳預測質量取決於各種因素，諸如負載特定的屬性，其對於不 同的程序或者在程序之間是不同的。因此，儘管現有技術已經允許合
優化預測。相反，結構(諸如竟賽預測器)、全局或局部預測的使用 以及1位預測器或者雙峰預測器的選擇必須在設計時確定，這需要實 現者一次性選擇特定的配置並且該配置將用於所有應用。
儘管預測器設計已經允許良好的平均性能，但是現有技術無法針 對特定應用來優化預測器。

發明內容
應用運行時將所述多態分支預測器配置為針對特定應用而選擇至少 一個結構或者算法。
一種多態分支預測器和方法，包括多個分支預測方法。可以選擇 性地啟用該方法來執行分支預測。將選擇機制配置為根據動態設置而 選擇一個或多個分支預測方法，以便根據當前任務在操作期間優化分 支預測器的性能。
一種多態分支預測器，包括多個分支預測方法，每個方法能夠被選擇性地啟用以執行分支預測。將選擇機制配置為根據動態設置來選 擇 一 個或多個分支預測方法，以便根據當前任務在操作期間優化分支 預測器的性能。
在備選實施方式中，多態分支預測器設置可以包括性能量度。可 以將選擇機制配置為選擇至少兩個分支預測方法，以便一起工作來提 供結果。選擇機制可以事先指派或者根據對運行時行為的分析來選擇 一個或多個分支預測方法以用於特定的應用或者應用集。
在另一實施方式中，可以將選拷^幾制配置為v^人編i奪器和運行時組 件之一接收信息，以選擇一個或多個分支預測方法。可以將選擇機制 配置為在應用的運行期間進行更新，或者將其配置為根據來自邏輯功 能、地址位、線程指示器和若干地址位或線程位的散列的至少一個輸 出來進行更新。
該多態分支預測器還可以包括預測器條目的陣列，其中，存儲在 陣列中的預測器條目針對信息位數、逐位寫使能信號或者多位寫使能 信號而被配置，以允許對陣列的寫操作。
每個分支預測方法可以包括邏輯元素，使得邏輯元素在分支預測 方法之間共享，以提高效率。在分支預測方法之間共享的邏輯元素可 以包括陣列、預測器更新邏輯以及地址生成邏輯中的至少一個。多態 分支預測器可以包括預測器條目的陣列以及分支信息隊列，其中，使 用來自分支信息隊列的信息來預先重寫從陣列讀取的信息。多態分支 預測器可以包括尋址邏輯，其被配置為在統一表和多組件預測器的表 之間共享。可以提供預測器條目的多組件陣列，其中，通過地址位或 者通過地址散列來選擇預測器條目，以選擇多組件陣列之一。
一種用於動態選擇分支預測方法的方法，包括提供多個可動態 配置的分支預測方法；根據動態配置來選擇一個或多個分支預測方 法，以便根據當前任務在操作期間優化分支預測器的性能；以及更新 該一個或多個分支預測方法的配置，以提供改進的預測結果。
當結合附圖閱讀下文對示範性實施方式的詳細描述時，這些以及 其他目的、特徵和優點將變得顯而易見。


本公開將在下文描述中參考附圖提供優選實施方式的細節，其
中
圖1示出了可以根據本發明而採用的包括分支預測器的示例性流 水線框圖2A和圖2B分別示出了 1位預測器狀態和雙峰預測器狀態； 圖3示出了示範性竟賽預測器；
圖4示出了根據示範性實施方式的對具有帶有分支信息隊列的1 位和雙峰預測器的多態預測器的讀訪問；
圖5A示出了根據示範性實施方式的使用能夠寫更新單個存儲位 的存儲器陣列來更新多態1位/雙峰預測器的實現；
圖5B示出了根據示範性實施方式的使用能夠通過雙位來寫更新 條目的存儲器陣列來更新多態1位/雙峰預測器的實現；
圖6是根據示範性實施方式的用於共享預測器以便進行1位和n 位預測的電路的示意圖7A是示出了根據示範性實施方式的用於可配置為實現單個統 一大小預測器或者竟賽預測器的多態分支預測器的讀路徑的示意圖7B是示出了根據示範性實施方式的用於可配置為實現單個統 一大小預測器或者竟賽預測器的多態分支預測器的另一讀路徑的示 意圖8是示出了根據另一示範性實施方式的用於可被配置為竟賽或 者統 一 陣列的示範性多態預測器的寫更新路徑的示意圖9是示出了根據示範性實施方式的用於竟賽/非竟賽分支預測 的更新邏輯共享的示意圖10A是示出了根據示範性實施方式的生成配置代碼以配置分 支預測的編譯器的框圖/流程圖10B是示出了根據另一示範性實施方式的例如使用連續剖析 (profiling)優化來動態地選擇分支預測方法的框圖/流程圖；以及圖11是示出了根據示範性實施方式的作業系統(OS)調度(或 者管理器劃分調度)的框圖/流程圖。
具體實施例方式
本發明的實施方式涉及實現多態分支預測器，以及通過軟體來使 用和選擇它們。本發明實施方式的形式可以採取全硬體實施方式、全 軟體實施方式或者包含硬體和軟體元件二者的實施方式。在優選實施 方式中，將多態預測器實現為集成電路。配置選擇可以通過軟體來實
現，包括但不限於微代碼、固件、駐留軟體、管理器、作業系統、 系統工具、應用程式等。
此外，本發明可以採取電腦程式產品的形式，其可從計算機可 用或者計算機可讀介質進行訪問，所述介質提供程序代碼以供計算機 或者任何指令執行系統使用或者與之結合使用。出於本說明書的目 的，計算機可用或者計算機可讀介質可以是能夠包括、存儲、通信、 傳播或者傳輸程序以供指令執行系統、裝置或設備使用或者與之結合 使用的任何裝置。介質可以是電、磁、光、電磁、紅外或者半導體系 統(或者裝置或設備)或者傳播介質。計算機可讀介質的示例包括半 導體或者固態存儲器、磁帶、可移動計算機碟片、隨機訪問存儲器 (RAM)、只讀存i者器(ROM)、硬乂磁碟和光碟。光碟的當前示例 包括壓縮盤-只讀存儲器(CD-ROM)、壓縮盤-讀/寫(CD-R/W)和 DVD。
適於存儲和/或執行程序代碼的數據處理系統可以包括至少 一 個 處理器，其直接或者通過系統總線間接耦合至存儲器元件。存儲器元
量存儲器以及緩存存儲器，其中緩存存儲器提供至少 一些程序代碼的 臨時存儲，以便減少在執行期間從大容量存儲器獲取代碼的次數。輸 入/輸出或稱1/0設備(包括但不限於鍵盤、顯示器、指示設備等)可 以直接或者通過中介I/O控制器而間接耦合至系統。
網絡適配器也可以耦合至系統，以使得數據處理系統能夠通過中介專有網絡或公共網絡而耦合至其他數據處理系統或者遠程印表機 或者存儲設備。數據機、纜線數據機以及乙太網卡僅僅是目 前可用的網絡適配器類型的幾個例子。
此處描述的多態分支預測器可以是針對集成電路晶片的設計的 一部分。晶片設計可以通過圖形化計算機程式語言來創建，並且存儲 在計算機存儲介質中(諸如碟片、帶、物理硬碟驅動，或者諸如存儲 訪問網絡中的虛擬硬碟驅動)。如果設計者沒有製造晶片或者用以制 造晶片的光刻掩模，則設計者直接或者間接的通過物理手段(例如， 通過提供存儲有設計的存儲介質副本)或者以電子形式(例如，通過 網際網路)將結果設計發送給這樣的實體。繼而將所存儲的設計轉換為
適當的格式(例如，GDSII)以用於光刻掩模的製造，其通常包括所 考慮的將要形成在晶片上的晶片設計的多個副本。使用光刻掩模來定 義將要蝕刻或者處理的晶片的區域(和/或其上的層)。
製造商可以採用未加工晶片(也即，作為具有多個未封裝晶片的 單個晶片)的形式、作為棵片或者以封裝形式來分發作為結果的集成 電路晶片。在後一種情況中，晶片被安裝在單片封裝(諸如塑料載體， 其具有附著於主板或者其他更高級別的載體的導線)或者多片封裝 (諸如陶瓷載體，其具有表面互連或嵌入互連或者二者)中。在任意 情況下，晶片繼而與其他晶片、離散電路元件和/或其他信號處理設備 集成，作為(a)中間產品(例如主板)或者(b)最終產品的部分。 最終產品可以是包括集成電路晶片的任意產品，從玩具和其他低端最 終應用到具有顯示器、鍵盤或其他輸入設備以及中央處理器的高級計 算機產品。
現在參考附圖，其中相同的數字表示相同或者類似的元件，首先 參考圖i，其範例化地示出了根據實現本發明的處理器的、可以使用
分支預測的示例性高性能微處理器流水線10。使用取指邏輯IF從指 令緩存IC取回指令。指令由分支預測邏輯BP處理，並且被傳遞給譯 碼邏輯D0、 Dl、 D2、 D3。如果遇到預測為發生的分支，則分支預測 可以通過更新取指邏輯IF中維護的取指地址來實現取指方向的改變。經由傳送工具XFER將經過解碼的指令(分支指令和非分支指令 二者)傳送給分派邏輯GD。使用寄存器映射表MP對所分派的各個 指令進行重命名，並且將其輸入到發射邏輯ISS中維護的發射隊列， 以便根據指令類型發射到適當的執行流水線BR、 LD/ST、 FX和FP。 發射邏輯ISS從發射邏輯中維護的發射隊列中彼此亂序地發射出指 令。
現在參考計算流水線LD/ST、 FX和FP中的執行，指令對一個或 多個寄存器文件RF執行寄存器文件訪問，並且進入執行階段。對於 LD/ST指令，執行階段包括第一地址生成階段EA,隨後是數據緩存 訪問和數據格式化。對於FX指令，執行包括由EX實現的邏輯功能。 對於FP指令，執行包括一個或多個邏輯功能F1到F6。現在參考BR 流水線中分支指令的執行，分支指令可選地執行一個或多個寄存器文 件訪問，以獲取寄存器文件訪問邏輯RF中的一個或多個條件、分支 計數器以及分支目標操作數。BR流水線中的分支執行邏輯EX計算 目標地址和分支條件，並且與預測目標和條件進行比較。如果檢測到 了錯誤預測(例如，錯誤地計算了條件或者提供了錯誤的目標)，則 進行分支重定向動作。使用清空(flush)或者其他適當的機制將錯誤 預測的指令從執行流水線移除，並且更新在取指邏輯IF中維護的取 回地址。
所有執行流水線通過執行計算結果的寫回以及向提交級CP的傳 送XFER來竟爭。
提交級CP將指令在其按序提交點處按照其相對於其他所有指令 的順序進行提交。中斷條件、異常以及其他特殊執行條件使提交級執 行清空和重取，其將取指邏輯IF中的取指地址設置為重新執行或中 斷或異常處理地址之一。
參考圖2A和圖2B,其示出了兩個示例性分支預測器條目類型。 每個預測器與特定的分支相關聯，其中該分支與使用分支地址、 gshare、 gselect或者局部預測器的結果相關聯。當在選擇和關聯機制 的控制下檢索預測器時，標識預測器狀態，並且基於該狀態來進行預
14測。
現在更具體地參考圖2A, 1位預測器202使用單個信息位來表示 兩個狀態(發生205和不發生210)之一，其對應於將要進行的下一 預測。如果預測器處於發生狀態205，預測返回分支將發生的指示。 如果預測器處於不發生狀態210，預測返回分支將不會發生的指示。 當在示例性BR流水線中的分支執行期間檢查預測時，錯誤預測將導 致狀態遷移，例如，預測將變為反映上次分支結果的方向，如標有分 支結果的狀態遷移弧線206所示。
參考圖2B,其示範性地示出了示例性雙峰預測器，其使用兩個 信息位來表示四個狀態之一，其對應於將要進行的下一預測。這四個 狀態包括強不發生250、弱不發生255、弱不發生260、強不發生265。 如果預測器處於兩個"發生"狀態250和255之一，預測返回分支將 發生的指示。如果預測器處於兩個"不發生"狀態之一，則預測返回 分支將不會發生的指示。當在示例性BR流水線中的分支執行期間檢 查預測時，將根據圖2B來執行狀態遷移。具體地，正確的預測將導 致選擇適當方向的"強"狀態。如果檢測到了錯誤預測，並且如果預 測器先前處於強狀態250或者265，則預測器更新將分別執行到弱狀 態255或者260。如標有分支結果的圖2B的遷移弧線257所示，如 果預測器處於弱狀態，則預測方向將在狀態255和260之間改變。
參考圖3，示出了示例性的竟賽預測器300,其包括三個示例性 組件預測器，例如局部預測器310、全局預測器320以及選擇預測器 330。選擇機制340在選擇預測器330的控制下選擇局部預測器310 和全局預測器320之一做出的預測。
參考圖4,示範性地示出了在模式控制選擇機制430 (例如"1位 /2位"模式)控制下的多態分支預測器400的實現方面。控制選擇機 制430或者使用將預測器400用作具有n個條目的1位預測器的第一 模式，或者使用將預測器400用作具有預測陣列410中數目減少的條 目(例如，n/2個條目)的2位預測器的第二模式。
才艮據優選實施方式，陣列410在輸入405處^f吏用(ldn)/2個地址位來尋址具有2位的單個條目，以讀出陣列410。根據分支預測器的一 種實現，從陣列410獲取的分支預測位(例如b0和bl )作為biq_bO 和biq_bl存儲在分支信息隊列BIQ 415中，以供BR執行流水線使用。
可以根據獲取的2位信息來進行預測，在第一操作模式中，實現 2位預測器，並且在選擇元件420和425的控制下分別將2個位提供 為方向輸出440和確信輸出445。在多態配置信息430的控制下配置 選擇元件420和425。在第二操作模式中，預測器400作為1位預測 的提供者而進行操作。選擇機制420在多態配置信息430的控制下選 才奪陣列410提供的兩個位之一，作為1位方向性預測輸出440。
根據多態預測器400的一種實現，按照如下方式實現對附加預測 器地址位(例如，地址位422)的選擇。當處於2位模式或者地址422 等於O時，方向440變為b0。否則，方向440等於bl。 ^使用標準化 VHDL符號來描述該條件、但是允許符號化名稱描述對應於此處所包 括的教導方面的條件和信號，可以將邏輯操作聲明為
formula see original document page 16
其中address—bit例如表示為圖中的"msb，，。(對於最高有效位， 其是可以選擇的一個可能位)。
根據一種實現，可選地通過將1位預測器的確信位重新設置為 "弱"狀態來將1位預測器格式化為雙峰預測器，以用於公共數據流 中的共享處理。這可以包括在2位模式中使確信445變為bl，否則使 其變為0。使用標準化VHDL符號來描述該條件、但是允許符號化名 稱描述對應於此處所包括的教導方面的條件和信號，該邏輯可以聲明 為
formula see original document page 16，
該示範性實施方式是示例性的和非限制性的。本領域的技術人員 將會理解，當實現1位預測器時可以使用其他機制來選擇兩個位之一 (例如，可以使用線程指示符來替代地址位)，可以使用各種不同的 地址位，例如包括夂f旦不限於最低有效位、最高有效位、多個地址位的 散列、線程位等等。本領域的技術人員還將理解，可以在每個線程的基礎上維護多態分支預測，允許一個線程將預測器用作l位預測器， 而另 一併發執行的應用可以使用存儲元件和邏輯來執行2位預測。
在至少 一種實現中，從具有寬讀取埠的單個陣列或者使用預測 器陣列的多個並行副本，來同時獲取用於多個分支的多個預測。在此 類實施方式中，將適當地調整和/或減小地址位的數目，以反映從預測 器存儲器並發獲取的位的數目。在另一實施方式中，選擇不同的位寬
度，允許支持不同於示例性的l位和2位預測器的位寬度的第一和第
二預測器位寬度。在又一實施方式中，從分離的陣列獲取兩個位的每 一個，這允許在預測器地址位的控制下釋放陣列之一，或者獲取可以
用來控制選擇邏輯420的其他這樣的位。
參考圖5A和圖5B,示範性地示出了用於根據多態預測機制執行 對預測器存儲陣列510的寫操作的實現。在圖5A中，示範性地示出 了對預測器存儲陣列510的預測器存儲器寫入，其支持兩個位(b0 和bl)的並發存儲，並且對於每個位具有獨立的寫使能工具。根據該 工具，存儲陣列510接收在輸出505處具有(ld n) /2個地址位的地 址、第一數據位bO和第二數據位bl以及第一寫使能信號we_bO 511 和第二寫使能信號we—bl 512,其對應於寫入地址所指定條目的第一 位b0和第二位bl。
#4居該示例性實施方式，可以進^f於1位預測器更新，或者可以通 過使用選擇機制520來進行2位預測器更新。對於用於執行2位預測 器更新的第一操作模式，在多態配置信息520的控制下將方向值530 提供給位bO,並且將確信值535提供給位bl。此外，選擇寫使能信 號we—b0 511和we—bl 512 二者，以更新位b0和位bl 二者。在用於 執行1位預測器更新的第二操作模式中，在選擇邏輯515以及寫使能 we—b0 511和weJ)1 512之一的控制下將方向值530寫到位b0和bl 之一。
在一個示例性實施方式中，如下來計算位(使用標準化VHDL符 號)
b0 <= direction;bl <= confidence when (mode = 2bit) else direction;
we—b0 <= 2_bit_update when (mode = 2bit) else
1—bit—update and address—bit = 'O，； we—bl <= 2—bit—update when (mode =2bit) else 1—bit update and address bit = 'l，；
參考圖5B,示範性地示出了對預測器存儲陣列560的預測器存 儲器寫入，其支持兩個位的並發存儲，並且具有用於這兩個位的公共 寫使能工具。根據該工具，存儲陣列560接收在輸入505處具有(Id n)/2 個地址位的地址、第一數據位b0和第二數據位bl，以及單個寫使能 we 563，其對應於寫入地址所指定條目的兩個位。4艮據該示例性實施 方式，可以進行l位預測器更新，或者可以進行2位預測器更新。
在用於執行2位預測器更新的第 一操作模式中，在多態配置信息 570以及由選擇(sel)信號控制的選擇邏輯562和565的控制下，將 方向值530提供給位bO,並將確信值535提供給位bl。此外，選擇 寫使能信號we 563,以利用方向信息530和確信信息535來更新地址 條目。在用於執行1位預測器更新的第二操作模式中，在選擇邏輯562 的控制下將方向值530寫到位b0和b 1之一 ，並且使用關於原始條目 內容的信息(biq—b0和biq_bl )(該信息已經存儲在示例性分支信息 隊列BIQ 415中)在選擇器位(sel)、邏輯562和565以及多態配置 信息570的控制下，來重新存儲先前的信息。在一個示例性實施方式 中，如下計算位(使用標準化VHDL符號) bO <= direction when (mode = 2bit OR address—bit = '0，) else
biq一bO;
bl <= confidence when (mode =2bit) else direction when (address—bit = ' 1，) else biq—bl;
we <= 2—bit—update when (mode = 2bit) else 1—bit—update;本領域的技術人員將會理解，圖5B描述的實施方式對陣列560 中的較高存儲密度進行了折衷，因為錯誤依賴性導致了預測器更新的 覆蓋，其可能發生在獲取BIQ信息的時間和存儲所獲取信息的時間之 間。本領域的技術人員還將理解，能夠提供一個或多個最近更新值的 關聯性旁路，以減小或者消除這種錯誤依賴性更新的影響。圖5A和 圖5B是示例性的而非限制性的。本領域的技術人員將會理解，在實 現1位預測器時可以4吏用其他才幾制來選擇兩個位之一 (例如，可以佳: 用線程指示符來替代地址位)，可以使用各種不同的地址位，諸如包 括但不限於最低有效位、最高有效位、多個地址位的散列、線程位等 等。本領域的技術人員還將理解，可以在每個線程的基礎上維護多態 分支預測，這允許一個線程將預測器用作1位預測器，而另一併發執 行的應用可以使用存儲元件和邏輯來執行2位預測。
參考圖6，示出了低開銷多態預測器的實現，其中，對多態功能 的支持沒有明顯增加邏輯複雜性。因此，期望使用公共邏輯功能來實 現針對所有可配置多態模式的預測更新邏輯。根據新穎的多態預測 器，示出了分支預測更新邏輯600,根據本發明，其被用來更新l位 和2位(雙峰)預測器二者。提供了分支信息隊列BIQ415的內容(諸 如biq—b0和biq_bl )以及由圖1所示的示例性孩i處理器的BR扭^亍流 水線的邏輯EX計算的"分支結果"。根據本發明，多態預測器更新 提供更新的方向信息650,更新的確信信息655,以及指出應當在預 測器存儲中更新1位(657)還是2位(雙峰)(656 )預測器的指示。
特別地，用於計算分支預測610的邏輯對應於圖2B的雙峰預測 器(2位預測器)的未修改功能。根據圖6的實施方式，在第一操作 模式中，在多態配置670的控制下，根據圖2B來計算2位預測更新 656結果，這提供了是否在預測器存儲器中更新2位預測器的更新信 息656以及更新的方向650、確信信息655。在第二操作模式中，提 供了根據圖2A的1位預測結果，其提供是否在預測器存儲器中更新 2位預測器的更新信息657以及更新的方向650。
在一個示例性實施方式中，如下計算更新U吏用標準化VHDL符號)
b0 <= biq—b0 when (mode = 2bit OR address—bit = 'O，) else biq_bl;
bl <= biq—bl when (mode = 2bit) else 'O，；
1— bit—update <= bO /= direction;
2— bit update <= bO /= direction OR bl /= confidence.
圖6中描述的邏輯和操作是非限制性的，可以根據此處的教導來 實踐其他類型的預測器更新共享。可以對寬度、功能進行其他的修改。 針對特定的技術以及使用公知的變換，本領域的技術人員將會找到邏 輯優化和變換來減小邏輯錐的大小和深度等。為了簡化而省略了這些內容。
現在參考圖7A和圖7B,示出了用於針對預測器的組織結構來多 態配置預測器的方法。這些方法以示例性的方式示出，可被配置為實 現單級統一預測器或者竟賽預測器。還可以根據圖4、圖5A和圖5B 中給出的教導、針對預測器條目的存儲和操作來配置每個預測器710、 720、 730。
參考圖7A,示範性地示出了用於多態預測器的第一示例性讀取 方法和裝置，其包括統一大小的單預測器或者竟賽預測器之一。根據 該示例性實施方式，使用來自尋址邏輯781的多態配置信息780來將 配置控制為竟賽預測器或者統一陣列預測器。竟賽預測器包含多個第 一尺寸的陣列(或者第一多尺寸)。單個大小統一的陣列對應於具有 較多條目的單預測器。
根據第一操作模式，示例性實施方式在選擇器750的控制下作為 竟賽預測器進行操作，其中選擇器750在配置信息780的控制下選擇 用於選擇器740的選擇源。選擇邏輯740被配置為在選擇預測器730 的控制下選擇示例性組件預測器710和720的多個預測之一。根據第 二操作模式，示例性實施方式在選擇器750的控制下作為單個大小統 一的預測器進行操作，其中選擇器750在配置信息780的控制下使用選擇器740來選擇選擇源。選擇邏輯740被配置為在輸入755的控制 下選擇多個子陣列結果之一，其中輸入755可以包括地址位、散列地
址位、線程位之一或者其他適當的尋址手^a。
現在參考圖7B,其示出了作為統一大小的單預測器或者竟賽預 測器之一的多態預測器的第二示例性讀取方法和裝置。根據該示例性 實施方式，使用多態配置信息780來將配置控制為包含第一尺寸(或 者第一多尺寸)的多個陣列的竟賽預測器，或者對應於具有較多條目 的單預測器的單個大小統一的陣列。
根據第 一操作模式，示例性實施方式作為竟賽預測器進行操作。 選擇器790從兩個示例性組件預測器710和720之一來選擇預測。選 擇器796在配置780的控制下選擇由選擇器790所生成的竟賽預測的 結果。根據第二操作模式，示例性實施方式作為單個大小統一的預測 器進行操作，在散列邏輯794所生成的地址的控制下使用選擇器792。 在該示例性邏輯794中，使用一個或多個地址位的散列功能在多個陣 列之間分布使用。具體地，由於陣列的數目不是2的指數，在使用組 件陣列作為較大邏輯陣列的子陣列時，不可能在不創建組件陣列的不
平衡使用的情況下而直接使用地址位。選擇器796在配置780的控制 下選擇子陣列選擇器792所生成的預測結果。
在示例性邏輯中，使用一個或多個地址位的散列功能794在多個 陣列之間分布使用。本領域的技術人員將會理解，可以使用選擇子陣 列的備選方法，例如，通過使用各種選擇源、級聯位串、使用各種位 的邏輯功能等，其可以用來根據本發明選擇子陣列。
在本發明的範圍內，在又一實施方式中，使用第一組件表來生成 第一位(例如方向預測位)和第二位(例如確信位)，以表示在第一 操作模式中例如使用1位預測器條目的、作為多組件預測器進行操作 的預測器，以及在第二操作模式中使用多位預測器條目(例如，雙峰 預測器)的單個統一預測器。本領域的技術人員將會理解，基於此處 的教導的範圍，另一配置機會是將具有n個組件表的第一竟賽預測器 重配置為具有邏輯上k個組件表的預測器，k<n，其中，所述k個組件表中的至少一個對應於來自n個組件表的至少兩個陣列的組合。組 件表是本領域已知的。
在多組件表預測器的示例配置中使用竟賽預測器是示例性而非 限制性的。本領域的技術人員將會進一步理解，根據時鐘門控邏輯的 定時限制，在選擇器沒有選擇組件陣列時，可以對一個或多個組件陣 列執行選擇性時鐘門控。
現在參考圖8,示出了用於多態預測器的預測器更新邏輯850， 其允許配置為多組件預測器(例如示例性竟賽預測器)或者單個統一 預測器，其對應於圖7A和圖7B中的多態讀取邏輯。預測器850包 括三個組件預測表810、 820和830。
在第一操作模式中，在多態配置780的控制下，根據用於多組件 預測器的更新規定來更新多組件預測器850的一個或多個組件預測 器。如果(在本地預測器陣列的示例性使用中)指示了針對第一預測 器陣列810的更新使能，則選擇器814在多態配置780的控制下選擇 本地預測更新(本地更新)，並且選擇器812選擇本地預測更新使能 (本地更新使能)。如果(在全局預測器陣列的示例性使用中)指示 了針對第二預測器陣列820的更新使能，則選擇器824在多態配置780 的控制下選擇全局預測更新(全局更新)，並且選擇器822選擇全局 預測更新使能(全局更新使能)。如果(在選擇預測器陣列的示例性 使用中)指示了針對第三預測器陣列820的更新使能，則選擇器834 在多態配置780的控制下選擇選擇預測更新(選擇更新)，並且選擇 器832選擇選擇預測更新使能(選擇更新使能)。
在第二操作模式中，合併陣列810、 820和830中的至少兩個， 以用作單個大陣列。根據優選實施方式，計算一個或多個散列函數840
(例如，對應於圖7B中的散列功能794),並且將其與更新使能相 結合用於大預測器配置，以便選擇至少 一個子陣列來更新較大邏輯預 測器陣列中的條目。
在第二操作模式中，選擇器814、 824、 834在多態配置信息780 的控制下從公共大預測器條目更新選擇預測器更新，並且選擇器812、
22822、 832基於所生成的散列函數和更新使能來選擇陣列寫使能信息。 本領域的技術人員將會理解，除了散列塊中的地址位，可以使用諸如 線程位之類的附加信息。此外，在本發明的範圍內，可以使用位的子 集來替代位的散列(並且根據圖7A的讀取實施方式來使用)。
參考圖9,針對根據圖7A、圖7B和圖8的多態預測器的第一操 作模式和第二操作模式，示範性地示出了具有共享更新地址計算邏輯 的示例性實施方式。根據該實施方式，通過提供附加的地址位，使用 更新地址計算邏輯950來計算用於第 一操作模式中的多組件預測器中 的全局預測器920的地址或者用於具有單個較大陣列的統 一 預測器的 更新地址二者。還可以使用這些地址位在散列邏輯940 (總體上對應 於圖8的散列功能840)的控制下來選擇單個邏輯陣列預測器的一個 或多個子陣列910、 920、 930。
多態分支預測器可以包括邏輯元件(例如，更新地址邏輯950), 使得邏輯元件在分支預測方法之間共享以提高效率。其他邏輯元件或 者組件也可以在分支預測方法之間共享，並且可以包括陣列、預測器 更新邏輯、地址生成邏輯等中的至少一個。
現在特別地參考圖IOA和圖10B,示範性地示出了用於使用多態 預測器來優化應用性能的方法。根據優選實施方式，通過軟體來實現 該功能，儘管其他實施方式也是可能的。
現在更具體地參考圖10A,方法1000優選地在編譯器中實現。 該方法開始於步驟1010。在步驟1010中，推導出用於多態預測器的 優選配置。在步驟1020中，生成代碼以選擇多態預測器的優選配置。 繼而方法終止。根據一個實施方式，該方法由編i奪器執行一次，以選 擇用於整個應用的優選配置。根據另一實施方式，該選擇執行多次， 以用於例如不同的程序階段。該選擇可以基於用戶指定的指示，諸如 命令行標誌、編譯指示(pragma)或者其他插入到程序代碼中的編譯 器指示、編譯器啟發或者程序屬性模型、以及屬性指示的反饋。
參考圖IOB，方法1050優選地在應用庫、動態編譯器、連續程 序優化模塊、固件或者微碼中實現，並且在程序運行時執行。該方法開始於步驟1060。在步驟1060中，分析應用運行時的行為。多種程 序分析技術是已知的(諸如包括但不限於配置嘗試和測試)，並且可 以與本發明結合使用。在步驟1070中，基於應用分析(或者應用階 段分析)來選擇優選配置。接著，方法終止。
根據一個實施方式，方法1050可以執行一次，以選擇用於整個 應用的優選配置。根據另一實施方式，該選擇在應用運行期間執行多 次，例如用於不同的程序階段。重新執行可以在固定的間隔處發生， 或者可以在關鍵應用量度改變(例如由性能監控基礎設置指示)時在 應用指示的(例如，通過調用動態配置選擇功能)明確的點處發生。 優選地使用提供應用統計(諸如分支執行和預測信息)的性能監控基 礎設置的支持來執行動態應用分析。
現在參考圖11, 一種用於在作業系統上下文或者管理器劃分之間 執行切換的方法1100。方法1100開始於步驟1110。在步驟1110中， 存儲用於應用或者預先調度的劃分的配置。在一個實施方式中，在對 過程或者劃分進行去調度時存儲配置。在備選實施方式中，此配置信 息在其更新時存儲，並且維護在特定於過程或者劃分的結構中。在步 驟1120，從步驟1110的預先存儲的信息中讀取用於下一過程或劃分 的配置信息，並且更新多態配置。方法終止。
工業實用性
在此公開了用於實現多態分支預測器的方法和裝置，所述多態分 支預測器可以在運行時被配置為選擇針對特定應用的結構或者算法 中的至少一個。 一種多態分支預測器，包括多個分支預測方法。所述 方法被選擇性地啟用，以執行分支預測。將選擇機制配置為根據動態 設置來選擇一個或多個分支預測方法，以便根據當前任務在操作期間 優化分支預測器的性能。每個方法可被選擇性地啟用以執行分支預 測。將選擇機制配置為根據動態設置來選擇一個或多個分支預測方 法，以便根據當前任務在操作期間優化分支預測器的性能。
已經描述了用於實現多態分支預測器的方法和裝置的優選實施方式(其意在示範而非限制)，注意，本領域的技術人員可以根據上 面的教導進行修改和變形。因此可以理解，在所附權利要求概括的本 發明的範圍和精神內，可以對所7>開的具體實施方式
進行修改。由此 描述了本發明的方面，其具有專利法要求的細節和特性，在所附權利 要求中記載了所要求和期望得到專利證書保護的內容。
權利要求
1. 一種多態分支預測器，包括多個分支預測方法，每個方法被選擇性地啟用以執行分支預測；以及選擇機制，其被配置為根據動態設置來選擇一個或多個所述分支預測方法，以便根據當前任務在操作期間優化所述分支預測器的性能。
2. 根據權利要求1所述的多態分支預測器，其中，所述設置包括性能量度。
3. 根據權利要求1所述的多態分支預測器，其中，所述選擇機制 被配置為選擇至少兩個分支預測方法，以便一起工作來提供結果。
4. 根據權利要求1所述的多態分支預測器，其中，所述選擇機制 按照事先指定，來選擇用於特定應用或者應用集的所述一個或多個分 支預測方法。
5. 根據權利要求1所述的多態分支預測器，其中，所述選擇機制 基於對運行時的行為的分析來選擇所述一個或多個分支預測方法。
6. 根據權利要求1所述的多態分支預測器，其中，所述選擇機制 被配置為從編譯器和運行時組件之一接收信息，以選擇所述一個或多 個分支預測方法。
7. 根據權利要求1所述的多態分支預測器，其中，所述選擇機制 被配置為在應用的運行時期間更新。
8. 根據權利要求1所述的多態分支預測器，其中，所述選擇機制 被配置為基於來自邏輯功能、地址位、線程指示符以及多個地址位或 線程位的散列中的至少 一個的輸出進行更新。
9. 根據權利要求1所述的多態分支預測器，進一步包括預測器條 目的陣列，其中，針對信息位的數目來配置存儲在所述陣列中的所述預測器條目。
10. 根據權利要求1所述的多態分支預測器，進一步包括預測器條目的陣列，其中，使用逐位寫使能信號和多位寫使能信號之一來允 許對所述陣列的寫操作，從而實現在所述陣列中的存儲。
11. 根據權利要求1所述的多態分支預測器，其中，每個分支預 測方法包括邏輯元件，使得所述邏輯元件在所述分支預測方法之間共 享以提高效率。
12. 根據權利要求11所述的多態分支預測器，其中，在分支預測 方法之間共享的所述邏輯元件包括陣列、預測器更新邏輯和地址生成 邏輯中的至少一個。
13. 根據權利要求1所述的多態分支預測器，進一步包括預測器 條目的陣列以及分支信息隊列，其中，使用來自所述分支信息隊列的信息來重寫先前從所述陣列讀取的信息。
14. 根據權利要求1所述的多態分支預測器，進一步包括尋址邏 輯，其被配置為在統一表和多組件預測器的表之間共享。
15. 根據權利要求1所述的多態分支預測器，進一步包括預測器 條目的多個組件陣列，其中，預測器條目由地址位選擇。
16. 根據權利要求1所述的多態分支預測器，進一步包括預測器 條目的多個組件陣列，其中，預測器條目由地址散列來選擇，以選擇 所述多個組件陣列之一。
17. —種用於動態選擇分支預測方法的方法，包括 提供多個可動態配置的分支預測方法；根據動態設置來選擇一個或多個所述分支預測方法，以便根據當 前任務在操作期間優化分支預測器的性能；以及更新所述一個或多個分支預測方法的配置，以提供改進的預測結果。
18. 根據權利要求17所述的方法，其中，選擇一個或多個所述分 支預測方法包括根據正在運行的應用、運行應用的階段、運行時的 行為以及可操作量度之一，來選擇一個或多個所述分支預測方法。
19. 根據權利要求17所述的方法，進一步包括生成程序代碼以引 起所述一個或多個分支預測方法的重配置。
20. —種電腦程式產品，包括包含計算機可讀程序的計算機可 用介質，其中，當所述計算機可讀程序在計算機上執行時，其使得所 述計算機執行權利要求19所述的步驟。
全文摘要
一種包括多個分支預測方法的多態分支預測器和方法。該方法被選擇性地啟用以執行分支預測。選擇機制被配置為根據動態設置來選擇一個或多個分支預測方法，以便根據當前任務在操作期間優化分支預測器的性能。
文檔編號G06F9/00GK101427213SQ200780013851
公開日2009年5月6日 申請日期2007年5月2日 優先權日2006年5月4日
發明者M·格施溫德 申請人:國際商業機器公司