面向分組密碼處理的可重構分簇式架構模型及其任務映射技術研究

摘要：提出了一種基于Crossbar互連的可重構分簇式分組密碼處理模型RCCPA和面向RCCPA的任務映射方法.所建立的任務就緒列表避免了任務劃分的死鎖問題，通過開發(fā)分組密碼組間并行及組內流水特性，提高了RCCPA架構的單元利用率和密碼處理性能.在RCCPA架構上使用自動化映射方法適配了AES/DES/IDEA等密碼算法，結果表明，該模型與方法有效提高了分組密碼算法的處理性能.

關鍵詞：分組密碼；可重構；分簇；任務映射

中圖分類號：TN 492 文獻標識碼：A

Research on Reconfigurable Clustered Architecture Model

and Task Mapping Targeted at Block Cipher Processing

CHEN Tao1，2， LUO Xing-guo2， LI Xiao-nan1， CHEN Xun1， CHANG Zhong-xiang1

（1.The PLA Information Engineering Univ， Zhengzhou， Henan 450004， China；

2.National Digital Switching System Engineering Technological Research Center， Zhengzhou， Henan 450004， China）

Abstract： A Reconfigurable Clustered Architecture Model named RCCPA and Task mapping method were proposed. Based on task ready list， this technique avoids the deadlock problem of the division of tasks. Through the development of block cipher's parallelization between packets and pipeline characteristic of the group， the unit utilization and cryptographic processing performance of the RCCPA architecture were improved. AES / DES / IDEA .etc cryptographic algorithm used automated method of mapping adaptation in RCCPA architecture， and the results show that the proposed model and method effectively improve the processing performance of the block cipher algorithm.

Key words： block cipher； reconfigurable； cluster； task mapping

隨著可重構設計技術的發(fā)展，面向分組密碼處理的可重構計算系統(tǒng)日益增多.針對分組密碼處理的可重構系統(tǒng)主要包括：1）基于FPGA實現(xiàn)的可重構處理芯片^[1]，該類芯片能夠獲得接近ASIC的處理性能，但是算法更換時需要重新設計電路、重新配置，存在配置信息多、布局布線復雜、處理粒度與分組密碼處理粒度不相符、對開發(fā)設計人員要求高等問題.2）面向密碼應用的專用指令處理器，如RCBCP^[2]和SophSEC^[3]等基于VLIW結構的處理芯片，通過開發(fā)分組密碼算法的指令級并行度，將可并行執(zhí)行的指令組合成一條指令，在一個指令周期內完成，提高了分組密碼算法的實現(xiàn)性能.另一方面通過軟件編程的方式實現(xiàn)密碼算法，降低了編譯器的設計復雜性和用戶的開發(fā)難度.但是該架構每個時鐘周期處理單元最多只能有一種運算邏輯工作，存在資源利用率低的問題.3）基于配置流的粗粒度可重構密碼處理架構，如RCPA^[4]和RHCA^[5]等基于陣列的處理架構.陣列結構能夠以較大的并行度和流水深度進行密碼處理，但是文獻[4]和[5]均沒有給出面向其架構的任務劃分及映射方法，用戶開發(fā)難度大.另一方面陣列結構存在互聯(lián)資源多、布局布線復雜的問題，并且其功能單元采用同構化設計，利用率低下.文獻[6]提出的ProDFA結構，通過執(zhí)行上下文快速更改數(shù)據(jù)流計算結構，在一定程度上提高了單元的利用率和密碼處理性能，通過定義一種配置描述語言，用戶可以使用此語言手動完成任務的劃分與映射，但是這要求用戶對ProDFA結構有深入的了解，同樣存在開發(fā)難度大的問題.

為提高可重構分組密碼架構的單元利用率，降低用戶使用的復雜性，實現(xiàn)分組密碼算法的在動態(tài)可重構架構上的自動任務映射，本文提出了一種基于分級互連結構的可重構分簇式密碼處理架構的模型RCCPA（Reconfigurable Clustered Cipher Processing Architecture），RCCPA通過動態(tài)配置數(shù)據(jù)處理路徑，提高了密碼算法處理性能和單元利用率.在此基礎上研究了任務的自動映射問題，提出了面向RCCPA架構的自動映射方法，并在并行優(yōu)化和流水優(yōu)化兩個方面進行了策略調整，實現(xiàn)了分組密碼算法的自動化映射.完成了RCCPA的原型設計，并評估了常用分組密碼算法在該架構上的實現(xiàn)性能.

1 可重構分簇式分組密碼處理架構

分組密碼算法適于分組（或分塊數(shù)據(jù)）內并行、分組間并行或流水處理，并且具有分組（或分塊數(shù)據(jù)）間數(shù)據(jù)交互少的特點^[5].結合分組密碼算法處理特點，本文提出的可重構分簇式分組密碼處理模型如圖1所示.架構采用分簇式設計，包含4個處理簇、配置單元、通用寄存器堆、子密鑰寄存器堆、控制邏輯和I/O接口.

各個簇設置了相同的可重構功能單元（Reconfiguable computer unit，RCU），并采用相似的互連方式，每個簇內包含6種32 bit的操作單元：S盒替代、移位、GF（2n）上的矩陣乘法、算術乘法、算術模加/減、邏輯運算等單元.為了支持超長位寬的處理需求，設計了兩類128 bit位寬的操作單元：比特置換、長移位單元，超長位寬單元通過將其輸入、輸出信號分為4組32 bit接入到4個處理簇中.功能單元設置的依據(jù)是可以快速支持分組密碼算法的9種基本操作^[2].為滿足密鑰及臨時數(shù)據(jù)的存儲需求，專門設置了通用寄存器堆和密鑰寄存器堆.為降低寄存器堆的資源消耗，結合分組密碼算法分組（或分塊）內的數(shù)據(jù)交互較少，設計了分簇式的寄存器堆結構.每個簇均包含一個容量為64×32 bit的通用寄存器堆，通用寄存器堆包含一個任意讀端口和一個任意寫端口.密鑰寄存器堆的設置與通用寄存器堆相似，只是存儲容量為128×32 bit，以及用途不同.

RCCPA可以根據(jù)密碼處理的需要，通過動態(tài)可重構互連網絡可靈活配置簇內、簇間的互連結構，充分滿足密碼處理的并行及流水需求.各處理簇內的RCU通過基于Crossbar互連的Level-1總線進行數(shù)據(jù)交互，任一RCU的輸出可以接到任一RCU的輸入上，不同簇間的數(shù)據(jù)交互通過基于部分Crossbar互連的Level-2總線完成.數(shù)據(jù)路徑通過多個RCU的協(xié)同并行工作，構成多級流水線，可以同時處理多個密碼分組，提高RCU資源利用率.在Level-2互連總線的配合下，還可以將數(shù)據(jù)路徑動態(tài)地重構成4個32 bit簇、2個64 bit簇和1個128 bit簇，充分滿足分組密碼處理靈活性的要求.

2 面向RCCPA的任務映射策略研究

為降低用戶的開發(fā)難度，提高RCCPA任務映射的效率，需要研究面向RCCPA的任務映射技術.現(xiàn)階段針對動態(tài)可重構系統(tǒng)的任務映射算法研究較多[7-9]，但集中在同構系統(tǒng)上.針對異構系統(tǒng)的映射研究又以不同處理器構成的多核架構為基礎，映射技術以任務的軟硬件合理劃分為研究對象.雖然針對同構系統(tǒng)的映射算法經過修改可以應用于異構系統(tǒng)，但存在調度成功率低、映射算法效率不高的問題，另外由于RCCPA架構基于分簇的Crossbar互連，與現(xiàn)有的可重構架構存在較大區(qū)別，因此必須研究基于RCCPA架構的任務映射算法.

2.1 相關定義

在動態(tài)可重構系統(tǒng)的任務映射過程中，需要建立相應的應用模型，以反映密碼處理任務的功能、屬性、任務間的約束關系等特征，以準確描述任務分配與映射的對象.

定義1密碼處理任務可以表示為有向無環(huán)圖Gf={V，E，P，W}.其中

1）V={vi|1≤i≤n}是子任務的集合，vi表示可面向密碼編碼環(huán)節(jié)的基本操作任務，每個vi均對應一個任務屬性pi∈P.

2）E={eij}表示任務之間存在通信約束，即任務與任務之間存在依賴關系，任務vj必須在任務vi完成后才能執(zhí)行.ei的值表示任務vi與vj之間的數(shù)據(jù)通信量.

3）P={pi|1≤i≤n}為所有任務節(jié)點屬性的集合，用于描述任務節(jié)點的類型、數(shù)據(jù)來源、密鑰需求等，當系統(tǒng)同時處理多個Gf分組時，不同分組間子密鑰的使用特點，如不同分組的Gf是否使用同一密鑰，如不是則需要指出下一分組的密鑰使用與上一分組的密鑰使用存在的關系.

4）W為任務節(jié)點的處理粒度，包括3種類型：32 bit， 64 bit， 128 bit，對于處理粒度小于32 bit的任務，在任務劃分時通過將多個任務并行組合，將其作為32 bit的任務處理.

定義2 初始配置序列是完成密碼處理任務Gf的一個多重上下文序列，執(zhí)行可以完成Gf表示的一個分組數(shù)據(jù)的加（解）密任務，配置序列={1，2，…，s}共需要執(zhí)行s個時鐘周期，i∈為單個配置上下文，該上下文執(zhí)行需要一個時鐘周期，每個上下文中均包含了子任務在該時刻的計算資源、存儲資源和互連資源占用情況.設T（i）為配置上下文i所完成的子任務集合，若此i中只是完成了操作數(shù)的提取，則此時T（i）=，N（i）表示i所對應的資源占用情況，ni[y][x]∈N（i）表示i所占用的處理簇y中x類型的功能單元的總數(shù)，主要包括：計算資源以及互連資源消耗等，Rtotal[y][x]表示可重構處理架構RCCPA處理簇y可以提供的x類型的功能單元數(shù)量或為簇y提供x類型的通信帶寬.MR（i）表示執(zhí)行到i時，需要占用的通用存儲空間的大小，MK（i）則表示任務執(zhí)行需要的密鑰存儲空間的大小，MRtotal和MKtotal為系統(tǒng)為各個簇提供的通用存儲空間及密鑰存儲空間的大小.一個可行的初始配置應該滿足以下條件.

1）任務約束：

即初始配置序列必須完成Gf包含的所有子任務，且每個子任務只能由某種功能單元完成一次.

2）資源約束：

i∈，ri[y][x]∈N（i），ni[y][x]≤Rtotal[y][x].

即每個配置上下文所占用的任意簇中任意功能單元的數(shù)量不能超過系統(tǒng)所提供的計算資源數(shù)量，存儲帶寬、簇間通信帶寬、輸出帶寬需求不能超過系統(tǒng)所提供的通信帶寬.由于各個處理簇內的互連單元采用全Crossbar互連，能夠保證任意時刻任何功能單元的輸出可以連接到任意功能單元的輸入上，不管如何配置密碼處理路徑，簇內帶寬肯定可以滿足需要，因此計算資源約束時不必考慮簇內通信帶寬的約束.

3）存儲約束：

mri[y]∈MR（i），mk[y]∈MK（），則mri[y]≤MRtotal，mk[y]≤MKtotal.

存儲資源約束要求任務執(zhí)行的任意時刻，需要占用的通用寄存器數(shù)量、密鑰寄存器數(shù)量，不能超過系統(tǒng)提供的寄存器空間.由于RCCPA沒有設計專門的子密鑰計算電路，密鑰需要預先計算存儲于子密鑰寄存器堆，密碼處理時由運算單元從密鑰寄存器中提取密鑰完成相應操作，因此密鑰存儲空間的需求相對固定，生成初始配置序列時，密鑰空間肯定可以滿足運算需求，不需要對存儲資源進行判斷.當進行多分組并行或流水處理時，根據(jù)各分組是否使用相同密鑰的情況，首先進行密鑰存儲空間是否滿足需求的判斷，如不滿足則不需要再進行映射序列調整.

2.2 基于任務就緒列表的基本映射策略

基于任務就緒列表的無死鎖基本映射策略根據(jù)輸入的密碼處理任務Gf和RCCPA的結構模型，在滿足約束條件的前提下，通過建立任務就緒列表避免死鎖，輸出為能夠處理一個分組的基本配置序列.主要分為以下步驟：

Step1 建立未分配任務集合、已分配任務集合，初始情況下未分配任務集合Gn=Gf，已分配任務集合Gp=.

Step2 根據(jù)未分配任務集合Gn和已分配任務集合Gp，生成就緒任務列表Gr，其過程是對Gn中的每個節(jié)點v，考查該節(jié)點的所有前驅節(jié)點prev（v）是否已經被分配到相應的模塊，即判斷prev（v）是否屬于Gp，如果所有的前驅節(jié)點屬于Gp，則該節(jié)點為就緒節(jié)點.就緒列表建立算法如下描述.

輸入：未分配任務集合Gn和已分配任務集合Gp

輸出：就緒任務節(jié)點集合Gr

Gr=；初始化就緒節(jié)點集合為空集

For each node v∈Gndo；遍歷未分配任務集合Gn中的所有節(jié)點

sign←0； //初始化標記

For each node u∈prev（v） do；

If uGp； //尚未分配節(jié)點

sign←1；//標記為非就緒節(jié)點

Break；

Endif

Endfor

If sign=0then //v為就緒節(jié)點

Gr=Gr∪v； //將v加入到節(jié)點就緒集合中

Endif

endforStep3 根據(jù)就緒任務集合Gr，RCCPA的資源約束情況，確定第i次（第1次執(zhí)行此步驟時i=1）任務分配生成的配置序列2i-1，2i.為就緒集合中的任務分配單元時，需要按照一定的規(guī)則進行.本文設置的分配規(guī)則為：1）盡量將存在通信關系的任務分配到相同的處理簇中；2）任務分配按照優(yōu)先分配處理簇1， 然后分配處理簇2，3，4中單元的順序進行.為硬件任務分配資源時，盡量滿足規(guī)則1），在不能滿足規(guī)則1）的情況下按照規(guī)則2）進行分配.分配算法的偽碼描述如下.

輸入：就緒任務集合Gr，RCCPA的資源約束Rtotal[y][x]，MRtotal，未分配任務集合Gn和已分配任務集合Gp

輸出：配置序列2i-1，2i，更新后的未分配任務集合Gn和已分配任務集合Gp

2i-1=，2i=；初始化配置序列為空集

n=card（Gr）；提取就緒列表中的任務個數(shù)

For j=0， j++， j

v∈Grdo；

（sign，2i-1，2i）←map（v，2i-1，2i）；

//根據(jù)分配原則、資源約束，2i-1，2i的資源使用情況為任務v分配資源，生成新的配置序列.若v分配成功，則置sign=0，更新2i-1，2i，否則sign=1，2i-1，2i序列不變.

If sign=0 then

{Gr，Gn，Gp}←updata{v，Gr，Gn，Gp}；

//分配成功，更新各任務集合

Else Gr=Gr-v；分配失敗，更新就緒任務集合

Endif

Endfor

Step4 判斷未分配任務集合是否為空集.若Gn≠表示尚有任務未分配，則返回Step2繼續(xù)執(zhí)行.若Gn=則表明任務分配完畢，將Step3生成的配置序列={1，2，…，s}依次輸出，即為生成的初始配置上下文序列.

基本映射策略采用建立任務就緒列表的方式進行任務分配，保證了每次分配的任務均是就緒節(jié)點，杜絕了任務分配時死鎖的出現(xiàn).按照約定的分配原則進行任務分配，保證了每次循環(huán)至少可以完成一個任務節(jié)點的分配，并保證了不會出現(xiàn)資源沖突，經多次循環(huán)后可以完成所有任務的分配.

設輸入任務圖的節(jié)點數(shù)目和邊數(shù)分別為|V|和|E|，對于基本映射策略的主循環(huán)，每次搜索就緒任務列表，至少可以分配一個子任務，因此最壞情況下只需要搜索|V|次就緒列表就可以完成任務分配.對于每次循環(huán)都需要計算一次就緒任務列表，建立就緒列表需要搜索任務中的所有節(jié)點和每個節(jié)點的所有前驅，因此復雜度為O（|V|+|E|）.另外，每次循環(huán)都需要搜索就緒列表，其時間復雜度為|L|，其中|L|為就緒列表中包含的任務個數(shù)，|L|≤|V|.因此基本映射策略的時間復雜度上界為（|V|）（|V|+|E|+|V|），即基本策略的復雜度為O（|V|2+|V||E|）.

2.3 基于并行優(yōu)化的映射策略

RCCPA基本架構提供了4個32 bit的處理簇，通過基本映射策略進行任務分配時，會出現(xiàn)4個處理簇沒有完全占用的情況；為開發(fā)分組密碼組內的并行性，充分利用各處理簇硬件資源，在基本映射策略的基礎上，提出了基于并行優(yōu)化的映射策略.該策略是為了利用基本配置策略沒有占用的處理簇資源，因此并行優(yōu)化映射序列時，不需要考慮系統(tǒng)的資源約束和存儲約束.并行優(yōu)化策略描述如下.

Step1 搜索初始配置序列={1，2，…，s}中占用的功能單元所對應的處理簇的最大編號max，max即為初始配置序列共占用的處理簇個數(shù)，其偽碼描述如下：

max =1； //初始化最大編號

for each i∈ do //遍歷所有的配置序列

for each ri[y][x]∈i do

if y

Break；

else max =y； //更新max

endif

endfor

RCBCP是一款采用VLIW結構具有4路并行的可重構分簇式密碼處理器，Crypto-nite為兩路并行的64 bit位寬RISC結構，RCPA是基于陣列結構的可重構密碼處理架構.通過對多種分組密碼算法的適配，從表2的對比結果可以得出，RCCPA結構可以靈活適配分組密碼算法，并且對不同設計結構、不同處理位寬、不同操作位寬的分組密碼算法均有較高的處理性能，與其他專用可重構密碼處理結構相比處理性能提高了1.3～5.8倍.

考慮到RCCPA架構使用crossbar進行互連，一定程度上降低了互連資源的約束，增大了電路實現(xiàn)面積.為更好地衡量RCCPA面向分組密碼的處理性能，定義面積效率來評估不同可重構系統(tǒng)的優(yōu)劣.RCBCP和RCPA在0.18 μm CMOS工藝下的等效門數(shù)分別為：121.25萬門和148.99萬門.RCCPA與RCBCP和RCPA架構在該工藝條件下分組密碼算法的面積效率對比如表3所示.

如表3所示，通過對比常見的分組密碼算法在不同架構上的面積效率可知，RCCPA架構在增強的互連資源約束下的面積效率仍可達RCPA和RCBCP的1.6～3.1倍，表明RCCPA具有相對更優(yōu)的架構、更高的單元利用率.

4 結 論

本文在總結分組密碼處理特征、分析可重構分組密碼處理架構優(yōu)勢及不足的基礎上，針對現(xiàn)有可重構系統(tǒng)資源利用率低、用戶開發(fā)使用難度大等問題，提出了可重構分簇式分組密碼處理架構RCCPA，并在此基礎上研究了任務的自動映射策略；結合分組密碼橫向上可并行、縱向上可深度流水的特性，研究了基于并行和流水的策略優(yōu)化，分析了策略的正確性和實現(xiàn)的時間復雜度；任務映射策略的設計實現(xiàn)，降低了用戶的開發(fā)難度.通過與其他架構進行處理性能與面積效率等指標的對比分析，更加合理地評估了可重構密碼處理架構的性能.從分析結果中可以看出，基于Crossbar互連的RCCPA架構，通過動態(tài)組織處理路徑，具有更高的功能單元利用率和密碼任務的處理性能.

參考文獻

[1] XU Jian，LIU Yuan-feng，DAI Zi-bin， et al.Design and implementation of reconfigurable AES IP core using FPGAs[C]//Proceedings of 6th International Conference on ASIC. New York： IEEE， 2005：765-768.

[2] 孟濤，戴紫彬.分組密碼處理器的可重構分簇式架構[J]. 電子與信息學報，2009，32（2）：453-456.

MENG Tao，DAI Zi-bin.Reconfigurable clustered architecture of block cipher processor[J]. Journal of Electronics Information Technology，2009，32（2）：453-456.（In Chinese）

[3] 黃偉.面向云計算的性能與功耗可配置安全終端技術研究[D].上海：復旦大學，2011.

HUANG Wei. The research of the performance and power configurable security terminal for cloud computing[D]. Shanghai： Fudan University， 2011.（In Chinese）

[4] 楊曉輝，戴紫彬，張永福.可重構分組密碼處理結構模型研究與設計[J]. 計算機研究與發(fā)展，2009，46（6）：962-967.

YANG Xiao-hui，DAI Zi-bin，ZHANG Yong-fu.Research and design of reconfigurable computing targeted at block cipher processing[J]. Journal of Computer Research and Development，2009，46（6）：962-967.（In Chinese）

[5] 姜晶菲.可重構密碼處理結構的研究與設計[D].長沙：國防科學技術大學，2004.

JIANG Jin-fei. The research and design of reconfigurable cipher processing architecture[D]. Changsha：National University of Defense Technology，2004.（In Chinese）

[6] 嚴明.面向領域應用的異構多核SoC系統(tǒng)結構設計與優(yōu)化[D].長沙：國防科學技術大學，2011.

YAN Ming.Design and implementation of heterogeneous multicore SoC system focused on domain applications[D].Changsha：National University of Defense Technology，2011.（In Chinese）

[7] 潘雪增，孫康，陸魁軍，等.動態(tài)可重構系統(tǒng)任務時域劃分算法[J].浙江大學學報：工學版，2007，41（11）：1841-1844.

PAN Xue-zeng，SUN Kang，LU Kui-jun，et al.Tempoal task partitioning algorithm for dynamically reconfigurable systems[J].Journal of Zhejiang University： Engineering Science，2007，41（11）：1841-1844.（In Chinese）

[8] 季愛明，沈海斌，嚴曉浪.基于任務分組的動態(tài)可重構結構編譯方法[J].浙江大學學報：工學版，2006，40（8）：1306-1310.

JI Ai-ming，SHEN Hai-bin，YAN Xiao-lang.Compilation approach for dynamically reconfigurable architecture based on grouped tasks[J].Journal of Zhejiang University： Engineering Science， 2006，40（8）：1306-1310.（In Chinese）

[9] 黃樂天.基于空-時映射的多維可重構數(shù)字系統(tǒng)資源與任務管理[D]. 成都：電子科技大學，2009.

HUANG Le-tian. The reconfigurable digital system resource and task management based on space-time mapping multidimensional[D]. Chengdu：University of Electronic Science and Technology of China，2009.（In Chinese）

[10]BUCHTY R. Cryptonite： a programmable crypto processor architecture for high-bandwidth applications [D]. Munchen： Institut fur Informatik der Technischen Universitat Munchen，2002.