TWI844775B - 快速預測器覆寫方法和微處理器 - Google Patents

Abstract

本申請涉及快速預測器覆寫方法和微處理器。所述微處理器包括：指令快取記憶體，其包括多個高速緩衝位址處的程式設計指令；快速預測器，其被配置為接收與同指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊、並基於快速預測器處的匹配來提供第一階段期間的第一分支預測；以及分支目標位址快取即BTAC，其根據第一階段之後的第二階段的組來進行操作，BTAC被配置為接收與第一分支指令相關聯的資訊並確定第二分支預測，BTAC被配置為通過在與第二階段的組相對應的時間處將與第二分支預測相關聯的分支目標位址寫入快速預測器來覆寫第一分支預測並更新快速預測器。

Description

快速預測器覆寫方法和微處理器

本發明一般涉及微處理器，特別地涉及微處理器中的分支預測。

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

在微處理器中常用的一個分支預測器被稱為分支目標位址快取(branch target address cache，BTAC)。BTAC包括硬體邏 輯，該硬體邏輯使用過去分支指令行為的全域歷史模式以實現對所拾取的分支指令的目標位址的預測。然而，根據微架構，BTAC的分支預測仍可能施加一個或多個時鐘週期的延遲。因此，期望改進分支預測，以改進流水線指令流並因此改進微處理器中的指令執行的速度和效率。

在一個實施例中，一種微處理器，包括：指令快取記憶體，其包括多個高速緩衝位址處的程式設計指令；快速預測器，其被配置為接收與同所述指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊、並基於所述快速預測器處的匹配來提供第一階段期間的第一分支預測；以及分支目標位址快取即BTAC，其根據所述第一階段之後的第二階段的組來進行操作，所述BTAC被配置為接收與所述第一分支指令相關聯的資訊並確定第二分支預測，所述BTAC被配置為通過在與所述第二階段的組相對應的時間處將與所述第二分支預測相關聯的分支目標位址寫入所述快速預測器來覆寫所述第一分支預測並更新所述快速預測器。

在一個實施例中，一種快速預測器覆寫方法，所述方法包括：在快速預測器處接收與同指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊；基於所述快速預測器處的資訊的匹配來提供第一階段期間的第一分支預測；在分支目 標位址快取(branch target address cache，BTAC)處接收與所述第一分支指令相關聯的資訊，所述BTAC根據所述第一階段之後的第二階段的組來進行操作；由所述BTAC基於所述資訊來確定第二分支預測；由所述BTAC利用所述第二分支預測來覆寫所述第一分支預測；以及通過在所述第二階段的組期間將與所述第二分支預測相關聯的分支目標位址寫入所述快速預測器來更新所述快速預測器。

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

10:微處理器

12:快速預測、快速預測器

14:BTAC

16:指令位元組佇列、XIB

18:分支解碼、分支解碼器

20:FIQ/迴圈佇列

22:轉譯、指令轉譯器

24:RAT/RS

26:功能單元、IU

28:分支表更新、分支表更新器

32:拾取單元

34:TLB

36:I高速緩衝資料

14:BTAC

30、40:高速緩衝位址

42:來自拾取單元的高速緩衝位址、來自拾取單元的高速緩衝位址值

44:快速預測器分支預測

46:BTAC陣列讀取

48:BTAC預測以及快速預測器覆寫和更新

50、64:方法

52:快速預測器分支預測的步驟

54:BTAC分支預測的步驟

56:預測不同的步驟

58:高速緩衝重定向的步驟

60:更新快速預測器的步驟

62:下一指令的步驟

66:在快速預測器處接收與同指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊的步驟

68:基於快速預測器處的資訊的匹配來提供第一階段期間的第一分支預測的步驟

70:在分支目標位址快取(BTAC)處接收與第一分支指令相關聯的資訊，該BTAC根據第一階段之後的第二階段的組來進行操作的步驟

72:由BTAC基於資訊來確定第二分支預測的步驟

74:由BTAC利用第二分支預測來覆寫第一分支預測的步驟

76:通過在與第二階段的組相對應的時間處將與第二分支預測相關聯的分支目標位址寫入快速預測器來更新快速預測器的步驟

參考以下附圖，可以更好地理解本發明的各個方面。不必按比例繪製附圖中的組件，而是將重點放在清楚地例示本發明的原理上。此外，在附圖中，相同的附圖標記在多個視圖中表示相應部件。

圖1是示出實現快速預測器覆寫系統的實施例的微處理器所用的示例分支單元流水線的框圖。

圖2A是示出在圖1所示的分支單元流水線的前端處使用以實現快速預測器覆寫系統的實施例的示例快速預測器和其它示例高速緩衝位址源的示意圖。

圖2B是示出快速預測器覆寫系統的實施例的一個示例操作的相對定時的示意圖。

圖3是示出示例快速預測器覆寫方法的實施例的流程圖。

圖4是示出另一示例快速預測器覆寫方法的實施例的流程圖。

公開了微處理器所用的快速預測器覆寫系統和方法的特定實施例，這些實施例使得能夠對快速預測器進行校正、通過分支目標位址快取(BTAC)進行分支預測、並且對快速預測器進行快速更新。在一個實施例中，微處理器包括：前端，其包括基於局部模式歷史來提供分支預測的快速預測器；以及採用BTAC的形式的大預測器，該大預測器提供使用全域模式歷史的分支預測。快速預測器根據如下假設進行操作：如果對於拾取的高速緩衝位址，BTAC的分支預測與較小的快速預測器的分支預測不同，則BTAC的分支預測是主導預測。因此，使用由BTAC提供用於拾取下一快取記憶體指令的目標(例如，指令快取記憶體的目標分支位址)和條件分支的方向(例如，採取、不採取)以取代先前由快速預測器提供的目標和方向，並且在BTAC階段期間，用來自BTAC的目標和方向快速更新快速預測器(例如，表)。

簡而言之，依賴於BTAC進行預測的微架構可能在預測中經歷延遲，並且在不同階段使用兩個預測器的微架構可能直到 執行階段為止或超出執行階段才能夠實現對前一階段預測器的更新。與此相反，本發明的快速預測器能夠實現單週期分支預測，並且如果根據BTAC，快速預測器進行了錯誤預測，則由BTAC使用更精密的預測方案進行覆寫並在BTAC的操作階段之一期間進行更新，從而改進微處理器速度和效率並減少分支預測中的延遲。

在總結了本發明的快速預測器覆寫系統的某些特徵之後，現在將詳細參考如附圖中所示的快速預測器覆寫系統的描述。雖然將結合這些附圖來描述快速預測器覆寫系統，但並不意在將其限制於這裡所公開的實施例。也就是說，雖然本發明易於進行各種修改和替代形式，但是其特定實施例在附圖中通過示例的方式示出，並且這裡將被詳細描述成足以使本領域技術人員理解。然而，應該理解，附圖及其詳細描述不意在將本發明限制於所公開的特定形式。相反，意圖是覆蓋落入如所附權利要求所限定的本發明的精神和範圍內的所有修改、等同項和替代。如在本申請中所使用的，單詞“可以”以允許的意義(即，意味著有可能)、而不是強制的意義(即，意味著必須)使用。類似地，單詞“包括”意味著包括但不限於。

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

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

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

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

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

特別注意圖1的微處理器10的分支單元流水線，微處理器10包括流水線微處理器，在一個實施例中，流水線微處理器的指令集基本上符合x86架構指令集。根據這裡提供的描述，本領域普通技術人員將理解，本發明可以以各種不同的電路結構和架構來實現，並且圖1所示的架構僅僅是許多合適架構其中之一。示例微處理器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快取記憶體，圖1中未示出)的訪問。

快速預測器12包括提供單週期預測(例如，採取一個週期來產生目標位址，在一個實施例中在I階段提供的預測)的單週期分支預測器。在一個實施例中，快速預測器12包括存儲先前執行的分支指令的分支目標位址的表或陣列(或目標陣列)，該表 使得能夠在隨後遇到所存儲的分支指令時進行分支預測。在一個實施例中，表包括128個條目，但是在一些實施例中可以使用其它大小(例如，64個條目、32個條目等)的表。表被組織為n路(例如，n是大於1的整數)的組關聯快取記憶體。在一個實施例中，各條目存儲八(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)計數器以及多位元全域分支歷史。作為另一示例，間接預測包括多條目(例如，1.5k)TAGE預測器，並且將表條目用於靜態間接分支。注意，在一些實施例中，可以使用其它類型的預測機制，包括基於相關性的預測機制。對於指令快取記憶體的快取記憶體行的各部分或拾取量(例如，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表或陣列的寫入。然而，對快速預測器12的更新不會等待那麼長時間，其在BTAC階段期間發生。注意，不在快速預測器12中的分支在兩個週期後在與BTAC階段相對應(例如，在BTAC階段期間)的時間被寫入快速預測器12。

XIB 16是條目佇列，其中各條目保持來自指令快取記憶體的16個位元組的資料。例如，來自XIB 16的高速緩衝資料僅僅是採用16個位元組的塊的指令位元組流，並且在給定指令具有可變長度的情況下，不知道給定x86指令在流內或在給定塊內開始或結束於何處。XIB 16包括用以確定和標記各指令在流內的 開始和結束位元組、從而將位元組流分解成x86指令流的已知邏輯，其中該x86指令流被提供給FIQ/迴圈佇列20並存儲在FIQ/迴圈佇列20中以供微處理器流水線的其餘部分處理。在L(長度)階段，XIB 16確定指令長度。在M(mux)階段，XIB通過多路複用給出指令，並在F(格式)階段將其遞送至分支解碼器18。與多階段分支解碼器有關的更多資訊可以在美國專利號8,473,862中找到，該文獻通過引用而整體併入。

在F階段，指令被格式化。在一個實施例中，格式化指令包括基本上符合x86架構指令集的指令。另外，在F階段判斷給定指令是否是分支。(例如，在最初啟動時)在快速預測器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還指示BTAC 14是否已正確地預測了分支指令。

分支表更新28包括階段S、W、Y和Z，並且被配置為用完全解碼和執行的分支指令(例如，分支的最終結果)來(例如，在S階段)對前端的各種陣列或表(例如，BTAC、間接、TAGE)進行更新。在階段S、W、Y和Z的更新可能涉及陣列讀取、目標位址寫入以及計數器遞增或遞減，這可能涉及一些延遲。

現在在繼續參考圖1的情況下參考圖2A，示出示例快速預測器12以及在針對圖1的微處理器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的條目進行比較以查找匹配。如果存在匹配，則根據TLB條目計算物理位址。如果不存在匹配，則拾取來自記憶體的頁表條目並將其放置到TLB中。

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

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

以上結合圖1來解釋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，並且在快取記憶體地址上沒有延遲且採取的懲罰為零。

在繼續參考圖1至2A的情況下，注意圖2B，該圖2B示意性地示出快速預測覆寫系統的一個示例操作的定時。本領域普通技術人員應當理解，一些實施例可以使用不同的定時/階段方法來操作，因此預期在本發明的範圍內。示出定時標度40(雙箭頭以反映正在進行的時間中的快照)，並且該定時標度40包括逐漸前進的時鐘定時(clk0、clk1、clk2、clkc3等)以及前端30的相應階段(例如，C、I、B、U)。在一個示例操作中，拾取單元32 在clk0的階段C通過選擇由上述的各種源提供的多個位址其中之一來輸出拾取或高速緩衝位址值(42)，其中該多個位址包括(經由加法器的)下一順序拾取位址、由BTAC 14提供的預測分支目標位址、由快速預測器12提供的預測分支目標位址，由功能(執行)單元26提供的校正目標位址以及由分支解碼器18提供的分支目標位址(解碼時間)。如已知的，控制邏輯控制拾取單元32以基於例如方向預測和所預測的分支指令的類型來選擇拾取單元32的輸入其中之一。

回應於拾取單元32所輸出的拾取或高速緩衝位址，I高速緩衝標籤38中的命中提示對I高速緩衝資料36和BTAC 14的訪問。此時(I階段，clk1)，快速預測器12提供分支預測(44)，並且在階段I和B(clk1和clk2)實現BTAC陣列讀取(46)。在一個實施例中，快速預測器12判斷在快速預測器12中是否存在比對I高速緩衝資料36和BTAC 14的訪問早的標籤匹配和有效條目。快速預測器12針對各時鐘預測多個分支(例如，針對各時鐘預測三個或更多個分支)。例如，在快速預測器包括根據16組8路佈置的128個條目的實施例中，快速預測器可以針對各時鐘預測多達8個分支。因此，在單個時鐘週期內，快速預測器12讀取一組的八(8)個條目並與(例如，從拾取單元32輸出的)輸入高速緩衝位址進行比較以判斷是否存在標籤匹配和有效條目，檢查分支類型(例如，條件、無條件等)，選擇(多路複用)有效的、預測採取的第一分支(並且該第一分支是尚未通過該階段的位址)， 並在沒有懲罰的情況下重定向緩存位址。

在U階段(clk3)，BTAC 14可以覆寫快速預測器12，更新快速預測器，並提供其自己的預測(48)。在一些實施例中，更新可以發生在接近U階段的不同時間(例如，在BTAC陣列讀取期間(例如，在階段B)，或在階段U之後但在執行階段之前)。如上所述，BTAC 14比快速預測器12大，並且使用基於全域分支模式的預測機制，而快速預測器使用不太複雜的局部分支模式(例如，三位元長)。在一個實施例中，當快速預測器12和BTAC 14之間的預測存在差異時，BTAC 14總是覆寫快速預測器12，並且更新發生在兩個週期後(例如，在U階段，與執行後階段的更新相反)。作為示例操作，假設快速預測器12預測為不採取，但是BTAC 14預測為採取。BTAC 14將高速緩衝位址改變為採取分支的目標。如果快速預測器12預測為採取、但BTAC 14預測為不採取，則高速緩衝位址的重定向是到順序路徑。儘管罕見，但後一動作可能施加在沒有快速預測器12的情況下通常不可能發生的懲罰。為了緩解這種情況，快速預測器系統的特定實施例包括快速預測器12偏向為不採取。如上所述，快速預測器12包括條件預測器以及包含八(8)個3位元數目器的多個陣列條目，其中條件預測器與陣列並行地被訪問，並為條件分支提供採取/不採取的方向。快速預測器12可以通過要求特定數量的預測採取判斷在預測時提供足夠置信度而偏向於不採取。例如，計數器可被配置為作為簡單的例示而要求八分之六的預測採取以自信地呈現 預測採取。用以實現偏差的實際數字或比率可能不同，這裡僅為了例示而給出為八分之六。此外，計數器的進程也被修改為偏向於不採取預測。例如，對於不採取預測，計時器可以以比遞增(例如，遞增1)更快的速率遞減(例如，遞減2)。

在描述了快速預測器覆寫系統的特定實施例之後，應當理解，圖3中表示為方法50的示例快速預測器覆寫方法的一個實施例包括提供分支預測(52)的快速預測器12(圖2A)、提供分支預測(54)的BTAC 14(圖2A)、以及判斷是否不同意快速預測器的分支預測(56)的BTAC 14(圖2A)。如果不同意快速預測器的分支預測(在56處為“是”)，則BTAC 14通過提供指令高速緩衝重定向(58)、更新分支預測器表(60)來覆寫快速預測器12，然後拾取下一指令(62)。如果BTAC 14同意快速預測器分支預測(在56處為“否”)，則拾取下一指令(62)。

在描述了快速預測器覆寫系統的特定實施例之後，應當理解，圖4中表示為方法64的另一示例快速預測器覆寫方法的一個實施例包括：在快速預測器處接收與同指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊(66)；基於快速預測器處的資訊的匹配來提供第一階段期間的第一分支預測(68)；在分支目標位址快取(BTAC)處接收與第一分支指令相關聯的資訊(70)，該BTAC根據第一階段之後的第二階段的組來進行操作；由BTAC基於資訊來確定第二分支預測(72)；由BTAC利用第二分支預測來覆寫第一分支預測(74)；以及通過在與第二階 段的組相對應的時間處(例如，在第二階段的組期間)將與第二分支預測相關聯的分支目標位址寫入快速預測器來更新快速預測器(76)。以上為了匹配的目的而引用的資訊至少包括標籤。

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

雖然在附圖和前面的描述中示出並詳細描述了本發明，但這樣的圖和描述應被認為是例示性或示例性的，而不是限制性的；本發明不限於所公開的實施例。通過研究附圖、公開內容和所附權利要求，本領域技術人員在實踐所要求保護的發明時可以理解並實現所公開的實施例的其它變形。

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

50:方法

52:快速預測器分支預測的步驟

54:BTAC分支預測的步驟

56:預測不同的步驟

58:高速緩衝重定向的步驟

60:更新快速預測器的步驟

62:下一指令的步驟

Claims (18)

1. 一種微處理器，包括：指令快取記憶體，其包括多個高速緩衝位址處的程式設計指令；快速預測器，其被配置為接收與同所述指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊、並基於所述快速預測器的條目處的所述資訊的匹配來在第一時鐘週期期間輸出包括第一方向以及第二快取位址的第一分支預測，所述快速預測器經配置以在單一時鐘週期期間完整地接收所述資訊並輸出所述第一分支預測；以及分支目標位址快取(branch target address cache，BTAC)，被配置為接收與所述第一分支指令相關聯的資訊並基於所述BATC的條目處的所述資訊的匹配來確定包括第二方向以及第三快取位址的第二分支預測，其中基於所述第一分支預測與所述第二分支預測之間的差值，所述BTAC被配置為將所述第三快取地址作為分支目標位址寫入所述快速預測器的所述條目處來覆寫所述第一分支預測並更新所述快速預測器，其中所述BATC被配置為在所述第一時鐘週期後的兩個週期更新所述快速預測器，所述BATC被配置為在BTAC的三個操作階段使用的三個連續時鐘期間完整地接收所述資訊、覆寫所述第一分支預測以及更新所述快速預測器以基於所述資訊提供所述第二分支預測，其中所述第一時鐘週期與所述三個連續時鐘週期期間中的第一個時鐘周期重疊。
2. 如請求項1所述的微處理器，其中，所述快速預測器包括具有多個第一表條目的表，所述表具有n路的組關聯組織，以及所述BTAC包括具有多個第二表條目的一組表，所述一組表具有m路的組關聯組織，所述多個第二表條目在數量上大於所述多個第一表條目，並且n和m皆為大於1的整數。
3. 如請求項2所述的微處理器，其中，所述快速預測器包括條件分支預測器。
4. 如請求項1所述的微處理器，其中，所述快速預測器包括零採取懲罰，以及所述BTAC包括二時鐘採取懲罰。
5. 如請求項1所述的微處理器，其中，所述快速預測器和所述BTAC各自能夠進行多個類型的分支預測。
6. 如請求項1所述的微處理器，其中，所述資訊至少包括標籤，以及所述快速預測器被配置為同時將當前指令拾取的標籤與所述快速預測器的相應表條目的標籤進行比較以確定所述匹配。
7. 如請求項1所述的微處理器，其中，所述快速預測器使用分支預測方向偏向於不採取的局部模式歷史。
8. 如請求項7所述的微處理器，其中，所述快速預測器包括條件分支預測器和計數器，所述計數器根據所述偏向以與遞增的方式不同的方式遞減。
9. 如請求項8所述的微處理器，其中，所述計數器包括三位元數目器。
10. 如請求項1所述的微處理器，其中，所述第一分支預測基於局部分支模式，以及所述第二分支預測基於全域分支模式。
11. 如請求項1所述的微處理器，其中所述更新包括對於所述第一方向的更新。
12. 如請求項1所述的微處理器，其中所述BTAC被配置為藉由基於所述第三快取地址提供快取指示重定向來覆寫。
13. 一種快速預測器覆寫方法，所述方法包括：在快速預測器處接收與同指令快取記憶體的第一高速緩衝位址相對應的第一分支指令相關聯的資訊；基於所述快速預測器的條目處的所述資訊的匹配來在第一時鐘週期期間輸出包括第一方向以及第二快取位址的第一分支預測，所述快速預測器經配置以在單一時鐘週期期間完整地接收所述資訊並輸出所述第一分支預測；在分支目標位址快取(branch target address cache，BTAC)處接收與所述第一分支指令相關聯的資訊；由所述BTAC基於所述BATC的條目處的所述資訊的匹配來確定包括第二方向以及第三快取地址的一第二分支預測；以及基於所述第一分支預測與所述第二分支預測之間的差值；由所述BTAC利用所述第二分支預測來覆寫所述第一分支預測；以及 通過於所述第一時鐘週期後的兩個週期將所述第三快取地址作為分支目標位址寫入所述快速預測器的所述條目處來更新所述快速預測器，所述BATC的所述接收、確定、覆寫以及更新被完整地執行於所述BTAC的三個操作階段使用的三個連續時鐘期間，以基於所述資訊提供所述第二分支預測，其中所述第一時鐘週期與所述三個連續時鐘週期期間中的第一個時鐘周期重疊。
14. 如請求項13所述的方法，其中，所述資訊至少包括標籤，以及所述快速預測器被配置為同時將當前指令拾取的標籤與所述快速預測器的相應表條目的標籤進行比較以確定所述匹配。
15. 如請求項13所述的方法，其中，所述第一分支預測基於分支預測方向偏向於不採取的局部模式歷史，以及所述第二分支預測基於全域模式歷史。
16. 如請求項15所述的方法，其中，所述快速預測器包括條件分支預測器和計數器，所述計數器根據所述偏向、相對於遞增而進行遞減。
17. 如請求項13所述的方法，其中所述更新包括對於所述第一方向的更新。
18. 如請求項13所述的方法，其中所述BTAC被配置為藉由基於所述第三快取地址提供快取指示重定向來覆寫。