面向對稱密碼協處理器的輕量級分支預測技術研究*

吳朋庭，李 軍，何衛國，梅 瑞

（成都三零嘉微電子有限公司，四川 成都 610041）

0 引言

隨著云計算、大數據、5G以及高清視頻業務等領域網絡信息技術的快速發展，通信設備對密碼處理單元的加解密性能提出了更高的要求。為了滿足網絡匯聚層、核心服務器對海量密碼業務處理能力的需求，需要研究具有高性能的對稱密碼協處理器。

高性能的對稱密碼協處理器主要采用數據并行和指令流水的架構來提高運算并行度，采用流水線級數加深的策略來提高運算頻率。理論上性能的提升應該與流水線級數加深程度成正比，然而實際情況并非如此。以簡單的五級流水為例，其執行級處于流水線的第三級，當一條分支指令進入流水線時，處理器無法確定這條分支指令是否跳轉。在分支預測器引入之前，流水線只能停止取指，等待這條分支指令的判斷結果出來之后再繼續執行，從而引入程序流控制開銷[1]；并且隨著流水線級數的增加，分支指令所產生的程序流控制開銷還可能不斷增大。因此，采用分支預測技術提前確定程序流的執行方向對提升協處理器的性能尤為重要[2]。

分支預測技術，就是在取指階段對即將取出的指令是否為分支指令，并對其跳轉方向和目標地址進行預測的技術，其本質是對程序運行行為的歸納總結和記錄，是一種機器學習的過程[3]。由于預測并不等于真實情況，一旦預測失誤即會引發流水線排空/沖刷（flush），從而降低流水線運行效率[4]。因此，研究如何提高分支預測的命中率成為了業界一直努力的方向。

在通用處理器領域，分支預測主要分為靜態預測和動態預測兩類。其中，靜態預測機制的硬件開銷較小，但是其命中率普遍不高；動態預測機制的命中率明顯好于靜態預測機制，但是其硬件開銷較大，并且隨著命中率的提升，硬件的開銷幾乎呈指數級增長[5]。對稱密碼協處理器是一種嵌入式微處理器，其硬件資源非常有限，因此需要一種不但硬件開銷小而且預測命中率高的分支預測機制，以實現更高的性價比[6]。

本文結合對稱密碼算法實現特征，分析了靜態分支預測的不足，設計了一種面向對稱密碼協處理器的輕量級分支預測器，在預測“跳轉必然發生”的靜態分支預測技術基礎之上，通過增加分支條件學習器、記錄指令跳轉閾值的方式，以輕量級的硬件開銷，將分支預測的平均命中率大幅提升，使其極限命中率與密碼算法的循環輪數無關，同時降低了不同代碼風格對分支預測命中率的影響。

1 對稱密碼算法實現的特征

對稱密碼算法主要包含分組、序列、雜湊算法，在算法編程實現時，普遍具有：①模式選擇結構；②分組循環結構；③子程序調用和返回結構；④子程序輪循環結構；⑤尾包特別處理結構。對稱密碼協處理器設計了無條件跳轉、條件跳轉、模式跳轉、數據結束跳轉、尾數長度跳轉、子程序調用/返回等分支指令來實現這些結構，其中：

（1）無條件跳轉指令，主要用于分組循環，跳轉必然發生；

（2）條件跳轉指令，主要用于子程序循環體，跳轉大概率發生；

（3）模式跳轉指令，主要用于模式選擇，算法模式不變時必然跳轉；

（4）數據結束跳轉指令，主要用于結束命令監測，僅數據結束時才跳轉；

（5）尾數長度跳轉指令，主要用于尾數處理，由于尾數長度隨機可變，跳轉概率是與尾數長度相關的函數；

（6）子程序調用/返回指令，主要用于子程序的調用和返回，跳轉必然發生。

這些結構大部分屬于必定跳轉或者多次循環跳轉結構，因此對稱密碼算法中的分支指令將會大概率執行跳轉。針對這一算法特性，對稱密碼協處理器采用“預測跳轉必定發生”的靜態分支預測機制，就可以獲得較高的預測命中率。

2 靜態分支預測機制

“預測跳轉必定發生”的靜態分支預測機制，其原理是在PC值剛好更新后的時鐘周期，根據PC值來預測該指令是否為分支指令，以及指令跳轉的方向，并索引分支目標緩存（Branch Target Buffer，BTB）來預測跳轉的目標地址。因此，m條分支指令總共需要m個BTB表項，以64條分支指令、24比特分支目標緩存為例，該機制僅需要192 B的CAM型存儲器資源開銷，具有硬件開銷小、預測命中率較高的優點。

然而研究發現，這種靜態分支預測機制雖然可將無條件分支指令的預測跳轉命中率提升到較高水平，但對于條件分支指令來說，其命中率始終與算法輪函數執行的輪數以及算法實現的代碼風格相關，預測命中率不穩定。

假設算法輪函數的執行輪數為N，理想情況下，除了第一個分組的第一次跳轉和最后一次跳轉不命中（命中次數為N-2），其余分組只有最后一次跳轉不命中（命中次數為N-1），因此分支預測命中率的極限值為1-1/N，這意味著不同的算法如果有不同的循環輪數，那么就有不同的分支預測命中率；如果將目標設定為95%以上的極限命中率是可以接受的，那么至少需要循環輪數N≥20，很明顯這個要求對于目前無論哪個領域的算法，都是大概率無法實現的。

此外，由于對稱密碼協處理器提供的分支指令比較豐富，實現算法輪函數循環體的編程方法也存在多樣化的情況，例如一個輪數為10的簡單循環體結構就可以使用加法、減法、條件跳轉、無條件跳轉指令的以下4種搭配來實現。

圖1 實現輪函數的不同代碼風格

對于（1）（2）代碼風格來說，第一個分組的處理會觸發兩次預測失敗，分別出現在第1次和最后1次執行循環體跳轉指令時，之后每個分組都會觸發1次預測失敗。對于（3）（4）代碼風格來說，第一個分組的處理會觸發一次預測失敗，出現在最后1次執行循環體跳轉指令時，之后每個分組會觸發N-1次預測失敗。

顯然，對于第（1）（2）種方式實現的循環體來說，采用“預測跳轉必定發生”的靜態分支預測，可以將條件跳轉指令的分支預測命中率提升到90%；但對于第（3）（4）種方式來說，這種預測方式雖然使程序中的無條件跳轉指令實現了100%的極限命中率，但是條件跳轉指令的極限命中率僅能達到10%，這是難以接受的。

因此，需要對分支預測機制做進一步改進，使其命中率更高，并且與循環輪數無關，同時減小代碼風格對預測命中率的影響。

3 改進分支預測機制

在通用處理器領域，一般采用兩級動態分支預測機制來提高分支預測的命中率，其原理是使用第一級的分支歷史寄存器（Branch History Register，BHR），記錄每條分支指令最近的跳轉執行情況，并根據其當前狀態索引第二級的模式歷史表（Pattern History Table，PHT）來預測分支指令是否跳轉，最后索引分支目標地址緩存（Branch Target Buffer，BTB）來預測跳轉目標地址。假設BHR的位寬為w，則PHT需要存儲2w個表項，因此m條分支指令總共需要m個BHR、m×2w個PHT表項和m個BTB表項的硬件開銷。

為了提高分支預測的命中率，往往需要更大的w取值，這導致硬件開銷幾乎呈指數級的增長。以64條分支指令、10比特歷史寄存器為例，兩級動態分支預測機制需要比靜態分支預測機制多出大約80 kB的CAM型存儲器資源開銷。

圖2 兩級動態分支預測結構示意圖[1]

對稱密碼協處理器是一種嵌入式微處理器，其硬件資源非常有限，無法提供如此大的存儲器資源用作分支預測，因此需要一種不但硬件開銷小，而且預測命中率高的分支預測機制來實現更高的性價比。進一步分析對稱密碼協處理器實現算法的指令集結構可以發現，其分支條件簡單并且相對固定。此外，一旦某條分支指令執行過一次，其分支條件信息就可以被譯碼模塊解析出來。基于該特征，本文在靜態分支預測基礎上提出基于分支條件學習的分支預測機制。

3.1 分支條件學習器

對于靜態分支預測而言，無論采用哪種代碼風格，當觸發第1次分支預測失敗時，分支預測器都會將跳轉指令和目標指令的PC值記錄到分支預測表中，用于后續基于PC的分支預測操作。由于初始的分支預測表中沒有記錄任何值，程序默認以PC指針遞增的方式執行，因此第1次觸發的必定是“該跳不跳”型的分支預測錯誤。

在這之后，分支預測器中已經記錄了分支預測表項，當程序指針再次指向該指令時，跳轉將必然發生?？梢灶A見，當（1）（2）代碼風格的循環結束時，或者（3）（4）代碼風格執行后續循環時，都將觸發“不該跳卻跳”型的分支預測錯誤。因此，要想進一步提高分支預測命中率，就必須解決由“預測跳轉必然發生”引起的“不該跳卻跳”型的分支預測錯誤。

由于“不該跳卻跳”型分支預測錯誤和“該跳不跳”型分支預測錯誤發生在同一條分支指令，僅僅通過PC地址無法提前預判跳轉條件是否跨越跳轉閾值而不再跳轉，因此還需要在“不該跳卻跳”錯誤發生的時候，根據譯碼狀態采集跳轉條件相關的各種信息。為此，本設計提出如圖3所示的分支條件學習器，學習“不該跳卻跳”預測失敗狀態。由于譯碼段滯后PC段兩個時鐘周期，為了在PC段就能完成分支條件的預測，分支條件預測基準需要記錄為分支判斷主體兩個周期前的狀態。

圖3 引入分支條件學習器的分支預測結構原理圖

對稱密碼協處理器采用計數器CNT作為分支條件的判斷主體，使用“≥”“≤”“=”“≠”作為分支判定符。因此，本文設計的分支條件學習器采用PC階段的CNT_PC作為分支預測判斷主體，使用比較符“≥”“≤”“=”“≠”作為分支預測判定符。下面證明設計的合理性。

以第（1）種代碼風格實現的輪函數為例，當觸發“不該跳卻跳”預測錯誤的時候，跳轉指令在PC階段時記錄的CNT_PC值為9（由于前一條指令處于IF階段，因此本輪的CNT_ID值尚未計算出來）。此時，分支條件學習器采用CNT_PC ＜9來預測CNT_ID ≤9，其極限命中率分析如下：

由于在PC階段進行分支預測時，前一條指令處于IF階段，其CNT值尚未遞增，但隨著分支指令執行到ID階段，前一條指令將處于ID階段的下一個流水段，其CNT值終將完成本輪遞增，因此預測CNT_PC ＜9相當于預測CNT_ID ＜10，又由于CNT的值必為整數，因此有CNT_ID ＜10等效于CNT_ID ≤9。

綜上，預測CNT_PC ＜9等效于預測CNT_ID≤9。

由此可見，分支條件學習器記錄的閾值信息可以反映真實的跳轉條件。在“預測跳轉必然發生”的靜態分支預測機制的基礎上，增加這樣的分支條件學習器，可以使分支預測的極限命中率達到100%。

由于每條分支指令只可能有一個分支條件，因此m條分支指令只需要m個分支條件學習表項。以64條分支指令、20比特的分支條件位寬為例，整個分支條件學習器的存儲器開銷僅為160 B，達到了輕量級設計的目標。

3.2 分支預測的執行流程

基于條件學習的分支預測技術在“預測跳轉必定發生”的靜態分支預測基礎上，通過引入“分支預測失敗狀態學習”的功能來獲取跳轉條件的閾值信息，從而實現預測“所有指令不跳轉”→“分支指令必定跳轉”→“分支指令條件跳轉”3個階段的逐步演進，使分支預測在運行過程中逐漸趨近于真實情況。

在程序運行過程中，當觸發過“該跳不跳”和“不該跳卻跳”兩型分支預測錯誤后，在程序指針PC更新的流水階段，根據PC值來判斷當前指令是否為跳轉指令，并且預測跳轉條件是否滿足，跳轉操作是否執行，并獲取跳轉方向和跳轉目標地址。其執行流程如圖4所示。

圖4 基于條件學習的分支預測指令執行流程

當程序開始執行（PC階段）時，分支預測器通過當前PC值查詢分支預測表（分支預測表中儲存有分支指令的PC值和對應跳轉目的地址信息）。若分支預測表中不存在該指令的PC值，則預測當前指令不是分支指令，程序順序執行（PC+1）；若分支預測表中存在該指令的PC值，則預測當前指令是分支指令，需要繼續查詢對應的分支條件表項（分支條件表項中儲存有分支預測錯誤狀態學習記錄）。如果表項中沒有學習記錄，則預測當前指令必定跳轉至分支預測表項中記錄的目標地址；如果表項中有學習記錄，則需要判斷當前的分支狀態是否達到記錄的錯誤狀態。如果沒有達到錯誤狀態則預測程序跳轉至目標地址，如果達到錯誤狀態則預測程序順序執行。

在譯碼（ID）階段，分支預測判斷邏輯根據指令的譯碼信息判斷該指令是否為分支指令。若為分支指令，則根據指令的相關譯碼信息對本次分支預測行為進行判斷，若分支預測成功，則對稱密碼協處理器繼續順序執行；若分支預測失敗，這時需要立刻更改PC值，并清除已錯誤取出的指令。此外，分支指令在觸發“該跳不跳”錯誤時，需將該指令的分支信息（PC值、跳轉目標地址）寫入分支預測表中；觸發“不該跳卻跳”錯誤時，需將錯誤閾值信息（CNT_PC）和分支判定符（“≥”“≤”“=”“≠”）記錄到分支條件表中。

4 分支預測改進的效果

對于條件分支指令，基于分支條件學習的分支預測技術在“預測跳轉必定發生”的靜態分支預測機制消除了“該跳不跳”分支預測錯誤的基礎上，進一步消除了由該機制引入的“不該跳卻跳”分支預測錯誤，通過最少1個、最多2個分組的學習，將分支預測的極限命中率從1-1/N或1/N提升至100%，基本消除了分支預測極限命中率受循環輪數以及代碼風格限制的問題。

假設待處理的數據包包含y個分組，每個分組執行z次循環。

4.1 對于第（1）（2）種代碼風格

“預測跳轉必然發生”的靜態分支預測在第1個分組失敗2次，后續每個分組失敗1次，因此，其平均命中率為P=1-(y+1)/yz，命中率與分組數、循環數的關系如圖5所示。

圖5 靜態分支預測命中率關系圖（代碼風格1、2）

本文研究的分支預測在第1個分組失敗2次，在后續分組全部命中，因此，其總體命中率為P=1-2/yz，命中率與分組數、循環數的關系如圖6所示。

圖6 改進后分支預測命中率關系圖（代碼風格1、2）

當循環輪數為8時，改進的分支預測處理5個分組就能得到95%的平均命中率，處理25個分組就能得到99%以上的平均命中率，相對于改進前的85%和87%分別提高10%和12%。當循環輪數為16時，改進的分支預測處理3個分組就能得到95%的平均命中率，處理13個分組就能得到99%以上的平均命中率，相對于改進前的91%和93%分別提高4%和6%。隨著分組數的不斷增大，命中率的極限值由1-1/z提升為100%。

4.2 對于第（3）（4）種代碼風格

“預測跳轉必然發生”的靜態分支預測在第1個分組失敗1次，在后續每個分組失敗z-1次，因此，其平均命中率為P=(y+z-1)/yz，命中率與分組數、循環數的關系如圖7所示。

圖7 靜態分支預測命中率關系圖（代碼風格3、4）

本文研究的分支預測在第1個分組失敗1次，在第2個分組失敗z-1次，后續分組全部命中，因此，其總體命中率為P=1-1/y，命中率與分組數、循環數的關系如圖8所示。

圖8 改進后分支預測命中率關系圖（代碼風格3、4）

當循環輪數為8或16時，改進的分支預測處理20個分組就能得到95%的平均命中率，相對于改進前的16%和10%分別提高79%和85%；處理100個分組就能得到99%的平均命中率，相對于改進前的13%和7%分別提高86%和92%。隨著分組數的不斷增大，命中率的極限值由1/z提升為100%。

5 結語

本文研究了面向對稱密碼協處理器的分支預測技術，結合對稱密碼算法實現結構中以循環體為代表的分支指令大概率會執行跳轉，密碼算法程序規模小、重復執行次數不高，以及跳轉條件簡單并且固定的特征，在“預測跳轉必定發生”的分支預測機制基礎上，通過新增分支條件學習器、記錄指令跳轉閾值的設計，以輕量級的硬件開銷和極短的學習過程，將分支預測的平均命中率大幅提升，使其極限命中率與密碼算法的循環輪數無關，同時降低了不同風格的代碼對分支預測命中率的影響，為高性能對稱密碼協處理器減少分支指令引入的程序流控制開銷提供了解決方案。