文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.04.010
中文引用格式： 徐金甫，楊宇航. SM4算法在粗粒度陣列平臺的并行化映射[J].電子技術應用，2017，43(4)：39-42，46.
英文引用格式： Xu Jinfu，Yang Yuhang. The parallel mapping implementation of SM4 based on coarse-grained reconfigurable block encryption array[J].Application of Electronic Technique，2017，43(4)：39-42，46.
0 引言
隨著現代集成電路工藝的發展，單位面積上所能集成的晶體管數量不斷增加，時鐘頻率不斷提升，限制應用實現性能提升的主要因素將不再是硬件資源，而是如何充分利用這些資源[1]。粗粒度可重構分組密碼陣列（Coarse-Grained Reconfigurable Block Encryption Array，RBEA）提供了大量密碼運算資源，是針對分組密碼算法高速實現而設計的加速平臺。在該平臺上通過設計分組密碼算法SM4的不同映射方案，來探究提高運算性能和資源效率的最佳方法。
1 SM4算法簡介
SM4算法是2012年3月國家密碼管理局授權的分組密碼算法[2]。該算法主要由32輪迭代組成，每輪迭代完全相同，均為非線性運算，運算數據位寬有8 bit和32 bit兩種。SM4算法的數據分組長度為128 bit，密鑰長度也為128 bit。
輪運算的主體是F函數，該函數的運算位寬為32 bit，每輪更新32 bit數據，其表達式如式(1)所示。
第32輪運算結束后將運算結果進行交換得到最終的密文。
2 粗粒度可重構密碼陣列
RBEA是針對分組密碼算法開發的粗粒度可重構運算平臺?？芍貥嬙O計采用數據流驅動，通過可重構單元的配置來滿足不同密碼算法的需求，具有高效率和高并行度的特點[3]。粗粒度單元的設計不同于傳統的細粒度可重構單元，在實現分組密碼算法時速度更快、效率更高[4]。
2.1 陣列結構
RBEA的基本結構如圖1所示，由輸入輸出控制器、共享存儲區和運算陣列組成。
FB中的4種運算單元FU1-4是在文獻[4]中有所描述。對分組密碼算法操作分析分類的基礎上，通過整合三輸入布爾函數、移位、模加減、模乘、比特置換、S盒運算和有限域乘法等7種基本操作而設計形成的異構單元。分組密碼算法中常用的非線性操作SBOX通過共享存儲與FB聯合實現。在功能單元（簡稱FU）輸出端增加異或單元，主要用于完成指定運算操作后結果與其他數據進行后異或運算。
運算陣列使用分散-聚簇設計方案，一行中相鄰的4個FB中的FU通過固定連線共同完成64 bit和128 bit的運算。該陣列固定輸入輸出結點，由輸入控制器負責數據注入和運算啟動，輸出控制器負責數據輸出。配置單元提供的配置信息將FB重構為需要的運算功能和數據路徑，共享存儲在本地控制器控制下完成運算存儲操作。
2.2 算法映射過程
不同于傳統以指令流驅動的處理器平臺，陣列平臺在實現算法映射時，通過運算、路由和存儲單元的重構配置來完成數據流的實現，通過控制單元配置來完成控制流的實現[1]。映射基本流程如下：
（1）數據流配置
使用圖形化編程工具搭建算法任務中的數據路徑，主要包括運算結點、寄存結點和結點連接等，并將這些任務分配到1個或多個FB上。最后通過布局布線算法完成陣列結構上的數據路徑搭建。
（2）控制流配置
通過設置周期級參數，在不同時刻產生所需的控制信號。使用匯編語言對輸入輸出與FB中的控制器進行編程，完成數據輸入輸出和運算控制任務。
（3）陣列配置信息生成
通過集成的編譯器將配置好的數據路徑和控制參數信息編譯成陣列配置信息，完成算法映射。
3 SM4算法的不同映射方案
通過對SM4算法的研究，結合RBEA的結構特點，本文采用操作合并、循環展開和任務并行復制等策略設計了不同的算法映射方案，并對這些方案進行評估來探究提高性能和資源效率的最佳映射策略。
通過對SM4算法的分析，僅需要移位、異或和S盒3種操作就可以完成全部運算。移位操作通過配置移位單元可以實現，異或操作通過配置三輸入布爾函數單元或直接使用各FU輸出端口的異或單元實現，S盒操作由配置共享存儲器實現。運算過程中的以32 bit為單位的數據移位可以直接通過路由實現，不占用功能單元資源。
使用吞吐率和性能面積比來量化地比較不同方案的性能和資源效率情況[5]。式(4)為吞吐率公式，表示單個時鐘內的平均數據處理量，單位為bit/cycle。式(5)為性能面積比公式，表示平均每個FB上單個時鐘內的平均數據處理量，單位為bit/cycle perFB。
其中S為處理分組個數，C為分組大小，T為數據運算所需時鐘數，N為映射方案中FB的個數。
3.1 操作合并
將各步驟操作獨立的映射到各個FB上，如圖2所示。由于數據輸入端口的限制，輪運算共需9個FB，6個時鐘周期完成。由于最后的交換可以通過路由單元進行交換，不占用運算資源和時間。因此完成1組數據加密共占用9個FB，(6×32)+3=195個時鐘周期，其吞吐率為0.65 bit/cycle，性能面積比為0.07 bit/cycle perFB。
這種映射方案，對于每個FB來說，只利用到了其中的1種FU，而對于其他FU完全沒有利用，FB的利用率僅為25%。通過分析發現，輪密鑰異或可以與S盒操作合并，而線性變換L的操作也可以合并，其合并后的映射結構如圖3所示。合并方案中輪運算只占用6個FB，4個時鐘周期，完成1組數據的加密時，N=6，T=131，性能為0.98 bit/cycle，提高了1.5倍，性能面積比為0.16 bit/cycle perFB，提高了2.25倍，效果非常明顯。
由于陣列結構中單元的獨立性允許將算法映射到更多的單元上進行并行運算，因此操作合并方案減少了資源占用，提高了性能，為其他并行方案打下了基礎。
3.2 任務并行
為提高SM4算法的性能，需要使用大量單元來承擔計算任務。本文認為使用這些單元的方式無非是將運算任務分配到這些單元上，并利用陣列特點，使這些單元能夠并行運算。分配方式主要有兩種，一種是不同的單元組合獨立地承擔不同數據的運算任務，即基于數據分配的任務復制方案；另一種是使不同的單元組合分別承擔同一數據運算的不同階段的計算任務，即基于循環展開的流水方案。
任務復制方案在合并操作的基礎上，將各個算法任務完整復制到未利用的單元上。由于輸入輸出的限制，只能將任務復制為4份，如圖4所示，4個陰影部分表示為4份復制后的任務。
在當前的映射方案中，理想情況下，性能提升4倍，但資源利用率是原始方案的37.5%，性能面積比僅為0.06 bit/cycle perFB，還不如操作合并前的資源利用率。因此，采用任務復制的方案關鍵在于如何能夠保證資源利用率不被顯著地降低，這樣才能最大化地提高性能。
循環展開流水方案在合并操作的基礎上，將輪運算進行復制映射，不同的輪運算承擔不同迭代次序的運算，被映射的單元接力處理數據，共同完成對一組數據的加/解密運算。針對陣列提供的資源不同，其流水形式也有所不同，可以分為全展開流水和集合展開流水。全展開流水以合并操作后的輪運算為基本單位進行復制映射，復制次數與迭代次數相同，如圖5(a)。集合展開流水同樣以輪運算為基本單元，而復制次數則根據外部條件設定，每個輪運算映射的單元不再承擔單次迭代任務而是多個輪運算任務的集合，如圖5(b)所示。集合展開方案需要滿足L×P×Q≥32?？梢钥闯?，全展開方案是集合展開在P=0，Q=1設定情況下的特殊形式。
根據流水線工作原理，吞吐率計算公式為：
其中II為迭代間隔，ET為處理一組數據所用的時鐘周期數。
在全展開方案中，II=4，ET=131，N=192，其吞吐率極限值為32 bit/cycle，性能面積比最大為0.167 bit/cycle perFB。性能提升明顯，而資源利用效率與操作合并方案基本相同。
在集合展開方案中，為達到最小II，應使Q=1，P=4，為簡化布線，映射時直接認為每輪運算占用兩行共8個FB。共占用48個FB，II=16，ET=131，其吞吐率極限值為8 bit/cycle，性能面積比最大為0.125 bit/cycle perFB。相對于操作合并后的方案，其性能提高了約7.8倍，而資源利用效率卻下降了，這是因為這種映射方案中共有16個FB未使用。為了提高資源利用效率需要研究自動布局布線算法，能夠將未使用的FB充分使用起來。
4 實驗驗證與分析
在65 nm工藝下，RBEA的工作頻率為320 MHz，測試數據量大小分別為1 KB、16 KB、32 KB、48 KB、64 KB，不同方案的測試結果如表1所示。
對比操作合并前后的實驗數據可以看出，SM4算法實現性能有較大提升，而且性能面積比提升效果非常明顯。采用任務復制的方案能夠線性地提升算法性能，但是由于陣列結構的限制，其資源利用率卻有所降低。采用循環展開流水方案能夠顯著地提升算法實現性能，但是同樣地其性能面積比有所下降。
對于與SM4結構相似的算法，采用合并操作能夠實現提升性能和資源利用率的雙重效果，而任務復制和循環展開方案僅能夠提高性能卻對資源利用的提升沒有貢獻。究其原因，是由于SM4算法實現的輪運算完全相同，一輪運算硬件可以實現完整算法映射，該組硬件在迭代運算過程中，始終處理被占用狀態，即以該組硬件為模板進行復制設計其他方案時資源利用率不會提高。因此，基于合并操作的后續方案中不能夠超越這一方案。若想進一步提升資源效率，應該進一步降低II，增加流水深度。
5 結論
基于操作合并和任務并行這兩種思路，本文在RBEA平臺上對SM4算法設計了不同的映射方案，并通過實驗數據分析了不同方案對性能和資源效率提升的影響。實驗結果表明，合并操作減少了操作時間和資源，顯著地提升了算法實現性能和資源效率；任務并行使用更多資源來提升性能，但沒有提升硬件資源使用效率。通過增加流水深度、減少迭代間隔和使用自動化布局布線算法，將會進一步提升算法的在該平臺上的實現性能和資源使用效率。
參考文獻
[1] 魏少軍，劉雷波，尹首一.可重構計算處理器技術[J].中國科學：信息科學，2012(12)：1559-1576.
[2] 國家密碼管理局.國家密碼管理局公告第23號[EB/OL].GM/T 0002-2012.(2012-03-21).http：//www.oscca.gov.cn/News/201204/News_1227.htm.
[3] 楊子煜，嚴明，王大偉，等.面向CGRA循環流水映射的數據并行優化[J].計算機學報，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] 朱敏，劉雷波，尹首一，等.面向對稱密碼領域的可重構陣列設計[J].微電子學，2012，42(6)：815-818.
作者信息:
徐金甫，楊宇航
（信息工程大學，河南 鄭州450000）