TW202219744A

TW202219744A - 微處理器和分支預測控制方法

Info

Publication number: TW202219744A
Application number: TW110124700A
Authority: TW
Inventors: 湯瑪斯Ｃ麥當勞
Original assignee: 美商聖圖爾科技公司
Priority date: 2020-11-09
Filing date: 2021-07-06
Publication date: 2022-05-16
Also published as: US20220147360A1; CN113515310A; TWI858271B; US11614944B2

Abstract

本發明提供了微處理器和分支預測控制方法。在一個實施例中，一種微處理器，包括：表，其包括多個邊，其中至少第一邊包括具有第一組預測表的第一條件分支預測器，其中至少第二邊包括具有第二組預測表的第二條件分支預測器，其中所述第二條件分支預測器被配置為基於針對包括所述第二邊中的資訊的分支指令的預測表命中來提供第一預測，以及其中所述第一條件分支預測器具有比所述第二條件分支預測器高的複雜度；以及控制邏輯，其中基於接收到與針對所述分支指令的第一預測相對應的錯誤預測的指示，所述控制邏輯被配置為將針對所述分支指令的資訊寫入所述第一邊的第一組預測表其中之一。

Description

微處理器和分支預測控制方法

本發明是有關於一種微處理器，且特別是有關於一種微處理器中的分支預測。

如今的微處理器使用流水線處理方案來操作，由此程式設計指令被分解成貫穿流水線的多個級併發執行的步驟。指令通常(例如，10~20%的程式設計代碼)包括分支指令或簡稱為分支，其包括無條件分支(例如，總是被採取的分支)和條件分支(例如，根據對指定條件的評價來採取或不採取)。一般不會確切地知道條件跳轉是將被採取、還是將被不採取，直到條件已被計算出並且條件跳轉已透過指令流水線中的執行級為止，這可能導致拾取(fetch)下一指令的延遲。已經開發了一種分支預測器，其嘗試在流水線的前端處猜測條件分支將朝哪個方向(採取或不採取)前進以及到哪個目標位址，並透過這樣做來改進透過流水線的指令流。

在微處理器中常用的一個分支預測器被稱為分支目標位址快取記憶體(BTAC)。BTAC包括硬體邏輯，該硬體邏輯可以包括使用過去分支指令行為的全域歷史模式以實現對所拾取的分支指令的目標位址的預測。一般而言，用於BTAC的分支預測器可以包括與經常用字母表示的多個、多組關聯快取記憶體或邊(side)(諸如在BTAC的兩個快取記憶體的情況下，邊A和B等)相結合使用的多個預測器表。各邊可以包括多個路(例如2路、4路等)。用於一些示例BTAC陣列的資訊可以在美國專利No.8,832,418和No.7,707,397中找到，在與當前揭示內容一致的程度上透過引用方式將其併入於此。對於給定的快取記憶體取指(fetch)(例如，指令快取記憶體中的快取記憶體行的十六(16)位元組取指)，可能存在多於單個分支指令。對於具有邊A和邊B的BTAC以及包括兩個分支指令的快取記憶體取指，可以分別在邊A和邊B中找到針對這兩個分支指令的資訊(例如，目標位址、方向等)。然而，儘管不常發生，但在給定的快取記憶體取指中可能存在多於兩個(例如，三個)分支指令，並且微處理器的預測邏輯應該能夠在沒有不適當延遲且與分支指令的複雜度無關的情況下有效率地處理在單個快取記憶體行取指中遇到的這些多個分支指令。

在一個實施例中，一種微處理器，包括：表，其包括多個邊，其中，至少第一邊包括具有第一組預測表的第一條件分支預測器，其中，至少第二邊包括具有第二組預測表的第二條件分支預測器，其中，所述第二條件分支預測器被配置為基於針對包括所述第二邊中的資訊的分支指令的預測表命中來提供第一預測，以及其中，所述第一條件分支預測器具有比所述第二條件分支預測器高的複雜度；以及控制邏輯，其中，基於接收到與針對所述分支指令的第一預測相對應的錯誤預測的指示，所述控制邏輯被配置為將針對所述分支指令的資訊寫入所述第一邊的第一組預測表其中之一。

透過審查以下附圖和詳細描述，本發明的其它系統、方法、特徵和優點對於本領域具有通常知識者將是或者將變得明顯。所有這些附加系統、方法、特徵和優點旨在包括在本說明書內、在本發明的範圍內，並且受到申請專利範圍的保護。

揭示了分支預測控制系統和方法的某些實施例，其包括具有三個快取記憶體記憶體邊的表，所述三個快取記憶體記憶體邊使用兩種類型的不同複雜度的條件分支預測器來有效率地處理單個快取記憶體行取指中的三個分支指令和/或更複雜的分支指令位於具有較小預測表的邊的情況。在一個實施例中，分支預測控制系統被配置為將錯誤預測的條件分支從使用較低複雜度條件分支預測器的較小的快取記憶體邊移動到使用較高複雜度條件分支預測器的兩個大快取記憶體邊其中之一。移動(寫入)是根據用於避免錯誤預測再發生的可配置概率或可能性來實現的，並且結果是減少了針對給定分支指令的錯誤預測的量。

稍微離題而言，傳統的分支預測方案使用包括多個邊的預測邏輯表(例如，分支目標位址快取記憶體或BTAC)的分支預測邏輯。儘管罕見，但具有三個分支指令的快取記憶體行取指可能導致分別在三個邊中的預測表命中。BTAC中分支指令的分配一般按程式設計代碼中出現的順序(例如，第一分支指令到第一邊或邊A，第二分支指令到第二邊或邊B，以及第三分支指令到第三邊或邊C)。然而，三個分支指令的發生是不常見的，並且因此在大多數情況下，要求這三個邊具有相等的大小和/或相等的預測邏輯複雜度是沒有根據的。然而，減小這些邊中的一個邊(例如，邊C)的大小和預測複雜度，儘管實現了降低複雜度和提高操作速度的益處，但是在(例如，與快取記憶體行拾取的其它兩個分支指令相比時)需要更精密的分支預測的分支指令位於較低複雜度邊(例如，邊C)時，可能導致性能妥協。分支預測控制系統的某些實施例檢測到在有問題的(offending)分支指令位於邊C的情況下存在錯誤預測的情形，並且因此根據表示多個不同的預定義比率(例如，1/128、1/32、1/8)其中之一的可配置可能性來提供將有問題的分支指令從邊C(較低的複雜度)到邊A或B(較高的複雜度)其中之一的脫離或移動。透過使用具有較低分支預測複雜度的分支預測微架構，實現了性能提升(例如，與使用相同複雜度的預測功能的三個邊相比)，同時在位於邊C的給定分支指令發生錯誤預測時實現小的分支預測器脫離(例如，移動至具有使用更精密的分支預測演算法的更多分支預測器表的邊)。

在總結了本發明的分支預測控制系統的某些特徵之後，現在將詳細參考如附圖中所例示的分支預測控制系統的描述。雖然將結合這些附圖來描述分支預測控制系統，但並不意在將其限制於這裡所揭示的實施例。也就是說，雖然本發明易於進行各種修改和替代形式，但是其特定實施例在附圖中透過示例的方式示出，並且這裡將被詳細描述成足以使本領域具有通常知識者理解。例如，儘管下面重點放在具有包括三個邊的條件分支預測器表的預測邏輯中，但是本領域具有通常知識者在本發明的上下文中應當理解，具有多於三個邊或者僅具有兩個邊的表也可以被使用，並且因此預期在本發明的範圍內。此外，儘管描述了具有在邊A和邊B的各個中包括多個不同複雜度的表的標籤幾何(TAGE：tagged geometric)預測器以及在邊C中包括單個預測器表的GSHARE預測器的特定實施例，但是在一些實施例中，可以存在所使用的不同類型的條件分支預測器，並且因此預期在本發明的範圍內。然而，應該理解的是，附圖及其詳細描述不意在將本發明限制於所揭示的特定形式。相反，意圖是覆蓋落入如所附申請專利範圍所限定的本發明的精神和範圍內的所有修改、等同項和替代。如在本申請中所使用的，單詞“可以”以允許的意義(即，意味著有可能)而不是強制的意義(即，意味著必須)被使用。類似地，單詞“包括”意味著包括但不限於。

各種單元、模組、電路、邏輯或其它元件可被描述為“被配置為”進行一個或多個任務。在這樣的上下文中，“被配置為”是對結構的廣泛敘述，其一般意味著“具有在操作期間進行或能夠進行一個或多個任務的電路或其它物理結構”。電路可以是專用電路、或在編碼指令的控制下操作的更通用處理電路。也就是說，在描述本發明的各種實現的某些方面或特徵時，這裡可以使用諸如“單元”、“模組”、“電路”、“邏輯”和“元件”等的術語。本領域具有通常知識者將理解，利用電路實現相應的特徵，無論該電路是專用電路還是在微編碼指令控制下操作的更通用電路。

另外，單元/模組/電路/邏輯/元件可被配置為即使在單元/模組/電路/邏輯/元件當前不處於操作中的情況下也進行任務。敘述被配置為進行一個或多個任務的單元/模組/電路/邏輯/元件明確不旨在針對該單元/模組/電路/邏輯/元件進行功能性限定。在這方面，本領域具有通常知識者將理解，電路元件的特定結構或互連通常將由設計自動化工具的編譯器(諸如暫存器傳送語言(RTL)編譯器)確定。RTL編譯器在與組合語言代碼非常相似的腳本上運行，以將該腳本編譯成用於最終電路的佈局或製造的形式。

也就是說，使用更高級的軟體工具來設計(諸如本發明的那些)積體電路以對電路的期望功能操作進行建模。眾所周知，“電子設計自動化”(或EDA)是一類用於設計諸如積體電路等的電子系統的軟體工具。EDA工具還用於將設計功能程式設計到現場可程式設計閘陣列(FPGA)中。使用諸如Verilog和超高速積體電路(VHDL)等的硬體描述符語言(HDL)來創建電路的高級表示，其中根據該高級表示可以推斷出較低級表示和最終實際佈線。實際上，由於現代半導體晶片可以具有數十億個元件，因此EDA工具被認為是對於其設計而言必不可少的。在實踐中，電路設計者使用諸如C/C++等的程式設計語言來指定操作功能。EDA軟體工具將該指定功能轉換為RTL。然後，硬體描述符語言(例如Verilog)將RTL轉換為門的離散網表。該網表定義了由例如代工廠等生產的實際電路。實際上，這些工具因其在促進電子和數位系統的設計過程中的作用和用途而被眾所周知並理解，因此於此無需描述。

圖1A示出微處理器10所用的示例分支單元流水線的實施例。應當理解，為了簡潔和易於解釋和例示，這裡省略了微處理器10的某些已知元件。眾所周知，流水線架構提供了在執行中重疊的多個指令，其中各級稱為管道級。分支單元流水線中所示的塊各自可以根據一個或多個級來實現，這些級顯示在塊的左邊並且在所描繪的實施例中由從上至下按順序前進並且被重定向(如箭頭所示)的大寫字母C、I、B、U、L、M、F、G、W、X、E、S、W、Y和Z表示。本領域具有通常知識者應當理解，圖1A中所描繪的級的數量和/或佈置僅僅例示一個示例實施例，並且在一些實施例中，級的不同數量和/或佈置可被實現，因此預期在本發明的範圍內。本領域具有通常知識者還應當理解，這些塊提供了對分支流水線的功能的一般描述，並且為了簡潔，這裡省略了本領域具有通常知識者已知的相關邏輯或電路。例如，本領域具有通常知識者應當理解，如已知的，流水線的各級可以由時脈流水線暫存器或鎖存器分開。作為另一示例，儘管在圖1A中未明確示出，但本領域具有通常知識者應當理解，前端處的操作涉及與指令快取記憶體的資料交換或交互。

指令快取記憶體是微處理器內的隨機存取記憶體裝置，其中微處理器將最近從較大快取記憶體(例如，L2快取記憶體、L3快取記憶體)或系統記憶體拾取和/或預拾取(例如，由匯流排界面單元從DRAM拾取和/或預拾取)並由微處理器在運行ISA機器語言程式的過程中進行的ISA機器語言程式的指令(諸如x86 ISA機器語言指令)放置到該指令快取記憶體中。ISA定義用於保持要進行的下一ISA指令的記憶體位址(由x86 ISA定義為指令指標(IP)，但有時稱為程式計數器(PC))的指令位址暫存器，並且微處理器在其運行機器語言程式以控制程式流時更新指令位址暫存器內容。為了隨後在下一次機器語言程式流時執行基於指令位址暫存器內容從指令快取記憶體而不是從系統記憶體更快地拾取ISA指令的目的，對ISA指令進行快取記憶體，使得暫存器保持指令快取記憶體中所存在的ISA指令的記憶體位址。特別地，基於指令位址暫存器(例如，IP)中所保持的記憶體位址而不是排他地基於載入或存儲指令所指定的記憶體位址來訪問指令快取記憶體。因此，保持ISA指令作為資料(諸如可以存在於採用軟體轉譯器的系統的硬體部分中)、並且排他地基於載入/存儲位址而不是透過指令位址暫存器值來訪問該資料的專用資料快取記憶體不是指令快取記憶體。此外，為了本發明的目的，對指令和資料兩者進行快取記憶體(即，基於指令位址暫存器值並基於載入/存儲位址，而不是排他地基於載入/存儲位址來訪問)的統一快取記憶體旨在包括在指令快取記憶體的定義中。

特別注意圖1A的微處理器10的分支單元流水線，微處理器10包括流水線微處理器，在一個實施例中，流水線微處理器的指令集基本上符合x86架構指令集。根據這裡提供的描述，本領域具有通常知識者將理解，本發明可以以各種不同的電路結構和架構來實現，並且圖1A所示的架構僅僅是許多合適架構其中之一。示例微處理器10包括快速預測器12、分支目標位址快取記憶體(BTAC) 14、指令位元組佇列(XIB) 16、分支解碼器18、格式指令佇列(FIQ)/迴圈佇列20、指令轉譯器22、暫存器別名表(RAT)/保留站(RS) 24、執行單元(例如，整數單元、浮點單元等) 26、以及分支表更新器28。微處理器10的數位標記塊各自與在相應的多個級C、I、B、U、L、M、F、G、W、X、E、S、W、Y和Z上實現的邏輯電路相對應，其中流水線架構在每一級實現不同的指令組。在一個實施例中，可以在每個級運行四個或更多個指令，其中控制信號對沿著流水線的每個級進行標記。與快速預測器12、BTAC 14和XIB 16相關聯的級涉及對指令快取記憶體(I快取記憶體，圖1A中未示出)的訪問。

快速預測器12包括提供單週期預測(例如，採取一個週期來產生目標位址，在一個實施例中在I級提供的預測)的單週期分支預測器。在一個實施例中，快速預測器12包括存儲先前執行的分支指令的分支目標位址的表(這裡也稱為陣列或目標陣列)，該表使得能夠在隨後遇到所存儲的分支指令時進行分支預測。在一個實施例中，表包括128個條目，但是在一些實施例中可以使用其它大小(例如，64個條目、32個條目等)的表。表被組織為n路(例如，n是大於1的整數)的組關聯快取記憶體。一般而言，n路的組關聯快取記憶體在這裡也稱為多組關聯快取記憶體。在一個實施例中，各條目存儲八(8)個3位元數目器和當前局部分支模式，該計數器是透過3位元局部分支模式而選擇的。快速預測器12還包括條件分支預測器，該條件分支預測器與表並行地被訪問並且為條件分支提供採取/不採取的方向。快速預測器還包括返回堆疊，該返回堆疊可以提供目標而不是表。在一個實施例中，返回堆疊包括四(4)個條目並且為返回指令提供目標。注意，以上列出的規範僅為了例示，並且一些實施例可以在不同的規範下進行，因此預期在本發明的範圍內。快速預測器12被配置為立即(在單個週期內)遞送預測分支目標，而不採取分支懲罰。在一些實施例中，快速預測器12可以根據其預測機制和/或表配置的其它規範來進行操作，或者在一些實施例中，可以省略。大多數分支由快速預測器12正確地預測。在一些實施例中，在基於相同的所拾取的分支指令快速預測器12提供與BTAC 14的分支預測不同(例如，在方向和/或目標上不同)的分支預測的情況下，BTAC 14利用BTAC 14所提供的分支預測資訊(例如，方向、目標位址、分支預測類型)來在BTAC 14的一組級內(例如，在U級)覆寫快速預測器12的分支預測並更新快速預測器表。

I級和/或B級對應於訪問分支單元流水線的各種表(包括I快取記憶體、標籤陣列、轉譯後備暫存器(TLB)陣列、BTAC陣列、返回堆疊陣列等)、(例如，基於標籤)透過多工給出方向或路、以及讀出指令。

BTAC 14保持與其用於預測後續執行期間的目標位址、方向和類型的先前執行分支指令有關的資訊。BTAC 14包括比快速預測器12的表大得多的一個或多個表。在一個實施例中，BTAC 14包括4k條目、m路的組關聯表(這裡也稱為陣列或目標陣列)，其中m是大於1的整數。BTAC 14的各條目包括有效位元、分支目標位址預測、方向預測和分支類型。分支類型指定分支指令是呼叫/返回、是間接分支、是條件相對分支、還是無條件相對分支。在一個實施例中，BTAC 14包括條件相對分支預測器(或者簡稱為條件分支預測器)或者與之協作，其中，條件分支預測器具有多條目(例如，12k)的基於標籤幾何(TAGE)的條件分支預測器、多個表、多位(例如，3位)、採取/不採取(T/NT)計數器以及多位元全域分支歷史。也就是說，TAGE條件分支預測器包括具有幾何上增加的分支歷史長度的標籤表，這是眾所周知的。作為另一示例，間接預測包括多條目(例如，1.5k) TAGE預測器，並且將表條目用於靜態間接分支。在一個實施例中，使用了兩個TAGE條件分支預測器，一個用於表的邊A，以及一個用於表的邊B。TAGE條件分支預測器可以是BTAC的一部分或與BTAC 14結合使用。在一個實施例中，BTAC 14包括具有比TAGE條件分支預測器低的複雜度的第二類型的條件分支預測器(例如與表的邊C相關聯的GSHARE預測器)或與之協作。GSHARE條件分支預測器可以是BTAC 14的一部分或與BTAC 14結合使用。GSHARE條件分支預測器包括在快速預測器12的複雜度與TAGE條件分支預測器的複雜度之間的複雜度(例如，大約TAGE條件分支預測器的大小的1/10)。在一個實施例中，GSHARE條件分支預測器包括單個表(例如，包括最後m個執行的分支指令的分支模式的m位元全域歷史暫存器，其中，m通常為10-12位，但不限於該數量)。GSHARE條件分支預測器使用全域分支歷史和分支指令的位址(例如IP)來(經由XOR邏輯運算)創建到計數器(例如2位元數目器)的表中的索引，其中索引的結果是用於當前分支的預測。由於TAGE和GSHARE類型的條件分支預測器在本領域中是已知的，因此為簡潔起見，在此省略對其的進一步描述。注意，在一些實施例中，可以使用其它類型的預測機制，包括基於相關性的預測機制、使用全域和局部分支歷史的組合的條件分支預測器等。此外，儘管這裡強調了邊A、B和C，但是在一些實施例中，可以使用更少或更多的邊。對於指令快取記憶體的快取記憶體行的各部分或各取指單位(quantum)(例如，16位元組)，BTAC 14可以保持三個條目(例如，邊A、B和C，儘管在一些實施例中可以使用更少的邊來存儲用於更少的分支指令的預測資訊)，該三個條目可以保持可能存在於快取記憶體行的一部分中的多達三個分支指令的預測資訊。BTAC 14包括透過一組級(例如，I級、B級和U級)的操作。實際上，分支指令的U級用作目標的C級(例如，從B級到C級的箭頭反映B級處的分支指令的情況，並且下一個時脈是目標的C級，或者在這裡也是快取記憶體位址)，從而導致BTAC預測的二時脈延遲。

BTAC 14具有二時脈採取懲罰(two-clock taken penalty)，這也揭示了快速預測器12透過立即引導新快取記憶體位址成為目標來提供快速分支預測(無採取懲罰)的益處。在一個實施例中，BTAC 14 (比快速預測器12大並且具有更精密的分支預測機制)被配置為在分支預測中存在分歧(例如，BTAC 14確定的分支預測與由快速預測器12確定的採取判斷和/或分支目標位址不同)時(例如，總是)覆寫快速預測器12的分支預測。在一些實施例中，BTAC 14被配置為透過將分支預測資訊寫入快速預測器12的表(並且還寫入BTAC 14的表)來在BTAC級其中之一(例如，U級)期間更新快速預測器12。在一些實施例中，對BTAC 14的更新被延遲直到分支被執行或退出為止，其中對BTAC 14的更新涉及對BTAC 14的預測器表的寫入。在一個實施例中，更新涉及目標資訊和/或計數器更新。更新包括基於可配置概率或可能性來將錯誤預測的條件分支資訊從BTAC 14的邊C寫入到邊A或邊B中的任何一個和/或條件分支預測器陣列(取決於快取記憶體替換方案)，以及將條件分支資訊從邊A或邊B寫入到邊C。然而，對快速預測器12的更新不會等待那麼長時間，其在BTAC級期間發生。注意，不在快速預測器12中的分支在兩個週期後在與BTAC級相對應(例如，在BTAC級期間)的時間被寫入快速預測器12。

XIB 16是條目佇列，其中各條目保持來自指令快取記憶體的16個位元組的資料。例如，來自XIB 16的快取記憶體資料僅僅是採用16個位元組的塊的指令位元組流，並且在給定指令具有可變長度的情況下，不知道給定x86指令在流內或在給定塊內開始或結束於何處。XIB 16包括用以確定和標記各指令在流內的開始和結束位元組、從而將位元組流分解成x86指令流的已知邏輯，其中該x86指令流被提供給FIQ/迴圈佇列20並存儲在FIQ/迴圈佇列20中以供微處理器流水線的其餘部分處理。在L (長度)級，XIB 16確定指令長度。在一個實施例中，預解碼器(圖1A中未示出)在U級實現，並且被配置為針對佇列中的各指令位元組檢測潛在的分支指令，並將其標記為潛在的分支指令。值得注意的是，在此級，關於給定的位元組是否是指令的開始，存在歧義。如果位元組是稍後(M級)確定的分支指令的操作碼位元組，則將該指令確認為分支指令。例如，分支解碼器18包括用於在多工器或M級中對指令進行多工的指令多工器(未示出)，其中分支指令被如此確認。

在F級，指令被格式化。在一個實施例中，格式化指令包括基本上符合x86架構指令集的指令。另外，在M級判斷給定指令(該給定指令可能由預解碼器預先標記)是否確實是分支。例如，(例如，在最初啟動時)在快速預測器12或BTAC 14中發生未命中的情況下，分支解碼器18(例如，指令多工器)決定為當前指令是分支，並且在級G將快取記憶體位址重定向到新目標，並且更新微處理器10的前端中的表。實際上，分支解碼器18在快速預測器12或BTAC 14處未命中的情況下提供分支預測，其中分支指令在C級轉向目標。在一些情形中，諸如在BTAC 14處針對每次取指存在多於有限或預定最大數量的分支(例如，針對每16位元組取指存在多於三個分支)的情況下，對額外分支的分支預測被延遲直到解碼時間為止。

FIQ/迴圈佇列20接收格式化指令並對其進行緩存，直到它們可被轉譯成微指令為止。FIQ/迴圈佇列20還提供初步解碼和快速迴圈功能(例如，在BTAC迴圈分支上，啟動迴圈佇列並且重複發送迴圈指令)，後者由塊20的右側的箭頭表示。

W級提供可選的額外定時時脈。

在X級，指令轉譯器22 (在X級或轉譯級)將FIQ/迴圈佇列20中所存儲的格式化指令轉譯為微指令。

指令按程式順序被提供給暫存器別名表/保留表(RAT/RS) 24。RAT/RS 24的RAT功能維持和生成針對各指令的依賴性資訊。RAT/RS 24的RAT功能將指令的源和目的地重命名到內部暫存器上，並將指令分派給RAT/RS 24的保留站，該保留站(可能不按照程式順序)向執行單元26發出指令。包括整數單元的功能或執行單元26在級E (執行)執行分支指令。這裡，執行單元、分支單元和整數單元是可互換使用的術語。在一個實施例中，執行單元26(例如，兩個執行單元)在單個時脈週期中執行兩個分支。執行單元26還指示BTAC 14是否已正確地預測了分支指令。

在一個實施例中，將執行的結果提供給重排序暫存器(未示出)，該重排序暫存器包括與已經執行的指令有關的資訊。眾所周知，重排序暫存器在指令發出之後保持指令的原始程式順序，並允許在退出級(retire stage)期間對結果進行序列化。在一個實施例中，可以將重排序暫存器的一些資訊存儲在沿著流水線的其它地方，諸如在解碼器18處等。存儲在重排序暫存器中的資訊可以包括分支資訊，諸如分支的類型、分支模式、目標、預測中使用的表以及快取記憶體替換策略資訊(例如，最近最少使用或LRU)等。

分支表更新28包括級S、W、Y和Z，並且被配置為用與完全解碼和執行的分支指令的資訊(例如，分支的最終結果)來(例如，在S級)對前端的各種表(例如，BTAC、TAGE)進行更新。在級S、W、Y和Z，更新可能涉及表讀取、目標位址寫入以及計數器遞增或遞減，這可能涉及一些延遲。在一個實施例中，分支表更新28針對給定條件分支指令和緩存有該條件分支指令的邊(例如，A、B或C)提供錯誤預測的指示。

現在在繼續參考圖1A的情況下參考圖1B，示出示例快速預測器12以及在針對圖1A的微處理器10所示的分支單元流水線的前端30處使用其它示例源。前端30包括拾取單元32 (例如，包括多工器和時脈暫存器)、轉譯後備暫存器(TLB) 34、指令快取記憶體(I快取記憶體資料) 36、I快取記憶體標籤38 (或標籤陣列)、BTAC 14和快速預測器12。拾取單元32接收多個快取記憶體指令位址源，包括(例如，來自I級的)順序指令位址、(例如，來自S級的)校正指令位址、(例如，來自G級的)解碼時間指令位址以及來自BTAC 14和快速預測器12的位址。拾取單元32的輸出是作為輸入提供給TLB 34、I快取記憶體資料36、I快取記憶體標籤38、BTAC 14和快速預測器12以用於訪問I快取記憶體資料36的下一指令的快取記憶體位址。

在記憶體管理單元(未示出)的管理下，TLB 34提供如已知的虛擬到物理頁位址轉譯。也就是說，TLB 34存儲最近使用的虛擬位址的物理位址。TLB 34從分段單元(其將來自程式的邏輯位址轉換為線性位址)接收線性位址，並且該線性位址的一部分與TLB 34的條目進行比較以查找匹配。如果存在匹配，則根據TLB條目計算物理位址。如果不存在匹配，則拾取來自記憶體的頁表條目並將其放置到TLB 34中。

I快取記憶體資料36包括從L2、L3或主記憶體拾取或預拾取的指令的1級快取記憶體。I快取記憶體資料36包括多個時脈暫存器。

I快取記憶體標籤38包括與I快取記憶體資料36中的指令相對應的標籤的陣列，並且包括多個時脈暫存器，並且用於確定與拾取的快取記憶體指令相關聯的資訊(例如，快取記憶體位址的標籤或部分)與I快取記憶體資料36以及BTAC 14之間的匹配。

以上結合圖1A來解釋BTAC 14，並且該BTAC 14具有多個時脈暫存器和二(2)時脈採取懲罰。也如以上所解釋的，快速預測器12具有零(0)時脈採取懲罰。例如，假設沿著I快取記憶體以每週期16位元組進行拾取，並且假設快取記憶體位址20至快取記憶體位址95的分支指令。注意，本示例中的地址描述暗示了十六進位標記法(例如，0x0、0x10、0x20等)。因此，拾取在快取記憶體位址0、快取記憶體位址10、快取記憶體位址20 (分支指令，但由於BTAC 14跨越多個週期進行讀取和多工因而尚未解決，其中在一些實施例中，該多個週期是與I快取記憶體相同的定時)、快取記憶體位址30 (相對時脈1)、快取記憶體位址40 (相對時脈2)、然後在第3時脈(相對時脈3)上發生，快取記憶體指令拾取被重定向到快取記憶體位址95。因此，在該示例中，採取的分支懲罰包括兩個時脈週期，因為快取記憶體位址30和40發生在分支之後。換句話說，在沒有快速預測器12的情況下，對於該特定設計示例，採取的分支懲罰總是兩個時脈。利用較小和較快的快速預測器12，在上述示例中，快取記憶體位址包括0、10、20和95，並且在快取記憶體地址上沒有延遲且採取的懲罰為零。如上所述，在一些實施例中，可以省略快速預測器12。

現在注意力轉到圖2A，其示出了示例分支預測控制系統40的實施例。在一個實施例中，分支預測控制系統40包括：包括或耦合到條件分支表42(在下文中，簡單地稱為表)的BTAC 14、分支表更新28、控制邏輯44、脫離邏輯46以及快取記憶體條目替換邏輯48。注意，為簡潔起見，這裡省略了流水線的其它部分，然而應該理解，該流水線如以上與圖1A-1B相關聯描述的那樣起作用。在一些實施例中，可以考慮預測控制系統40包括更少或更多的元件。在一個實施例中，表42包括第一邊(A)、第二邊(B)和第三邊(C)，第一邊A和第二邊B各自包括具有多組關聯表的群組(例如，具有不同複雜度全域分支模式的多個表，未示出)的第一條件預測器(或更具體地，對於本實施例，TAGE條件分支預測器(一個用於邊A，一個用於邊B))，第三邊包括具有單個預測器表的條件分支預測器(例如，GSHARE條件分支預測器)。如以上所解釋的，各TAGE條件分支預測器具有比GSHARE條件分支預測器高的複雜度。儘管用單個表42描繪，但是本領域具有通常知識者應該理解，BTAC 14和條件分支預測器(TAGE、GSHARE)這兩者具有多邊的表(各自具有邊A、B和C)。例如，如果分支存在於BTAC 14的邊B，則它也存在於條件預測器的邊B。如圖2A中所示，表42的邊A、邊B各自具有單獨的TAGE條件預測器，而邊C具有gshare條件分支預測器。

簡而言之，將GSHARE條件分支預測器用於邊C，這是因為單個快取記憶體行取指中的兩個或更多個分支是罕見的。兩個TAGE條件分支預測器分別用於條件分支預測器表42的邊A和邊B。一般而言，根據快取記憶體條目替換邏輯48(諸如，最近最少使用(LRU)等)，將第一分支(和第二分支)分配給邊A和邊B。邊A和邊B是獨立的，並且通常包含來自不同快取記憶體取指的分支。然而，存在使用GSHARE條件分支預測器來處理比其它分支指令更難預測的分支指令的情形。例如，邊C的分支指令可能具有每27次被採取一次的更複雜的方向模式，或者可能具有四次採取後七次不採取的重複模式的方向模式。本領域具有通常知識者可以考慮到更複雜的分支方向模式的其它示例。這樣的條件分支指令對於性能也可能是至關重要的(例如，對性能至關重要的緊密迴圈)，從而微處理器的性能進一步妥協，這是因為在使用GSHARE條件分支預測器的這些情形下錯誤預測的風險增加。在沒有校正的情況下，錯誤預測可能隨著數百萬或數十億的週期而再發生，從而導致相應的整體性能下降(例如，高達約20％的性能下降)。分支預測控制系統40透過使用控制邏輯44根據給定的可能性或概率使來自邊C的條件分支預測脫離並將有問題的分支指令寫入邊A或邊B，來解決至少這些情況，其中TAGE條件分支預測器更適合處理更複雜的分支指令。

如圖2A中所示，分支表更新器28向控制邏輯44提供資訊，包括給定條件分支指令是否被錯誤預測以及有問題的(錯誤預測的)條件分支指令是否在邊C。控制邏輯44與脫離邏輯46以及快取記憶體條目替換邏輯48進行協作以將分支指令寫入邊A、B或C。在一個實施例中，下面與圖2B相關聯地進一步描述的脫離邏輯46包括偽隨機生成器，該偽隨機生成器用於向控制邏輯44提供脫離觸發以將錯誤預測的分支指令條目(以一定百分比的次數)寫入邊A或B。快取記憶體條目替換邏輯48包括利用多個已知快取記憶體替換方案其中之一的陣列。例如，在一個實施例中，使用了最近最少使用(LRU)替換演算法。在表42中(例如，在邊C)的條件分支正在被寫入邊A或邊B時以及在邊A或邊B的條件分支被寫入邊C時，控制邏輯44控制位址多工器(未示出)來選擇更新位址。快取記憶體條目替換邏輯48針對邊A、B和C存儲替換資訊。因此，快取記憶體條目替換邏輯48是在表42的各邊之間共用的全域資源。在一個實施例中，替換資訊包括用於指示哪個邊和各邊的哪個路最近最少使用的位元，控制邏輯44使用這些位元來進行對表42的寫入。控制邏輯44還控制對快取記憶體條目替換邏輯48的LRU陣列的更新。

在繼續參考圖2A的情況下將注意力轉向圖2B，其示出了脫離邏輯46的實施例。本領域具有通常知識者根據本發明應當理解，圖2B中所示的示例脫離邏輯46是一個說明性示例，並且在一些實施例中，可以使用不同的電路來進行類似的功能。脫離邏輯46一般被配置為生成偽隨機脫離觸發，即可配置的時間百分比。在一個實施例中，脫離邏輯46包括線性回饋移位暫存器(LFSR) 50、處理邏輯52和特徵控制暫存器(FCR) 54。在一個實施例中，LFSR 50包括饋送至處理邏輯52的七(7)位，在一個實施例中該處理邏輯52包括反相器。注意，使用7位僅是一個示例的說明，並且在一些實施例中，可以使用其它大小的暫存器。實際上，LFSR 50和處理邏輯52產生針對7位元的每個可能值(例如，以偽隨機順序迴圈透過所有2^7狀態(除了所有零的狀態之外))。一部分位元(例如，5位元樣本，儘管不限於此)提供給FCR 54，其選擇從邊C到邊A或B的脫離或寫入(例如，取決於LRU方案)將被觸發的多個可能性或概率值其中之一。在一個實施例中，FCR 54可配置為(例如，透過物理或軟體/微代碼調整)使脫離觸發的可能性或概率為1/128、1/32、1/8、或者甚至為零(關閉)。注意，在一些實施例中，可以使用這些值或比率以及/或者其它值或比率的全部或一部分。例如，在設置為1/32的情況下，存在使邊C能夠在大約3％的時間隨機地脫離的脫離觸發(提供給控制邏輯44)。該隨機機制與每32個週期觸發的簡單計數器相反，因為脫離邏輯46以隨機方式提供該觸發(這避免了與總是防止脫離發生的程式設計代碼的可能的對稱性)。

鑒於以上描述，本領域具有通常知識者應理解，一種分支預測控制方法(在圖3中表示為方法56，並且在一個實施例中由控制邏輯44實現)包括接收分支指令的錯誤預測的指示(步驟58)。方法56判斷錯誤預測的分支指令是否是邊C中的條目(步驟60)。如果“不是”(步驟60為“否”)，則方法56繼續監視錯誤預測的分支指令。如果“是”(步驟60為“是”)，則方法56判斷有問題的分支指令是否是條件分支指令(步驟62)，並且如果“不是”(步驟62為“否”)則返回步驟58，而如果“是”(步驟62為“是”)，則使用以上與圖2B相關聯地描述的脫離邏輯46來實現邊C脫離。應理解，在一些實施例中，方法56的步驟可以在順序上切換或並行進行。

已經描述了分支預測控制系統40(圖2A)和方法56(圖3)的某些實施例，應理解，在微處理器中實現了分支預測控制方法(在圖4中表示為方法64)的一個實施例，該微處理器具有包括多個邊的表，其中該多個邊中的至少第一邊包括具有第一組預測表的第一條件分支預測器，其中該多個邊中的至少第二邊包括具有第二組預測表的第二條件分支預測器，其中第一條件分支預測器具有比第二條件分支預測器高的複雜度。分支預測控制方法64包括接收與針對包括第二邊中的資訊的分支指令的第一預測相對應的錯誤預測的指示(步驟66)；以及基於接收到錯誤預測的指示來將針對分支指令的資訊寫入第一邊(步驟68)。

鑒於以上描述，應理解，在微處理器中實現了分支預測控制方法(在圖5中表示為方法70)的又一實施例，該微處理器具有包括第一邊、第二邊和第二邊的表，第一邊和第二邊中各自包括具有多組關聯表的群組的第一條件分支預測器，第三邊包括具有單個表的第二條件分支預測器，其中第一條件分支預測器各自具有比第二條件分支預測器高的複雜度。分支預測控制方法包括：基於針對包括第三邊中的資訊的分支指令的預測表命中來提供第一預測(步驟72)；接收與針對分支指令的第一預測相對應的錯誤預測的指示(步驟74)；將針對分支指令的資訊寫入第一邊或第二邊其中之一(步驟76)；以及基於針對包括第一邊和第二邊其中之一的資訊的分支指令的預測表命中來提供第二預測，其中基於對第一邊和第二邊其中之一的寫入，減少了分支指令的後續預測表命中的錯誤預測的量(步驟78)。

流程圖中的任何過程描述或塊應理解為表示代碼的模組、段、邏輯或部分(其包括用於在過程中實現特定邏輯功能或步驟的一個或多個可執行指令)，並且替代實現包括在實施例的範圍內，其中如本發明領域具有通常知識者將理解的，功能可以不按所示或討論的順序地執行(包括基本上同時執行或以不同循序執行)，這取決於所涉及的功能。

雖然在附圖和前面的描述中示出並詳細描述了本發明，但這樣的圖和描述應被認為是例示性或示例性的，而不是限制性的；本發明不限於所揭示的實施例。透過研究附圖、揭示內容和所附申請專利範圍，本領域具有通常知識者在實踐所要求保護的發明時可以理解並實現所揭示的實施例的其它變形。

注意，可以使用所揭示的實施例的各種組合，因此參考實施例或一個實施例並不意味著從其它實施例的特徵的使用中排除該實施例的特徵。在申請專利範圍中，單詞“包括”不排除其它元件或步驟。

10:微處理器 12:快速預測器 14:分支目標位址快取記憶體 16:指令位元組佇列 18:分支解碼器 20:格式指令佇列/迴圈佇列 22:指令轉譯器 24:暫存器別名表/保留站 26:執行單元 28:分支表更新器 30:前端 32:拾取單元 34:轉譯後備暫存器 36:I快取記憶體資料 38:I快取記憶體標籤 42:表 44:控制邏輯 46:脫離邏輯 48:替換邏輯 50:線性回饋移位暫存器 52:處理邏輯 54:特徵控制暫存器 56:方法 58-62:步驟 64:方法 66-68:步驟 70:方法 72-78:步驟

參考以下附圖，可以更好地理解本發明的各個方面。不必按比例繪製附圖中的組件，而是將重點放在清楚地例示本發明的原理上。此外，在附圖中，相同的附圖標記在多個視圖中表示相應部件。圖1A是示出實現分支預測控制系統的實施例的微處理器所用的示例分支單元流水線的方塊圖。圖1B是示出圖1A中所示的分支單元流水線的示例前端的示意圖。圖2A是示出示例分支預測控制系統的實施例的示意圖。圖2B是示出在圖2A的分支預測控制系統中使用的示例脫離(escape)邏輯的實施例的示意圖。圖3是示出分支預測控制方法的實施例的流程圖。圖4是示出示例分支預測控制方法的實施例的流程圖。圖5是示出另一示例分支預測控制方法的實施例的流程圖。

70:方法

72:步驟

74:步驟

76:步驟

78:步驟

Claims

一種微處理器，包括：表，其包括多個邊，其中，至少第一邊包括具有第一組預測表的第一條件分支預測器，其中，至少第二邊包括具有第二組預測表的第二條件分支預測器，其中，所述第二條件分支預測器被配置為基於針對包括所述第二邊中的資訊的分支指令的預測表命中來提供第一預測，以及其中，所述第一條件分支預測器具有比所述第二條件分支預測器高的複雜度；以及控制邏輯，其中，基於接收到與針對所述分支指令的第一預測相對應的錯誤預測的指示，所述控制邏輯被配置為將針對所述分支指令的資訊寫入所述第一邊的第一組預測表其中之一。
如請求項1所述的微處理器，還包括偽隨機生成器邏輯，所述偽隨機生成器邏輯被配置為提供用於提示透過所述控制邏輯進行寫入的觸發信號，所述觸發信號根據能夠配置的概率而提供。
如請求項1所述的微處理器，其中該所述能夠配置的概率包括多個可能比率其中之一。
如請求項1所述的微處理器，其中所述第一條件分支預測器被配置為基於針對分支指令的預測表命中來提供第二預測，所述分支指令包括所述第一邊的第一組預測表其中之一中的資訊。
如請求項4所述的微處理器，其中基於對所述第一邊的第一組預測表其中之一的寫入，針對所述分支指令的後續預測表命中的錯誤預測的量減少。
如請求項1所述的微處理器，其中所述第二條件分支預測器包括單個預測表，所述第二條件分支預測器包括GSHARE預測器。
如請求項1所述的微處理器，其中所述第一條件分支預測器包括具有不同分支歷史長度的多個分支預測器表，所述第一條件分支預測器包括標籤幾何預測器即TAGE預測器。
如請求項7所述的微處理器，還包括第二TAGE預測器，所述第二TAGE預測器用於所述多個邊中的第三邊。
如請求項1所述的微處理器，其中所述控制邏輯還被配置為：在與寫入所述第一邊和第二邊其中之一相對應的時間，將與其它分支指令相對應的資訊寫入第三邊。
如請求項9所述的微處理器，其中對要寫入所述第三邊的與所述其它分支指令相對應的資訊的選擇是基於多個不同的快取記憶體條目替換方案其中之一。
一種在微處理器中實現的分支預測控制方法，所述微處理器具有包括多個邊的表，其中，所述多個邊中的至少第一邊包括具有第一組預測表的第一條件分支預測器，其中，所述多個邊中的至少第二邊包括具有第二組預測表的第二條件分支預測器，其中，所述第一條件分支預測器具有比所述第二條件分支預測器高的複雜度，所述分支預測控制方法包括：接收與針對包括所述第二邊中的資訊的分支指令的第一預測相對應的錯誤預測的指示；以及基於接收到所述錯誤預測的指示來將針對所述分支指令的資訊寫入所述第一邊。
如請求項11所述的分支預測控制方法，其中寫入還基於接收到根據能夠配置的概率而提供的、基於偽隨機生成器的觸發信號。
如請求項12所述的分支預測控制方法，其中所述能夠配置的概率包括多個可能比率其中之一。
如請求項11所述的分支預測控制方法，還包括：根據所述第一條件分支預測器基於針對包括所述第一邊中的資訊的分支指令的預測表命中來提供第二預測，與來自所述第二邊的分支指令的預測相比、接收更少的再發生錯誤預測的指示。
如請求項11所述的分支預測控制方法，還包括：在與寫入所述第一邊相對應的時間，將與其它分支指令相對應的資訊寫入所述第二邊。
如請求項15所述的分支預測控制方法，其中對要寫入所述第二邊的與所述其它分支指令相對應的資訊的選擇是基於多個不同的快取記憶體條目替換方案其中之一。
一種在微處理器中實現的分支預測控制方法，所述微處理器具有表，所述表包括第一邊、第二邊和第三邊，所述第一邊和所述第二邊各自包括具有多組關聯表的群組的第一條件分支預測器，所述第三邊包括具有單個表的第二條件分支預測器，其中，所述第一條件分支預測器各自具有比所述第二條件分支預測器高的複雜度，所述分支預測控制方法包括：基於針對包括所述第三邊中的資訊的分支指令的預測表命中來提供第一預測；接收與針對所述分支指令的第一預測相對應的錯誤預測的指示；將針對所述分支指令的資訊寫入所述第一邊和所述第二邊其中之一；以及基於針對包括所述第一邊和所述第二邊其中之一的資訊的分支指令的預測表命中來提供第二預測，其中，基於對所述第一邊和所述第二邊其中之一的寫入，減少所述分支指令的後續預測表命中的錯誤預測的量。
如請求項17所述的分支預測控制方法，還包括：在與對所述第一邊和第二邊其中之一的寫入相對應的時間，將與其它分支指令相對應的資訊寫入所述第三邊。
如請求項17所述的分支預測控制方法，其中所述第二條件分支預測器包括GSHARE預測器。
如請求項17所述的分支預測控制方法，其中所述第一條件分支預測器各自包括標籤幾何預測器即TAGE預測器。