0 引言

    隨著現(xiàn)代集成電路工藝的發(fā)展，單位面積上所能集成的晶體管數(shù)量不斷增加，時(shí)鐘頻率不斷提升，限制應(yīng)用實(shí)現(xiàn)性能提升的主要因素將不再是硬件資源，而是如何充分利用這些資源^[1]。粗粒度可重構(gòu)分組密碼陣列（Coarse-Grained Reconfigurable Block Encryption Array，RBEA）提供了大量密碼運(yùn)算資源，是針對(duì)分組密碼算法高速實(shí)現(xiàn)而設(shè)計(jì)的加速平臺(tái)。在該平臺(tái)上通過設(shè)計(jì)分組密碼算法SM4的不同映射方案，來探究提高運(yùn)算性能和資源效率的最佳方法。

1 SM4算法簡(jiǎn)介

    SM4算法是2012年3月國(guó)家密碼管理局授權(quán)的分組密碼算法^[2]。該算法主要由32輪迭代組成，每輪迭代完全相同，均為非線性運(yùn)算，運(yùn)算數(shù)據(jù)位寬有8 bit和32 bit兩種。SM4算法的數(shù)據(jù)分組長(zhǎng)度為128 bit，密鑰長(zhǎng)度也為128 bit。

    輪運(yùn)算的主體是F函數(shù)，該函數(shù)的運(yùn)算位寬為32 bit，每輪更新32 bit數(shù)據(jù)，其表達(dá)式如式(1)所示。

    第32輪運(yùn)算結(jié)束后將運(yùn)算結(jié)果進(jìn)行交換得到最終的密文。

2 粗粒度可重構(gòu)密碼陣列

    RBEA是針對(duì)分組密碼算法開發(fā)的粗粒度可重構(gòu)運(yùn)算平臺(tái)。可重構(gòu)設(shè)計(jì)采用數(shù)據(jù)流驅(qū)動(dòng)，通過可重構(gòu)單元的配置來滿足不同密碼算法的需求，具有高效率和高并行度的特點(diǎn)^[3]。粗粒度單元的設(shè)計(jì)不同于傳統(tǒng)的細(xì)粒度可重構(gòu)單元，在實(shí)現(xiàn)分組密碼算法時(shí)速度更快、效率更高^[4]。

2.1 陣列結(jié)構(gòu)

    RBEA的基本結(jié)構(gòu)如圖1所示，由輸入輸出控制器、共享存儲(chǔ)區(qū)和運(yùn)算陣列組成。

    FB中的4種運(yùn)算單元FU1-4是在文獻(xiàn)[4]中有所描述。對(duì)分組密碼算法操作分析分類的基礎(chǔ)上，通過整合三輸入布爾函數(shù)、移位、模加減、模乘、比特置換、S盒運(yùn)算和有限域乘法等7種基本操作而設(shè)計(jì)形成的異構(gòu)單元。分組密碼算法中常用的非線性操作SBOX通過共享存儲(chǔ)與FB聯(lián)合實(shí)現(xiàn)。在功能單元（簡(jiǎn)稱FU）輸出端增加異或單元，主要用于完成指定運(yùn)算操作后結(jié)果與其他數(shù)據(jù)進(jìn)行后異或運(yùn)算。

    運(yùn)算陣列使用分散-聚簇設(shè)計(jì)方案，一行中相鄰的4個(gè)FB中的FU通過固定連線共同完成64 bit和128 bit的運(yùn)算。該陣列固定輸入輸出結(jié)點(diǎn)，由輸入控制器負(fù)責(zé)數(shù)據(jù)注入和運(yùn)算啟動(dòng)，輸出控制器負(fù)責(zé)數(shù)據(jù)輸出。配置單元提供的配置信息將FB重構(gòu)為需要的運(yùn)算功能和數(shù)據(jù)路徑，共享存儲(chǔ)在本地控制器控制下完成運(yùn)算存儲(chǔ)操作。

2.2 算法映射過程

    不同于傳統(tǒng)以指令流驅(qū)動(dòng)的處理器平臺(tái)，陣列平臺(tái)在實(shí)現(xiàn)算法映射時(shí)，通過運(yùn)算、路由和存儲(chǔ)單元的重構(gòu)配置來完成數(shù)據(jù)流的實(shí)現(xiàn)，通過控制單元配置來完成控制流的實(shí)現(xiàn)^[1]。映射基本流程如下：

    （1）數(shù)據(jù)流配置

    使用圖形化編程工具搭建算法任務(wù)中的數(shù)據(jù)路徑，主要包括運(yùn)算結(jié)點(diǎn)、寄存結(jié)點(diǎn)和結(jié)點(diǎn)連接等，并將這些任務(wù)分配到1個(gè)或多個(gè)FB上。最后通過布局布線算法完成陣列結(jié)構(gòu)上的數(shù)據(jù)路徑搭建。

    （2）控制流配置

    通過設(shè)置周期級(jí)參數(shù)，在不同時(shí)刻產(chǎn)生所需的控制信號(hào)。使用匯編語(yǔ)言對(duì)輸入輸出與FB中的控制器進(jìn)行編程，完成數(shù)據(jù)輸入輸出和運(yùn)算控制任務(wù)。

    （3）陣列配置信息生成

    通過集成的編譯器將配置好的數(shù)據(jù)路徑和控制參數(shù)信息編譯成陣列配置信息，完成算法映射。

3 SM4算法的不同映射方案

    通過對(duì)SM4算法的研究，結(jié)合RBEA的結(jié)構(gòu)特點(diǎn)，本文采用操作合并、循環(huán)展開和任務(wù)并行復(fù)制等策略設(shè)計(jì)了不同的算法映射方案，并對(duì)這些方案進(jìn)行評(píng)估來探究提高性能和資源效率的最佳映射策略。

    通過對(duì)SM4算法的分析，僅需要移位、異或和S盒3種操作就可以完成全部運(yùn)算。移位操作通過配置移位單元可以實(shí)現(xiàn)，異或操作通過配置三輸入布爾函數(shù)單元或直接使用各FU輸出端口的異或單元實(shí)現(xiàn)，S盒操作由配置共享存儲(chǔ)器實(shí)現(xiàn)。運(yùn)算過程中的以32 bit為單位的數(shù)據(jù)移位可以直接通過路由實(shí)現(xiàn)，不占用功能單元資源。

    使用吞吐率和性能面積比來量化地比較不同方案的性能和資源效率情況[5]。式(4)為吞吐率公式，表示單個(gè)時(shí)鐘內(nèi)的平均數(shù)據(jù)處理量，單位為bit/cycle。式(5)為性能面積比公式，表示平均每個(gè)FB上單個(gè)時(shí)鐘內(nèi)的平均數(shù)據(jù)處理量，單位為bit/cycle perFB。

    其中S為處理分組個(gè)數(shù)，C為分組大小，T為數(shù)據(jù)運(yùn)算所需時(shí)鐘數(shù)，N為映射方案中FB的個(gè)數(shù)。

3.1 操作合并

    將各步驟操作獨(dú)立的映射到各個(gè)FB上，如圖2所示。由于數(shù)據(jù)輸入端口的限制，輪運(yùn)算共需9個(gè)FB，6個(gè)時(shí)鐘周期完成。由于最后的交換可以通過路由單元進(jìn)行交換，不占用運(yùn)算資源和時(shí)間。因此完成1組數(shù)據(jù)加密共占用9個(gè)FB，(6×32)+3=195個(gè)時(shí)鐘周期，其吞吐率為0.65 bit/cycle，性能面積比為0.07 bit/cycle perFB。

    這種映射方案，對(duì)于每個(gè)FB來說，只利用到了其中的1種FU，而對(duì)于其他FU完全沒有利用，F(xiàn)B的利用率僅為25%。通過分析發(fā)現(xiàn)，輪密鑰異或可以與S盒操作合并，而線性變換L的操作也可以合并，其合并后的映射結(jié)構(gòu)如圖3所示。合并方案中輪運(yùn)算只占用6個(gè)FB，4個(gè)時(shí)鐘周期，完成1組數(shù)據(jù)的加密時(shí)，N=6，T=131，性能為0.98 bit/cycle，提高了1.5倍，性能面積比為0.16 bit/cycle perFB，提高了2.25倍，效果非常明顯。

    由于陣列結(jié)構(gòu)中單元的獨(dú)立性允許將算法映射到更多的單元上進(jìn)行并行運(yùn)算，因此操作合并方案減少了資源占用，提高了性能，為其他并行方案打下了基礎(chǔ)。

3.2 任務(wù)并行

    為提高SM4算法的性能，需要使用大量單元來承擔(dān)計(jì)算任務(wù)。本文認(rèn)為使用這些單元的方式無(wú)非是將運(yùn)算任務(wù)分配到這些單元上，并利用陣列特點(diǎn)，使這些單元能夠并行運(yùn)算。分配方式主要有兩種，一種是不同的單元組合獨(dú)立地承擔(dān)不同數(shù)據(jù)的運(yùn)算任務(wù)，即基于數(shù)據(jù)分配的任務(wù)復(fù)制方案；另一種是使不同的單元組合分別承擔(dān)同一數(shù)據(jù)運(yùn)算的不同階段的計(jì)算任務(wù)，即基于循環(huán)展開的流水方案。

    任務(wù)復(fù)制方案在合并操作的基礎(chǔ)上，將各個(gè)算法任務(wù)完整復(fù)制到未利用的單元上。由于輸入輸出的限制，只能將任務(wù)復(fù)制為4份，如圖4所示，4個(gè)陰影部分表示為4份復(fù)制后的任務(wù)。

    在當(dāng)前的映射方案中，理想情況下，性能提升4倍，但資源利用率是原始方案的37.5%，性能面積比僅為0.06 bit/cycle perFB，還不如操作合并前的資源利用率。因此，采用任務(wù)復(fù)制的方案關(guān)鍵在于如何能夠保證資源利用率不被顯著地降低，這樣才能最大化地提高性能。

    循環(huán)展開流水方案在合并操作的基礎(chǔ)上，將輪運(yùn)算進(jìn)行復(fù)制映射，不同的輪運(yùn)算承擔(dān)不同迭代次序的運(yùn)算，被映射的單元接力處理數(shù)據(jù)，共同完成對(duì)一組數(shù)據(jù)的加/解密運(yùn)算。針對(duì)陣列提供的資源不同，其流水形式也有所不同，可以分為全展開流水和集合展開流水。全展開流水以合并操作后的輪運(yùn)算為基本單位進(jìn)行復(fù)制映射，復(fù)制次數(shù)與迭代次數(shù)相同，如圖5(a)。集合展開流水同樣以輪運(yùn)算為基本單元，而復(fù)制次數(shù)則根據(jù)外部條件設(shè)定，每個(gè)輪運(yùn)算映射的單元不再承擔(dān)單次迭代任務(wù)而是多個(gè)輪運(yùn)算任務(wù)的集合，如圖5(b)所示。集合展開方案需要滿足L×P×Q≥32?？梢钥闯?，全展開方案是集合展開在P=0，Q=1設(shè)定情況下的特殊形式。

    根據(jù)流水線工作原理，吞吐率計(jì)算公式為：

    其中II為迭代間隔，ET為處理一組數(shù)據(jù)所用的時(shí)鐘周期數(shù)。

    在全展開方案中，II=4，ET=131，N=192，其吞吐率極限值為32 bit/cycle，性能面積比最大為0.167 bit/cycle perFB。性能提升明顯，而資源利用效率與操作合并方案基本相同。

    在集合展開方案中，為達(dá)到最小II，應(yīng)使Q=1，P=4，為簡(jiǎn)化布線，映射時(shí)直接認(rèn)為每輪運(yùn)算占用兩行共8個(gè)FB。共占用48個(gè)FB，II=16，ET=131，其吞吐率極限值為8 bit/cycle，性能面積比最大為0.125 bit/cycle perFB。相對(duì)于操作合并后的方案，其性能提高了約7.8倍，而資源利用效率卻下降了，這是因?yàn)檫@種映射方案中共有16個(gè)FB未使用。為了提高資源利用效率需要研究自動(dòng)布局布線算法，能夠?qū)⑽词褂玫腇B充分使用起來。

4 實(shí)驗(yàn)驗(yàn)證與分析

    在65 nm工藝下，RBEA的工作頻率為320 MHz，測(cè)試數(shù)據(jù)量大小分別為1 KB、16 KB、32 KB、48 KB、64 KB，不同方案的測(cè)試結(jié)果如表1所示。

    對(duì)比操作合并前后的實(shí)驗(yàn)數(shù)據(jù)可以看出，SM4算法實(shí)現(xiàn)性能有較大提升，而且性能面積比提升效果非常明顯。采用任務(wù)復(fù)制的方案能夠線性地提升算法性能，但是由于陣列結(jié)構(gòu)的限制，其資源利用率卻有所降低。采用循環(huán)展開流水方案能夠顯著地提升算法實(shí)現(xiàn)性能，但是同樣地其性能面積比有所下降。

    對(duì)于與SM4結(jié)構(gòu)相似的算法，采用合并操作能夠?qū)崿F(xiàn)提升性能和資源利用率的雙重效果，而任務(wù)復(fù)制和循環(huán)展開方案僅能夠提高性能卻對(duì)資源利用的提升沒有貢獻(xiàn)。究其原因，是由于SM4算法實(shí)現(xiàn)的輪運(yùn)算完全相同，一輪運(yùn)算硬件可以實(shí)現(xiàn)完整算法映射，該組硬件在迭代運(yùn)算過程中，始終處理被占用狀態(tài)，即以該組硬件為模板進(jìn)行復(fù)制設(shè)計(jì)其他方案時(shí)資源利用率不會(huì)提高。因此，基于合并操作的后續(xù)方案中不能夠超越這一方案。若想進(jìn)一步提升資源效率，應(yīng)該進(jìn)一步降低II，增加流水深度。

5 結(jié)論

    基于操作合并和任務(wù)并行這兩種思路，本文在RBEA平臺(tái)上對(duì)SM4算法設(shè)計(jì)了不同的映射方案，并通過實(shí)驗(yàn)數(shù)據(jù)分析了不同方案對(duì)性能和資源效率提升的影響。實(shí)驗(yàn)結(jié)果表明，合并操作減少了操作時(shí)間和資源，顯著地提升了算法實(shí)現(xiàn)性能和資源效率；任務(wù)并行使用更多資源來提升性能，但沒有提升硬件資源使用效率。通過增加流水深度、減少迭代間隔和使用自動(dòng)化布局布線算法，將會(huì)進(jìn)一步提升算法的在該平臺(tái)上的實(shí)現(xiàn)性能和資源使用效率。

參考文獻(xiàn)

[1] 魏少軍，劉雷波，尹首一.可重構(gòu)計(jì)算處理器技術(shù)[J].中國(guó)科學(xué)：信息科學(xué)，2012(12)：1559-1576.

[2] 國(guó)家密碼管理局.國(guó)家密碼管理局公告第23號(hào)[EB/OL].GM/T 0002-2012.(2012-03-21).http：//www.oscca.gov.cn/News/201204/News_1227.htm.

[3] 楊子煜，嚴(yán)明，王大偉，等.面向CGRA循環(huán)流水映射的數(shù)據(jù)并行優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2013，36(6)：1280-1289.

[4] Li Wei，Zeng Xiaoyang，Nan Longmei，et al.A reconfigurable block cryptographic processor based on VLIW architecture[J].China Communications，2016，13(1)：91-99.

[5] LIU B，BAAS B M.Parallel AES encryption engines for many-core processor arrays[J].Computers IEEE Transactions on，2013，62(3)：536-547.

[6] SIM H，LEE H，SEO S，et al.Mapping imperfect loops to coarse-grained reconfigurable architectures[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2016，35(7)：1092-1104.

[7] SHAO S，YIN S，LIU L，et al.Map-reduce inspired loop parallelization on CGRA[C]//IEEE International Symposium on Circuits and Systems.2014：1231-1234.

[8] ZHOU L，LIU H，ZHANG J.Loop acceleration by cluster-based CGRA[J].Ieice Electron Express，2013，10(16).

[9] 朱敏，劉雷波，尹首一，等.面向?qū)ΨQ密碼領(lǐng)域的可重構(gòu)陣列設(shè)計(jì)[J].微電子學(xué)，2012，42(6)：815-818.

作者信息:

徐金甫，楊宇航

（信息工程大學(xué)，河南 鄭州450000）