面向?qū)ΨQ密碼協(xié)處理器的輕量級分支預(yù)測技術(shù)研究

０引言隨著云計算、大數(shù)據(jù)、5G以及高清視頻業(yè)務(wù)等領(lǐng)域網(wǎng)絡(luò)信息技術(shù)的快速發(fā)展，通信設(shè)備對密碼處理單元的加解密性能提出了更高的要求。為了滿足網(wǎng)絡(luò)匯聚層、核心服務(wù)器對海量密碼業(yè)務(wù)處理能力的需求，需要研究具有高性能的對稱密碼協(xié)處理器。高性能的對稱密碼協(xié)處理器主要采用數(shù)據(jù)并行和指令流水的架構(gòu)來提高運(yùn)算并行度，采用流水線級數(shù)加深的策略來提高運(yùn)算頻率。理論上性能的提升應(yīng)該與流水線級數(shù)加深程度成正比，然而實(shí)際情況并非如此。以簡單的五級流水為例，其執(zhí)行級處于流水線的第三級，當(dāng)一條分支指令進(jìn)入流水線時，處理器無法確定這條分支指令是否跳轉(zhuǎn)。在分支預(yù)測器引入之前，流水線只能停止取指，等待這條分支指令的判斷結(jié)果出來之后再繼續(xù)執(zhí)行，從而引入程序流控制開銷；并且隨著流水線級數(shù)的增加，分支指令所產(chǎn)生的程序流控制開銷還可能不斷增大。因此，采用分支預(yù)測技術(shù)提前確定程序流的執(zhí)行方向?qū)μ嵘齾f(xié)處理器的性能尤為重要。分支預(yù)測技術(shù)，就是在取指階段對即將取出的指令是否為分支指令，并對其跳轉(zhuǎn)方向和目標(biāo)地址進(jìn)行預(yù)測的技術(shù)，其本質(zhì)是對程序運(yùn)行行為的歸納總結(jié)和記錄，是一種機(jī)器學(xué)習(xí)的過程。由于預(yù)測并不等于真實(shí)情況，一旦預(yù)測失誤即會引發(fā)流水線排空/沖刷（flush），從而降低流水線運(yùn)行效率。因此，研究如何提高分支預(yù)測的命中率成為了業(yè)界一直努力的方向。在通用處理器領(lǐng)域，分支預(yù)測主要分為靜態(tài)預(yù)測和動態(tài)預(yù)測兩類。其中，靜態(tài)預(yù)測機(jī)制的硬件開銷較小，但是其命中率普遍不高；動態(tài)預(yù)測機(jī)制的命中率明顯好于靜態(tài)預(yù)測機(jī)制，但是其硬件開銷較大，并且隨著命中率的提升，硬件的開銷幾乎呈指數(shù)級增長。對稱密碼協(xié)處理器是一種嵌入式微處理器，其硬件資源非常有限，因此需要一種不但硬件開銷小而且預(yù)測命中率高的分支預(yù)測機(jī)制，以實(shí)現(xiàn)更高的性價比。本文結(jié)合對稱密碼算法實(shí)現(xiàn)特征，分析了靜態(tài)分支預(yù)測的不足，設(shè)計了一種面向?qū)ΨQ密碼協(xié)處理器的輕量級分支預(yù)測器，在預(yù)測“跳轉(zhuǎn)必然發(fā)生”的靜態(tài)分支預(yù)測技術(shù)基礎(chǔ)之上，通過增加分支條件學(xué)習(xí)器、記錄指令跳轉(zhuǎn)閾值的方式，以輕量級的硬件開銷，將分支預(yù)測的平均命中率大幅提升，使其極限命中率與密碼算法的循環(huán)輪數(shù)無關(guān)，同時降低了不同代碼風(fēng)格對分支預(yù)測命中率的影響。１對稱密碼算法實(shí)現(xiàn)的特征對稱密碼算法主要包含分組、序列、雜湊算法，在算法編程實(shí)現(xiàn)時，普遍具有：①模式選擇結(jié)構(gòu)；②分組循環(huán)結(jié)構(gòu)；③子程序調(diào)用和返回結(jié)構(gòu)；④子程序輪循環(huán)結(jié)構(gòu)；⑤尾包特別處理結(jié)構(gòu)。對稱密碼協(xié)處理器設(shè)計了無條件跳轉(zhuǎn)、條件跳轉(zhuǎn)、模式跳轉(zhuǎn)、數(shù)據(jù)結(jié)束跳轉(zhuǎn)、尾數(shù)長度跳轉(zhuǎn)、子程序調(diào)用/返回等分支指令來實(shí)現(xiàn)這些結(jié)構(gòu)，其中：（1）無條件跳轉(zhuǎn)指令，主要用于分組循環(huán)，跳轉(zhuǎn)必然發(fā)生；（2）條件跳轉(zhuǎn)指令，主要用于子程序循環(huán)體，跳轉(zhuǎn)大概率發(fā)生；（3）模式跳轉(zhuǎn)指令，主要用于模式選擇，算法模式不變時必然跳轉(zhuǎn)；（4）數(shù)據(jù)結(jié)束跳轉(zhuǎn)指令，主要用于結(jié)束命令監(jiān)測，僅數(shù)據(jù)結(jié)束時才跳轉(zhuǎn)；（5）尾數(shù)長度跳轉(zhuǎn)指令，主要用于尾數(shù)處理，由于尾數(shù)長度隨機(jī)可變，跳轉(zhuǎn)概率是與尾數(shù)長度相關(guān)的函數(shù)；（6）子程序調(diào)用/返回指令，主要用于子程序的調(diào)用和返回，跳轉(zhuǎn)必然發(fā)生；這些結(jié)構(gòu)大部分屬于必定跳轉(zhuǎn)或者多次循環(huán)跳轉(zhuǎn)結(jié)構(gòu)，因此對稱密碼算法中的分支指令將會大概率執(zhí)行跳轉(zhuǎn)。針對這一算法特性，對稱密碼協(xié)處理器采用“預(yù)測跳轉(zhuǎn)必定發(fā)生”的靜態(tài)分支預(yù)測機(jī)制，就可以獲得較高的預(yù)測命中率。２靜態(tài)分支預(yù)測機(jī)制“預(yù)測跳轉(zhuǎn)必定發(fā)生”的靜態(tài)分支預(yù)測機(jī)制，其原理是在PC值剛好更新后的時鐘周期，根據(jù)PC值來預(yù)測該指令是否為分支指令，以及指令跳轉(zhuǎn)的方向，并索引分支目標(biāo)緩存（BranchTargetBuffer，BTB）來預(yù)測跳轉(zhuǎn)的目標(biāo)地址。因此，m條分支指令總共需要m個BTB表項，以64條分支指令、24比特分支目標(biāo)緩存為例，該機(jī)制僅需要192B的CAM型存儲器資源開銷，具有硬件開銷小、預(yù)測命中率較高的優(yōu)點(diǎn)。然而研究發(fā)現(xiàn)，這種靜態(tài)分支預(yù)測機(jī)制雖然可將無條件分支指令的預(yù)測跳轉(zhuǎn)命中率提升到較高水平，但對于條件分支指令來說，其命中率始終與算法輪函數(shù)執(zhí)行的輪數(shù)以及算法實(shí)現(xiàn)的代碼風(fēng)格相關(guān)，預(yù)測命中率不穩(wěn)定。假設(shè)算法輪函數(shù)的執(zhí)行輪數(shù)為N，理想情況下，除了第一個分組的第一次跳轉(zhuǎn)和最后一次跳轉(zhuǎn)不命中（命中次數(shù)為N－2），其余分組只有最后一次跳轉(zhuǎn)不命中（命中次數(shù)為N－1），因此分支預(yù)測命中率的極限值為1－1/N，這意味著不同的算法如果有不同的循環(huán)輪數(shù)，那么就有不同的分支預(yù)測命中率；如果將目標(biāo)設(shè)定為95%以上的極限命中率是可以接受的，那么至少需要循環(huán)輪數(shù)N≥20，很明顯這個要求對于目前無論哪個領(lǐng)域的算法，都是大概率無法實(shí)現(xiàn)的。此外，由于對稱密碼協(xié)處理器提供的分支指令比較豐富，實(shí)現(xiàn)算法輪函數(shù)循環(huán)體的編程方法也存在多樣化的情況，例如一個輪數(shù)為10的簡單循環(huán)體結(jié)構(gòu)就可以使用加法、減法、條件跳轉(zhuǎn)、無條件跳轉(zhuǎn)指令的以下4種搭配來實(shí)現(xiàn)。圖1實(shí)現(xiàn)輪函數(shù)的不同代碼風(fēng)格對于（1）（2）代碼風(fēng)格來說，第一個分組的處理會觸發(fā)兩次預(yù)測失敗，分別出現(xiàn)在第1次和最后1次執(zhí)行循環(huán)體跳轉(zhuǎn)指令時，之后每個分組都會觸發(fā)1次預(yù)測失敗。對于（3）（4）代碼風(fēng)格來說，第一個分組的處理會觸發(fā)一次預(yù)測失敗，出現(xiàn)在最后1次執(zhí)行循環(huán)體跳轉(zhuǎn)指令時，之后每個分組會觸發(fā)N－1次預(yù)測失敗。顯然，對于第（1）（2）種方式實(shí)現(xiàn)的循環(huán)體來說，采用“預(yù)測跳轉(zhuǎn)必定發(fā)生”的靜態(tài)分支預(yù)測，可以將條件跳轉(zhuǎn)指令的分支預(yù)測命中率提升到90%；但對于第（3）（4）種方式來說，這種預(yù)測方式雖然使程序中的無條件跳轉(zhuǎn)指令實(shí)現(xiàn)了100%的極限命中率，但是條件跳轉(zhuǎn)指令的極限命中率僅能達(dá)到10%，這是難以接受的。因此，需要對分支預(yù)測機(jī)制做進(jìn)一步改進(jìn)，使其命中率更高，并且與循環(huán)輪數(shù)無關(guān)，同時減小代碼風(fēng)格對預(yù)測命中率的影響。３改進(jìn)分支預(yù)測機(jī)制在通用處理器領(lǐng)域，一般采用兩級動態(tài)分支預(yù)測機(jī)制來提高分支預(yù)測的命中率，其原理是使用第一級的分支歷史寄存器（BranchHistoryRegister，BHR），記錄每條分支指令最近的跳轉(zhuǎn)執(zhí)行情況，并根據(jù)其當(dāng)前狀態(tài)索引第二級的模式歷史表（PatternHistoryTable，PHT）來預(yù)測分支指令是否跳轉(zhuǎn)，最后索引分支目標(biāo)地址緩存（BranchTargetBuffer，BTB）來預(yù)測跳轉(zhuǎn)目標(biāo)地址。假設(shè)BHR的位寬為w，則PHT需要存儲個表項，因此m條分支指令總共需要m個BHR、m×個PHT表項和m個BTB表項的硬件開銷。為了提高分支預(yù)測的命中率，往往需要更大的w取值，這導(dǎo)致硬件開銷幾乎呈指數(shù)級的增長。以64條分支指令、10比特歷史寄存器為例，兩級動態(tài)分支預(yù)測機(jī)制需要比靜態(tài)分支預(yù)測機(jī)制多出大約80KB的CAM型存儲器資源開銷。圖2兩級動態(tài)分支預(yù)測結(jié)構(gòu)示意圖對稱密碼協(xié)處理器是一種嵌入式微處理器，其硬件資源非常有限，無法提供如此大的存儲器資源用作分支預(yù)測，因此需要一種不但硬件開銷小，而且預(yù)測命中率高的分支預(yù)測機(jī)制，來實(shí)現(xiàn)更高的性價比。進(jìn)一步分析對稱密碼協(xié)處理器實(shí)現(xiàn)算法的指令集結(jié)構(gòu)可以發(fā)現(xiàn)，其分支條件簡單并且相對固定；此外，一旦某條分支指令執(zhí)行過一次，其分支條件信息就可以被譯碼模塊解析出來?；谠撎卣?，本文在靜態(tài)分支預(yù)測基礎(chǔ)上，提出“基于分支條件學(xué)習(xí)的分支預(yù)測機(jī)制”。3.1分支條件學(xué)習(xí)器對于靜態(tài)分支預(yù)測而言，無論采用哪種代碼風(fēng)格，當(dāng)觸發(fā)第1次分支預(yù)測失敗時，分支預(yù)測器都會將跳轉(zhuǎn)指令和目標(biāo)指令的PC值記錄到分支預(yù)測表中，用于后續(xù)基于PC的分支預(yù)測操作。由于初始的分支預(yù)測表中沒有記錄任何值，程序默認(rèn)以PC指針遞增的方式執(zhí)行，因此第1次觸發(fā)的必定是“該跳不跳”型的分支預(yù)測錯誤。在這之后，分支預(yù)測器中已經(jīng)記錄了分支預(yù)測表項，當(dāng)程序指針再次指向該指令時，跳轉(zhuǎn)將必然發(fā)生?？梢灶A(yù)見，當(dāng)（1）（2）代碼風(fēng)格的循環(huán)結(jié)束時，或者（3）（4）代碼風(fēng)格執(zhí)行后續(xù)循環(huán)時，都將觸發(fā)“不該跳卻跳”型的分支預(yù)測錯誤。因此，要想進(jìn)一步提高分支預(yù)測命中率，就必須解決由“預(yù)測跳轉(zhuǎn)必然發(fā)生”引起的“不該跳卻跳”型的分支預(yù)測錯誤。圖3引入分支條件學(xué)習(xí)器的分支預(yù)測結(jié)構(gòu)原理圖由于“不該跳卻跳”型分支預(yù)測錯誤和“該跳不跳”型分支預(yù)測錯誤發(fā)生在同一條分支指令，僅僅通過PC地址無法提前預(yù)判跳轉(zhuǎn)條件是否跨越跳轉(zhuǎn)閾值而不再跳轉(zhuǎn)，因此還需要在“不該跳卻跳”錯誤發(fā)生的時候，根據(jù)譯碼狀態(tài)采集跳轉(zhuǎn)條件相關(guān)的各種信息。為此，本設(shè)計提出如圖3所示的分支條件學(xué)習(xí)器，學(xué)習(xí)“不該跳卻跳”預(yù)測失敗狀態(tài)。由于譯碼段滯后PC段兩個時鐘周期，為了在PC段就能完成分支條件的預(yù)測，分支條件預(yù)測基準(zhǔn)需要記錄為分支判斷主體兩個周期前的狀態(tài)。由于對稱密碼協(xié)處理器采用計數(shù)器CNT作為分支條件的判斷主體，使用≥≤＝≠作為分支判定符；因此，本文設(shè)計的分支條件學(xué)習(xí)器采用PC階段的CNT_PC作為分支預(yù)測判斷主體，使用比較符＞＜≠≠作為分支預(yù)測判定符。下面證明設(shè)計的合理性。以第（1）種代碼風(fēng)格實(shí)現(xiàn)的輪函數(shù)為例，當(dāng)觸發(fā)“不該跳卻跳”預(yù)測錯誤的時候，跳轉(zhuǎn)指令在PC階段時記錄的CNT_PC值為9（由于前一條指令處于IF階段，因此本輪的CNT_ID值尚未計算出來）。此時，分支條件學(xué)習(xí)器采用CNT_PC＜9來預(yù)測CNT_ID≤9，其極限命中率分析如下：由于在PC階段進(jìn)行分支預(yù)測時，前一條指令處于IF階段，其CNT值尚未遞增，但隨著分支指令執(zhí)行到ID階段，前一條指令將處于ID階段的下一個流水段，其CNT值終將完成本輪遞增，因此預(yù)測CNT_PC＜9相當(dāng)于預(yù)測CNT_ID＜10，又由于CNT的值必為整數(shù)，因此有CNT_ID＜10等效于CNT_ID≤9。綜上，預(yù)測CNT_PC＜9等效于預(yù)測CNT_ID≤9。由此可見，分支條件學(xué)習(xí)器記錄的閾值信息可以反映真實(shí)的跳轉(zhuǎn)條件。在“預(yù)測跳轉(zhuǎn)必然發(fā)生”的靜態(tài)分支預(yù)測機(jī)制的基礎(chǔ)上，增加這樣的分支條件學(xué)習(xí)器，可以使分支預(yù)測的極限命中率達(dá)到100%。由于每條分支指令只可能有一個分支條件，因此m條分支指令只需要m個分支條件學(xué)習(xí)表項。以64條分支指令、20比特的分支條件位寬為例，整個分支條件學(xué)習(xí)器的存儲器開銷僅為160B，達(dá)到了輕量級設(shè)計的目標(biāo)。3.2分支預(yù)測的執(zhí)行流程“基于條件學(xué)習(xí)的分支預(yù)測技術(shù)”，在“預(yù)測跳轉(zhuǎn)必定發(fā)生”的靜態(tài)分支預(yù)測基礎(chǔ)上，通過引入“分支預(yù)測失敗狀態(tài)學(xué)習(xí)”的功能來獲取跳轉(zhuǎn)條件的閾值信息，從而實(shí)現(xiàn)預(yù)測“所有指令不跳轉(zhuǎn)”→“分支指令必定跳轉(zhuǎn)”→“分支指令條件跳轉(zhuǎn)”三個階段的逐步演進(jìn)，使分支預(yù)測在運(yùn)行過程中逐漸趨近于真實(shí)情況。在程序運(yùn)行過程中，當(dāng)觸發(fā)過“該跳不跳”和“不該跳卻跳”兩型分支預(yù)測錯誤后，在程序指針PC更新的流水階段，根據(jù)PC值來判斷當(dāng)前指令是否為跳轉(zhuǎn)指令，并且預(yù)測跳轉(zhuǎn)條件是否滿足，跳轉(zhuǎn)操作是否執(zhí)行，并獲取跳轉(zhuǎn)方向和跳轉(zhuǎn)目標(biāo)地址。其執(zhí)行流程如圖4所示。圖4基于條件學(xué)習(xí)的分支預(yù)測指令執(zhí)行流程當(dāng)程序開始執(zhí)行（PC階段）時，分支預(yù)測器通過當(dāng)前PC值查詢分支預(yù)測表（分支預(yù)測表中儲存有分支指令的PC值和對應(yīng)跳轉(zhuǎn)目的地址信息）。若分支預(yù)測表中不存在該指令的PC值，則預(yù)測當(dāng)前指令不是分支指令，程序順序執(zhí)行（PC＋1）；若分支預(yù)測表中存在該指令的PC值，則預(yù)測當(dāng)前指令是分支指令，需要繼續(xù)查詢對應(yīng)的分支條件表項（分支條件表項中儲存有分支預(yù)測錯誤狀態(tài)學(xué)習(xí)記錄），如果表項中沒有學(xué)習(xí)記錄，則預(yù)測當(dāng)前指令必定跳轉(zhuǎn)至分支預(yù)測表項中記錄的目標(biāo)地址；如果表項中有學(xué)習(xí)記錄，則需要判斷當(dāng)前的分支狀態(tài)是否達(dá)到記錄的錯誤狀態(tài)，如果沒有達(dá)到錯誤狀態(tài)則預(yù)測程序跳轉(zhuǎn)至目標(biāo)地址，如果達(dá)到錯誤狀態(tài)則預(yù)測程序順序執(zhí)行。在譯碼（ID）階段，分支預(yù)測判斷邏輯根據(jù)指令的譯碼信息判斷該指令是否為分支指令。若為分支指令，則根據(jù)指令的相關(guān)譯碼信息對本次分支預(yù)測行為進(jìn)行判斷，若分支預(yù)測成功，則對稱密碼協(xié)處理器繼續(xù)順序執(zhí)行；若分支預(yù)測失敗，這時需要立刻更改PC值，并清除已錯誤取出的指令。此外，分支指令在觸發(fā)“該跳不跳”錯誤時，需將該指令的分支信息（PC值、跳轉(zhuǎn)目標(biāo)地址）寫入分支預(yù)測表中；觸發(fā)“不該跳卻跳”錯誤時，需將錯誤閾值信息（CNT_PC）和分支判定符（≥≤＝≠）記錄到分支條件表中。４分支預(yù)測改進(jìn)的效果對于條件分支指令，“基于分支條件學(xué)習(xí)的分支預(yù)測技術(shù)”，在“預(yù)測跳轉(zhuǎn)必定發(fā)生”的靜態(tài)分支預(yù)測機(jī)制消除了“該跳不跳”分支預(yù)測錯誤的基礎(chǔ)上，進(jìn)一步消除了由該機(jī)制引入的“不該跳卻跳”分支預(yù)測錯誤，通過最少1個、最多2個分組的學(xué)習(xí)，將分支預(yù)測的極限命中率從1－1/N或1/N提升至100%，基本消除了分支預(yù)測極限命中率受循環(huán)輪數(shù)以及代碼風(fēng)格限制的問題。假設(shè)待處理的數(shù)據(jù)包包含y個分組，每個分組執(zhí)行z次循環(huán)。4.1對于第（1）（2）種代碼風(fēng)格“預(yù)測跳轉(zhuǎn)必然發(fā)生”的靜態(tài)分支預(yù)測在第1個分組失敗2次，后續(xù)每個分組失敗1次，因此，其平均命中率為P＝1－(y＋1)/yz，命中率與分組數(shù)、循環(huán)數(shù)的關(guān)系如圖5所示。圖5靜態(tài)分支預(yù)測命中率關(guān)系圖（代碼風(fēng)格1、2）本文研究的分支預(yù)測在第1個分組失敗2次，在后續(xù)分組全部命中，因此，其總體命中率為P＝1－2/yz，命中率與分組數(shù)、循環(huán)數(shù)的關(guān)系如圖6所示：圖6改進(jìn)后分支預(yù)測命中率關(guān)系圖（代碼風(fēng)格1、2）典型的，當(dāng)循環(huán)輪數(shù)為8時，改進(jìn)的分支預(yù)測處理5個分組就能得到95%的平均命中率，處理25個分組就能得到99%以上的平均命中率，相對于改進(jìn)前的85%和87%分別提高10%和12%。當(dāng)循環(huán)輪數(shù)為16時，改進(jìn)的分支預(yù)測處理3個分組就能得到95%的平均命中率，處理13個分組就能得到99%以上的平均命中率，相對于改進(jìn)前的91%和93%分別提高4%和6%。隨著分組數(shù)的不斷增大，命中率的極限值由1－1/z提升為100%。4.2對于第（3）（4）種代