滑動窗口、基於區塊的分支目標地址高速緩衝存儲器的製作方法
2023-06-22 12:23:36 2
專利名稱：滑動窗口、基於區塊的分支目標地址高速緩衝存儲器的製作方法
技術領域：
本發明大體上涉及處理器領域，且具體來說，涉及具有滑動窗口組織的基於區塊的分支目標地址高速緩衝存儲器。
背景技術：
微處理器在很多應用中執行計算任務。改進處理器性能是永恆的設計目標，通過經由增強的軟體來實現更快的操作和/或增加的功能性，來推動產品改進。在許多嵌入式應用中，例如可攜式電子裝置，節省功率並減少晶片大小在處理器設計和建構中也是重要的目標。大多數現代處理器採用管線化架構，其中連續指令(其每一者具有多個執行步驟)在執行中是重疊的。這種開發連續指令流中的指令之間的並行度的能力對改進的處理器性能作出顯著貢獻。在理想條件下且在於一個循環中完成每一管級的處理器中，在填充管線的短暫初始過程之後，指令可在每一循環完成執行。實際上從沒實現此類理想條件，這歸因於多種因素，其中包含指令之間的數據相依性(數據冒險)、例如分支的控制相依性(控制冒險)、處理器資源分配衝突(結構冒險)、中斷、高速緩衝存儲器未命中等。處理器設計的主要目標是避免這些冒險，且保持管線「充滿」。所有現實的程序都包含分支指令，其可包括無條件或條件分支指令。分支指令的實際分支行為常常是未知的，直到指令被評估為在管線深處。這產生使管線停止的控制冒險，因為處理器不知道在分支指令後獲取哪些指令，且將直到分支指令評估之後才知道。大多數現代處理器採用各種形式的分支預測，藉此在管線中較早地預測條件分支指令的分支行為和分支目標地址，且處理器基於分支預測以推測方式獲取並執行指令，因此保持管線充滿。如果預測是正確的，那麼性能得以最大化，且功率消耗得以最小化。當實際評估分支指令時，如果分支被錯誤預測，那麼必須從管線中清洗以推測方式獲取的指令，且從正確的分支目標地址獲取新的指令。經錯誤預測的分支不利地影響處理器性能和功率消耗。分支預測存在兩個組成部分條件評估和分支目標地址。條件評估(當然，僅與條件分支指令相關)是二進位決策分支被採取(導致執行跳到不同的代碼序列)，或不被採取(在此情況下，處理器執行緊接在條件分支指令之後的下一順序指令)。分支目標地址(BTA)是控制針對評估為採取的無條件分支指令或條件分支指令而分支到的地址。某些共同分支指令將BTA包含在指令操作碼中，或包含借其可容易地計算BTA的偏移。對於其它分支指令，不計算BTA，直到其處於管線深處，且因此必須被預測。
一種已知的BTA預測技術利用分支目標地址高速緩衝存儲器(BTAC)。現有技術中已知的BTAC是由分支指令地址(BIA)標引的完全聯合的高速緩衝存儲器，其中每一數據位置(或高速緩衝存儲器「線」)含有單個BTA。當分支指令在管線中評估為被採取且其實際BTA經計算時，(例如，在寫回管級期間)將BIA和BTA寫入到BTAC。當獲取新的指令時，與指令高速緩衝存儲器(或1-高速緩衝存儲器)並行地存取BTAC。如果指令地址在BTAC中命中，那麼處理器知道所述指令是分支指令(這是在解碼從1-高速緩衝存儲器獲取的指令之前)，且提供經預測的BTA，其為分支指令的先前執行的實際BTA。如果分支預測電路預測分支將被採取，那麼指令獲取開始於經預測的BTA。如果分支被預測為不被採取，那麼指令獲取順序地繼續下去。應注意，術語BTAC也用於此項技術中以表示將飽和計數器與BIA相關聯的高速緩衝存儲器，因此僅提供條件評估預測(即，採取或不採取)。這不是本文所使用的此術語的含義。高性能處理器可一次從1-高速緩衝存儲器獲取一個以上指令。舉例來說，可包括例如四個指令的整個高速緩衝存儲器線可被獲取到指令獲取緩衝器中，所述指令獲取緩衝器順序地將所述指令饋送到管線中。轉讓給本申請案的受讓人並以引用的方式併入本文的第11/089，072號專利申請案揭示了 BTAC在每一高速緩衝存儲器線中存儲兩個或兩個以上BTA,且標引分支預測偏移表(BPOT)以確定哪一 BTA被採取為BTAC命中的經預測的BTA。BPOT避免了成本較高的具有多個讀取埠的BTAC硬體結構，所述多個讀取埠原本是並行地存取多個BTA所必需的。轉讓給本申請案的受讓人並以引用的方式併入本文的第_號專利申請案「基於區塊的分支目標地址高速緩衝存儲器」揭示了基於區塊的BTAC存儲多個條目，每一條目與一指令區塊相關聯，其中所述區塊中的指令中的一者或一者以上是已評估為被採取的分支指令。所述BTAC條目包含相關聯的區塊內的哪個指令是經採取的分支指令的指示符，以及經採取的分支的BTA。BTAC條目由區塊中的所有指令共同的地址位標引(即，通過截斷選擇區塊內的指令的較低階地址位)。因此區塊大小和相對的區塊邊界兩者都是固定的。在每一區塊僅包含一個經採取的分支指令的情況下，基於區塊的BTAC運作良好。當區塊內的兩個或兩個以上分支指令評估為被採取時，必須作出決策以存儲一個分支指令的BTA而不存儲另一分支指令的BTA，從而在另一分支評估為被採取時導致性能和功率降級。每一 BTAC條目中可存儲多個BTA ;然而，在指令區塊不包含與BTAC條目中的BTA存儲位置一樣多的經採取的分支指令的正常情況下，這浪費了寶貴的矽區域。
發明內容
根據本文所揭示的一個或一個以上實施例，滑動窗口、基於區塊的BTAC包括多個條目，每一條目與含有至少一個已被評估為經採取的分支指令的指令的區塊相關聯，且由所述區塊中的第一指令的地址標引。區塊大小是固定的(且對應於指令獲取群組的大小)，但區塊邊界不是固定的，且指令區塊可重疊。因此分支指令可包含在由BTAC條目表示的兩個或兩個以上指令區塊中。在某些情況下，這允許所述滑動窗口、基於區塊的BTAC通過界定新區塊並創建相關聯的BTAC條目而存儲處於單個指令區塊中的兩個或兩個以上經採取的分支指令的BTA，通過增加每一 BTAC條目的BTA存儲容量而不會浪費存儲器。
一個實施例涉及一種在處理器中預測分支指令的方法。將與包含至少一個已被評估為經採取的分支指令的兩個或兩個以上指令的區塊相關聯的條目存儲在分支目標地址高速緩衝存儲器(BTAC)中，BTAC條目具有與所述區塊中的第一指令的地址相關聯的標籤。在獲取指令時，存取BTAC以確定一個或一個以上區塊中的指令是否為條件分支指令。另一實施例涉及一種處理器。所述處理器包含存儲多個條目的分支目標地址高速緩衝存儲器(BTAC)，每一條目與含有至少一個已被評估為經採取的分支指令的兩個或兩個以上指令的區塊相關聯，且所述BTAC條目具有與所述區塊中的第一指令的地址相關聯的標籤。所述處理器還包含指令執行管線，其經操作以在獲取指令群組時使用指令地址來標引 BTAC。
圖1是處理器的一個實施例的功能方框圖。圖2是分支目標地址高速緩衝存儲器和伴隨電路的一個實施例的功能方框圖。
具體實施例方式圖1描繪處理器10的功能方框圖。處理器10根據控制邏輯11執行指令執行管線12中的指令。在某些實施例中，管線12可為具有多個並行管線的超標量設計。管線12包含組織成管級的各種寄存器或鎖存器16，以及一個或一個以上算術邏輯單元(ALU) 18。通用寄存器(GPR)堆20提供構成存儲器層級的頂部的寄存器。管線12使用由指令側翻譯後備緩衝器(ITLB) 24管理的存儲器地址翻譯和許可來從指令高速緩衝存儲器(1-高速緩衝存儲器)22獲取指令。管線12並行地將指令地址提供到滑動窗口、基於區塊的分支目標地址高速緩衝存儲器(BTAC) 25。如果指令地址在BTAC25中命中，那麼滑動窗口、基於區塊的BTAC25將分支目標地址(BTA)提供到1-高速緩衝存儲器22，以立即開始從經預測的BTA獲取指令。下文更全面地描述滑動窗口、基於區塊的BTAC25的結構和操作。使用由主翻譯後備緩衝器(TLB) 28管理的存儲器地址翻譯和許可來從數據高速緩衝存儲器(D-高速緩衝存儲器)26存取數據。在各種實施例中，ITLB可包括TLB的一部分的副本。或者，ITLB和TLB可集成。類似地，在處理器10的各種實施例中，1-高速緩衝存儲器22和D-高速緩衝存儲器26可集成或統一。1-高速緩衝存儲器22和/或D-高速緩衝存儲器26中的未命中導致在存儲器接口 30的控制下存取主(晶片外)存儲器32。處理器10可包含輸入/輸出(I/O)接口 34，從而控制對各種外圍裝置36、38的存取。所屬領域的技術人員將認識到，處理器10的許多變化形式都是可能的。舉例來說，處理器10可包含用於I和D高速緩衝存儲器22、26中任一者或兩者的二級(L2)高速緩衝存儲器。另外，可從特定實施例中省略處理器10中描繪的功能區塊中的一者或一者以上。分支指令在大多數代碼中都是共同的。根據某些估計，可能五個指令中便有一個指令是分支。因此，早期分支檢測、分支評估預測(針對條件分支指令)以及從經預測的BTA中獲取指令對於處理器性能來說可為關鍵的。大多數現代處理器包含在每一高速緩衝存儲器線中存儲多個指令的1-高速緩衝存儲器22。從「獲取群組」中的I高速緩衝存儲器獲取指令。獲取群組可包括高速緩衝存儲器線的一部分、整個高速緩衝存儲器線，或一個以上高速緩衝存儲器線。作為一個實例，假定處理器的獲取群組匹配其四個指令的1-高速緩衝存儲器22線的大小，但此實例僅是說明性的且沒有限制。如果一個以上指令地址在BTAC中命中，那麼存取共同已知的BTAC來並行地搜索所有四個指令地址將需要四個地址比較輸入埠、四個BTA輸出埠，以及一個多路復用器和控制邏輯來選擇BTA。根據一個或一個以上實施例，滑動窗口、基於區塊的BTAC25包括多個條目，每一條目存儲與指令區塊中的經採取的分支指令相關聯的分支信息。所述指令區塊對應於獲取群組，且BTAC條目包含與區塊中的第一指令的地址相關聯的標籤。所述標籤還用於從1-高速緩衝存儲器獲取所述獲取群組。在某些實施例中，所述標籤可為獲取群組中的第一指令。如本文中所使用，術語「指令區塊」和「獲取群組」是同義的。每一 BTAC條目指示以下事實區塊中的至少一個指令是已評估為被採取的分支指令(由BTAC25中的命中指示)，且包含區塊中的哪個指令是經採取的分支的指示符以及其BTA。圖2描繪滑動窗口、基於區塊的BTAC25、I_高速緩衝存儲器22、管線12和分支預測邏輯電路15(其可例如包括控制邏輯11的一部分)的功能方框圖。在此實例中，指令A-L駐存在1-高速緩衝存儲器22中的三條線中。為解釋清晰起見，此實例中的處理器獲取群組為高速緩衝存儲器線，但這不是對本發明的限制。代碼段的指令和對應區塊200A-200C列示在電路圖的左側。應注意，雖然按次序標記區塊，但不應解釋為以區塊被標記的次序來獲取它們。更可能的是，由於示範性代碼段的分支性質，獲取區塊的次序將為區塊200A、接下來是區塊200C，且然後是區塊200B。圖2的滑動窗口、基於區塊的BTAC25中的每一條目包括三個組成部分標籤欄位，其包括相關聯的指令區塊中的第一指令(其也是用於存取1-高速緩衝存儲器的指令)的地址；分支指示符，其描繪區塊內的哪個指令是經採取的分支；以及當分支指令最後評估為被採取時，所述分支指令的實際BTA。在圖2的實例中，獲取並執行包括指令A、B、C和D的1-高速緩衝存儲器的第一線(或獲取群組)。其中，指令B和C都是分支指令。指令B經執行，被評估為經採取，且計算分支目標地址BTAb。針對指令區塊AB⑶創建BTAC條目。BTAC條目(圖2中所描繪的第一條目)具有與指令A的地址相關聯的標籤、區塊中的第二指令是經採取的分支的指示符(地址01)以及BTAb。在另一實施例中，分支指示符可包括哪個指令是經採取的分支的經解碼指示，例如0100。在此實例中，指令B導致到達代碼的另一段中的程序的分支(其細節與本論述無關)。在完成執行時，另一代碼分支返回到指令C，其在執行時評估為被採取且具有目標BTAC。在通常已知的具有固定指令區塊邊界的基於區塊的BTAC中，BTAc必須取代BTAC條目中的BTAb，或者保留BTAb且丟棄BTA。，因為指令C將固定地與區塊200A相關聯。然而，通過利用滑動窗口、基於區塊的BTAC25的流動的指令區塊邊界，界定了新的指令區塊，其對應於在從程序返回到指令C時從1-高速緩衝存儲器獲取的獲取群組。新的區塊包括指令C、D、E和F，且因此部分與指令區塊AB⑶重疊。在滑動窗口、基於區塊的BTAC25中創建對應的BTAC條目。新BTAC條目(圖2中所描繪的第二條目)的標籤與區塊中的第一指令(也是用於存取1-高速緩衝存儲器的指令)——指令C的地址相關聯。分支指示符具有值00 (區塊中的第一指令的地址)，其指示指令C是區塊CDEF中的經採取的分支指令。最終，與區塊⑶EF相關聯的BTAC條目包含BTA。(分支指令C的目標地址)。以此方式，滑動窗口、基於區塊的BTAC25可存儲用於區塊ABCD中的經採取的分支指令兩者的BTA，而不需要每一 BTAC條目包含用於兩個或兩個以上BTA的存儲空間。此外，滑動窗口、基於區塊的BTAC25中的第二條目將分支指令C的行為聯繫到在其從1-高速緩衝存儲器獲取之前採取的代碼路徑。也就是說，因為當所述代碼在從程序返回時被分支到指令C時，分支指令C被評估為經採取，所以從所述程序到指令C的下一返回將可能也被評估為經採取。相反，當順序地執行指令C時(即，如果分支指令B被評估為未採取，且不執行介入的程序)，其可被評估為未採取。第三BTAC條目對應於包括1、J、K和L的指令區塊，從而對應於以指令I開始的獲取群組。第三BTAC條目的標籤與區塊中的第一指令的地址相關聯，所述地址是在獲取所述獲取群組IJKL的過程中存取1-高速緩衝存儲器所用的地址。在此群組中，指令J和L是分支指令。在此實例中，指令J被評估為經採取，分支指示符尋址區塊中的第二指令，且指令J的BTAj存儲在BTAC條目中。當然，圖2中所描繪的區塊組織和BTAC條目僅是代表性的，且本發明不限於此實施方案。具體來說，獲取群組不需要與1-高速緩衝存儲器線的大小對準。一般來說，獲取群組可在1-高速緩衝存儲器線內的任何地方開始，例如在分支指令分支到目標的情況下，所述獲取群組可在1-高速緩衝存儲器線中的任何地方開始。對應的滑動窗口、基於區塊的BTAC25條目的標籤將與獲取群組中的第一指令的地址相關聯。因此，當再次從1-高速緩衝存儲器獲取同一獲取群組時，對滑動窗口、基於區塊的BTAC25的同時存取將檢索指示指令區塊內先前被評估為經採取的分支指令的條目。管線12中的解碼/獲取邏輯13經配置以產生用於從1-高速緩衝存儲器22獲取下一指令獲取群組的指令地址。在操作中，指令地址同時比較於滑動窗口、基於區塊的BTAC25的標籤欄位。如果指令地址匹配BTAC25中的標籤，那麼將命中指示和對應的分支指示符提供到解碼/獲取邏輯13，以指示區塊中的哪個指令是經採取的分支指令。還將指示符提供到分支預測邏輯15。同時，將對應條目的BTA提供到1-高速緩衝存儲器22，以允許立即以推測方式從BTA獲取指令，以在所述分支被預測為經採取的情況下保持管線充滿。在解碼邏輯13中解碼指令。當檢測到分支指令時(無論獲取群組地址在滑動窗口、基於區塊的BTAC25中是否命中)，將獲取群組信息保留在管線12中。此信息可例如包括從分支指令地址(BIA)到獲取群組中的第一指令的地址的負偏移。針對分支指令被評估為經採取的可能性而保留此信息，從而允許將其BTA存儲在新BTAC條目中，所述新BTAC條目具有獲取群組中的第一指令的地址(即，存取1-高速緩衝存儲器所用的地址)作為標籤。在管線12中的執行級的邏輯14中評估條件分支指令。EXE邏輯14額外計算並提供評估為被採取的無條件分支指令和條件分支指令兩者的BTA。如果經預測分支評估是不正確的且/或經高速緩衝存儲的BTA不匹配計算出的BTA，那麼管線12必須執行錯誤預測分支恢復，其可包含從管線中清洗推測性指令、重新分配存儲以及計算資源等。由EXE邏輯14將實際的分支評估提供到分支預測邏輯15，以更新關於實際的分支行為的預測邏輯。分支預測邏輯15更新其預測表(例如，分支歷史寄存器、分支預測表、飽和計數器等)，且額外更新滑動窗口、基於區塊的BTAC25。對於現有的BTAC條目，這可包括如果計算出不同的實際BTA便更新經高速緩衝存儲的BTA，或可包括如果對應區塊中的不同分支指令評估為被採取且作出取代現有的經高速緩衝存儲的BTA的決策，便更新分支指示符和BTA兩者。如果分支指令評估為被採取且獲取群組信息指示群組獲取地址對於滑動窗口、基於區塊的BTAC25中的任何標籤是唯一的，那麼分支預測邏輯15便創建新的BTAC條目。新的BTAC條目對應於以其中獲取所述分支指令的獲取群組的第一指令開始的指令區塊，且因此新BTAC條目的標籤與第一指令的地址相關聯。以此方式，分支指令可包含於在滑動窗口、基於區塊的BTAC25中具有對應條目的兩個或兩個以上指令區塊中。此特徵的一個顯著優點在於第一區塊中的第一分支指令的BTA可存儲在第一 BTAC條目中，且處於第一區塊中但由於單獨存取1-高速緩衝存儲器而同樣是第二獲取群組的一部分的第二分支指令的BTA可存儲在第二 BTAC條目(界定第二指令區塊)中。因此，滑動窗口、基於區塊的BTAC25可存儲兩個BTA，通過在每一 BTAC條目中提供用於多個BTA的存儲器而不會浪費寶貴的矽區域。如本文所使用，一般來說，分支指令可指代條件或無條件分支指令。如本文所使用，「經採取的分支」、「經採取的分支指令」或「已被評估為經採取的分支指令」指代已被評估為將順序的指令執行流轉向到非順序的地址(即，與不被採取相反的被採取)的無條件分支指令或條件分支指令。雖然已在本文相對於本發明的特定特徵、方面和實施例描述了本發明，但將明白，在本發明的廣義範圍內，許多變化形式、修改和其它實施例都是可能的，且因此所有變化形式、修改和實施例將被視為處於本發明的範圍內。因此，本發明實施例在所有方面被解釋為說明性的，而不是限制性的，且希望處於所附權利要求書的含義和等效範圍內的所有修改都包含在其中。
權利要求
1.一種預測包含在指令高速緩衝存儲器1-cache的指令線中的分支指令的方法，其包括 僅當將有一分支指令評估為被採取時，才將第一分支目標地址高速緩衝存儲器BTAC條目存儲在所述BTAC中，其中所述分支指令和第二分支指令位於第一指令區塊中，所述第一指令區塊存儲在所述1-cache的線中； 僅當將所述第二分支指令評估為被採取時，才將第二 BTAC條目存儲在所述BTAC中，其中具有所述第二分支指令的第二指令區塊存儲在所述1-cache的一個或多個線中且與所述第一指令區塊重疊； 其中所述第一 BTAC條目包括第一標籤欄位，所述第一標籤欄位具有所述第一指令區塊中的第一指令的全指令地址，且所述第二 BTAC條目包括第二標籤欄位，所述第二標籤欄位具有存儲於所述1-cache線中的任意全指令地址的所述第二指令區塊的全指令地址； 從始於所述第二指令區塊的所述全指令地址的所述1-cache中獲取指令群組，將所述全指令地址與BTAC條目的標籤欄位進行比較以確定與所述第二標籤欄位的匹配；以及一旦確定與所述第二標籤欄位的匹配，就使用所述第二 BTAC條目中的指示符以確定所述第二指令區塊中的哪一個指令是所述第二經採取的分支指令；並且，從存儲在所述第二 BTAC條目中的所述分支目標地址中獲取指令。
2.根據權利要求1所述的方法，其進一步包括一旦獲取指令區塊，就存取所述BTAC以確定對應的指令區塊中的指令是否是經採取的指令。
3.—種在處理器中預測分支指令的方法，其包括 在分支目標地址高速緩衝存儲器BTAC中存儲第一 BTAC條目和第二 BTAC，所述第一BTAC條目與具有兩個或更多個指令的第一區塊相關聯，所述第一區塊具有存儲在指令高速緩衝存儲器1-cache的線中的第一和第二經採取分支指令，所述第二 BTAC條目與具有兩個或更多個指令的第二區塊相關聯，所述第二區塊與所述第一區塊重疊且包括所述第二經採取分支指令，每一 BTAC條目都具有標籤欄位，所述標籤欄位包括對應區塊中的始於1-cache線中的任意全指令地址的第一指令的全指令地址； 一旦獲取指令群組，就存取所述BTAC以確定對應的指令區塊中的指令是否是經採取的指令；以及 其中每一 BTAC條目包括一個指示符，用於指示相關聯指令群組中的哪一個指令是經採取的指令，且其中每一 BTAC條目包括相關聯指令群組中經採取的分支指令的分支目標地址BTA。
4.根據權利要求3所述的方法，其進一步包括 確定與所述第二 BTAC條目相關聯的分支目標地址BTA不同於存儲在現有的第二 BTAC條目的BTA ； 更新現有的第二 BTAC條目。
5.根據權利要求3所述的方法，其進一步包括 確定在所述獲取的指令群組中檢測的分支指令不是經採取的分支指令；以及一旦確定所述分支指令被評估為經採取，就在所述BTAC中存儲新的條目，其中所述BTAC中的新條目基於當所述分支指令被檢測時保存的獲取群組信息。
6.根據權利要求5所述的方法，其中所述獲取群組信息包括從所述分支指令地址到所述獲取的指令群組中的所述第一指令的所述地址的負偏移。
全文摘要
一種滑動窗口、基於區塊的分支目標地址高速緩衝存儲器(BTAC)包括多個條目，每一條目與含有至少一個已被評估為經採取的分支指令的指令區塊相關聯，且具有與所述區塊中的第一指令的地址相關聯的標籤。所述區塊每一者對應於從例如I-高速緩衝存儲器等存儲器獲取的指令群組。在分支指令包含在兩個或兩個以上獲取群組中處，其也包含在與BTAC條目相關聯的兩個或兩個以上指令區塊中。所述滑動窗口、基於區塊的BTAC通過存儲與不同的指令區塊(其每一者含有所述經採取的分支指令中的至少一者)相關聯的BTAC條目而允許存儲處於同一指令區塊中的兩個或兩個以上經採取的分支指令的分支目標地址(BTA)，而不需要在每一BTAC條目中提供多個BTA存儲空間。
文檔編號G06F9/38GK103019652SQ20121047353
公開日2013年4月3日 申請日期2007年5月31日 優先權日2006年6月5日
發明者羅德尼·韋恩·史密斯, 詹姆斯·諾裡斯·迪芬德費爾, 布萊恩·麥可·斯坦普爾, 託馬斯·安德魯·薩託裡烏斯 申請人:高通股份有限公司