TW201908966A - 針對固定方向分支指令的分支預測 - Google Patents

Abstract

用於對固定方向分支指令的分支預測的系統和方法涉及布隆過濾器。被採用布隆過濾器記錄正在被採用或者已經在被採用方向上解析的分支指令的實例；而不被採用布隆過濾器記錄不是正在被採用的或者已經在不被採用方向上解析的分支指令的實例。針對將被執行的分支指令，存取該被採用布隆過濾器和該不被採用布隆過濾器，並且使用該被採用布隆過濾器或者該不被採用布隆過濾器中的至少一項預測該分支指令的執行方向。

Description

針對固定方向分支指令的分支預測

所揭示的態樣針對處理系統中的分支預測。更具體而言，示例性態樣針對改良針對分支指令的分支預測，該等分支指令總是在相同的方向上解析（諸如總是被採用或者總是不被採用的分支指令）並且在本文中被稱為「固定方向」分支指令。

處理系統可以使用引起控制流程的改變的指令，諸如是有條件分支指令。有條件分支指令的方向是基於條件如何評估的，但評估可以僅是在處理器的指令流水線的深處已知的。為了避免直到評估已知之前皆使流水線暫停，處理器可以使用分支預測機制在流水線中早期地預測有條件分支指令的方向。基於預測，處理器可以推測地取回並且執行來自兩個路徑（「被採用路徑」，其在分支目標位址處開始，其中相對應的方向被稱為「被採用的方向」；或者「不被採用的」路徑，其在有條件分支指令之後的下一個順序的位址處開始，其中相對應的方向被稱為「不被採用的方向」）中的一個路徑上的所預測的位址的指令。

在條件被評估並且實際的分支方向被決定時，若分支被誤預測（亦即，遵循錯誤的路徑的執行），則可以從流水線中沖掉被推測地取回的指令，並且可以從正確的下一個位址取回正確的路徑上的新指令。相應地，改良針對有條件分支指令的分支預測的準確度減輕與誤預測和對錯誤路徑指令的執行相關聯的損失，並且對應地改良處理系統的效能和能量利用。

習知的分支預測機制可以包括一或多個狀態機，可以利用過去的和當前的分支指令的評估歷史來對該一或多個狀態機進行訓練。但該等分支預測機制在一些場景中可能未能準確地預測分支指令的方向。此外，在誤預測發生時，為分支預測花費的能量和資源亦是浪費的。

具體而言，對於其分支行為可以保持不變的一些分支指令，可以認為與複雜的分支預測機制相關聯的能量花費是浪費的。例如，一些分支指令每當其被執行時，可以在相同的方向（被採用或者不被採用）上解析。在本案內容中，此種分支指令被稱為「相同方向」或者「固定方向」分支指令。然而，習知的分支預測機制不為此種固定方向分支指令辨識或者提供特殊考慮。此外，在一些情況下，習知的分支預測機制亦可以誤預測固定方向分支指令。

因此，存在對於改良習知的分支預測機制的能耗、效率和預測準確度的需求。

本發明的示例性態樣針對用於分支預測的系統和方法。在本案內容中，固定方向分支指令指總是在相同的方向上解析的（總是被採用的或者總是不被採用的）分支指令。對於此種固定方向分支指令，示例性布隆過濾器（Bloom Filter）被配置為辨識並且實現對該分支方向的高效的預測。該布隆過濾器可以包括可以被索引的資料結構。在一個實例中，一種示例性布隆過濾器可以包括位元的陣列（例如，暫存器或者類似的記憶體元件），其中可以使用分支指令的分支程式計數器（PC）值對該等位元進行索引。若在被對應地索引的位置處存在針對分支指令的位於布隆過濾器中的命中條目（例如，位元集），此情形表示該布隆過濾器已經記錄該分支指令的歷史。更具體而言，被採用布隆過濾器記錄正在被採用或者已經在被採用方向上解析的分支指令的實例；而不被採用布隆過濾器記錄不是正在被採用的或者已經在不被採用方向上解析的分支指令的實例。若對於分支指令，在僅一個而非全部兩個布隆過濾器中存在命中條目，則認為此情形傳達該分支指令是具有與在其中存在命中條目的該布隆過濾器相對應的方向的固定方向分支指令，並且相應地預測該分支指令的該方向。

例如，一個示例性態樣針對一種分支預測的方法。該方法包括以下步驟：針對將被執行的分支指令，存取被採用布隆過濾器和不被採用布隆過濾器，其中該被採用布隆過濾器包括已經在被採用方向上解析至少一次的分支指令的記錄，並且該不被採用布隆過濾器包括已經在不被採用方向上解析至少一次的分支指令的記錄；及使用該被採用布隆過濾器和該不被採用布隆過濾器中的至少一項來預測該分支指令的執行方向。

另一個示例性態樣針對一種裝置，該裝置包括被配置為執行分支指令的處理器。該處理器包括：被採用布隆過濾器，其包括已經在被採用的方向上解析至少一次的分支指令的記錄；不被採用布隆過濾器，其包括已經在不被採用的方向上解析至少一次的分支指令的記錄；及邏輯單元，其被配置為基於該被採用布隆過濾器或者該不被採用布隆過濾器中的至少一項來預測分支指令的執行方向。

又另一個示例性態樣針對一種包括代碼的非暫時性電腦可讀取儲存媒體，該代碼在被電腦執行時使該電腦執行用於分支預測的操作。該非暫時性電腦可讀取儲存媒體包括：針對將被執行的分支指令，用於存取被採用布隆過濾器和不被採用布隆過濾器的代碼，其中該被採用布隆過濾器包括已經在被採用方向上解析至少一次的分支指令的記錄，並且該不被採用布隆過濾器包括已經在不被採用的方向上解析至少一次的分支指令的記錄；及用於使用該被採用布隆過濾器和該不被採用布隆過濾器中的至少一項來預測該分支指令的執行方向的代碼。

又另一個示例性態樣針對一種裝置，該裝置包括：用於執行分支指令的構件；第一構件，其用於記錄已經在被採用的方向上解析至少一次的分支指令；第二構件，其用於記錄已經在不被採用的方向上解析至少一次的分支指令；及用於基於該第一構件或者該第二構件中的至少一項來預測分支指令的執行方向的構件。

在針對本發明的具體的態樣的以下描述內容和相關附圖中揭示本發明的態樣。可以設想替換的態樣，而不脫離本發明的範疇。額外地，本發明的公知的元素將不被詳細地描述或者將被省略，以便不使本發明的相關的細節模糊不清。

術語「示例性」在本文中被用於表示「充當示例、實例或者說明」。任何在本文中被描述為「示例性」的態樣不必被解釋為是較佳的或者比其他的態樣有利的。同樣地，術語「本發明的態樣」不要求本發明的全部態樣包括所論述的特徵、優點或者操作模式。

本文中使用的術語僅是出於描述具體的態樣的目的的，而不意欲作為對本發明的態樣的限制。如本文中使用的，除非上下文清楚地另外指出，否則單數形式「一」、「一個」和「該」意欲亦包括複數形式。應當進一步理解，術語「包括（comprises）」、「包括（comprising）」、「包含（includes）」及/或「包含（including）」在被用在本文中時指定所指出的特徵、整數、步驟、操作、元素及/或部件的出現，而不排除一或多個其他的特徵、整數、步驟、操作、元素、部件及/或其群組的存在或者添加。

進一步地，根據將由例如計算設備的元件執行的動作的序列描述了許多態樣。應當認識到，本文中描述的各種動作可以由具體的電路（例如，特殊應用積體電路（ASIC））、由被一或多個處理器執行的程式指令或者由該兩者的組合被執行。額外地，本文中描述的動作的該等序列可以被看作是全部在任何形式的電腦可讀取儲存媒體內被體現的，該電腦可讀取儲存媒體具有儲存在其中的相對應的電腦指令集，該電腦指令集在執行之後將使相關聯的處理器執行本文中描述的功能。因此，本發明的各種態樣可以以一些不同的形式被體現，此種形式中的全部形式已經被設想為落在所主張保護的標的的範疇內。另外，對於本文中描述的態樣之每一者態樣，任何此種態樣的相對應的形式在本文中可以被描述為例如「被配置為」執行所描述的動作的「邏輯單元」。

本案內容的示例性態樣針對改良分支預測效率、準確度和能耗。具體而言，在本案內容中，考慮固定方向分支指令，該等固定方向分支指令如之前提到的一般是總是在相同的方向上解析（總是被採用或者總是不被採用）的分支指令。對於此種固定方向分支指令，揭示諸如是布隆過濾器此種示例性設計，其被配置為辨識並且實現對分支方向的高效預測。

在本案內容中，布隆過濾器可以包括可以被索引的資料結構。在一個實例中，一種示例性布隆過濾器可以包括位元的陣列（例如，暫存器或者類似的記憶體元件），其中可以使用分支指令的分支程式計數器（PC）值對位元進行索引。若在相對應地被索引的位置處存在針對分支指令的位於布隆過濾器中的命中條目（例如，位元集），則此情形表示布隆過濾器已經記錄了該分支指令的歷史。更具體而言，被採用布隆過濾器記錄正在被採用或者已經在被採用的方向上解析的分支指令的實例；而不被採用布隆過濾器記錄不是正在被採用的或者已經在不被採用的方向上解析的分支指令的實例。若對於分支指令，在僅一個而非全部兩個布隆過濾器中存在命中條目，則認為此情形傳達分支指令是固定方向分支指令。

固定方向分支指令的執行方向是從在其中存在命中條目的布隆過濾器中被匯出的（亦即，若僅在被採用布隆過濾器中存在命中，則分支指令是總是被採用的；或者類似地，若僅在不被採用布隆過濾器中存在命中，則分支指令是總是不被採用的）。對於此種固定方向分支指令，繞過習知的分支預測機制。如此，對於固定方向分支指令獲得準確的預測，並且避免習知的分支預測機制的能耗和不準確性。

亦應當認識到，本案內容的態樣可以被擴展到其解析度可以與如上文論述的固定方向偏離相對少的或者微不足道的次數的分支指令。例如，亦揭示布隆過濾器的替換的結構，其可以被用於獲得對「幾乎總是」（例如，多於99%的時間）被採用或者不被採用的分支指令的預測。例如，上文提到的布隆過濾器可以替換地使用計數器（而非單個位元）的陣列來實現，其中可以使用分支指令的PC對計數器進行索引。在經索引的位置處，用於相對應的分支指令的計數器若存在（亦即，命中條目中存在計數器），則可以提供分別關於該分支指令在被採用的方向上解析（在被採用布隆過濾器的情況下）多少次或者分支指令在不被採用的方向上解析（在不被採用布隆過濾器的情況下）多少次的資訊。因此，對於分支指令，可以經由讀取用於分支指令的被採用布隆過濾器和不被採用布隆過濾器兩者來決定分支指令被採用的次數和分支指令不被採用的次數。可以對該等數量進行比較，或者可以決定分支指令被採用或者不被採用的次數的比例（例如，作為被獲得為兩個計數值的和的分支指令的實例的總數的百分比）。若分支被採用的次數的比例非常高（例如，大於99%的閾值），則分支指令可以被預測為被採用；或者，若分支不被採用的次數的比例非常高（例如，大於99%的閾值），則分支指令可以被預測為不被採用。

現在參考圖1，圖示可以在其中使用本案內容的態樣的一個示例性處理系統100。處理系統100被示為包括被耦合到指令快取記憶體108的處理器110。儘管未在該視圖中圖示，但諸如是功能單元、輸入/輸出單元、介面結構、記憶體結構等此種額外的部件亦可以存在，但由於該等額外的部件可以不是與本案內容有關的而亦未被明確地辨識或者描述。如所示的，處理器110可以被配置為從指令快取記憶體108接收指令，並且使用例如執行流水線112來執行指令。如本領域中已知的，執行流水線112可以被配置為包括諸如是指令取回、解碼、執行、寫回等此種一或多個流水線化的階段。有代表性地，分支指令在指令快取記憶體108中被圖示，並且被辨識為指令102。

在一種示例性實現中，分支指令102可以具有相對應的位址或者為102pc的程式計數器（PC）值。處理器110被概括地示為包括分支預測機制106，如本領域中已知的，該分支預測機制106可以進一步包括諸如是包括在先的分支指令的行為的歷史的歷史表此種分支預測單元、諸如是分支預測計數器/雙峰預測器此種狀態機等。在分支102由處理器110取回以便進行執行時，諸如是散列104（例如，實現XOR功能）此種邏輯單元可以利用位址或者PC值102pc及/或來自分支指令102的其他的資訊存取分支預測機制並且對預測107進行檢索，該預測107代表對分支指令102的預測（亦被稱為動態預測）。

在示例性態樣中，處理器110亦包括布隆過濾器120，將參考圖2進一步描述該布隆過濾器120的一種示例性實現。布隆過濾器120可以經由例如分支指令102的PC值102pc來被索引，並且為固定方向分支指令或者具有關於被採用/不被採用的強統計偏差的分支指令提供方向122（例如，被採用/不被採用）。可以從布隆過濾器120獲得其方向122的分支指令可以在與方向122相對應的方向（被採用或者不被採用）上被執行，而忽略由分支預測機制106提供的預測107。在一種實現中，若方向122是從用於具體的分支指令的布隆過濾器120可得的，則可以避免或者忽略來自分支預測機制106的預測107，並且進一步地，可以對於該分支指令關斷分支預測機制106或者使分支預測機制106掉電，此舉可以導致固定方向分支指令的情況下的能量節省。

繼續對圖1的描述，分支指令102可以在執行流水線112中被推測地執行（基於從預測107匯出的方向或者方向122）。在遍歷一或多個流水線狀態之後，對分支指令102的實際的評估將是已知的，並且該評估被示為評估113。在預測檢查方塊114中將評估113與預測107進行比較，以決定評估113與預測107相匹配（亦即，分支指令102是被正確地預測的）還是與預測107不匹配（亦即，分支指令102是被誤預測的）。在一種示例性實現中，匯流排115包括資訊，該等資訊包括正確的評估113（被採用/不被採用）以及分支指令102是被正確地預測的還是被誤預測的。可以將匯流排115上的資訊提供給布隆過濾器120。

現在結合圖1參考圖2，說明布隆過濾器120的一種示例性實現。在由處理器110執行的一些示例性指令串流中，可以存在一些總是被採用或者總是不被採用的固定方向分支指令。由於使用分支預測機制106對此種固定方向分支指令進行預測可能不是能量/功率高效的，並且此外，預測107可能是不正確的（亦即，不與固定方向分支指令的方向對準），所以對於此種固定方向分支指令，可以作為代替使用布隆過濾器120。更具體而言，布隆過濾器120可以包括兩個部件布隆過濾器：被採用布隆過濾器202和不被採用布隆過濾器204。布隆過濾器120被配置為根據將在以下部分中被描述的示例性態樣使用被採用布隆過濾器202或者不被採用布隆過濾器204中的至少一項來預測分支指令的執行方向。此外，在一些態樣中，布隆過濾器120可以包括被配置為基於被採用布隆過濾器202或者不被採用布隆過濾器204中的至少一項來預測分支指令的推測性的執行的方向的相對應的邏輯單元，此情形亦是可能的（儘管應當理解，此種邏輯單元將在處理系統100內的其他地方或者具體而言在處理器110內被提供）。

如之前論述的，布隆過濾器、被採用布隆過濾器202和不被採用布隆過濾器204可以包括可以被索引的資料結構。例如，被採用布隆過濾器202和不被採用布隆過濾器204可以各自包括位元的陣列（例如，暫存器或者類似的記憶體元件），其中可以使用分支指令的分支程式計數器（PC）值對位元進行索引。例如，在圖2中，條目203可以代表可以與總是被採用分支指令相對應的被採用布隆過濾器202的一個位元，並且可以是位於經由總是被採用分支指令的PC進行索引的位置處的。類似地，條目205可以代表可以與總是不被採用分支指令相對應的不被採用布隆過濾器204的一個位元，並且可以是位於經由總是不被採用分支指令的PC進行索引的位置處的。

在一種實現中，若在相對應地被索引的位置處存在用於分支指令的分別的布隆過濾器202/204的條目203/205，則此情形表示相對應的布隆過濾器202/204已經記錄了該分支指令的歷史。若針對分支指令的此種條目203/205存在於相對應的布隆過濾器202/204中，則此種情況被稱為命中，並且條目被稱為命中條目。更詳細而言，被採用布隆過濾器202記錄正在被採用的分支指令的實例，而不被採用布隆過濾器204記錄不是正在被採用的分支指令的實例。若對於分支指令，在僅一個而非全部兩個布隆過濾器中存在命中條目，則認為此種情況傳達分支指令是固定方向分支指令。

從在其中存在命中的布隆過濾器匯出固定方向分支指令的執行方向（亦即，若僅在被採用布隆過濾器中存在命中，則分支指令是總是被採用的；或者類似地，若僅在不被採用布隆過濾器中存在命中，則分支指令是總是不被採用的）。被採用布隆過濾器202可以被配置為擷取或者記錄總是被採用的固定方向分支指令的程式計數器（PC）值，並且不被採用布隆過濾器204可以被用於記錄總是不被採用分支指令的PC值。在各種實現中，被採用布隆過濾器202和不被採用布隆過濾器204可以是具有不同的大小的，例如，被採用布隆過濾器202可以是比不被採用布隆過濾器204大的或者具有比其多的條目。

在一種實現中，在諸如是分支指令102此種分支指令被取回時，其相關聯的分支PC 102pc被用於對布隆過濾器120的被採用布隆過濾器202和不被採用布隆過濾器204兩者進行索引。在以此種方式對布隆過濾器120進行存取時，兩種場景可以產生。

在第一場景中，可以在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在命中（亦即，可以在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在位於使用分支PC 102pc被索引的位置處的被設置為例如值「1」的命中條目），或者在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在未命中（亦即，可以在被採用布隆過濾器202和不被採用布隆過濾器204兩者中不存在位於使用分支PC 102pc被索引的位置處的命中條目）。若對於分支指令102的分支PC 102pc，在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在命中，則此情形表示分支指令102可能已經被採用至少一次並且不被採用至少一次，並且因此，分支指令102將不是總是被採用或者總是不被採用的固定方向分支指令。若在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在未命中，則此情形表示布隆過濾器120中不存在用於分支指令102的足夠的資訊。因此，在該兩種情況下，為了為分支指令102提供方向，可以不依賴於布隆過濾器120。作為代替，可以諮詢分支預測機制106以獲得對於對分支指令102的推測性的執行的預測107。

在一個態樣中，若對於分支指令102，在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在命中，則相對應的命中條目在被採用布隆過濾器202和不被採用布隆過濾器204兩者中被重置，此舉實現使布隆過濾器120的實現調適於程式的階段的改變（例如，分支指令102在一個程式階段中可以具有固定方向分支指令的行為，而在不同的程式階段中，分支指令102可以有時被採用並且有時不被採用）。在另一個態樣中，例如可以以定期的方式（例如，每1百萬條指令或者10千個處理器週期地）重置被採用布隆過濾器202和不被採用布隆過濾器204兩者中的位於相同的位置處的條目。在另一個態樣中，可以監視在被採用布隆過濾器202和不被採用布隆過濾器204兩者中被設置的條目的數量，並且例如若該等被設置的條目（在條目的總數中）的比例超過預先指定的閾值數量，則或者被採用布隆過濾器202和不被採用布隆過濾器204兩者可以被完全重置，或者被採用布隆過濾器202和不被採用布隆過濾器204兩者中的相同的位置（其可以是被隨機地選擇的）可以被重置。

第二場景涉及對於分支指令102在兩個布隆過濾器中的僅一個布隆過濾器中的命中：或者被採用布隆過濾器202，或者不被採用布隆過濾器204。在此種情況下，僅其中存在命中的被採用布隆過濾器202或者不被採用布隆過濾器204具有分支指令102的關於其在處理器110中的執行的歷史的記錄。相對應地，基於在其中存在命中的布隆過濾器設置方向122，並且取代預測107而使用方向122（在於兩個布隆過濾器202或者204中的僅一個布隆過濾器中存在命中時，分支預測機制106可以被使得掉電或者關斷以節省能量）。例如，若在被採用布隆過濾器202中存在命中，則分支指令102的方向可以被設置為被採用。另一態樣，若在不被採用布隆過濾器204中存在命中，則分支指令102的方向可以被設置為不被採用。

在另一種實現中，布隆過濾器120的條目（例如，被採用布隆過濾器202的條目203和不被採用布隆過濾器204的條目205）可以包括用於對在其中分別的分支指令在相對應的方向上解析的實例的數量進行計數的計數器（例如，2位元或者更多位元的）。例如，條目203可以包括被採用計數器，被採用計數器追蹤具有索引到條目203的PC的分支指令被採用的次數。類似地，條目205可以包括不被採用計數器，該不被採用計數器追蹤具有索引到條目205的PC的分支指令不被採用的次數。在此種實現中，可以對幾乎總是在相同的方向上解析的分支指令或者可以具有與固定方向的微不足道的或者相當小的偏離的固定方向分支指令進行追蹤，並且預測其方向。因此，在此種實現中，相同的分支指令可以在被採用布隆過濾器202以及不被採用布隆過濾器204兩者中具有條目，並且使用布隆過濾器120被預測。

詳細而言，可以經由存取位於經由分支指令的PC進行索引的相對應的位置處的被採用布隆過濾器202和不被採用布隆過濾器204的條目而獲得被採用計數器和不被採用計數器的值。若在被採用布隆過濾器202和不被採用布隆過濾器204兩者中存在命中條目，則對來自該等分別的命中條目的被採用計數器和不被採用計數器的相對應的值進行比較。或者，可以將被採用計數器的比例與被採用計數器和不被採用計數器的值的和進行比較以獲得分支指令被採用的次數的被採用百分比。或者，可以類似地計算分支指令不被採用的次數的不被採用百分比。若被採用百分比是充分高的，例如，大於為99%的閾值百分比，則分支指令可以被預測為被採用。另一態樣，若不被採用百分比是充分高的，例如，大於為99%的閾值百分比，則分支指令可以被預測為不被採用。此種具有一個方向上的實質偏差的分支指令可以被稱為充分固定方向分支指令。相應地，在布隆過濾器120的替換的實現中，經由使用計數器而非單個位元，亦可以預測充分固定方向分支指令的方向。

相應地應當認識到，示例性態樣包括用於執行本文中揭示的程序、功能及/或演算法的各種方法。例如，圖3圖示分支預測的方法300。

在方塊302中，方法300包括以下步驟：對於將被推測地執行的分支指令，存取被採用布隆過濾器和不被採用布隆過濾器，其中被採用布隆過濾器包括已經在被採用方向上解析至少一次的分支指令的記錄，並且不被採用布隆過濾器包括已經在不被採用方向上解析至少一次的分支指令的記錄（例如，使用針對分支指令102的分支PC 102pc對被採用布隆過濾器202和不被採用布隆過濾器204進行索引）。

方塊304包括：使用被採用布隆過濾器或者不被採用布隆過濾器中的至少一項預測分支指令的執行方向（例如，基於在僅被採用布隆過濾器202還是不被採用布隆過濾器204中存在命中，將分支指令102預測為總是被採用的固定方向分支指令或者總是不被採用的固定方向分支指令）。

此外，本案內容的示例性態樣亦針對包括用於執行本文中描述的功能的構件的系統。例如，一種示例性裝置（例如，處理系統100）包括：用於執行分支指令的構件（例如，處理器110，或者更具體而言，執行流水線112）。因此，裝置可以包括：用於記錄已經在被採用方向上解析至少一次的分支指令的第一構件（例如，被採用布隆過濾器202）和用於記錄已經在不被採用方向上解析至少一次的分支指令的第二構件（例如，不被採用布隆過濾器204）。裝置可以亦包括：用於基於第一構件或者第二構件中的至少一項（例如，布隆過濾器120）預測分支指令的執行方向的構件。

現在將就圖4論述可以在其中利用本案內容的示例性態樣的另一種示例性裝置。圖4圖示計算設備400的方塊圖。計算設備400可以與圖1的處理系統100的一種示例性實現相對應，其中處理器110可以被配置為執行圖3的方法300。在圖4的圖示中，計算設備400被示為包括處理器110，為了清楚起見，處理器110具有從圖1複製的僅有限的細節（包括布隆過濾器120、分支預測機制106、執行流水線112和預測檢查方塊114）。應當指出，在圖4中，處理器110被示例性地示為是被耦合到記憶體432的，並且應當理解，諸如是快取記憶體108此種本領域中已知的其他的記憶體配置還未被圖示，但是該等其他的記憶體配置可以出現在計算設備400中。

圖4亦圖示被耦合到處理器110和顯示器428的顯示器控制器426。在一些情況下，計算設備400可以被用於無線通訊，並且圖4亦用虛線圖示可選的方塊，諸如被耦合到處理器110的編碼器/解碼器（轉碼器）434（例如，音訊及/或語音轉碼器），並且揚聲器436和麥克風438可以被耦合到轉碼器434；及被耦合到無線控制器440的無線天線442，無線控制器440被耦合到處理器110。在該等可選的方塊中的一或多個方塊存在的情況下，在一個具體的態樣中，處理器110、顯示器控制器426、記憶體432和無線控制器440被包括在系統級封裝或者晶片上系統設備422中。

相應地，一個具體的態樣，輸入設備430和電源444被耦合到晶片上系統設備422。此外，在一個具體的態樣中，如圖4中圖示的，在一或多個可選的方塊出現的情況下，顯示器428、輸入設備430、揚聲器436、麥克風438、無線天線442和電源444是位於晶片上系統設備422的外部的。然而，顯示器428、輸入設備430、揚聲器436、麥克風438、無線天線442和電源444中的每項可以被耦合到晶片上系統設備422的一個部件（諸如介面或者控制器）。

應當指出，儘管圖4概括地圖示了計算設備，但處理器110和記憶體432亦可以被整合在機上盒、伺服器、音樂播放機、視訊播放機、娛樂單元、導航設備、個人數位助理（PDA）、固定位置資料單元、電腦、膝上型電腦、平板型電腦、通訊設備、行動電話或者其他類似的設備中。

熟習此項技術者將認識到，可以使用多種不同的技術和製程中的任何技術和製程代表資訊和信號。例如，可以由電壓、電流、電磁波、磁場或者粒子、光場或者粒子或者其任意組合代表可以貫穿上文描述內容被引用的資料、指令、命令、資訊、信號、位元、符號和碼片。

進一步地，熟習此項技術者應當認識到，結合本文中揭示的態樣描述的各種說明性的邏輯方塊、模組、電路和演算法步驟可以被實現為電子硬體、電腦軟體或者該兩者的組合。為了清楚地說明硬體與軟體的該可互換性，已經在上文概括地按照其功能描述了各種說明性的部件、方塊、模組、電路和步驟。此種功能被實現為硬體還是軟體取決於具體的應用和被強加於整體系統的設計約束。技術者可以針對每個具體的應用以不同的方式實現所描述的功能，但此種實現決策不應當被解釋為導致脫離本發明的範疇。

結合本文中揭示的態樣描述的方法、序列及/或演算法可以直接地用硬體、用被處理器執行的軟體模組或者用該兩者的組合來體現。軟體模組可以常駐在RAM記憶體、快閃記憶體、ROM記憶體、EPROM記憶體、EEPROM記憶體、暫存器、硬碟、可移除磁碟、CD-ROM或者本領域中已知的任何其他形式的儲存媒體中。一種示例性儲存媒體被耦合到處理器以使得處理器可以從儲存媒體讀資訊和向儲存媒體寫資訊。或者，儲存媒體可以是處理器的組成部分。

相應地，本發明的一個態樣可以包括一種體現用於對固定方向分支指令的分支預測的方法的電腦可讀取媒體。相應地，本發明不限於所說明的實例，並且任何用於執行本文中描述的功能的構件被包括在本發明的態樣中。

儘管前述揭示內容圖示本發明的說明性的態樣，但應當指出，可以在本文中作出各種改變和修改，而不會脫離如由所附請求項定義的本發明的範疇。根據本文中描述的本發明的態樣的方法請求項的功能、步驟及/或動作不需要按照任何具體的次序被執行。此外，儘管可以以單數形式描述或者主張保護本發明的元素，但除非明確地指出了限於單數，否則亦設想了複數。

100‧‧‧處理系統

102‧‧‧分支指令

102pc‧‧‧分支指令的程式計數器（PC）

104‧‧‧散列

106‧‧‧分支預測機制

107‧‧‧預測

108‧‧‧快取記憶體

110‧‧‧處理器

112‧‧‧執行流水線

113‧‧‧評估

114‧‧‧預測檢查方塊

115‧‧‧匯流排

120‧‧‧布隆過濾器

122‧‧‧方向

202‧‧‧被採用布隆過濾器

203、205‧‧‧條目

204‧‧‧不被採用布隆過濾器

300‧‧‧方法

302、304‧‧‧方塊

400‧‧‧計算設備

422‧‧‧晶片上系統設備

426‧‧‧顯示器控制器

428‧‧‧顯示器

430‧‧‧輸入設備

432‧‧‧記憶體

434‧‧‧轉碼器

436‧‧‧揚聲器

438‧‧‧麥克風

440‧‧‧無線控制器

442‧‧‧無線天線

444‧‧‧電源

附圖是為了輔助對本發明的態樣的描述被提供的，並且僅是為了對態樣的說明而非對其的限制被提供的。

圖1圖示根據本案內容的態樣的處理系統。

圖2圖示根據本案內容的態樣的布隆過濾器。

圖3圖示與根據本案內容的態樣的一種示例性方法有關的事件的序列。

圖4圖示了可以在其中有利地使用本案內容的態樣的一種示例性計算設備。

Claims (30)

1. 一種分支預測的方法，該方法包括以下步驟： 針對將被執行的一分支指令，存取一被採用布隆過濾器和一不被採用布隆過濾器，其中該被採用布隆過濾器包括對已經在一被採用方向上解析至少一次的分支指令的一記錄，並且該不被採用布隆過濾器包括對已經在一不被採用方向上解析至少一次的分支指令的一記錄；及使用該被採用布隆過濾器和該不被採用布隆過濾器中的至少一項來預測該分支指令的一執行方向。
2. 根據請求項1之方法，包括以下步驟：若對於該分支指令，在該被採用布隆過濾器或者該不被採用布隆過濾器中的僅一項中存在一命中，則使用該被採用布隆過濾器或者該不被採用布隆過濾器中的至少一項來預測該分支指令的該執行方向， 其中若在該被採用布隆過濾器中存在一命中，則該被採用布隆過濾器包括位於經由該分支指令的一程式計數器（PC）進行索引的一位置處的一條目，並且若在該不被採用布隆過濾器中存在一命中，則該不被採用布隆過濾器包括位於經由該分支指令的一程式計數器（PC）進行索引的一位置處的一條目。
3. 根據請求項2之方法，包括以下步驟：若在僅該被採用布隆過濾器中而不在該不被採用布隆過濾器中存在一命中，則將該分支指令的該執行方向預測為被採用，其中該分支指令是一總是被採用分支指令。
4. 根據請求項2之方法，包括以下步驟：若在僅該不被採用布隆過濾器中而不在該被採用布隆過濾器中存在一命中，則將該分支指令的該執行方向預測為不被採用，其中該分支指令是一總是不被採用分支指令。
5. 根據請求項2之方法，包括以下步驟：若在該被採用布隆過濾器或者該不被採用布隆過濾器中的僅一項中存在該命中，則忽略包括一狀態機和分支歷史的一分支預測機制。
6. 根據請求項5之方法，亦包括以下步驟：關斷該分支預測機制或者使該分支預測機制掉電。
7. 根據請求項2之方法，包括以下步驟：若在該被採用布隆過濾器和該不被採用布隆過濾器兩者中存在一命中，或者若在該被採用布隆過濾器和該不被採用布隆過濾器兩者中存在一未命中，則基於由包括一狀態機和分支歷史的一分支預測機制提供的一預測來推測地執行該分支指令。
8. 根據請求項7之方法，亦包括以下步驟：若在該被採用布隆過濾器和該不被採用布隆過濾器兩者中存在一命中，則重置該被採用布隆過濾器和該不被採用布隆過濾器兩者中的該命中條目。
9. 根據請求項1之方法，其中該被採用布隆過濾器的每個條目包括用於對該被採用布隆過濾器的該條目進行索引的一相對應的分支指令在一被採用方向上被解析的實例的一數量進行計數的一被採用計數器，並且其中該不被採用布隆過濾器的每個條目包括用於對該不被採用布隆過濾器的該條目進行索引的一相對應的分支指令在一不被採用方向上被解析的實例的一數量進行計數的一不被採用計數器，並且其中預測該分支指令的該方向是基於該分支指令的被採用計數器和該不被採用計數器的值的。
10. 根據請求項9之方法，包括以下步驟：若該被採用計數器的該值充分地大於該不被採用計數器的該值，則將該分支指令的該方向預測為被採用。
11. 根據請求項9之方法，包括以下步驟：若該不被採用計數器的該值充分大於該被採用計數器的該值，則將該分支指令的該方向預測為不被採用。
12. 根據請求項1之方法，其中該被採用布隆過濾器是比該不被採用布隆過濾器大的或者具有較多的條目的。
13. 一種裝置，包括： 被配置為執行分支指令的一處理器，其中該處理器包括：一被採用布隆過濾器，其包括對已經在一被採用方向上解析至少一次的分支指令的一記錄；一不被採用布隆過濾器，其包括對已經在一不被採用方向上解析至少一次的分支指令的一記錄；及邏輯單元，其被配置為基於該被採用布隆過濾器或者該不被採用布隆過濾器中的至少一項預測一分支指令的一執行方向。
14. 根據請求項13之裝置，其中該邏輯單元亦被配置為若對於該分支指令，在該被採用布隆過濾器或者該不被採用布隆過濾器中的僅一項中存在一命中，則基於該被採用布隆過濾器或者該不被採用布隆過濾器中的至少一項來預測該分支指令的該執行方向， 其中若在該被採用布隆過濾器中存在一命中，則該被採用布隆過濾器包括位於經由該分支指令的一程式計數器（PC）進行索引的一位置處的一條目，並且若在該不被採用布隆過濾器中存在一命中，則該不被採用布隆過濾器包括位於經由該分支指令的一程式計數器（PC）進行索引的一位置處的一條目。
15. 根據請求項14之裝置，其中該邏輯單元亦被配置為若在僅該被採用布隆過濾器中而不在該不被採用布隆過濾器中存在一命中，則將該分支指令的該執行方向預測為被採用，其中該分支指令是一總是被採用分支指令。
16. 根據請求項14之裝置，其中該邏輯單元亦被配置為若在僅該不被採用布隆過濾器中而不在該被採用布隆過濾器中存在一命中，則將該分支指令的該執行方向預測為不被採用，其中該分支指令是一總是不被採用分支指令。
17. 根據請求項14之裝置，其中該處理器亦包括一分支預測機制，該分支預測機制包括一狀態機和分支歷史，其中若在該被採用布隆過濾器或者該不被採用布隆過濾器中的僅一項中存在該命中，則由該分支預測機制作出的一預測被忽略。
18. 根據請求項17之裝置，其中該分支預測機制是被關斷或者被掉電的。
19. 根據請求項17之裝置，其中若在該被採用布隆過濾器和該不被採用布隆過濾器兩者中存在一命中，或者若在該被採用布隆過濾器和該不被採用布隆過濾器兩者中存在一未命中，則該分支指令是基於由一分支預測機制提供的一預測來推測地執行的。
20. 根據請求項19之裝置，其中若在該被採用布隆過濾器和該不被採用布隆過濾器兩者中存在一命中，則該命中條目被配置為在該被採用布隆過濾器和該不被採用布隆過濾器兩者中被重置。
21. 根據請求項12之裝置，其中該被採用布隆過濾器的每個條目包括被配置為對該被採用布隆過濾器的該條目進行索引的一相對應的分支指令在一被採用方向上被解析的實例的一數量進行計數的一被採用計數器，並且其中該不被採用布隆過濾器的每個條目包括被配置為對該不被採用布隆過濾器的該條目進行索引的一相對應的分支指令在一不被採用方向上被解析的實例的一數量進行計數的一不被採用計數器，並且其中該邏輯單元亦被配置為基於該分支指令的被採用計數器和該不被採用計數器的值來預測該分支指令的該方向。
22. 根據請求項21之裝置，其中該邏輯單元亦被配置為若該被採用計數器的該值充分地大於該不被採用計數器的該值，則將該分支指令的該方向預測為被採用。
23. 根據請求項21之裝置，其中該邏輯單元被配置為若該不被採用計數器的該值充分大於該被採用計數器的該值，則將該分支指令的該方向預測為不被採用。
24. 根據請求項12之裝置，其中該被採用布隆過濾器是比該不被採用布隆過濾器大的或者具有較多的條目的。
25. 根據請求項12之裝置，其被整合在從以下各項組成的該群組中選出的一設備中：一機上盒、一伺服器、一音樂播放機、一視訊播放機、一娛樂單元、一導航設備、一個人數位助理（PDA）、一固定位置資料單元、一電腦、一膝上型電腦、一平板型電腦、一通訊設備和一行動電話。
26. 一種包括代碼的非暫時性電腦可讀取儲存媒體，該代碼在被一電腦執行時使該電腦執行用於分支預測的操作，該非暫時性電腦可讀取儲存媒體包括： 針對將被執行的一分支指令，用於存取一被採用布隆過濾器和一不被採用布隆過濾器的代碼，其中該被採用布隆過濾器包括對已經在一被採用方向上解析至少一次的分支指令的一記錄，並且該不被採用布隆過濾器包括對已經在一不被採用方向上解析至少一次的分支指令的一記錄；及用於使用該被採用布隆過濾器和該不被採用布隆過濾器中的至少一項來預測該分支指令的一執行方向的代碼。
27. 根據請求項26之非暫時性電腦可讀取儲存媒體，包括：用於若對於該分支指令，在該被採用布隆過濾器或者該不被採用布隆過濾器中的僅一項中存在一命中，則使用該被採用布隆過濾器或者該不被採用布隆過濾器中的至少一項來預測該分支指令的該執行方向的代碼， 其中若在該被採用布隆過濾器中存在一命中，則該被採用布隆過濾器包括位於由該分支指令的一程式計數器（PC）索引的一位置處的一條目，並且若在該不被採用布隆過濾器中存在一命中，則該不被採用布隆過濾器包括位於由該分支指令的一程式計數器（PC）索引的一位置處的一條目。
28. 根據請求項27之非暫時性電腦可讀取儲存媒體，包括：用於若僅在該被採用布隆過濾器中而不在該不被採用布隆過濾器中存在一命中，則將該分支指令的該執行方向預測為被採用的代碼，其中該分支指令是一總是被採用分支指令。
29. 根據請求項27之非暫時性電腦可讀取儲存媒體，包括：用於若僅在該不被採用布隆過濾器中而不在該被採用布隆過濾器中存在一命中，則將該分支指令的該執行方向預測為不被採用的代碼，其中該分支指令是一總是不被採用分支指令。
30. 一種裝置，包括： 用於執行分支指令的構件；一第一構件，其用於記錄已經在一被採用方向上解析至少一次的分支指令；一第二構件，其用於記錄已經在一不被採用方向上解析至少一次的分支指令；及用於基於該第一構件或者該第二構件中的至少一項來預測一分支指令的一執行方向的構件。