一種面向序列密碼的混合粒度并行運(yùn)算單元

曲彤洲 戴紫彬 陳 琳 劉燕江

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450000)

1 引言

密碼處理器作為一種能夠高效靈活處理密碼任務(wù)的硬件載體，是實(shí)現(xiàn)密碼算法的主要方式之一[1]。序列密碼算法又稱為流密碼算法，是全球移動(dòng)通信領(lǐng)域中使用的主要密碼之一[2]，特別是基于反饋移位寄存器 (Feedback Shift Register, FSR)所構(gòu)造的序列密碼是目前數(shù)量最多、應(yīng)用最廣泛的一類算法。由于該類算法的種類多、更新快，且不同算法在硬件實(shí)現(xiàn)上具有一定的相似性。因此，適合采用可重構(gòu)方式硬件實(shí)現(xiàn)。

目前，國(guó)內(nèi)外針對(duì)FSR的可重構(gòu)實(shí)現(xiàn)進(jìn)行了一系列研究。文獻(xiàn)[3]提出了一種基于與-異或邏輯網(wǎng)絡(luò)實(shí)現(xiàn)反饋函數(shù)的可重構(gòu)FSR單元，支持實(shí)現(xiàn)不同類型的非線性反饋移位寄存器(Nonlinear Feedback Shift Register, NFSR)和線性反饋寄存器(Linear Feedback Shift Register, LFSR)。徐光明等人[4]提出了一種可重構(gòu)NFSR處理結(jié)構(gòu)，主要計(jì)算模塊是基于查找表實(shí)現(xiàn)的支持任意6變量布爾函數(shù)的高級(jí)非線性邏輯單元(Advanced Nonlinear Logic Unit,ANLU)，與文獻(xiàn)[3]相比，具有靈活性高、配置量少、資源開(kāi)銷小的優(yōu)點(diǎn)。Nan等人[5]提出了一種將NFSR,LFSR和有限域乘法單元相融合的可重構(gòu)電路，提升了密碼支持的硬件資源利用率。但上述專用電路結(jié)構(gòu)僅支持FSR的重構(gòu)更新，并不能完整執(zhí)行序列密碼算法。以文獻(xiàn)[3]提出的與-異或邏輯網(wǎng)絡(luò)為基礎(chǔ)，文獻(xiàn)[6]與文獻(xiàn)[7]分別設(shè)計(jì)了各自的可重構(gòu)序列密碼處理器，能夠完整執(zhí)行大部分工作在2元域上的序列密碼算法。

除了可重構(gòu)FSR電路外，面向?qū)ΨQ密碼領(lǐng)域設(shè)計(jì)的粗粒度可重構(gòu)陣列(Coarse Grain Reconfigurable Array, CGRA)也能夠?qū)崿F(xiàn)序列密碼算法。其面向密碼應(yīng)用領(lǐng)域的計(jì)算特征，定制芯片的邏輯通路和存儲(chǔ)系統(tǒng)，從而在高能效和高靈活性間達(dá)到平衡。Anole[8]是一種以分組密碼高性能流水處理為設(shè)計(jì)目標(biāo)的粗粒度可重構(gòu)陣列，同時(shí)支持實(shí)現(xiàn)部分序列密碼算法，其利用查找表或系統(tǒng)的存儲(chǔ)器來(lái)存儲(chǔ)FSR的狀態(tài)值，其他運(yùn)算單元執(zhí)行密碼操作，但這種設(shè)計(jì)方案并不支持以bit為粒度的序列密碼。PVHarray[9]是以高效流水線為設(shè)計(jì)目標(biāo)的密碼CGRA，內(nèi)部集成了專用的非線性布爾函數(shù)處理模塊和FSR，但其處理粒度是基于字的，這使處理器在實(shí)現(xiàn)2元域上序列密碼時(shí)，高位計(jì)算資源被閑置，系統(tǒng)計(jì)算資源利用率較低。與上述結(jié)構(gòu)類似的還包括Sayilar等人[10,11]提出的Cryptograptor架構(gòu)和文獻(xiàn)[12]中東南大學(xué)所設(shè)計(jì)的可重構(gòu)密碼處理器。

綜上所述，面向?qū)ΨQ密碼算法所設(shè)計(jì)的CGRA[8-12]沒(méi)有專用的FSR處理結(jié)構(gòu)，雖然可以實(shí)現(xiàn)序列密碼，但支持的算法種類少，硬件資源利用率差；而專用的可重構(gòu)FSR電路[3-7]針對(duì)以bit為粒度的序列密碼設(shè)計(jì)，不支持以大位寬為處理粒度。因此，基于可重構(gòu)計(jì)算思想設(shè)計(jì)一種既能獨(dú)立執(zhí)行2元域上序列密碼算法，又能集成在處理器中配合其他計(jì)算資源兼容實(shí)現(xiàn)大位寬算法的FSR運(yùn)算單元，提升序列密碼算法在可重構(gòu)處理器中的實(shí)現(xiàn)性能，具有重要的理論意義與實(shí)踐價(jià)值。針對(duì)上述問(wèn)題，本文研究了序列密碼算法的多級(jí)可開(kāi)發(fā)并行性，并建立了關(guān)于FSR的預(yù)抽取并行更新模型。在此基礎(chǔ)上，面向CGRA體系結(jié)構(gòu)設(shè)計(jì)了一種可重構(gòu)反饋移位寄存器運(yùn)算單元(Reconfigurable Feedback-shift-register Arithmetical Unit, RFAU)，兼容實(shí)現(xiàn)多域序列密碼的同時(shí)，充分開(kāi)發(fā)了算法并行性。

2 序列密碼算法并行性分析

2.1 基礎(chǔ)知識(shí)與符號(hào)說(shuō)明

本節(jié)簡(jiǎn)要介紹了基于FSR構(gòu)造的序列密碼算法以及面向密碼處理領(lǐng)域設(shè)計(jì)CGRA的結(jié)構(gòu)組成，并說(shuō)明了后文中所用到的數(shù)學(xué)符號(hào)。如圖1(a)，基于FSR構(gòu)造的序列密碼算法結(jié)構(gòu)模型包括多個(gè)FSR、它們對(duì)應(yīng)的狀態(tài)反饋函數(shù)(線性或非線性反饋函數(shù))以及1個(gè)密鑰生成函數(shù)f。算法的工作原理是通過(guò)反饋函數(shù)不斷更新每個(gè)FSR的狀態(tài)，再利用FSR的部分狀態(tài)值輸入至密鑰生成函數(shù)作為自變量，函數(shù)f隨著FSR更新所輸出的計(jì)算結(jié)果即是偽隨機(jī)密鑰序列。算法中所使用的FSR包括工作在有限域(Galois Field, GF)(2)上和GF(2u) (u＞1, u∈Z)上兩種。前者以bit為單位更新，每次向左或向右移1 bit，如Grain和Trivium系列算法；而后者大部分以字節(jié)、半字或字為單位動(dòng)作[2]。

圖1(b)描繪了面向密碼領(lǐng)域所設(shè)計(jì)的CGRA的基本結(jié)構(gòu)組成，其內(nèi)部集成了大量的數(shù)據(jù)處理單元(Processing Unit, PE)和執(zhí)行數(shù)據(jù)傳輸功能的互連網(wǎng)絡(luò)。PE中包括多類面向密碼操作的運(yùn)算邏輯單元(Cryptographic Arithmetic Logic Unit, CALU)，每一類CALU實(shí)現(xiàn)一種密碼算子并通過(guò)連接寄存器的方式構(gòu)造多功能流水線，但目前的流水實(shí)現(xiàn)技術(shù)均面向分組密碼，缺乏針對(duì)序列密碼實(shí)現(xiàn)性能提升的相關(guān)研究。因此，除設(shè)計(jì)一種專用CALU能夠兼容實(shí)現(xiàn)多個(gè)域上的序列密碼算法外，本文的研究目標(biāo)還包括配合CGRA計(jì)算資源開(kāi)發(fā)序列密碼算法的并行性，達(dá)成對(duì)工作在不同域上序列密碼算法的高速處理。本文中所使用的變量及其他符號(hào)所表示的含義如表1所示。

表1 4×4規(guī)模的RFAU硬件性能參數(shù)

圖1 序列密碼算法和CGRA基本結(jié)構(gòu)

2.2 FSR的預(yù)抽取并行更新模型

序列密碼算法作為一種可執(zhí)行程序可分解為串行部分和具有多種并行性的并行部分，采用并行計(jì)算的方式加速執(zhí)行并行部分能夠顯著提升系統(tǒng)性能。本文通過(guò)分析現(xiàn)有算法的結(jié)構(gòu)特征，總結(jié)出序列密碼算法中存在3級(jí)可開(kāi)發(fā)并行性。包括：(1) 函數(shù)級(jí)并行性(FP)：由圖1(a)可知，序列密碼算法中包含1個(gè)或多個(gè)FSR的狀態(tài)反饋函數(shù)以及密鑰生成函數(shù)，函數(shù)級(jí)并行性是指在資源足夠的情況下，系統(tǒng)可以并行執(zhí)行密鑰生成函數(shù)和狀態(tài)反饋函數(shù)。(2) FSR級(jí)并行性(RP)：在序列密碼算法中，F(xiàn)SR是一種通過(guò)不斷移位、賦值來(lái)更新自身狀態(tài)的密碼組件，F(xiàn)SR的1次移位與賦值可以看作1次完整的運(yùn)算，如圖2所示，在某些序列密碼算法中，可以1次性完成多步的移位與賦值，從而實(shí)現(xiàn)并行更新，將這種并行性稱為序列密碼的FSR級(jí)并行性。(3) 操作級(jí)并行性(OP)：序列密碼的狀態(tài)反饋函數(shù)或密鑰生成函數(shù)中包含多個(gè)獨(dú)立的密碼操作，其中的一些操作之間沒(méi)有數(shù)據(jù)相關(guān)性，可以通過(guò)并行執(zhí)行來(lái)提升系統(tǒng)性能。

圖2 序列密碼算法FSR級(jí)并行性

在計(jì)算機(jī)體系結(jié)構(gòu)中，并行度是指操作或數(shù)據(jù)并行執(zhí)行的最大數(shù)目，本文規(guī)定3種并行性對(duì)應(yīng)的并行度分別代表算法中可并行執(zhí)行函數(shù)的最大數(shù)目、FSR1次更新過(guò)程的最大步數(shù)和可并行執(zhí)行密碼操作的最大數(shù)量。對(duì)于FP和OP，可以通過(guò)擴(kuò)展硬件資源使多個(gè)函數(shù)或操作并行執(zhí)行，它們實(shí)現(xiàn)的并行度取決于算法本身包含的函數(shù)和不相關(guān)操作的數(shù)量。對(duì)于RP，本文提出一種FSR的預(yù)抽取并行更新策略，該策略通過(guò)提前抽取出未來(lái)多個(gè)時(shí)刻FSR反饋函數(shù)的自變量，從而1次計(jì)算出多個(gè)反饋值完成并行更新。接下來(lái)分析FSR并行更新過(guò)程中RP的實(shí)現(xiàn)并行度，即根據(jù)當(dāng)前FSR運(yùn)行狀態(tài)可推算出的最大反饋值數(shù)量，并評(píng)估關(guān)于并行性不同硬件實(shí)現(xiàn)方式的優(yōu)劣。

FSR在時(shí)刻t的狀態(tài)St可建模為2維n × l元矩陣，如式(3)所示

根據(jù)式(7)可知，若在時(shí)刻t能夠得知FSR中所有狀態(tài)變量rF1,rF2,...,rFk在下1個(gè)時(shí)刻的值aF1+1,aF2+1,...,aFk+1，便可以預(yù)先根據(jù)這些值計(jì)算出t+2時(shí)刻的狀態(tài)反饋值an+2，從而在t時(shí)刻同時(shí)計(jì)算下1個(gè)時(shí)鐘和再下個(gè)時(shí)鐘的狀態(tài)反饋值an+1和an+2。但對(duì)于狀態(tài)St而言，所能預(yù)先計(jì)算出后續(xù)移位過(guò)程中所需狀態(tài)反饋值的最大數(shù)量，取決于反饋端an和距它最近的狀態(tài)變量之間的距離d(代表兩者間存在的寄存器數(shù)量，如圖3)，由此可得：Fk+d=n。此時(shí)，在t時(shí)刻至多能夠從FSR的當(dāng)前狀態(tài)中得到t+d+1時(shí) 刻的狀態(tài)反饋值an+d+1, 而t+d+2時(shí)刻的反饋值如式(8)所示

圖3 FSR更新過(guò)程圖示

其中an+1= rnt+1代表Regn在時(shí)刻t+1的狀態(tài)，不能直接從狀態(tài)St中得到。在任意時(shí)刻t，能夠通過(guò)預(yù)先抽取出FSR此后d個(gè)時(shí)鐘周期內(nèi)參與狀態(tài)反饋函數(shù)的狀態(tài)變量集合Rt+1～Rt+d，從而預(yù)計(jì)算出時(shí)刻t+2～t+d+1時(shí)刻的d個(gè)FSR狀態(tài)反饋值：an+2-an+d+1。即RP可實(shí)現(xiàn)的最大更新位數(shù)為d+1。式(8)為FSR的預(yù)抽取更新模型，該模型證明了FSR可以通過(guò)狀態(tài)變量預(yù)抽取的方式實(shí)現(xiàn)RP并給出了其并行度，下一節(jié)進(jìn)一步評(píng)估不同并行性實(shí)現(xiàn)方式的優(yōu)劣。

2.3 CGRA上序列密碼算法的并行性實(shí)現(xiàn)分析

在CGRA上，算法并行性的實(shí)現(xiàn)方式分為兩種，一是通過(guò)擴(kuò)展硬件資源來(lái)并發(fā)執(zhí)行多線程，二是利用分時(shí)計(jì)算的方式構(gòu)造流水線，令單一硬件資源交替執(zhí)行不同線程。就FP和OP而言，不同函數(shù)之間和操作之間使用的硬件電路并不相同，只能采取擴(kuò)展硬件資源方式實(shí)現(xiàn)并行。對(duì)于RP，可采取流水處理方案，通過(guò)在原有的硬件結(jié)構(gòu)中添加多級(jí)寄存器，將狀態(tài)反饋函數(shù)劃分成多個(gè)子函數(shù)來(lái)執(zhí)行，從而令多組狀態(tài)變量流水作業(yè)依次生成狀態(tài)反饋值。與資源擴(kuò)展方案相比，流水處理方案仍然在每個(gè)時(shí)鐘周期輸出1個(gè)狀態(tài)反饋值，但通過(guò)縮短關(guān)鍵路徑提升了電路工作頻率。此時(shí)，電路中能添加的流水線級(jí)數(shù)受限于能夠預(yù)抽取的狀態(tài)變量數(shù)量。

兩種方案均能開(kāi)發(fā)算法的FSR級(jí)并行性。資源擴(kuò)展方案所帶來(lái)的性能提升與硬件開(kāi)銷之間近似呈線性關(guān)系。而流水實(shí)現(xiàn)方案帶來(lái)的性能收益取決于寄存器插入后的關(guān)鍵路徑長(zhǎng)度，由于難以實(shí)現(xiàn)每一級(jí)流水線對(duì)關(guān)鍵路徑的均等劃分，導(dǎo)致其性能增益低于資源擴(kuò)展方案。但該方案只需增加少量寄存器資源，理論上能有效提升算法實(shí)現(xiàn)的面積效率。尤其對(duì)于工作在有限域GF(2u)上的序列密碼，包含更多的復(fù)雜運(yùn)算，如S盒、模加、有限域乘法、移位操作等，資源擴(kuò)展方案的代價(jià)較大，采用流水處理方案開(kāi)發(fā)RP能夠均衡電路的面積與性能。但對(duì)于FP和OP，由于無(wú)法采取流水處理方案，仍需依靠資源擴(kuò)展的方式實(shí)現(xiàn)并行計(jì)算。

3 可重構(gòu)反饋移位寄存器運(yùn)算單元RFAU

3.1 RFAU結(jié)構(gòu)設(shè)計(jì)

結(jié)合上文分析，本文提出一種面向密碼CGRA的混合粒度并行運(yùn)算單元RFAU。圖4以4行4列的陣列結(jié)構(gòu)為例展開(kāi)說(shuō)明，陣列每個(gè)PE中集成1個(gè)RFAU，內(nèi)部包括32 bit FSR，狀態(tài)變量抽取網(wǎng)絡(luò)、選擇網(wǎng)絡(luò)、布爾函數(shù)實(shí)現(xiàn)單元NBF以及輸出網(wǎng)絡(luò)5個(gè)模塊。單個(gè)RFAU支持實(shí)現(xiàn)GF(2)上的32 bit FSR，也可作為大位寬FSR的一部分配合陣列中的其他模塊實(shí)現(xiàn)GF(2u)域上的序列密碼。FSR支持以級(jí)聯(lián)方式運(yùn)行，每個(gè)寄存器的輸入來(lái)源分為4類。(1) 來(lái)自本地PE，即相鄰左側(cè)寄存器的1 bit數(shù)據(jù)，此時(shí)FSR以bit為單位動(dòng)作；(2) 來(lái)自前1個(gè)PE中處于同位置的寄存器數(shù)據(jù)(FSR4-4將值傳輸至FSR1-1)，此時(shí)FSR以字為單位動(dòng)作；(3) 將輸出網(wǎng)絡(luò)計(jì)算得到的狀態(tài)反饋值作為輸入，此場(chǎng)景下完成FSR以bit為單位動(dòng)作時(shí)的狀態(tài)更新；(4) PE內(nèi)互連網(wǎng)絡(luò)的輸入，此時(shí)外部輸入數(shù)據(jù)進(jìn)入FSR，用作初始化FSR或?qū)⑵渌鸆ALU計(jì)算得到的反饋值傳輸至端寄存器，實(shí)現(xiàn)以字為單位動(dòng)作時(shí)的FSR更新。

圖4 RFAU結(jié)構(gòu)框圖

密碼CGRA中普遍采用Benes網(wǎng)絡(luò)作為置換類操作的硬件實(shí)現(xiàn)方式，鑒于該網(wǎng)絡(luò)特性，RFAU中規(guī)定Benes網(wǎng)絡(luò)在實(shí)現(xiàn)分組密碼和序列密碼時(shí)執(zhí)行不同的硬件功能，當(dāng)處理分組密碼和GF(2u)域上的序列密碼算法時(shí)，RFAU作為置換類操作的執(zhí)行部件；當(dāng)陣列處理GF(2)上的序列密碼算法時(shí)，Benes網(wǎng)絡(luò)作為抽取網(wǎng)絡(luò)完成狀態(tài)變量抽取。選擇網(wǎng)絡(luò)基于交叉開(kāi)關(guān)設(shè)計(jì)，能夠從目的地址序列中為每個(gè)NBF的數(shù)據(jù)輸入端選擇其對(duì)應(yīng)的狀態(tài)變量值。陣列執(zhí)行GF(2)上算法時(shí)，抽取網(wǎng)絡(luò)抽取出參與狀態(tài)反饋函數(shù)的狀態(tài)變量，選擇網(wǎng)絡(luò)完成對(duì)抽取網(wǎng)絡(luò)輸出的重排序，得到狀態(tài)變量傳輸至NBF單元的輸入端，NBF單元的設(shè)計(jì)方案詳見(jiàn)文獻(xiàn)[4]。輸出網(wǎng)絡(luò)將NBF的計(jì)算結(jié)果反饋用于更新FSR，或傳輸至陣列其他模塊。陣列執(zhí)行GF(2u)上算法時(shí)，F(xiàn)SR的狀態(tài)直接作為單元的輸出連接至陣列互連網(wǎng)絡(luò)。

RFAU的結(jié)構(gòu)特點(diǎn)包括：(1) 混合粒度處理模式： RFAU集成在陣列中，1個(gè)完整的PE行能夠組成GF(2)上128 bit以內(nèi)任意長(zhǎng)度的FSR；多行RFAU支持級(jí)聯(lián)，實(shí)現(xiàn)有限域GF(2u)上的512 bit以內(nèi)任意長(zhǎng)度FSR，隨著陣列規(guī)模的擴(kuò)大，RFAU也可根據(jù)實(shí)際的應(yīng)用場(chǎng)景進(jìn)行擴(kuò)展來(lái)提升所適配FSR的長(zhǎng)度，這樣的組織方式保證了RFAU能夠兼顧粗粒度和細(xì)粒度的算法實(shí)現(xiàn)需求，具備高度的處理靈活性。(2)實(shí)現(xiàn)序列密碼算法的并行性：RFAU中的多個(gè)布爾函數(shù)單元支持CGRCA開(kāi)發(fā)GF(2)域上序列密碼算法的FP和OP。此外，在實(shí)現(xiàn)GF(2u)域上算法的RP時(shí)，基于反饋函數(shù)的不同輸入狀態(tài)變量滿足異步處理的特點(diǎn)，在下一節(jié)中提出了一種延遲抽取技術(shù)，并設(shè)計(jì)了面向GF(2u)上序列密碼算法的陣列流水線。

3.2 基于延遲抽取的流水處理策略

對(duì)于工作在有限域GF(2u)上的序列密碼算法，本文提出一種延遲抽取策略，利用輸入狀態(tài)變量進(jìn)入狀態(tài)反饋函數(shù)的時(shí)間差，使流水處理不受FSR反饋端與狀態(tài)變量距離之間的限制。下面以祖沖之密碼算法(ZU Chongzhi, ZUC)為例說(shuō)明該技術(shù)，如圖5，ZUC算法共包含模加、移位10個(gè)計(jì)算節(jié)點(diǎn)，當(dāng)利用流水方案開(kāi)發(fā)算法的并行性時(shí)，處理并行度取決于能夠進(jìn)入流水線的狀態(tài)變量組數(shù)量。ZUC算法的狀態(tài)反饋函數(shù)被劃分為6級(jí)流水線，反饋端和距它最近的狀態(tài)變量rF5之間的距離d=0, k=5。當(dāng)t＜6時(shí)電路求解反饋值a17，反饋函數(shù)的各輸入狀態(tài)變量值保持a1, a5, a12, a14, a16不變。若所有狀態(tài)變量于t=1時(shí)同步進(jìn)入流水線，當(dāng)t=6時(shí)得到第1個(gè)反饋值a17。t=7時(shí)，R7進(jìn)入流水線，狀態(tài)變量取值變?yōu)閍2, a6, a13, a15, a17，系統(tǒng)每經(jīng)過(guò)6個(gè)時(shí)鐘更新FSR，沒(méi)有起到流水加速的預(yù)期效果。

圖5 ZUC算法狀態(tài)反饋函數(shù)

延遲抽取技術(shù)的原理即利用不同狀態(tài)變量進(jìn)入流水線的時(shí)間差，提升流水線能夠并行處理的狀態(tài)變量數(shù)量。如圖6所示，t=2時(shí)組R2的第1個(gè)狀態(tài)變量r12即a2進(jìn)入流水線，直至t=5時(shí)組R6的第1個(gè)狀態(tài)變量r16即a6進(jìn)入流水線，流水線填充完畢。而后系統(tǒng)同時(shí)計(jì)算來(lái)自組R1～R6的多個(gè)變量，t=6后每經(jīng)過(guò)1個(gè)時(shí)鐘輸出1個(gè)反饋值。采用延遲抽取技術(shù)后，屬于同一變量組的不同狀態(tài)變量異步進(jìn)入流水線，不必等待FSR完成更新，其他變量組的部分變量可以提前進(jìn)入流水線。這使得處理并行度不再受狀態(tài)變量在FSR中所處位置的限制，能夠充分發(fā)揮出流水線技術(shù)的性能優(yōu)勢(shì)。

圖6 采用延遲抽取技術(shù)后的流水實(shí)現(xiàn)DFG

保證流水線執(zhí)行過(guò)程時(shí)序匹配的關(guān)鍵在于保證將狀態(tài)變量準(zhǔn)確地抽取并傳輸至其他運(yùn)算單元。因?yàn)閰⑴c變量抽取的R F A U 位置固定且與其他CALU之間的互連方向不變化，因此不能直接按照狀態(tài)變量在FSR中所處的位置設(shè)置被抽取單元，需要按照延遲抽取的順序和變量進(jìn)入流水線的時(shí)刻，決定參與抽取的RFAU。每個(gè)狀態(tài)變量在FSR中的初始位置和經(jīng)過(guò)延遲處理后的被抽取位置決定了延遲抽取的時(shí)間，記該時(shí)間為tz={|1≤z ≤k},t1=0。則延遲抽取策略下的流水線工作流程為，首先計(jì)算出tz與流水線級(jí)數(shù)L，而后在特定時(shí)間節(jié)點(diǎn)依次抽取狀態(tài)變量進(jìn)入流水線，當(dāng)流水線填充完畢并產(chǎn)生第1個(gè)反饋值后更改反饋端寄存器的輸入數(shù)據(jù)源，并保持FSR持續(xù)更新直至運(yùn)算結(jié)束。利用延遲抽取策略，大量序列密碼算法都能以流水方式開(kāi)發(fā)其并行性。

4 實(shí)驗(yàn)及性能評(píng)估

實(shí)驗(yàn)通過(guò)Verilog硬件描述語(yǔ)言，在55 nm CMOS工藝下，對(duì)RFAU單元進(jìn)行實(shí)現(xiàn)，并將其整合在文獻(xiàn)[13]所提出的規(guī)模為4行4列的CGRA中。綜合時(shí)參數(shù)為典型工藝角、最低溫度(-40°C和最低電壓1.08 V。仿真結(jié)果為每個(gè)128 bit的RFAU延遲為2.51 ns；面積約為23456.5 μm2。相較于陣列架構(gòu)的整體延遲與電路面積來(lái)說(shuō)，該單元的延遲和開(kāi)銷并不影響算法的實(shí)現(xiàn)效能。

在RFAU上適配了GF(2)域上的序列密碼算法，由于現(xiàn)有CGRA架構(gòu)中不支持GF(2)上序列密碼算法的實(shí)現(xiàn)，因此本文選取文獻(xiàn)[6, 7]中的可重構(gòu)處理結(jié)構(gòu)，以及文獻(xiàn)[14]中面向特定算法所提出的專用電路結(jié)構(gòu)作為對(duì)比對(duì)象。為實(shí)現(xiàn)公平對(duì)比，本文根據(jù)文獻(xiàn)[15]中的最小特征尺寸轉(zhuǎn)換方法，針對(duì)不同工藝下的延遲、面積換算關(guān)系，將所有數(shù)據(jù)統(tǒng)一至工藝55 nm的條件下，從而盡可能地降低由于工藝偏差而導(dǎo)致的性能評(píng)估偏差。實(shí)驗(yàn)結(jié)果如圖7所示，RFAU的性能表現(xiàn)略遜于文獻(xiàn)[14]所提出的電路結(jié)構(gòu)，這是由于該設(shè)計(jì)針對(duì)每種算法分別進(jìn)行了優(yōu)化，本文所提出的結(jié)構(gòu)則基于可重構(gòu)設(shè)計(jì)理念。與其他可重構(gòu)處理器相比，RFAU的算法實(shí)現(xiàn)性能提升23%～186%。這是由于RFAU能夠同時(shí)實(shí)現(xiàn)序列密碼算法的FSR更新和密鑰生成函數(shù)，保證每個(gè)時(shí)鐘周期輸出1 bit密鑰，高效開(kāi)發(fā)了序列密碼算法的函數(shù)級(jí)并行性。

圖7 GF(2)上序列密碼算法實(shí)現(xiàn)性能對(duì)比

為了驗(yàn)證流水線技術(shù)對(duì)于工作在GF(232)上序列密碼算法的性能提升作用，本文基于文獻(xiàn)[13]中的陣列平臺(tái)對(duì)典型序列密碼算法進(jìn)行映射。在映射算法的選擇上，選取了現(xiàn)有文獻(xiàn)中最為廣泛分析的Snow 3G和ZUC算法以及Sober-t32和SOSEMANUK算法進(jìn)行對(duì)比；在陣列平臺(tái)方面，除第1節(jié)所介紹的Anole[8]和PVHarray[9]外，還包括文獻(xiàn)[12]中東南大學(xué)于2018年所設(shè)計(jì)的一款密碼CGRA，同樣支持GF(232)域上的序列密碼。通過(guò)與以上3個(gè)平臺(tái)進(jìn)行對(duì)比，本文結(jié)構(gòu)和相關(guān)架構(gòu)的性能指標(biāo)如表2所示。對(duì)比內(nèi)容主要包括處理器面積、工作頻率、吞吐率等性能指標(biāo)，同時(shí)本文還對(duì)比了相應(yīng)的面積能效比(單位面積的性能)。

表2 GF(232)上序列密碼算法實(shí)現(xiàn)性能及面積效率對(duì)比

對(duì)于Snow 3G算法，本文所提出的架構(gòu)在吞吐率方面相較于其他兩種陣列結(jié)構(gòu)分別提升了22%和101%，但在面積效率方面分別是其他架構(gòu)的76%和42%；對(duì)于ZUC算法，本文架構(gòu)相較于其他兩種陣列結(jié)構(gòu)帶來(lái)了117%和48%的性能提升，在面積效率方面對(duì)比Anole仍有一定優(yōu)勢(shì)，是文獻(xiàn)[12]所提出結(jié)構(gòu)的31%。實(shí)驗(yàn)結(jié)果表明，由于采用了流水處理結(jié)構(gòu)，本文結(jié)構(gòu)在實(shí)現(xiàn)相關(guān)序列密碼算法時(shí)的性能表現(xiàn)優(yōu)于其他兩種結(jié)構(gòu)；而在面積效率方面不如文獻(xiàn)[12]，與Anole相近，這主要是本文所采用的工藝落后于文獻(xiàn)[12]，若在相同的工藝條件下，本文的面積效率將與之更為接近；同時(shí)其采用了定制化結(jié)構(gòu)的S盒編碼單元，帶來(lái)了更高的面積效率。與未集成RFAU的相同工藝條件下的PVHarray陣列平臺(tái)相比，本文所提出的結(jié)構(gòu)在工作頻率方面，提升約為67%～92%；吞吐率提升約為66%～79%；面積效率提升約為64%～91%，這說(shuō)明RFAU結(jié)構(gòu)可以顯著提升GF(2u)域上序列密碼實(shí)現(xiàn)的工作頻率、吞吐率、和面積效率。

5 結(jié)束語(yǔ)

本文旨在提升基于FSR構(gòu)造的序列密碼算法在CGRA上的兼容性和處理性能。首先研究了序列密碼算法的多級(jí)并行性并建立了FSR的預(yù)抽取并行更新模型；然后分析了CGRA上不同并行性實(shí)現(xiàn)方案的優(yōu)劣。根據(jù)分析結(jié)論，設(shè)計(jì)了一種支持不同域上序列密碼算法統(tǒng)一實(shí)現(xiàn)的硬件單元RFAU，針對(duì)GF(2)和GF(2u)上的序列密碼，分別采取并行抽取和流水處理策略開(kāi)發(fā)了算法的FSR級(jí)并行性。實(shí)驗(yàn)結(jié)果表明，RFAU所需的硬件開(kāi)銷相較于其他結(jié)構(gòu)有明顯優(yōu)勢(shì)，在集成了該單元后，目標(biāo)陣列平臺(tái)不僅可額外支持GF(2)域上的序列密碼算法，同時(shí)提升了GF(2u)域上算法的實(shí)現(xiàn)性能與面積效率，與其他可重構(gòu)陣列結(jié)構(gòu)相比具有較大的性能優(yōu)勢(shì)。綜上，本文技術(shù)不僅有效擴(kuò)展了陣列結(jié)構(gòu)所支持序列密碼的種類，還提升了算法執(zhí)行的吞吐率，為今后CGRA上序列密碼算法處理的研究提供了理論依據(jù)和技術(shù)支撐。