一種密碼專用可編程邏輯陣列的分組密碼能效模型及其映射算法

李 偉高嘉浩 杜怡然 陳 韜

(戰略支援部隊信息工程大學 鄭州450001)

1 引言

密碼計算是一種典型的數據密集型計算形式，在信息安全領域發揮著重要作用，對其處理結構的計算性能有著一定的要求，同時隨著不同類型密碼算法的不斷發展以及對密碼處理結構攻擊方法和手段的進步，對于密碼處理結構還要求其具備一定的靈活性和安全性[1]。

密碼專用可編程邏輯陣列(Cipher Specific Programmable Logic Array,CSPLA)作為一種新型的密碼專用處理結構，迎合了密碼計算的數據流處理特點，使其兼具一定的靈活性和安全性，因而對比密碼專用電路、密碼專用指令集架構處理器等結構更為適應當今密碼處理任務[2]。CSPLA內部由專為密碼處理而設計的運算單元規則排列而成，通過配置信息來形成特定的數據通路，從而完成特定的密碼計算任務。

陣列內部越多的運算單元意味著更豐富的硬件資源，進而能夠映射更大規模密碼計算任務，達到更高的處理性能。隨著陣列規模的不斷擴大，整體結構的功耗和面積也將隨之線性增長，若在映射過程中無法充分利用內部運算單元，將影響到整體的能效比和計算資源利用率。目前，國內外有很多相關的文獻針對粗粒度可重構結構應用映射過程的相關算法、執行時間、實現性能等方面均有所深入研究[3–7]，但是密碼計算任務在運算過程中和通用型計算任務相比而言在數據、存儲等方面有較為明顯的差異，相關模型并未針對密碼陣列的具體結構進行優化，特別是基于不同規模的陣列結構的能效模型研究相對較少。

因此本文以分組密碼算法為出發點，在設計的可重構密碼處理單元基礎上結合層次化的互連網絡擴展了多種不同規模的CSPLA結構并構建了分組密碼算法的能效模型，同時以盡可能提高映射時計算資源利用率為目標，提出了基于該模型的映射算法。選取幾種典型分組密碼算法在不同規模的陣列結構上進行映射實驗，通過實驗數據尋找到計算資源和整體能效比之間的平衡點，選取一個最優的計算資源規模以及排布結構，使得密碼算法映射時達到最優的能效比。

2 密碼專用可編程邏輯陣列

2.1 CSPLA基本結構

本文提出的密碼專用可編程邏輯陣列CSPLA由計算系統、互連網絡、共享存儲類單元(Shared Store Unit,SSU)、控制器以及接口部分組成。其中作為主體部分的計算系統由可重構密碼計算單元

(Reconfigur able Cip her Pr ocess Element,RCPE)規整排列組成，RCPE內部由不同類型的密碼算子單元、多級寄存網絡、分布式控制器和內層互連網絡組成，粒度為32 bit，主要包括算術類AG、邏輯類LG、置換類BP和非線性類NF4類單元，能夠滿足對稱密碼算法中的大部分運算操作。其結構如圖1所示。

RCPE中內層互連網絡可以靈活選擇外部數據的來源以及去向，實現單個單元數據流循環處理，能夠使得陣列內部硬件資源利用率一直處于一個較高的水平，有助于提升整體能效比。CSPLA中規整排列的相鄰RCPE之間通過雙向數據通路連接起來，同時將計算系統、SSU以及輸入輸出接口互相連通，靈活實現數據在陣列內部的傳輸、交換。SSU主要由寄存器堆和SRAM組成，完成密碼算法中子密鑰、常數、中間數據以及配置信息的存取；接口則由兩個FIFO組成，分別對應數據的輸入和輸出緩存。

CSPLA中第1級RCPE為輸入級單元，內部互連網絡同INFIFO相連，用于接收待處理的輸入數據；最后一級RCPE為輸出級單元，內部互連網絡同OUTFIFO相連，用于輸出處理完成的數據。CSPLA同其他陣列結構一樣，內部計算資源具備較為明顯的可擴展性，通過互連網絡，內部單元的排列規模可以進行靈活調整，以此適應不同場景下密碼處理的需求。

2.2 CSPLA硬件資源模型

CSPLA作為實現密碼算法的硬件資源平臺，本文首先對陣列結構進行集合形式的抽象[8]，為之后的映射過程提供具體的依據，將一個m×n規模的CSPLA的硬件資源定義如下：

圖1 CSPLA整體結構及RCPE結構示意圖

(1)將CSPLA中所有的硬件資源根據映射功能上的不同劃分為計算、互連、存儲、輸入輸出接口和控制5類元素，則CSPLA的硬件資源模型可以視為一個集合A={FUN,CON,CTR,MEM,IO}；

(2)CSPLA中的計算資源主要由規則排布的可重構密碼計算單元中的4類算子組成，其集合可表示為FUN={(AG,LG,BP,NF)i,j|i=1,2,···,m;j=1,2,···,n}；

(3)CSPLA中的互連資源主要包括RCPE內部的數據傳輸網絡和RCPE外部的互連網絡，可表示為CON={(Con_in,Con_ex)i,j|i=1,2,···,m;j=1,2,···,n}；

(4)CSPLA中的存儲資源主要包括RCPE內部的寄存資源和共享存儲單元SSU，可表示為MEM={SSU,(Rst)i,j|i=1,2,···,m;j=1,2,···,n}；

(5)CSPLA中的輸入輸出接口由輸入級單元和輸出級單元同外部FIFO的數據通路，每一路均為32 bit，可表示為IO={Input1,j,Outputm,j|j=1,2,···,n}；

(6)CSPLA中的控制結構包括處于全局控制器和各可重構運算單元的分布式控制器，可表示為CTR={Ctr_top,(Ctr_cuc)i,j|i=1,2,···,m;j=1,2,···,n}。

整個映射過程就是針對特定密碼計算任務在硬件模型的集合內部限定的資源上進行數據的調度和分配，最終映射的結果為包含上述全部5類元素的配置信息。

CSPLA優勢在于數據處理的多路并行性，從理論上CSPLA可以通過無限堆疊計算單元來擴充計算資源，實現更大規模的密碼計算任務以提升吞吐率。隨著規模的擴大，陣列結構的面積和功耗將顯著增加。內部各類資源不一定能滿足數據實時處理的需求，從而影響到整體能效。因此陣列結構規模并非越大越好，單純以性能指標來評價其結構規模的優劣往往不足以說明問題。本文擬從密碼處理的能效作為評價CSPLA結構的參數指標。對于陣列而言必然存在一個相對的規模，在處理特定密碼任務時達到相對最優能效。

3 CSPLA能效模型

3.1 模型建立

針對模型需求，結合分組密碼和陣列結構的基本特點，首先給出如下定義：

定義1循環空間和非循環空間：將待映射的分組密碼中需要反復執行多次的操作組成的集合稱為循環空間C；算法過程中僅僅執行1次的操作構成的集合為非循環空間M。兩者關系為C ∩M=?，且C∪M=Block，即C和M交集為空，兩者共同組成完整的待映射的分組密碼算法。

定義2空間映射：C=(V,E)和M=(V,E)是對應循環空間和非循環空間的數據流圖，包括操作節點和數據依賴邊，空間映射就是在陣列的硬件基礎上生成一個由計算資源和互連資源組成的數據路徑。

定義3 RCPE計算能力：對算子單元和循環空間中的運算操作歸一化處理，RCPE能夠完成循環空間中操作比例定義為RCPE的計算能力α，顯然對于不同的算法或不同的映射方案α值不同且0≤tα≤1。

定義4最大算子頻次：將待映射算法中映射單分組獨立操作所需最多的算子數目定義為最大算子頻次Nmax，對于m×n規模的陣列，映射的并行度受限于Nmax。

CSPLA最終能效比取決于密碼算法實現的吞吐率和功耗。在實現過程中一方面要提高密碼算法吞吐率，另一方面則盡可能降低陣列的整體功耗。對于一個m×n規模的陣列，吞吐率可表示為

吞吐率表示每秒數據處理量，能夠直觀體現陣列的密碼計算能力。F為陣列運行頻率，顯然陣列運行頻率越高，吞吐率也越高。而D為陣列運行周期平均處理數據量，單位為bit，可表示為

其中，Q為 數據分組數量，W為算法分組長度，Tcycle為完成數據處理所需的運算周期。由式(2)分析可知，對于特定的密碼算法，W為固定值，若要提高陣列運行周期內數據處理量，一方面是盡可能增加內部并行處理的數據量；另一方面則是縮短運算的時鐘周期。假設各分組內部映射并行度為i，不考慮數據依賴關系和其他非計算延時的情況下，算法的運算周期Tcycle可表示為

m×n規模的陣列功耗可表示為式(4)，其中PFIFO和PSSU分別為FIFO和共享存儲單元的功耗，PS和PD分別為單個RCPE的靜態功耗和動態功耗。隨著陣列規模的擴大，功耗的各項數值必將有一定幅度的增加。映射的最終能效模型可表示為式(5)

3.2 模型參數分析

3.2.1運算周期Tcycle

數據在運算過程中的傳輸可能受到互連資源和接口的限制而產生一定程度的延時，與此同時還需要占用陣列內部的互連資源進行數據傳輸。當內部處理的數據較多時，有限的互連資源無法滿足多組數據同時傳輸的需求，陣列輸入、輸出FIFO也可能出現無法滿足數據輸入輸出需求的情況，這時數據子塊處理完成后產生阻塞，浪費單元計算性能的同時也產生了一定的傳輸延時。CSPLA的輸入輸出FIFO每個時鐘周期內只能有1組32 bit數據進出，假設算法數據塊以最大粒度進行處理，當計算資源對數據的實時處理效率超過了接口的輸入輸出效率，即

RCPE必須等待接口的數據輸入或輸出才能繼續執行運算任務，從而產生接口延時。在實際運算過程中，陣列內部的互連資源總是有限的，接口往往不是限制運算性能發揮的主要因素。一般在計算資源滿足映射需求前提下只需考慮外部互連資源是否滿足資源限制。RCPE間每一個傳輸通路都可以實現1組數據的傳輸，對于一個m×n規模的陣列，RCPE外層的互連資源量可以表示為(m ?1)n+m(n ?1)。

從分組密碼處理橫向角度來看，每個時鐘周期內各個數據子塊在處理上很少有數據交互，彼此的運算過程較為獨立，使用的互連資源相對較少；從縱向角度來看，分組密碼采用的是迭代型結構，核心的輪運算過程中各個數據子塊都與前一時鐘周期中間數據存在著直接的數據交互，各個順序排列的算子單元間存在著直接的數據交互，互連資源開銷較大。假設數據運算過程中間不存在橫向的數據傳輸需求，則此時運算過程額外產生的傳輸延時可表示為

此外由于運算單元在運行過程中計算任務的改變而暫停計算，等待重新寫入配置信息后再次進入運算狀態也將產生一定的時鐘延時。RCPE中完成動態重構的過程需要兩個時鐘周期，設β為RCPE的動態重構能力，分組內部數據重構信息量為R，則由完成運算任務而產生的動態重構延時可表示為

當陣列內部單元需要進行配置重構時，可將待重構計算單元的任務暫停并轉移至其它空閑的計算單元，如圖2所示，通過運算任務的合理分配從而將重構的時鐘延時隱藏在整體的計算任務周期中，在這種情況下重構產生的時鐘延時對最終能效的影響可以通過計算資源合理調度得到有效削減[9]。假設互連資源能夠完全滿足任務轉移需求，則產生的動態重構延時可表示為

當陣列內部多個分組數據并行處理時，處于空閑狀態的計算單元減少，若沒有充足的空閑單元承接轉移的計算任務，待重構的計算單元只能暫停相應的計算任務，將中間數據寫入存儲資源，待重構完成再進入運算狀態，由此在運算過程中引入了重構延時。任務處理周期將延長，導致陣列的吞吐率降低。

圖2 計算任務轉移隱藏動態重構延時

綜合考慮運算過程中的非計算延時，映射的最終能效模型可以改寫為式(10)。在實際映射過程中，數據在運算過程中不可能完全不存在橫向的數據互連，同時當分組數量達到一定程度時，互連資源可能無法滿足數據無阻塞傳輸的需求，從而成為限制能效提升的主要因素，由此必然使整個算法的處理周期延長，產生的非計算延時大小與具體的分組密碼算法及映射方案有關。

3.2.2整體功耗P m×n

CSPLA中RCPE組成的計算資源在整體資源中占據絕大部分比重。由上文分析可知，陣列整體功耗P m×n將隨著陣列規模的擴大而增大。基于課題前期的研究，在規模參數m和n變化的過程中，輸入輸出FIFO和SSU的功耗開銷即PFIFO和PSSU相對穩定，僅有微小幅度增加，而靜態功耗PS變化幅度最為顯著，與陣列規模參數呈現出線性變化的關系，且單個RCPE的靜態功耗一般是其動態功耗的數10倍。

當陣列規模上升到一定程度后，m×n個RCPE產生的靜態功耗PS成為整體功耗的主要來源，在P m×n開銷中占據的比重遠大于其它幾項功耗開銷，則CSPLA整體功耗的表達可簡化為

由此可見，映射能效受到運行頻率、運算周期、功耗等因素的共同影響。對于m×n規模的陣列，映射過程中應當充分利用陣列內部的運算單元，提高硬件資源的利用率，以平衡隨著規模增大而引入的功耗開銷，使有限的運算單元盡可能處在運算狀態中，能夠使得映射達到相對最優能效值。

3.2.3陣列規模參數

目前分組密碼算法的分組長度大多為64 bit和128 bit，其中128 bit是更為主流的分組長度。相對集中的分布范圍有利于選擇CSPLA的規模，即m和n的取值。m和n的值越大，即陣列中RCPE數量越多，包含的各類資源也越豐富。理想情況下陣列映射的最大分組數量Q可表示為式(12)。

從陣列的橫向規模來看，RCPE處理粒度為32 bit，m取值應該在適應算法分組長度的基礎上進行選擇，當每一級設置4個RCPE時能夠基本滿足128 bit的單分組數據處理需求。與此同時第1級作為輸入級，其內部寄存器與輸入FIFO的接口直連，考慮到接口電路負載能力，橫向RCPE數量應該控制在10以內，因此本文中將m的取值設定為4或者8。

從陣列的縱向規模來看，對于分組密碼的工作模式而言，在ECB模式下不存在數據依賴關系時，將單周期內的操作在每一級RCPE上完全流水展開，達到較高的映射性能。但實際應用中分組密碼更多的情況下使用的是CBC和OFB這類存在前后數據依賴的工作模式，無法實現算法的流水展開。縱向上的級數過大使得陣列整體的面積和功耗開銷變得難以承受，從而限制其應用場景。因此本文中考慮CSPLA的自循環處理機制，結合分組密碼的多個分組并行處理方法，考慮到SSU單元的兩級擴展性，將n取值從2開始并進行遞增。通過對不同規模CSPLA的映射分析，選取出相對最優能效的陣列規模結構。

3.3 映射算法

在CSPLA上進行算法的分組并行映射的基本步驟如下[10]：

(1)根據待映射算法的操作劃分對應的循環空間和非循環空間，生成對應的數據流圖；

(2)設定分組數量，多個數據子塊的處理首先需要在滿足陣列計算資源限制下選取合適的值；

(3)為單分組的數據選取映射的可重構計算單元RCPE，以及內部具體的算子單元；

(4)由數據流圖，即根據映射過程中數據的傳輸關系完成互連配置信息的生成，搭建相應的數據路徑，涵蓋除控制之外的其他4類硬件資源；

(5)根據數據路徑和時序關系，生成控制配置信息，包括讀寫控制、動態重構控制等。

基于上文得到的能效模型，為得到盡可能高的能效值，在相關資源滿足前提的情況下，針對CSPLA的自循環單分組并行映射，提出如表1所示的算法，輸入為陣列的硬件資源模型和待映射的分組密碼算法，輸出為算法具體的配置信息，算法的約束條件為CSPLA包含的有限硬件資源。

首先對于待映射的分組密碼算法，通過操作劃分，確定算法的循環空間和非循環空間并生成對應的數據流圖(行(1)、行(2))。循環空間中的運算操作一般利用RCPE的自循環運算實現，而非循環空間中的運算操作在單次運算完成后還需要考慮數據傳輸和配置重構的問題。其次根據最大算子頻次初步設定映射并行度，同時需要考慮互連、接口資源是否符合約束條件，在計算和互連兩類元素均滿足約束條件的情況下，可以確定并行度并繼續映射，否則應當調整Q值直至滿足約束條件(行(3)～行(6))。在映射過程中針對每一個獨立操作選擇RCPE中合適的算子單元，并確定前后操作的互連關系，更新操作映射后的陣列計算、存儲以及接口、互連資源信息(行(7)～行(13))。將循環空間和非循環空間的數據流圖生成全部的計算和互連配置信息的集合，并生成與映射方案對應的控制配置信息(行(14)～行(16))，最終輸出包含相關5類資源的全部配置信息。

表1 分組密碼的自循環單分組并行映射算法

4 實驗及參數分析

4.1 映射實驗

得益于CSPLA結構的可擴展性，通過對RCPE和SSU的數量、排列方式以及互連網絡的調整可以較為靈活地搭建不同規格的陣列結構。使用Verilog HDL對不同規格的CSPLA設計進行描述，并利用EDA工具對設計進行映射的仿真分析和數據的驗證測試。

本文選取了AES,SM 4和DES 3個最為典型的分組密碼算法，在不同規模的陣列上進行不同數量的單分組映射實驗，得到的參數結果如表2所示，其單項指標參數隨陣列規模的變化情況如圖3所示。

4.2 實驗結果分析

從表2中的數據分析可知，陣列規模的擴大意味著其內部可以容納更多分組的數據的映射，并行映射分組數據數量不斷增大，在性能上帶來了吞吐率的顯著提升，實際的映射并行度和最終的運算吞吐率則與具體算法有關。而同一算法在不同規模陣列上的運行頻率隨規模參數的變化并不明顯，這是因為運行頻率取決于映射方案中的關鍵路徑，算法所映射的算子單元組成了內部數據路徑，規模的變換并不會改變算法映射中關鍵路徑的延時。

CSPLA整體功耗則與規模參數呈現出線性關系，規模越大則整體功耗開銷越大。為了保持能效收益，在陣列上進行多組數據的并行映射，隨著資源使用程度趨于飽和，產生的非計算延時導致平均運算周期變長，導致吞吐率偏低的同時能效隨之降低。由此得出的不同CSPLA規模參數下的能效數據如圖4所示。

當陣列結構為4×2時，內部的硬件資源較為緊張，而擴展為4×4時，陣列各類資源都更加充裕，例如在4×2規模的陣列上映射DES算法，在運算過程中需要對BP單元以及部分互連網絡進行重配，由此產生了動態重構延時。而在4×4陣列上映射時則能夠保證計算資源的充足，僅需對互連信息進行重配，運算周期反而降低。因此在保障基本運算能力前提下，陣列規模不宜過小。當陣列橫向規模不變，縱向規模繼續擴大時，即陣列結構為4×6或4×8時，多組數據并行映射帶來資源使用的擁擠，產生的非計算延時特別是其中占主要部分的傳輸延時將使得運算周期延長2～10個時鐘周期不等，同時伴隨著整體功耗開銷增大，從而幾種典型算法的能效約有10%及以上不同幅度降低，對于橫向參數為8時的變化趨勢也幾乎類似。

表2 典型分組密碼算法映射參數

圖3 各項參數隨陣列規模的變化示意圖

圖4 典型分組密碼算法映射能效

當縱向規模相同時，陣列的橫向規模從4擴展至8時，CSPLA內部的硬件資源能夠滿足更多數據的并行映射，但是功耗也同步增加，且陣列接口FIFO的輸出能力總是有限的，特別是當數據填充耗時高于分組數據在每一級處理周期時，就將存在接口延時導致計算資源閑置的情形。平均而言橫向規模為8時單個分組數據所需的完整運算周期普遍多于規模為4的陣列結構，因而在運算周期延長4～6個時鐘周期的情況下能效將受到一定程度的影響。其中不同算法由于自身相關參數的差異受影響的程度不同，最終幾種典型分組算法的能效有5%～34%不同程度的降低。結合上述分析可知，AES和DES算法在4×4規模時分別取得相對最優映射能效33.68和11.31 Mbps/mW,SM4算法在4×6規模時取得最優能效14.63 Mbps/mW。

表3 AES算法相關參數對比

密碼處理結構普遍采用AES算法實現的相關參數作為評價指標，因此本文同樣選取AES算法在幾種典型規模的CSPLA上的映射參數同其它結構進行比對，得到的結果如表3所示。

本文參考了文獻[16]中的工藝換算方法能效進行了簡單等價，該方法無法消除工藝偏差帶來的影響，僅作為參考依據。對比表3中結果可以看出在55 nm工藝下，CSPLA(8×8)得益于數據流計算的優勢，其整體結構的計算效率更高，在能效上對比文獻[11]、文獻[12]中的指令集密碼處理結構有明顯提升，而對比文獻[14]中同為陣列類型的處理結構在能效上則只存在小幅度優勢。根據本文所提能效模型及映射算法，通過適當控制陣列結構規模的同時兼顧較高的資源利用率，可以適當縮減運算過程中不必要的非計算性延時，雖然規模的降低導致了吞吐率的降低，但得益于功耗開銷的顯著降低，因而映射能效反而表現出一定提升。此時CSPLA(4×4)的映射能效相較于8×8規模時有明顯提高，對比文獻[14]中的結構能效提升了將近1倍，略優于文獻[15]中所提出的結構。

綜上所述，分組密碼算法在CSPLA的映射能效并不會隨規模的擴大而持續增加。CSPLA的橫向規模參數應當和接口輸入輸出能力、算法運算位寬相適應，一方面在較短的時間內完成單級計算的數據處理填充，另一方面可以充分開發算法分組內的處理并行性；CSPLA的縱向規模參數應與算法計算周期、資源需求量相適應，以盡可能在提高資源利用率的同時縮短運算周期，從而達到最優的能效值。本文提出的能效模型及其映射算法能夠有效地實現分組密碼算法在CSPLA結構上的高能效映射。

5 結束語

本文提出了一種密碼專用可編程邏輯陣列結構CSPLA的規模參數與映射能效的關系，在一種確定的陣列結構的基礎上，結合分組密碼算法單包并行處理的特點，從陣列的橫向和縱向規模參數出發，分析了影響陣列最終映射能效的相關因素，建立了與硬件結構相匹配的能效模型并提出了對應的映射算法，結合典型分組密碼算法進行了映射實驗分析，結果表明陣列規模的持續擴大并不會帶來密碼算法映射能效的持續提升。在實現多個分組并行處理的情況下陣列引入的非計算延時會延長平均運算周期，降低整體的運算吞吐率，無法平衡整體增加的功耗開銷，導致能效降低。在應用過程中應靈活確定陣列的規模參數，以適應不同情形下的指標需求。本文提出基于陣列結構的分組密碼算法能效模型，對于序列密碼算法、雜湊密碼算法的高能效映射實現也具有一定的適用價值。