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

隋兵才

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

1 引言

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

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

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

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

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

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

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

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

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

Figure 1 Structure of RH-TAGE

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

Figure 2 Structure of value predict table

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

Value=Last_value+inflight*Stride

(1)

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

Figure 3 Format of value predict table entry

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

Figure 4 Structure of accuracy prediction

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

Figure 5 Structure of failure table

3 結構改進與性能優(yōu)化

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

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

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

3.2 性能評測

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

Table 1 Comparison results of IPC

Figure 7 IPC results comparison of integer-point program

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

Figure 6 IPC results comparison of floating-point program

4 結束語

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