隋兵才

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

1 引言

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

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

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

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

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

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

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

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

2 基于真實(shí)歷史反饋的上下文值預(yù)測器

Figure 1 Structure of RH-TAGE

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

Figure 2 Structure of value predict table

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

Value=Last_value+inflight*Stride

(1)

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

Figure 3 Format of value predict table entry

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

Figure 4 Structure of accuracy prediction

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

Figure 5 Structure of failure table

3 結(jié)構(gòu)改進(jìn)與性能優(yōu)化

3.1 基于真實(shí)歷史反饋的自適應(yīng)預(yù)測

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

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

3.2 性能評測

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

Table 1 Comparison results of IPC

Figure 7 IPC results comparison of integer-point program

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

Figure 6 IPC results comparison of floating-point program

4 結(jié)束語

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