實現現代處理器間接轉移預測的裝置及方法
2023-04-25 21:48:01
專利名稱：實現現代處理器間接轉移預測的裝置及方法
技術領域：
本發明涉及現代微處理器及其應用系統的設計，尤其涉及實現現代處理器間接轉移指令預測的裝置及方法。
背景技術：
現代高性能處理器利用分支指令預測技術開發指令級並行，從而提高處理器性能。之前的研究主要集中在開發高準確率的直接轉移指令預測技術，而對於間接轉移指令預測，通常很難達到較高的準確率。近年來，隨著面向對象語言程序的廣泛應用，間接轉移指令使用的場合也更多了起來。該類型指令通常用於實現虛函數指針、函數指針以及 Switch-Case語句等常見的數據結構。此外，Intel Pentium M處理器中也已經加入了專用的間接轉移預測部件。因此，提高間接轉移預測的準確率，對處理器性能的提升具有重要意義。間接轉移指令的轉移目標地址保存在其指令指定的寄存器中，該寄存器中的值可能會隨著程序的執行而發生各種變化，即可能存在多個轉移目標地址。現代處理器通常使用分支目標緩衝器(BTB，Branch Target Buffer)和方向預測器對分支指令進行預測。其中，BTB用來負責記錄分支轉移指令的目標地址，而方向預測器則用來預測該分支轉移指令執行的方向，即預測是否進行轉移。然而，這種傳統的分支轉移預測方式對直接轉移有著很高的分支轉移預測效率，但是對間接轉移指令的預測準確率卻很低。首先，是由於方向預測器總是預測跳轉與否(在使用預解碼的處理器中，間接轉移指令必定會跳轉，故分支方向預測器不必對該類指令的方向進行預測)；其次，由於BTB結構是一種緩存(Cache)結構， 其記錄的每個目標地址只能使用指令地址進行索引，即每個分支指令最多只有一個目標地址與之對應，如圖1所示。因此，BTB結構只能記錄最近一次間接轉移指令的目標地址。當間接轉移指令擁有多個目標地址時，BTB的預測準確率會很低。已有的一些使用專用部件的間接轉移預測技術，可以有效地提升間接轉移預測準確率。Chang等人提出的TTC結構，使用記錄在全局歷史寄存器(GHR，Global History Register)中的分支轉移歷史信息區分不同的間接轉移場景，並使用一個類似Cache結構的專用結構記錄各個間接轉移場景下間接轉移目標地址及其索引，如圖2所示，其設計類似兩級分支預測方案(即異或器XOR前的一級與XOR後的一級)。當取得一條間接轉移指令時，TTC預測器(其結構如圖2所示右端)通過異或器XOR獲取程序計數器(PC)和分支轉移歷史信息(GHR)的異或值作為索引，獲得預測的目標地址。當該間接轉移指令提交時， 使用正確的目標地址更新對應的TTC項。通過組合使用多個目標地址預測器，Driesen等人提出了另一種直接地址預測技術，即Cascade預測器。該方法對於可簡單預測(只有一個目標地址)的間接轉移指令使用簡單的一級預測器預測(通常為BTB結構)，而對於擁有多個目標地址的間接轉移指令，使用複雜的二級或多級預測器進行預測。kznec和Michaud提出了與該設計非常類似的一種預測器，由一個基礎預測器及一系列能夠捕捉非常長的歷史信息的預測表組成；在預測時，選擇歷史信息最長的預測表中的命中項值作為輸出結果。虛擬程序計數器(VPC，Virtual Program Counter)預測技術，側重於使用已有的條件轉移預測部件進行間接轉移預測，它是將一條具多個目標地址的間接轉移指令的每個目標地址等價地表示成一個虛擬的條件分支轉移指令的轉移目標地址；當進行間接轉移指令預測時，VPC每個周期以不同的虛擬分支指令循環訪問條件分支預測器，如圖3所示，直到一條虛擬指令被預測為發生或達到循環訪問的上界時才停止預測。該VPC技術的效果， 與流水線的長度以及間接轉移目標地址的數目密切相關。以上研究提出的基於硬體的間接轉移預測技術，使用分支轉移歷史信息(GHR)區分不同的間接轉移場景，並直接將對應不同轉移場景的目標地址保存在一個專用的存儲部件中。這種使用專用部件一類技術的預測速度較快，但其額外的存儲單元需求會在晶片中佔用一定面積，並產生大量的能耗。而側重使用已有分支預測部件的VPC技術雖可以取得較高的預測準確率，但這種需要多次循環才能完成一次間接轉移的預測，一方面會阻礙處理器性能的進一步提升，另一方面會帶來更多的能耗開銷，從而導致處理器的能效性降低。
發明內容
本發明所要解決的技術問題是提供一種實現現代處理器間接轉移預測的裝置及方法，能夠在提高預測準確率的同時提高處理器的能效性。為了解決上述技術問題，本發明提供了一種實現現代處理器間接轉移預測的裝置，其特徵在於，包括分支方向預測器、目標地址映射裝置以及分支目標緩衝器，其中分支方向預測器，用於根據定義的多個子預測器預測的間接轉移方向生成目標指針；目標地址映射裝置，用於將分支方向預測器生成的目標指針映射為索引分支目標緩衝器的虛擬地址；分支目標緩衝器，用於為間接轉移指令分配目標地址項和分配項，其中，目標地址項通過虛擬地址索引；分配項記錄每一間接轉移指令目標地址項的使用情況，通過程序計數器的值索引。進一步地，目標地址映射裝置包括目標指針寄存器、虛擬地址映射器以及第一多選器，其中分支方向預測器根據定義的4個子預測器預測的間接轉移方向生成4位目標指針；目標指針寄存器，用於保存分支方向預測器生成的4位目標指針；虛擬地址映射器，用於根據目標指針寄存器保存的4位目標指針通過計算映射式 FA = f (PC，TP)生成索引目標地址項的虛擬地址；式中，TP為目標指針，FA為虛擬地址，PC 為程序計數器的值；第一多選器，用於選擇通過所述PC訪問分配項的第一索引和通過虛擬地址訪問目標地址項的第二索引。進一步地，虛擬地址映射器包括第一異或器和第二異或器，其中第一異或器用於將所述PC 的最高4位與4位目標指針相異或；第二異或器用於將PC的最低4位與一個常數相異或；將第一異或器和第二異或器的結果組合，構成虛擬地址；或者，虛擬地址映射器包括第一加法器和第二加法器，其中第一加法器用於將PC 的最高4位與4位目標指針相加；第二加法器用於將PC的最低4位與一個常數相加；將第一加法器和第二加法器的結果組合，構成虛擬地址。進一步地，目標地址映射裝置還包括訓練循環計數器和第二多選器，其中訓練循環計數器，用於輸出循環計數值；第二多選器，用於在預測時選擇輸出目標指針寄存器生成的目標指針，在出現預測錯誤時選擇輸出訓練循環計數器輸出的循環計數值作為更新的目標指針；虛擬地址映射器根據第二多選器輸出的目標指針，通過計算映射式生成虛擬地址。進一步地，分支目標緩衝器中分配項的記錄用於作為遍歷間接轉移指令全部已分配的目標地址項的依據，遍歷情況用於作為更新分配項或目標指針的依據；遍歷情況及其更新包括以下三種中任意一種第一種，遍歷時一旦出現使用一個目標指針訪問分支目標緩衝器而未命中的情況，則將分配項中的對應位更新為未使用狀態；第二種，遍歷時如果一個目標地址項中的目標地址與正確的目標地址相同，則更新相應的目標指針指向該目標地址項，將正確目標指針的對應位作為訓練目標進行訓練；第三種，遍歷時如果遍歷全部已分配的目標地址項後，沒有找到與正確地址匹配的目標地址項，則根據分配項中記錄的信息，隨機地分配一個新的目標地址項或替換一項已使用的目標地址項來記錄正確的目標地址，並更新相應的目標指針指向該目標地址項， 以及訓練分支方向預測器。為了解決上述技術問題，本發明提供了一種實現現代處理器間接轉移預測的方法，涉及分支方向預測器和分支目標緩衝器，該方法包括在分支方向預測器中定義多個子預測器，每一個子預測器預測的間接轉移方向作為目標指針的每一位，通過目標指針映射生成索引分支目標緩衝器的虛擬地址；在分支目標緩衝器中為每一間接轉移指令分配目標地址項和分配項，其中，目標地址項通過目標指針映射的虛擬地址索引；分配項用於記錄每一間接轉移指令目標地址項的使用情況，並通過程序計數器的值索引。進一步地，當處理器獲取一條間接轉移指令要進行預測時，同時執行以下步驟通過程序計數器的值訪問分支目標緩衝器；若訪問命中，則將命中項作為該間接轉移指令的分配項；否則，暫停取指，直到在流水線中獲得實際的間接轉移目標地址為止；通過分支方向預測器中定義的4個子預測器獲得4位目標指針，通過計算映射式 FA = f (PC，TP)生成虛擬地址；在該計算映射式中，該TP為4位目標指針，該FA為生成的虛擬地址，該PC為程序計數器的值。進一步地，該方法還包括在預測的下一周期，使用虛擬地址再次訪問分支目標緩衝器，以獲得預測的間接轉移目標地址。進一步地，該方法還包括
在出現預測錯誤時選擇一訓練循環計數器輸出的循環計數值作為更新的目標指針；分支目標緩衝器將分配項作為遍歷間接轉移指令全部已分配的目標地址項的依據，遍歷情況用於作為更新所述分配項或目標指針的依據；遍歷情況及其更新包括以下三種中任意一種第一種，遍歷時一旦出現使用一個目標指針訪問分支目標緩衝器而未命中的情況，則將分配項中的對應位更新為未使用狀態；第二種，遍歷時如果一個目標地址項中的目標地址與正確的目標地址相同，則更新相應的目標指針指向該目標地址項，將正確目標指針的對應位作為訓練目標進行訓練；第三種，遍歷時如果遍歷全部已分配的目標地址項後，沒有找到與正確地址匹配的目標地址項，則根據分配項中記錄的信息，隨機地分配一個新的目標地址項或替換一項已使用的目標地址項來記錄正確的目標地址，並更新相應的目標指針指向該目標地址項， 以及訓練分支方向預測器。本發明提供的現代處理器實現間接轉移預測的裝置及方法實施例，使用指針結構，並融入快速、高準確率的分支方向預測器，將其進行拓展和重定義；通過指針結構並使用計算方式替代原有的存儲方式可以快速索引到BTB中的目標地址，在不需要大容量存儲結構支持的基礎上，以與已有的間接轉移預測技術類似的時間代價，換取同時提高預測準確率和處理器能效的效果，且能有效地避免存儲目標地址易出現的錯誤。
圖1為現有的BTB結構的目標地址預測機制示意圖；圖2為現有的TTC結構與BTB關係示意圖(左)以及TTC內部結構示意圖(右)；圖3為現有的採用VPC技術的預測流程圖；圖4為本發明的間接轉移預測的裝置及方法中目標指針映射關係示意圖；圖5為現有的O-GEHL預測器原有結構示意圖；圖6為本發明的間接轉移預測裝置實施例的結構示意圖；圖7是在本發明的間接轉移預測裝置實施例中O-GEHL預測器的改進結構示意圖；圖8為是用來說明如何使用本發明的間接轉移預測裝置及方法而給出的間接轉移指令的程序實例；圖9為本發明的間接轉移預測的方法實施例的流程。
具體實施例方式以下結合附圖和優選實施例對本發明的技術方案進行詳細地說明。應當理解，此處所描述的具體實施例僅用以解釋本發明，並不用於限定本發明的技術方案。本發明提供的實現現代處理器間接轉移預測的方法及裝置，具有以下三個關鍵佔.
^ \\\ ·1)如何將同一間接轉移指令的多個目標地址存入目標地址預測結構中；2)如何辨識不同的間接轉移場景，並與目標地址相對應；
3)當發生預測錯誤時如何進行更新。針對上述三個問題，本發明分別採用以下方式予以解決本發明在取得一條間接轉移指令時，通過經重定義的分支方向預測器識別間接轉移場景，從而生成目標指針；通過目標指針映射到同一間接轉移指令的多目標地址，如圖4 所示。發現預測錯誤時，更新重定義的分支方向預測器，以生成正確的目標指針。(1)間接轉移場景的映射每一種間接轉移場景與一個目標指針相對應，即建立間接轉移場景與目標指針之間的映射關係。為了適應高性能的分支預測結構，本發明採用了一種簡單而高效的方法來生成目標指針，即在現有的分支方向預測器構建數個較小的同類型預測器，被稱為子預測器，請參見圖7，其運行機制與原有的分支方向預測器相同，但使用較少的歷史信息。本發明將每個子預測器的輸出「跳轉/不跳轉」的方向，定義為目標指針寄存器的每一位的「1/0」。由此， 生成4位的目標指針需要4個子預測器。換言之，本發明通過使用4個獨立的小預測器來獲得4位的目標指針預測值。對於條件轉移指令，其預測方式不受本發明在分支方向預測器中的子預測器的影響，與原有的預測機制相同。由於本發明依賴於分支方向預測器通過目標指針對間接轉移目標進行預測，因此高準確率的分支方向預測器對本發明有著積極的影響。下面以一種現有的基於計算處理的分支方向預測器O-GEHL為例，具體介紹本發明的間接轉移預測結構中對間接轉移場景映射的實現。等人提出的O-GEHL分支方向預測器(以下簡稱O-GEHL預測器)的結構如圖5所示，具有使用100 200位(bit)長的全局轉移歷史信息，故對條件轉移指令的預測具有相當高的準確率。該O-GEHL預測器實現了 n+1個由不同轉移歷史長度索引的預測表(ΡΗΤΟ η)。 其中，預測表中每一項為一個4位(或5位)飽和計數器。各預測表用於生成索引的轉移歷史信息長度形成一個幾何序列，L(j) = α ^1L(I) (1 < j < η)。該索引機制可同時捕捉距離當前條件轉移指令非常近和非常遠的轉移歷史信息，並通過使用動態歷史調整和動態閾值調整技術，取得更高的預測準確率。O-GEHL預測器在進行條件轉移預測時，將各個預測表的輸出相加，如果結果為正，則預測跳轉；否則預測不跳轉，即是否跳轉的方向取決於加法運算的符號。在更新時，向實際運算結果方向自增或自減，直至到達各個預測表飽和計數值閾值。本發明基於O-GEHL預測器的間接轉移場景映射具體實現方法如下將O-GEHL預測器中預測表分為4組，每組預測表組成一個O-GEHL子預測器，請參見圖6所示；其中，每個O-GEHL子預測器預測1位目標指針，共形成4位目標指針。考慮到子預測器相對原有的O-GEHL預測器使用的預測表數目較少，為了保證 O-GEHL預測機制的高預測準確率，每個子預測器只使用距離當前間接轉移指令最近的32 位轉移歷史信息生成預測表索引，預測表索引生成算法與O-GEHL機制相同。現有的基於計算處理的O-GEHL預測器由於使用更長的歷史信息，並通過計算方式減少別名衝突問題帶來的影響，因而方向預測準確率更高。對於這類預測器，目標指針不是直接保存在預測表中，而是通過計算方式形成；由此可避免因存儲顯著改變參與計算的參數值使計算結果發生改變而導致的預測錯誤。例如，如果將目標指針『 1000』直接存儲在某個預測表的表項中，則可能會出現將『0000』改為『1000』的情況，亦即將計算參數由0改變為_8，該改變可能會造成計算結果符號的改變，從而影響原有的預測機制，造成條件轉移預測錯誤。當然，本發明的間接轉移場景映射不限於基於O-GEHL預測器，也可以基於類似的其它分支方向預測器實現映射。(2)同一間接轉移指令的多目標地址映射區別於傳統的BTB結構，本發明的間接轉移預測的裝置結構中一條間接轉移指令佔用多個BTB項，從功能上將這些項劃分為目標地址項(圖中可簡稱目標項)和分配項。目標地址項用於存儲一條間接轉移指令的目標地址，每個目標地址項由目標指針生成的虛擬地址進行索引。隨著程序的運行，根據該條間接轉移指令出現過的目標地址動態地分配目標地址項。通過以往分析和評測結果表明，大多數評測程序中一條間接轉移指令的目標地址不會超過16個。基於此種情況，本發明為一條間接轉移指令最多分配16個目標地址項。如果一條間接轉移指令的目標地址超過16個，則將最新遇到的目標地址替換已有的目標地址項，即以最新遇到目標地址來刷新一已有的目標地址項。由於程序運行時可能佔用多個目標地址項，本發明通過分配項來記錄每個間接轉移指令目標地址項的使用情況。譬如通過一個16位或更多位的寄存器作為分配項，其中每一位對應於間接轉移指令的一目標地址項的使用情況，如值1為使用，值0為未使用。為了在預測時儘快確認BTB中是否存在該間接轉移指令的目標地址項，分配項在BTB中使用PC 直接索引。在本發明的間接轉移預測的裝置實施例中，創建目標指針，該目標指針指向BTB 中存儲的目標地址項，以此實現目標地址的映射。每個目標指針對應一個目標地址項，因此對於一個間接轉移指令，最多可擁有16個目標指針。這些指針譬如使用4位數值表示。其中，每個目標指針(TP，Target Pointer)用以生成索引每個目標地址項的虛擬地址(FA，Fake Address)，該虛擬地址的位數與PC相同。不同的目標指針會生成不同的FA， 即 FA = f (PC, TP)。一種簡單的映射方式是將PC的最高4位和最低4位分別與目標指針以及一個常數異或。當然，也可以採用將PC的最高4位和最低4位分別與目標指針以及一個常數相加的映射方式。這種通過計算處理實現映射的方式可以將生成的FA廣泛地散列分布在BTB 中，以減少間接轉移目標之間的衝突以及與條件轉移目標之間的衝突。(3)更新機制更新時，每個子預測器將目標指針的對應位作為該預測器的訓練目標進行更新。如果間接轉移指令提交時發現預測正確，本發明對BTB的操作與條件轉移指令更新BTB時相同。一旦發現預測錯誤，本發明需要更新子預測器以生成正確的目標指針，以使間接轉移場景映射到BTB中正確的目標地址項。預測通常會產生如下兩類錯誤1)目標指針錯誤BTB中一個目標地址項已存放了正確的間接轉移地址，但目標指針映射到了其他目標地址項；該情況主要是由於分支方向預測器中條件轉移方向預測與目標指針預測的別名衝突所致。2)目標指針無意義BTB中沒有目標地址項存儲正確目標地址，因此目標指針無意義；該情況主要是由於BTB中記錄間接轉移目標地址時的義務失效所致。為了能夠區分上述兩種情況並據此更新分配項，本發明需要根據分配項中的記錄，遍歷BTB中該間接轉移指令全部已分配的目標地址項。該遍歷過程可能需要多個周期完成。然而，由於本發明只需訪問那些已分配的目標地址項(根據分配項中記錄的信息確定)，它相比於VPC技術需要遍歷全部間接轉移目標地址存儲項而言，已較大幅降低了更新所需花費的時間代價。本發明在上述遍歷過程中通過依次生成目標指針映射到虛擬地址(FA)，遍歷BTB 中已分配的目標地址項1)分配項的更新遍歷時，一旦出現某個FA訪問BTB失效的情況，說明其索引的目標地址項已被其它分支指令替換，此時需要將分配項中的對應位更新為未使用狀態。2)指針錯誤情況更新如果某個目標地址項中的目標地址與正確目標地址相同，則更新目標指針來指向該目標地址項由於每個子預測器的更新機制與原有預測器的更新機制相同，故只需將正確目標指針的對應位作為訓練目標進行訓練即可。3)無意義指針情況更新如果遍歷全部的地址仍沒有發現與正確地址匹配的目標地址項，則需要根據分配項中的信息，隨機分配一個新的目標地址項或替換一個已使用的目標地址項來記錄正確的目標地址，並訓練分支方向預測器。本發明提供的間接轉移預測的裝置實施例，其結構如圖7所示，包括分支方向預測器、目標地址映射裝置(圖7中虛線所框部分)以及BTB，其中分支方向預測器，用於根據定義的多個子預測器預測的間接轉移方向生成目標指針；目標地址映射裝置，用於將分支方向預測器生成的目標指針映射為索引BTB中目標地址項的虛擬地址；BTB，用於為間接轉移指令分配目標地址項和分配項，其中，目標地址項通過所述虛擬地址索引；分配項記錄每一間接轉移指令目標地址項的使用情況，通過PC的值索引。在圖7中所示的目標地址映射裝置實施例中，包括目標指針寄存器、虛擬地址映射器以及第一多選器，其中分支方向預測器根據定義的4個子預測器預測的間接轉移方向生成4位目標指針；目標指針寄存器，用於保存分支方向預測器生成的4位目標指針；虛擬地址映射器，用於根據目標指針寄存器保存的4位目標指針通過計算映射FA =f(PC, TP)生成索引目標地址項的虛擬地址，式中TP為目標指針，FA為虛擬地址，PC為程序計數器的值；第一多選器，用於選擇通過PC的值訪問BTB中分配項的第一索引和通過虛擬地址訪問BTB中目標地址項的第二索引。在圖7中所示的目標地址映射裝置實施例中，虛擬地址映射器包括第一異或器和第二異或器，其中第一異或器用於將PC的最高4位與目標指針相異或；第二異或器用於將PC的最低4位與一個常數相異或；將第一異或器和第二異或器的結果組合，構成虛擬地址；或者，虛擬地址映射器包括第一加法器和第二加法器，其中第一加法器用於將PC 的最高4位與目標指針相加；第二加法器用於將PC的最低4位與一個常數相加；將第一加法器和第二加法器的結果組合，構成虛擬地址。在圖7中所示的目標地址映射裝置實施例中，還包括訓練循環計數器和第二多選器，其中訓練循環計數器，用於輸出循環計數值；第二多選器，用於在預測時選擇輸出目標指針寄存器生成的目標指針，在出現預測錯誤時選擇輸出訓練循環計數器輸出的循環計數值作為更新的目標指針；虛擬地址映射器根據第二多選器輸出的目標指針計算生成虛擬地址。在圖7中所示的目標地址映射裝置實施例中，BTB的分配項的記錄用於作為遍歷間接轉移指令全部已分配的目標地址項的依據，遍歷情況用於作為更新分配項或目標指針的依據，遍歷情況及其更新包括以下三種中任意一種第一種，遍歷時一旦出現使用某個目標指針訪問BTB而未命中的情況，則將分配項中的對應位更新為未使用狀態；第二種，遍歷時如果一個目標地址項中的目標地址與正確的目標地址相同，則更新相應的目標指針指向該目標地址項，將正確目標指針的對應位作為訓練目標進行訓練；第三種，遍歷時如果遍歷全部已分配的目標地址項後，沒有找到與正確地址匹配的目標地址項，則根據分配項中的信息，隨機地分配一個新的目標地址項或替換一項已使用的目標地址項來記錄正確的目標地址，並更新相應的目標指針指向該目標地址項，以及訓練分支方向預測器。本發明對基於O-GEHL預測器的間接轉移場景映射為目標地址進行了如下修改1)增加目標指針寄存器，用於在預測時保存4位目標指針；2)增加2個XOR或加法器，用於計算FA，並在BTB輸入端增加1個第一多選器，選擇PC或FA作為BTB訪問地址；3)增加1個循環計數器，在更新時根據分配項中信息產生遍歷的目標指針；並增加1個第二多選器，選擇在預測時的目標指針或預測出現錯誤時更新的目標指針；4)增加分配項寄存器，以便在整條流水線中攜帶該分配項的信息。如圖6所示，表示了本發明基於現有的O-GEHL預測器所進行的修改(圖6中灰色部件為本發明需要加入的部件)1)增加Hash變換使用全局歷史寄存器(GHR)生成子預測器索引，並增加多選器選擇原始索引值或子預測器索引值；2)增加4個加法器(圖6中用Σ表示)，每個加法器有5位，用以計算每個子預測器的預測結果；並增加多選器，選擇目標指針的對應位作為子預測器的更新目標。本發明的間接轉移預測的方法實施例流程，其流程可參見圖9，包括如下兩個步
11驟當處理器獲取一條間接轉移指令時，通過PC訪問BTB和分支方向預測器；其中，具體包括如果首次訪問BTB命中，則表示在BTB中存有該間接轉移指令的目標地址項，該命中項即為該間接轉移指令的分配項；否則，暫停取指，直到在流水線中獲得實際的間接轉移目標地址為止。使用分支方向預測器中的子預測器獲得目標指針(TP)，通過FA = f (PC，TP)計算得到虛擬地址(FA)。在下一周期，使用FA 二次訪問BTB，以獲得預測的間接轉移目標地址。如果訪問BTB命中，即BTB項有效且標籤域和間接轉移地址匹配，則將存儲的目標地址發送到指令緩存和流水線中；否則，暫停預測，直到從流水線中獲得實際的轉移目標地址為止。如圖8所示，表示的是C++程序Richards中的虛函數調用片段，以期說明本發明如何使用目標指針快速準確地進行間接轉移指令的預測。Richards程序模擬了作業系統中任務調度行為，並被用於評測間接轉移預測器的性能。該段程序中父類TaskControlBlock定義了一個ActionFunc的虛函數，並在4個子類中定義了不同的ActionFimc行為。該程序片段中第25行的ActionFimc函數調用，對應一條間接轉移指令jsr$26， ($27),0o隨著程序的執行，不同的子類調用RunTask函數時，會調用各個子類下的 ActionFunc函數，即間接轉移指令的目標地址不同($27不同)。例如，DeviceTCB子類調用RunTask函數時，會使用DeviceTCB下定義的ActionFunc實現。程序執行實現虛函數調用時，使用本發明的機制進行間接轉移預測的流程，如圖9 所示。當取得該間接轉移指令時，分支方向預測器中的子預測器使用GHR的低32位生成預測表索引(請參見圖6)，並通過加法計算生成目標指針的對應位。DeviceTCB調用時，生成的目標指針為『1011，。該目標指針生成對應的FA，以訪問BTB獲得DeviceTCB下定義的 ActionFunc函數的入口地址。對於本領域的專業人員來說，在了解了本發明內容和原理後，能夠在不背離本發明的原理和範圍的情況下，根據本發明的方法進行形式和細節上的各種修正和改變，但是這些基於本發明的修正和改變仍在本發明的權利要求保護範圍之內。
1權利要求
1.一種實現現代處理器間接轉移預測的裝置，其特徵在於，包括分支方向預測器、目標地址映射裝置以及分支目標緩衝器，其中分支方向預測器，用於根據定義的多個子預測器預測的間接轉移方向生成目標指針； 目標地址映射裝置，用於將分支方向預測器生成的目標指針映射為索引分支目標緩衝器的虛擬地址；分支目標緩衝器，用於為間接轉移指令分配目標地址項和分配項，所述目標地址項通過所述虛擬地址索引；所述分配項記錄每一間接轉移指令目標地址項的使用情況，通過程序計數器的值索引。
2.按照權利要求1所述的裝置，其特徵在於，所述目標地址映射裝置包括目標指針寄存器、虛擬地址映射器以及第一多選器，其中所述分支方向預測器根據定義的4個子預測器預測的間接轉移方向生成4位目標指針；目標指針寄存器，用於保存所述分支方向預測器生成的4位目標指針； 虛擬地址映射器，用於根據目標指針寄存器保存的所述4位目標指針通過計算映射式 FA = f (PC，TP)生成索引目標地址項的虛擬地址；在該計算映射式中，該TP為目標指針，該 FA為虛擬地址，該PC為程序計數器的值；第一多選器，用於選擇通過所述PC訪問所述分配項的第一索引和通過虛擬地址訪問所述目標地址項的第二索引。
3.按照權利要求2所述的裝置，其特徵在於，所述虛擬地址映射器包括第一異或器和第二異或器，其中第一異或器用於將所述PC 的最高4位與所述4位目標指針相異或；第二異或器用於將所述PC的最低4位與一個常數相異或；將第一異或器和第二異或器的結果組合，構成所述虛擬地址；或者，所述虛擬地址映射器包括第一加法器和第二加法器，其中第一加法器用於將所述PC的最高4位與所述4位目標指針相加；第二加法器用於將PC的最低4位與一個常數相加；將第一加法器和第二加法器的結果組合，構成所述虛擬地址。
4.按照權利要求2所述的裝置，其特徵在於，所述目標地址映射裝置還包括訓練循環計數器和第二多選器，其中訓練循環計數器，用於輸出循環計數值；第二多選器，用於在預測時選擇輸出所述目標指針寄存器生成的目標指針，在出現預測錯誤時選擇輸出訓練循環計數器輸出的所述循環計數值作為更新的目標指針；所述虛擬地址映射器根據第二多選器輸出的目標指針，通過所述計算映射式生成虛擬地址。
5.按照權利要求4所述的裝置，其特徵在於，所述分支目標緩衝器中所述分配項的記錄用於作為遍歷間接轉移指令全部已分配的目標地址項的依據，遍歷情況用於作為更新所述分配項或所述目標指針的依據；所述遍歷情況及其更新包括以下三種中任意一種第一種，遍歷時一旦出現使用一個目標指針訪問所述分支目標緩衝器而未命中的情況，則將分配項中的對應位更新為未使用狀態；第二種，遍歷時如果一個目標地址項中的目標地址與正確的目標地址相同，則更新相應的目標指針指向該目標地址項，將正確目標指針的對應位作為訓練目標進行訓練；第三種，遍歷時如果遍歷全部已分配的目標地址項後，沒有找到與正確地址匹配的目標地址項，則根據所述分配項中記錄的信息，隨機地分配一個新的目標地址項或替換一項已使用的目標地址項來記錄正確的目標地址，並更新相應的目標指針指向該目標地址項， 以及訓練所述分支方向預測器。
6.一種實現現代處理器間接轉移預測的方法，涉及分支方向預測器和分支目標緩衝器，該方法包括在分支方向預測器中定義多個子預測器，每一個子預測器預測的間接轉移方向作為目標指針的每一位，通過所述目標指針映射生成索引分支目標緩衝器的虛擬地址；在分支目標緩衝器中為每一間接轉移指令分配目標地址項和分配項，其中，所述目標地址項通過目標指針映射的虛擬地址索引；所述分配項用於記錄每一間接轉移指令目標地址項的使用情況，並通過程序計數器的值索引。
7.按照權利要求6所述的方法，其特徵在於，當所述處理器獲取一條間接轉移指令要進行預測時，同時執行以下步驟通過所述程序計數器的值訪問所述分支目標緩衝器；若所述訪問命中，則將命中項作為該間接轉移指令的所述分配項；否則，暫停取指，直到在流水線中獲得實際的間接轉移目標地址為止；通過所述分支方向預測器中定義的4個子預測器獲得4位目標指針，通過計算映射式 FA = f (PC, TP)生成所述虛擬地址；在該計算映射式中，該TP為所述4位目標指針，該FA 為生成的所述虛擬地址，該PC為所述程序計數器的值。
8.按照權利要求7所述的方法，其特徵在於，還包括在所述預測的下一周期，使用所述虛擬地址再次訪問所述分支目標緩衝器，以獲得預測的間接轉移目標地址。
9.按照權利要求8所述的方法，其特徵在於，還包括在出現預測錯誤時選擇一訓練循環計數器輸出的循環計數值作為更新的目標指針；所述分支目標緩衝器將所述分配項作為遍歷間接轉移指令全部已分配的目標地址項的依據，遍歷情況用於作為更新所述分配項或所述目標指針的依據；所述遍歷情況及其更新包括以下三種中任意一種第一種，遍歷時一旦出現使用一個目標指針訪問所述分支目標緩衝器而未命中的情況，則將分配項中的對應位更新為未使用狀態；第二種，遍歷時如果一個目標地址項中的目標地址與正確的目標地址相同，則更新相應的目標指針指向該目標地址項，將正確目標指針的對應位作為訓練目標進行訓練；第三種，遍歷時如果遍歷全部已分配的目標地址項後，沒有找到與正確地址匹配的目標地址項，則根據所述分配項中記錄的信息，隨機地分配一個新的目標地址項或替換一項已使用的目標地址項來記錄正確的目標地址，並更新相應的目標指針指向該目標地址項， 以及訓練所述分支方向預測器。
全文摘要
本發明披露了實現現代處理器間接轉移預測的裝置及方法，其中裝置包括分支方向預測器根據定義的多個子預測器預測的間接轉移方向生成目標指針；目標地址映射裝置將分支方向預測器生成的目標指針映射為索引分支目標緩衝器的虛擬地址；以及分支目標緩衝器為間接轉移指令分配目標地址項和分配項，其中，目標地址項通過虛擬地址索引；分配項記錄每一間接轉移指令目標地址項的使用情況，通過程序計數器的值索引。本發明在不需要大容量存儲結構支持的基礎上，能夠以與已有的間接轉移預測技術類似的時間代價，換取同時提高預測準確率和處理器能效的效果。
文檔編號G06F9/38GK102306094SQ20111023551
公開日2012年1月4日 申請日期2011年8月16日 優先權日2011年8月16日
發明者佟冬, 史秦青, 宋天寶, 程旭, 謝子超, 陸俊林, 黃明凱 申請人:北京北大眾志微系統科技有限責任公司