CRCLA的雜湊算法優先級決策映射方法

章宇雷，李 偉，徐金甫，陳 韜

(信息工程大學 信息安全重點實驗室，河南 鄭州 450000)

0 引 言

近年來，國內外針對雜湊算法硬件實現的研究較多，但絕大多數文獻僅僅是針對專用集成電路硬件結構進行設計的，在靈活性上具有局限性，難以適應多種算法實時切換的需求。粗粒度可重構密碼邏輯陣列(coarse-grained reconfigurable cipher logical array，CRCLA)是一種基于數據流的高效運算結構[2]，兼顧了靈活性和處理速度的需求，能夠通過配置實現多種算法的實時重構。

目前，國內外針對算法映射到CRCLA上的研究，主要集中在分組密碼算法上，如文獻[2-5]。然而國內外還沒有針對雜湊算法映射問題的專項研究，相較于其它類型算法，雜湊算法在運算中具有其不同的特征，在映射的方法上會有一定的區別。同時，在映射過程中，對于某一具體操作的映射，往往存在著多種候選映射方案，最佳映射方案的選取必定會影響后續操作的映射，且決定了整個映射結果的優劣，需要結合雜湊算法的映射特征設定相應的決策機制來選取最佳映射方案。

本文分析了雜湊算法的基本特征，結合可重構陣列的硬件結構，采用空間展開操作并行的映射手段，針對在具體映射過程中某一操作的多種候選映射方案提出了一種優先級決策機制，從而總結出雜湊算法高能效映射方法，并選取了幾種典型的雜湊算法進行實驗。

1 雜湊密碼算法處理特征

雜湊密碼算法是將任意長度消息編碼的數字序列按照一定的規則進行填充后按固定長度分成一些消息塊，經過消息擴展后的消息塊經過壓縮變換后輸出固定長度的雜湊值。雜湊算法處理流程如圖1所示。

圖1 雜湊算法處理流程

通過對多種典型的雜湊算法的運算過程進行分析，雜湊算法具有以下幾個特征：

特征1：不同算法涉及的運算操作均較為簡單，大部分運算操作在陣列上僅需計算單元中的一個算子單元即可實現，因此在映射時可以將部分操作進行合并，減少映射資源。

特征2：消息擴展部分輪間數據依賴強烈但有固定規律，由計算過程可以發現，從某一輪開始，該輪輸出數據依賴于之前輪的輸出數據，但具有固定性。在映射中，需要注意每一輪數據的存儲以方便后續的運算，因此數據的存儲方式是一個需要考慮的問題。

特征3：消息擴展模塊與壓縮部分的關聯數據呈單向流動，且兩部分可同步進行，映射時存在并行執行的可能性，從而可以減少算法的執行周期，提高算法的吞吐率。

特征4：壓縮部分輪內數據依賴強烈但無輪間數據依賴，壓縮部分的輪運算每輪輸出只與前一輪的數據存在依賴關系，輪運算內部數據僅與當前輪相關，不存在輪間數據依賴關系。因此在映射時，相關計算PE的跨度不要過大，減少不必要的互連資源。

綜上所述，雜湊密碼算法的基本特征對算法的映射方式進行了一定的約束，本文將依據雜湊算法的基本特征提出雜湊算法的高能效映射方法。

2 CRCLA基本結構及模型

CRCLA采用了數據流加配置流驅動的方式，通過配置信息來配置陣列內部計算單元以及互連結構，從而實現不同種類的密碼運算操作。

2.1 CRCLA硬件結構

CRCLA整體上由輸入輸出FIFO、接口控制器、陣列控制器、配置控制單元、共享存儲單元(shared store unit，SSU)和運算系統組成，其結構如圖2所示。

圖2 CRCLA整體結構

其中，輸入輸出FIFO負責數據的緩存以及與外部數據的交互，輸入FIFO用來存儲輸入的配置信息以及數據，輸出FIFO用來存儲經過陣列計算后得到的輸出數據；配置控制單元由1個配置解析器和4個配置頁面組成，4個配置頁面之間可以通過控制進行切換，可實現陣列的實時重構，配置解析器用來解析配置信息，將配置信息送至對應的部件；陣列控制器可通過配置信息的配置，負責產生陣列內部所需要的控制信號，以保證算法的正常執行；計算系統由64個計算單元(process element，PE)和基于2D-Mesh的互連結構組成。

PE由可重構密碼塊(reconfigurable cryptography block，RCB)及互連單元組成，RCB承擔主要的計算任務，內部包含著能實現多種運算的運算部件，且可通過內部互連實現數據互通，能夠實現復雜的密碼運算。RCB內部還包含寄存器單元，便于實現數據的暫存以及控制數據路徑的延時，可以適應不同算法的需求。由于部分密碼算法存在大位寬計算需求，同一行多個PE能夠級聯，以實現64 bit、128 bit的運算。

2.2 問題描述

為方便問題描述，需要將雜湊算法到可重構陣列上的映射抽象成數學模型，結合國內外提出的陣列結構，本小節抽象出通用陣列數據流模型，對算法映射問題給出以下定義。

定義1 粗粒度可重構陣列的硬件資源圖(coarse-grained reconfigurable array resource graph，CRAG)可表示為：給定一個由N×N個PE構成的CRCLA，包含共享存儲單元等資源，其硬件資源圖可表示為CRAG={PE,Con,M}，其中，PE為陣列中所有計算單元PEi,j的集合，i,j分別表示PE位于第i行，第j列，1≤i≤N, 1≤j≤N;Con表示互連資源的集合；M表示存儲資源的集合。

定義2 可重構陣列的計算單元資源的集合可表示為：PE={OU1,OU2,…OUn}，其中OU表示PE內部包含的算子單元，如算術類單元、邏輯類單元、置換類單元等各類密碼運算單元。

定義3 可重構陣列的互連資源的集合可表示為：Con={ConPE,ConPES}，其中，ConPE表示PE之間的互連，ConPES表示PE與共享存儲單元之間的互連。

定義4 可重構陣列的存儲資源的集合可表示為：M={Rs,SSU}，其中Rs為陣列中的寄存器單元Rsi,j的集合，i,j分別表示Rs位于第i行，第j列，1≤i≤N, 1≤j≤N；SSU表示共享存儲單元。

定義5 一個雜湊算法的集合可表示為：Ha={op，L，SData}，其中，op表示雜湊算法包含的一系列運算操作，L表示各個操作之間的連接關系，SData表示雜湊算法運算過程中需要寄存的數據。

定義6 雜湊算法到可重構陣列上的映射：給定一個雜湊算法的集合Ha={op，L，SData}和一個可重構陣列的硬件資源圖CRAG={PE,Con,M}，Ha到CRAG上的映射可表示為在滿足資源約束的條件下，完成op→PE，L→Con，SData→M的綁定。

3 雜湊算法高能效映射方法

本節首先進行雜湊算法的映射分析，為提高映射能效，確定總體采用的映射手段后，針對映射過程中某一具體操作的多種候選映射方案提出了基于優先級的決策機制，并對映射方法進行了描述。

3.1 雜湊算法映射分析

對于雜湊算法的填充部分，其操作是將數據“1”添加到消息末尾，再添加k個“0”，需要滿足以下條件

1+l+k=448 mod 512或1+l+k=896 mod 512

(1)

式中：l表示填充后的總長度，mod為模運算。由于填充部分運算的特殊性，通過對現有的陣列結構進行研究發現，其計算單元無法滿足填充部分運算的需求，因此，僅針對經過填充后的一個消息塊的消息擴展、迭代壓縮的映射進行研究。通過對比多種雜湊算法的研究分析，其主要參數數據見表1。

表1 多種雜湊算法主要參數對比

不難看出，不同種類的雜湊算法不同之處在于數據位寬、操作數長度，循環次數以及最后輸出的雜湊值。其算法流程以及涉及的運算幾乎是一致的。

CRCLA陣列結構的輸入數據位寬為32 bit，在陣列內部同一行多個PE之間可以通過級聯來實現大位寬處理。上述列表中所涉及到的運算通過配置RCB即可完全實現，并且能夠滿足多個操作并行的處理。

對于雜湊密碼算法，衡量其性能的指標主要通過吞吐率來體現，假設L為處理數據位寬，N為雜湊運算過程所需時鐘周期數，F為時鐘頻率，則雜湊算法的吞吐率可以表示如式(2)所示

(2)

式(2)中可以看出，要提高雜湊算法的吞吐率，主要可以通過增大數據處理位寬，增大時鐘頻率，以及降低運算過程所需時鐘周期數來實現。由于大多數文獻中評價雜湊算法的處理性能通常以吞吐率作為評價指標，而可重構陣列可采用堆疊可重構單元的方式來提高吞吐率[3]，因此僅考慮吞吐率指標是不夠客觀的，需要同時考慮算法運行的功耗。其功耗取決于具體的映射方案，以及消耗的資源總數來確定。

3.2 空間展開操作并行

通過3.1節對雜湊算法的映射分析，其主要運算過程體現在消息擴展和迭代壓縮中的循環部分。首先，對消息擴展模塊和迭代壓縮模塊進行分別討論。在一組消息經過消息擴展后將各消息塊分成若干個操作數(不超過16個)，再將這些操作數通過一些基本的運算生成下一個操作數后并更新。陣列中存在著通用的共享存儲單元SSU，若將劃分后的這些數據都存入SSU，將會大大加劇從SSU到PE的互連資源的壓力，極有可能造成互連資源不足導致映射失敗的情況，且不方便后續的數據更新及運算。陣列中每個PE中都包含寄存器單元，因此，將初始化的若干個數據通過移位的方式傳送至每個PE的寄存器單元中，通過PE之間的互連網絡來實現移位，每當生成一個新的數據后，通過配置打開寄存器的使能信號，實現移位的功能，來達到數據上的更新。以16個32位操作數為例，深色箭頭表示PE內部寄存器內的數據的走向，每個PE承擔著不同的計算任務，如圖3所示。

圖3 移位寄存器的構成

而對于迭代壓縮模塊，每一輪的運算實質上也是對各個數據進行密碼運算并更替，每一輪輸出數據僅與上一輪相關，因此，只需考慮在映射時，哪一些操作可以合并映射在同一個PE上以及布局布線，減少陣列中的資源消耗。

在同時考慮兩個模塊的映射時，采取空間展開并行操作的方式，在其資源充足的前提下，將CRCLA陣列在空間上劃分成兩塊，上半部分映射消息擴展模塊，下半部分映射迭代壓縮模塊。上下兩部分存在著從消息擴展部分到壓縮迭代部分數據的單向流動，通過對控制上的配置，當消息擴展模塊生成數據后，送入迭代壓縮模塊進行運算，實現兩個模塊的并行映射與執行，這樣既能充分利用可重構陣列的資源，又能減少運算周期，有效提高算法的吞吐率。當陣列規模較小時，則采用多重配置頁面的模式進行映射。

3.3 優先級決策機制

在制定了總體的映射方案后，再對映射過程中某一具體操作的映射進行分析。

在映射過程中，一個雜湊算法的某個操作往往會存在多種映射方案，如寄存器的選取、互連資源的走向、運算PE的選取等等。

定義7 候選映射方案：針對雜湊算法映射中的某一具體操作及與其相關的操作數和連接關系，存在多種組合方式Map={Mapk∶op→PEi，j，L→Con，SData→Mi,j，k=1,2,…n}，能滿足當前映射的需求，則Mapk稱為一種候選映射方案。

某個操作的多個候選映射方案的選取往往會直接影響后續操作的映射方案的選取以及整個映射方案的優劣，因此，需要建立一套適配于雜湊算法映射的決策機制，來從多種映射方案中選取最佳方案，使得其在各個方面都較優。本文從存儲資源開銷、PE內部占用率開銷、互連資源開銷、配置信息量、延時開銷5個方面進行討論并確定其優先級。

存儲資源開銷。在雜湊算法映射到陣列的過程中，由以上分析可知，對陣列內部的寄存器需求較高，若某個映射操作上占用過多的寄存器資源，極有可能導致后續的映射操作難度加大。

PE占用率開銷。可重構處理單元PE是用來執行具體運算的功能單元，若在映射中導致一些PE上承擔的計算任務明顯比其它PE要多，而在后續的映射過程中由于互連資源的限制需要再次使用這部分PE，將會導致需要重構配置的次數增多，同時也會加大配置信息量。

互連資源開銷。由于陣列內的互連資源是有限的，而面積和功耗導致了不可能保證任意兩個PE之間的直接連接。由第2節可知，本文基于的陣列結構在互連上采用的是最為常規的2D-mesh結構，只能夠保證一個PE可以同其相鄰的PE進行直接連接。在配置當前操作時，必須要考慮使用的互連資源，否則后續的映射操作可能會存在互連資源沖突的情況，導致需要切換配置頁面重構配置，這不僅大大加劇了映射的復雜度，并且也可能直接導致映射失敗。

配置信息量。映射方案的配置信息量越少，數據注入輸入FIFO占用的時鐘周期越少，同時說明需要配置的結構單元越少，映射復雜度越低，效率越高。

延時開銷。輪函數的循環部分為核心部分，其核心循環的延時開銷將直接決定映射的性能優劣。

這5個方面如果單獨考慮則過于片面，但是如果僅僅通過計算相加的方式來擇優選取，由于各個開銷在計算結果的單位上完全不同，且重要性不同，則不能客觀反應出總的映射開銷，選取的映射方案實質上并不一定就是最佳的。因此，本節設計了針對雜湊算法的決策機制，分析這5種開銷的重要性程度，給出優先級排序，按照優先級從大到小的方式進行篩選得出最佳方案。

本文的目標瞄準點為雜湊算法的高能效映射，為了提高雜湊算法映射后的計算性能，將延時開銷作為首要評判指標。其次，雜湊算法在映射過程中，需要用到大量的存儲資源，而存儲資源的分配不佳將會導致后續的操作存儲資源分配難度大大加劇，且在一定程度上會影響到互連資源的消耗上，因此，將存儲資源消耗作為決策機制中的第二評判指標。當決定互連時，若選取占用較多的互連資源的方案，將會導致后續的操作在互連上存在繞線過多，或占用過多PE作為路由PE的情況，甚至可能導致映射失敗，因此將互連資源作為第三評判指標。考慮PE占用率是為了平衡各個PE的使用程度，以免出現某些PE操作過多某些PE操作過少的情況，因此將PE占用率作為第四評判指標。最后，在剩下的侯選映射方案中選取配置信息量最小的方案進行映射。據此，得出表2所示的決策機制偽代碼。

表2 決策機制偽代碼

3.4 雜湊算法高能效映射方法

通過以上分析，得到基于優先級決策機制的雜湊算法高能效映射方法描述如下，其流程如圖4所示。

圖4 雜湊算法高能效映射方法流程

步驟1對目標陣列硬件結構及其可用的資源總量進行分析，得到陣列資源圖CRAG={PE,Con,M}；

步驟2對需要映射的算法進行分析，得到算法中可映射加速的部分的集合Ha={op，L，SData}；

步驟3依據陣列可用資源及待映射算法的復雜程度，判斷是否可以采用空間展開操作并行的方式進行映射，如可行，將按照3.2節所述方案進行映射劃分。如不可行，則采用多配置頁面方式；

步驟4依據陣列中計算單元的結構對算法中可以合并的操作進行操作合并，得到新的算法操作集合Ha`;

步驟5按照算法操作的優先級對算法中的每個操作進行映射，判斷該操作是否存在候選映射方案，若存在，則跳至步驟6；若不存在，則跳至步驟7；

步驟6計算各個候選映射方案的5個開銷值，按照3.3節所述映射決策機制進行決策，得到最佳映射方案；

步驟7更新硬件資源映射圖，并判斷是否存在未映射的操作，若存在，則重復步驟5～步驟7；若不存在，則映射結束，依據硬件資源映射圖得到陣列數據流配置信息。

4 實驗驗證與分析

本節首先通過SM3映射示例來展示整個映射流程及映射結果，然后對決策機制進行實驗對比。

4.1 算法映射示例

以SM3算法為例，遵照以上映射流程進行映射。對運算操作進行合并后映射到PE中，選取RAM單元用來存儲算法中涉及到的IV等常量。依據所需算子數量，將SM3的消息擴展和迭代壓縮部分分別映射到陣列上，得到圖5所示的陣列數據路徑映射圖。

如圖5所示，將SM3的消息擴展部分映射在陣列的上半部分，SM3的操作位寬為32位，移位寄存器的構成部分為16個操作數，選取左上部分16個PE通過PE內部寄存器以及互連構成移位寄存器。此外考慮到該部分涉及到的運算為移位、異或等操作，可以操作合并至同一個PE當中，減少資源消耗。

圖5 SM3陣列映射圖

陣列圖的下半部分用來映射壓縮模塊。壓縮模塊運算相對于消息擴展模塊較為復雜，需要更為精確的劃分運算操作，在映射前期，更需要對同一操作的多種候選映射方案準確利用好映射決策機制。算法中壓縮模塊的布爾運算取決于當前操作的輪數，因此需要兩個配置頁面來完成整個運算，圖中下半部分的深色PE即為映射布爾運算的PE。

在將數據注入陣列移位寄存器的過程中，僅需在第5個時鐘周期就可將Wj和W′j通過配置送入迭代壓縮部分，實現操作上的并行，大大減少了算法運行的周期。經過優化后的方案相比典型的映射方案減少了11個時鐘周期，提高了算法的吞吐率。

4.2 對決策機制的實驗對比

本文提出了一種針對雜湊算法映射的決策機制，基于存儲資源開銷、PE占用率開銷、互連資源開銷、配置信息量、延時開銷5種開銷按照影響程度排列優先級，如果一個操作存在多種映射方案時，決策機制將依據優先級篩選出最佳映射方案。

本文以課題組設計的陣列結構進行實驗，由于大部分文獻所實現的可重構陣列結構無源碼支持，且相關文獻中列舉的映射算法均為分組密碼算法，而課題組設計的陣列結構基本符合2.2節中所提到的陣列數據流模型，因此可以作為典型陣列硬件結構進行實驗，其實驗結果能夠具有一定的參考價值。

實驗基于課題組前期設計的55 nm工藝下流片的粗粒度可重構密碼邏輯陣列芯片，其基本硬件結構如圖2所示。選取了SM3、SHA-256、SHA-384、SHA-512、MD4、MD5等多種典型雜湊算法在陣列芯片上進行實測分析，通過構建Xilinx AX7020開發板與陣列芯片的數據交互，并將數據通過串口助手打印至PC端，得到的吞吐率及功耗測試結果見表3、表4。

表3 不同決策方案得到的吞吐率/(Mb/s)

表4 不同決策方案得到的功耗/mW

表3分別對5種開銷單獨決策、直接相加決策、本文優化后的決策進行了多種雜湊算法的吞吐率測試，由表中所示數據可以看出，在吞吐率上以延時開銷進行決策的吞吐率最佳，這是因為延時開銷很大程度上決定了其算法的吞吐率，但本文優化后的結果也處于較優水平；表4分別對多種決策方案進行了多種雜湊算法的功耗測試，由表中所示數據可以看出，功耗上基本是以配置信息量決策最佳，但本文優化后的結果同時也處于較優水平；由于大多數文獻中評價雜湊算法的處理性能通常以吞吐率作為評價指標，但對于陣列結構，僅考慮吞吐率及功耗指標是不夠客觀的，本文將能效比作為主要評價指標。

上述典型算法在7種決策方案上的能效比如圖6所示。其中橫坐標1～7分別表示基于存儲資源開銷、PE占用率開銷、互連資源開銷、配置信息量、延時開銷，直接相加以及優化后，縱坐標表示能效值，其單位為Mbps/mW。從圖中可以明顯看出，本文提出的優化后的決策機制在能效提升上有著明顯的優勢，相較于其它不同決策機制的映射方法，本文提出的決策機制在能效上提升了約10%到20%。

圖6 典型雜湊算法映射結果

5 結束語

本文通過分析雜湊算法的基本特征，結合陣列數據流處理模型，采用空間展開操作并行手段，并針對某一具體操作的候選映射方案提出了一種優先級決策機制。以課題組設計的陣列結構作為實驗平臺，選取了幾種典型的雜湊算法進行驗證，數據表明，本文提出的映射方法在能效上具有一定的優勢，能夠滿足典型雜湊算法的映射需求。由于本文僅針對雜湊算法的數據路徑映射上進行分析，且未對陣列結構上進行改進，下一步將結合控制路徑，以及修改部分陣列結構，進一步完善映射方法及提高雜湊算法映射的能效。