基于真實歷史反饋的自適應值預測器的設計與優化*

隋兵才

(國防科技大學計算機學院,湖南 長沙 410073)

1 引言

現代處理器已經進入多核多線程時代，但是高性能應用對于單核單線程性能的需求仍然沒有止境。傳統亂序處理器的指令級并行度通常通過增大指令窗口，提升發射寬度來增加串行程序的指令并行度。為了配合指令窗口的增大，前瞻調度執行機制需要的亂序執行和控制資源，如寄存器文件、重定序緩沖ROB(ReOrder Buffer)和發射隊列等，必須相應增加，以支持背靠背的執行或者亂序控制或者旁路機制，這又必然會導致功耗和面積開銷的進一步增加。

物理寄存器文件必須隨著指令窗口的增大提供更多的讀寫端口，以匹配ROB的增大[1]。但是，寄存器文件的端口增多，給現代高性能處理器的面積和功耗帶來巨大挑戰，設計的復雜度也呈指數級增長。同時，指令窗口增大，INFLIGHT的指令數目急劇增加，所需要的寄存器的數目也相應增加，也會導致操作數的訪問時間增長[2]。

亂序控制邏輯中所能獲得的性能提升越來越有限，因此學術界開始重新轉向數據的并行性和相關的值預測進行研究[3,4]。20世紀90年代，Gabbay等[5-7]進行了值預測的相關研究，但是由于當時處理器發展的限制，并沒有引起相當多的關注。

Gabbay等認為可以通過預測數據值的方式提前執行存在數據相關的指令，以縮短關鍵路徑的執行時間。但是，最初的研究中值預測器的預測精度一般，并且預測失效的開銷比較大，因此值預測的性能提升有限。

Lipasti等[8,9]提出了新值預測方法LVP(Last Value Prediction)，并對Gabbay[5,6]所提出的預測方法在不同情況下性能提升原理進行了分析研究。Sazeides等[9]將值預測的預測器分為計算型預測和上下文型預測2種。計算型預測器通過對所獲得的數據進行一定規則的運算來產生最終的預測數據，稱為步長預測器，都是通過將獲得的值加上步長來產生最終的預測值。而上下文預測器利用值預測的歷史信息，通過一定的模式匹配產生最終的預測值,如文獻[9]所提出的FCM(Finite Contex Method)預測器。上下文預測器一般分為2級結構，第1級用于保存和索引值預測歷史，通過第1級索引獲得的預測歷史用于索引第2級值預測表來產生最終的預測值。上下文預測器通常還包含一個置信度的計數器，以判定所預測值的可信度。

Goeman等[10]在FCM預測的基礎上增加了預測歷史和值預測表的差別關系分析，在上次預測值的基礎上遞增一定的步長值來計算最新的預測值,而不是簡單地根據數值本身預測結果，因此具有更大的空間有效性。Zhou等[11]基于全局值歷史信息分析了數值的局部特性，并提出了gDiff預測器。gDiff預測器通過計算某條指令與之前n條指令之間的差異來判定信息。如果檢測出固定模式的差異值，可以通過之前的n條指令產生預測值,但gDiff在預測時需要增加一個單獨的預測器以判定前瞻的全局值歷史信息。Ishii[12]提出了一種將預測值和步長共享存儲的預測器CBC-VTAGE(Context-Based Computational Value predictor TAGE)，并采用數據壓縮緩存來檢索數據以最大化存儲效率。CBC-VTAGE利用一個專用的預測精度表控制預測的準確度，并維護一個預測失效的黑名單以提高預測的準確度。但是，CBC-VTAGE在預測失效時，并未考慮到預測器的重新訓練時間，導致重新訓練的時間較長；雖然CBC-VTAGE對預測器的置信度進行了閾值控制，但是并沒有根據正確結果對所預測的結果進行修正，以提高預測器的準確度。

本文針對CBC-VTAGE預測器存在的部分缺陷進行了改進，提出了基于真實歷史預測反饋的上下文預測器RH-VTAGE，針對預測器的實際預測行為反饋判定預測值正確與否。同時針對預測失效后，處理器現場切換開銷較大的問題，優化了RH-VAGE的置信度計數器控制邏輯。

論文的結構如下：第1節介紹值預測的相關背景；第2節介紹值預測器的結構及改進設計；第3節分析RH-VTAGE的性能并進行性能對比；第4節總結全文。

2 基于真實歷史反饋的上下文值預測器

Figure 1 Structure of RH-TAGE

RH-VTAGE預測器的結構如圖1中灰色部分所示。預測器根據取值部件所獲得的指令PC值，更新預測歷史信息表、失效列表和預測精度表。預測歷史信息表根據所得到的PC的哈希值，通過重命名的相關控制，存儲INFLIGHT指令的index、tag信息和INFLIGHT的指令數目。值預測表根據INFLIGHT的指令信息同步更新預測表的所有存儲項，并根據PC值對當前指令進行值預測。值預測表在進行預測的過程中需要查詢預測精度表，如果當前的預測精度不滿足預期值，則本次預測的置信度就會比較低。預測的置信度低于給定的閾值時，則不進行相應的預測輸出。由于值預測失效時，需要對流水線中已經前瞻執行的指令進行相應的刷新操作，并且流水線的刷新操作對性能的影響較大，因此RH-VTAGE中設置了失效列表和預測精度表來控制反饋RH-VTAGE的預測精度，以減少預測失效時流水線的恢復開銷。

Figure 2 Structure of value predict table

RH-VTAGE預測器的預測表結構如圖2所示。預測表包含多個Bank，每個Bank通過PC的哈希值進行索引，索引出來的項的tag值如果與所預測指令的tag域匹配成功，則表示該Bank存儲的值為所需要的預測值。如果多個Bank同時匹配成功，則以最長歷史的Bank的值作為預測結果值。預測表每一項的格式如圖3所示。預測表項中包含tag、數據值和置信度3個部分。tag用于查找表的匹配，數據值分為步長和數值部分，根據模式的不同可以用作數值或者指針。對于大部分的預測值，其高位或者低位部分具有固定的模式，因此不需要在預測表的每一項中存儲所有的數據部分，可以使用一個單獨的壓縮數據緩沖來保存預測值的固定部分數值。根據每一項的模式位選取數據段的步長或者數據指針索引壓縮緩存，所得到的數據進行拼接或者符號擴展之后通過計算得到最終的預測值value，如式(1)所示：

Value=Last_value+inflight*Stride

(1)

其中，Last_value為預測器中保存的最新數值，Stride為步長值，inflight為當前PC的指令在指令窗口中的指令數目。

Figure 3 Format of value predict table entry

預測精度表的結構如圖4所示。預測精度表根據指令的類型和指令的延遲分別維護不同的精度隊列，根據當前指令的PC值進行索引。由于值預測主要針對LOAD指令，所獲得的性能提升明顯，因此預測精度表中針對不同延遲的LOAD指令維護不同的精度隊列。通過預測精度表索引得到的精度參數用于控制預測表的置信度生成，預測表的最終預測結果反饋到精度預測表對應的精度控制隊列中。預測精度表的精度參數代表了值預測對應當前指令的預測精度，如果所預測的精度達不到所需要的閾值，那么預測表所預測結果的置信度就會相應地降低，最終的預測結果就不會由控制邏輯輸出。

Figure 4 Structure of accuracy prediction

失效列表結構如圖5所示。失效列表通過指令的PC值進行索引，并根據tag進行匹配，所匹配項的置信度用于標識所預測的指令是否存在預測失效行為。如果所匹配項的置信度不高，說明預測表對當前指令的預測行為不準確，失效列表會抑制預測表對指令的預測行為。預測表每次預測的結果也被用于同步更新失效列表。

Figure 5 Structure of failure table

3 結構改進與性能優化

3.1 基于真實歷史反饋的自適應預測

由于預測表的準確度與實際程序的行為緊密相關，因此存在預測表預測值與最終的值不一致的現象，這就會導致處理器的流水線進行刷新。由于處理器流水線刷新的開銷很大，所以一次預測失效會導致整個處理器流水線的重啟，對性能影響較大，這種情況在分支預測器中也不可避免地存在。因此，為了提高值預測的準確度，降低預測失效對處理器流水線的影響，本文在值預測器的最后階段增加了真實歷史反饋的控制計數器。在指令提交時，如果預測值與指令的真實值一致，反饋控制計數器遞增。一旦出現預測失效，計數器就被復位為0。只有在預測器連續正確預測指定次數后，預測器的預測結果才會被用于指令的前瞻執行。本文通過分析cvp的基準測試程序，可以確定RH-VTAGE的預測器的模式長度為20。

所有的值預測器都包含置信度控制邏輯。只有置信度達到指定的閾值，所預測的值才具有一定的可信度。大部分值預測器在預測失效時，會將置信度計數器復位為0,而在預測成功時，將置信度計數器遞增。但是,對于不同程序中的不同指令，如果置信度以固定的模式遞增，必然導致不同指令之間預測的乒乓效應，預測表中置信度低的項可能很快被替換，這對預測的準確度會產生一定的負面效應。因此，本文在RH-VTAGE預測器中專門設計了自適應的置信度計數器控制邏輯來分別處理預測正確和預測失效2種情況。在RH-VTAGE預測器中，當預測正確時，對于不同類型的指令，按概率對置信度進行遞增操作。長延遲的LOAD指令更新計數器的概率為1，而單周期的整數指令更新計數器的概率為1/256。同時，當預測器預測失效時，需要將置信度計數器復位為0。但是，對于特定的模式，一旦置信度計數器復位為0，流水線要重新使用預測器所預測的值，就必須等到置信度計數器重新達到閾值。預測器再將置信度恢復到閾值以上的時間為預測器的熱訓練時間。通過對比分析標準的值預測程序的執行蹤跡后，我們發現預測器的單次失效并不表示該指令的預測值無意義，相反該值預測表項很有可能再次被使用。因此，RH-VTAGE在預測失效時并不立即將置信度計數器復位為0，而是根據計數器值與閾值的關系進行不同的遞減處理。如果計數器值大于閾值，則將計數器值設置為小于閾值。如果計數器值小于閾值，則將計數器值遞減；當計數器值小于某個特定值時，直接將計數器復位為0。

3.2 性能評測

基于135個值預測的基準測試程序，RH-VTAGE預測器的IPC(Instructions Per Cycle)執行結果如表1所示。相對于無值預測,RH-VTAGE的IPC(幾何平均)由2.779提升為3.265，約提升17.5%。相對于CBC-VTAGE，改進后的RH-VTAGE的IPC均有所提高。主要原因是RH-VTAGE能夠將預測的真實歷史反饋到預測器中并控制預測值的輸出，同時在預測的置信度控制上根據不同的指令類型和指令延遲按概率采取自適應的遞增或遞減策略。相對于典型的 E-Sride和E-VTAGE預測器，RH-VTAGE的性能有較大提升，主要在于RH-VTAGE同時存儲了數值與步長，采用壓縮數據緩沖的結構共享步長和數值。

Table 1 Comparison results of IPC

Figure 7 IPC results comparison of integer-point program

RH-VTAGE預測器與其他預測器的浮點與整數測試程序的IPC結果對比如圖6和圖7所示。對于整數程序，3個預測器的性能相當，對于部分程序RH-VTAGE的預測性能甚至還有一定的下降(相對于E-VTAGE最大下降4%)。這是由于RH-VTAGE 在自適應預測過程中，偏重于訪存和長延時的指令，對于ALU指令預測器的置信度控制偏弱。對于浮點程序，RH-VTAGE的預測性能要明顯高于其它2種預測器(相對于E-VTAGE最大提升31.2%)。RH-VTAGE同時融合了步長和數值預測2種預測器的結構，能夠同時適應數值預測和步長預測的模式，可以匹配預測多種程序的數據模式。

Figure 6 IPC results comparison of floating-point program

4 結束語

本文設計了基于真實歷史反饋的自適應預測器RH-VTAGE。在該預測器中，只有預測器連續正確預測指定次數后，預測器的預測結果才會被用于指令的前瞻執行。此外，該預測器還包含專門設計的自適應置信度計數器控制邏輯來分別處理預測正確和預測失效2種情況。當預測正確時，對于不同類型的指令，按概率對置信度進行遞增操作；預測失效時，并不立即將置信度計數器復位為0，而是根據計數器值與閾值的關系，進行不同的遞減處理。相對于無值預測，RH-VTAGE的幾何平均IPC提升了17.5%。