密碼多核處理器互聯(lián)結(jié)構(gòu)研究與設(shè)計(jì)

徐金甫，陳 帆，馮 曉，李 偉

（解放軍信息工程大學(xué)，河南 鄭州 450001）

0 引言

作為保障信息安全的重要手段之一，密碼算法在整個(gè)信息系統(tǒng)中占有非常重要的地位[1]。隨著用戶對信息安全越來越重視，加密模式正朝著多協(xié)議配合完成的復(fù)雜加密模式發(fā)展，同時(shí)密碼算法也正朝著大位寬、可重構(gòu)的方向發(fā)展[2]。傳統(tǒng)的單核密碼處理器已經(jīng)無法滿足新型加密模式和復(fù)雜密碼算法日益增長的性能需求。

相對于單核處理器而言，多核處理器可以提供更強(qiáng)的處理能力。采用多核處理器是解決當(dāng)前復(fù)雜密碼算法實(shí)現(xiàn)高性能計(jì)算的有效方案[3]。但是當(dāng)前面向密碼操作的專用多核處理器仍沒有相對成熟的設(shè)計(jì)技術(shù)。結(jié)合多核處理器設(shè)計(jì)技術(shù)和密碼算法硬件實(shí)現(xiàn)技術(shù)，設(shè)計(jì)一款面向多任務(wù)密碼算法的多核密碼處理器，不僅能夠有效滿足信息安全領(lǐng)域日益增長的需求，同時(shí)也有一定的理論研究價(jià)值。

本文基于多任務(wù)密碼算法并行處理特點(diǎn)與多核互連結(jié)構(gòu)設(shè)計(jì)技術(shù)，分析了密碼算法處理特征，提出了密碼多核處理器性能模型，設(shè)計(jì)了符合密碼算法的密碼多核處理器互聯(lián)結(jié)構(gòu)，并與通用多核處理器中廣泛使用的2D-Mesh互聯(lián)結(jié)構(gòu)在密碼算法執(zhí)行性能方面進(jìn)行了對比。

1 密碼算法并行化分析及Amdahl定律的擴(kuò)展

密碼算法數(shù)據(jù)處理結(jié)構(gòu)與數(shù)據(jù)處理過程具有不同于通用計(jì)算任務(wù)的特殊性，設(shè)計(jì)與密碼處理特征相吻合的多核處理器互聯(lián)結(jié)構(gòu)勢必能夠提高密碼的處理性能[4]。本文研究和分析了密碼多核處理模型，為實(shí)現(xiàn)密碼多核處理器互聯(lián)結(jié)構(gòu)的優(yōu)化設(shè)計(jì)奠定基礎(chǔ)。

1.1 密碼算法統(tǒng)計(jì)分析

本文針對典型的對稱密碼算法的執(zhí)行過程進(jìn)行統(tǒng)計(jì)分析，分析結(jié)果如表1所示。

由分析結(jié)果可得如下結(jié)論：

(1)無論是分組算法、雜湊算法還是序列算法，其結(jié)構(gòu)要素內(nèi)部均存在大量的數(shù)據(jù)并行性可開發(fā)，其主要表現(xiàn)為大操作位寬下的小位寬操作并行執(zhí)行。

表1 常用密碼算法可并行性分析

(2)對稱密碼算法的不同結(jié)構(gòu)要素間存在一定的數(shù)據(jù)并行性。例如分組密碼算法中，結(jié)構(gòu)要素間的數(shù)據(jù)并行性體現(xiàn)為各子塊數(shù)據(jù)在同一算法執(zhí)行階段可執(zhí)行不同類型的基本操作。在序列密碼算法的不同結(jié)構(gòu)要素中，反饋移位寄存器的更新函數(shù)和密鑰流生成函數(shù)表現(xiàn)為當(dāng)前時(shí)刻FSR狀態(tài)序列中部分狀態(tài)的不同函數(shù)，可以同時(shí)并行執(zhí)行。鐘控型和結(jié)構(gòu)可變性的序列密碼算法，其鐘控/結(jié)構(gòu)控制信號和密鑰流生成函數(shù)，表現(xiàn)為某時(shí)刻一個(gè)或多個(gè)反饋移位寄存器狀態(tài)序列中相關(guān)狀態(tài)位的不同函數(shù)可以并行計(jì)算。基于分組原理設(shè)計(jì)的序列算法的FSR反饋函數(shù)的計(jì)算過程各操作間可并行計(jì)算。

由分析可知，密碼算法在數(shù)據(jù)處理過程及數(shù)據(jù)處理特征上具備并行處理潛能，符合多核處理器并行處理特征。因此，可以通過設(shè)計(jì)密碼多核處理器來提升密碼算法的實(shí)現(xiàn)效率。

1.2 Amdahl定律分析及推論

Amdahl定律是研究如何提升系統(tǒng)性能的經(jīng)典定律[5]。定律指出加快某部件執(zhí)行速度所獲得的系統(tǒng)性能提升受限于該部件在系統(tǒng)中被使用的頻率或所占總執(zhí)行時(shí)間的比例[6]。

由Amdahl定律可以確定系統(tǒng)中影響性能最大的部件，同時(shí)也可以衡量由于改進(jìn)某些部件而獲得的系統(tǒng)性能的提高[7]。假設(shè)改進(jìn)系統(tǒng)某一部件，那么系統(tǒng)的性能提升比就是：

通過分析系統(tǒng)性能提升比的公式可知，影響系統(tǒng)性能提升比的兩個(gè)主要因素為：(1)系統(tǒng)完成某任務(wù)的總時(shí)間中待改進(jìn)部分的執(zhí)行時(shí)間所占總時(shí)間的比重，記為f；(2)待改進(jìn)部分改進(jìn)后比改進(jìn)前性能提高的倍數(shù)，記為n。基于上述分析可以得出如下推論：

推論1：設(shè)T0為系統(tǒng)改進(jìn)前完成整個(gè)任務(wù)的總時(shí)間。改進(jìn)后完成整個(gè)任務(wù)的時(shí)間Tn為：

推論2：系統(tǒng)改進(jìn)后整個(gè)系統(tǒng)的性能提升比Sp為：

推論3：改進(jìn)后被改進(jìn)部件執(zhí)行時(shí)間占系統(tǒng)總運(yùn)行時(shí) 間 比f′為 ：

則有：

當(dāng)f′-f＜0時(shí)，說明被改進(jìn)部件在改進(jìn)后的執(zhí)行時(shí)間占系統(tǒng)運(yùn)行時(shí)間比相較于改進(jìn)前要少。

2 密碼多核處理器互聯(lián)結(jié)構(gòu)研究與設(shè)計(jì)

2.1 密碼多核處理器模型研究

事實(shí)上，密碼多核處理器系統(tǒng)不可能集成無限多個(gè)密碼運(yùn)算核心。當(dāng)密碼運(yùn)算核心數(shù)目為N、任務(wù)工作量并行度為i，單個(gè)密碼運(yùn)算核心的運(yùn)算能力為 Δ時(shí)，且N＞i時(shí)，多核系統(tǒng)完成Wi工作量的時(shí)間ti=Wi/(Δ·i)；當(dāng)N＜i時(shí)，多核系統(tǒng)完成Wi工作量的時(shí)間ti=(Wi/(Δ·i))·「i/N?。

并行計(jì)算中運(yùn)算核心間存在通信延遲，設(shè)完成Wi工作量的通信延遲為tdi，此時(shí)多核系統(tǒng)完成W工作量所需時(shí)間為：

通信時(shí)間消耗與通信任務(wù)量及通信網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)，而通信任務(wù)量是與任務(wù)并行度i及計(jì)算任務(wù)Wi的函數(shù)[9]。設(shè)密碼處理任務(wù)為Wi，任務(wù)并行度為i，N個(gè)密碼運(yùn)算核心的多核系統(tǒng)內(nèi)單位時(shí)間可傳輸?shù)臄?shù)據(jù)量為Pd=Ψ(N)，并行度為i時(shí)通信/計(jì)算比為 σ(i)，則通信任務(wù)總量Wdi=σ(i)Wi，且：

同樣，考慮密碼多核系統(tǒng)集成的計(jì)算核心數(shù)N可能小于密碼算法中的任務(wù)并行度i，式(3)修訂為：

將式(3)、式(4)代入式(2)，可以推得：

式(5)給出了適用于密碼多核處理器的結(jié)構(gòu)模型。式(5)中，參數(shù)Δ為常數(shù)；當(dāng)密碼應(yīng)用確定時(shí)，參數(shù)Wi為固定值；多核密碼處理器結(jié)構(gòu)確定時(shí)Ψ(N)為固定值；σ(i)與處理器結(jié)構(gòu)及密碼應(yīng)用有關(guān)[10]。

2.2 模型參數(shù)分析

由2.1節(jié)推導(dǎo)模型可知，密碼任務(wù)并行度及并行部分所占比例決定了密碼處理器可達(dá)到的最高性能，通信延遲是影響密碼多核處理器實(shí)現(xiàn)性能的主要因素之一。在設(shè)計(jì)面向該模型的密碼多核處理器時(shí)，應(yīng)該首先分析密碼應(yīng)用的可開發(fā)并行度，初步確定系統(tǒng)運(yùn)算核心數(shù)目，然后設(shè)計(jì)互聯(lián)結(jié)構(gòu)等。設(shè)計(jì)互聯(lián)結(jié)構(gòu)時(shí)注意使Ψ(N)及σ(i)盡量小，最后根據(jù)設(shè)計(jì)對N值微調(diào)直至最優(yōu)。

表2給出了常見密碼算法并行度的統(tǒng)計(jì)結(jié)果。由表2的統(tǒng)計(jì)結(jié)果分析可知：密碼應(yīng)用的特點(diǎn)是數(shù)據(jù)運(yùn)算比較整齊，并行度變化較少。密碼算法內(nèi)并行度一般為i=1、2、4、8、16，例如 AES 輪運(yùn)算并行度i取值為 1 或 4(S盒可開發(fā)i=16并行度)，DES輪運(yùn)算并行度i取值為 1或 8，IDEA輪運(yùn)算并行度i取值為 1或 4，MD5輪運(yùn)算并行度i取值為1或4。對于密碼協(xié)議等應(yīng)用，通過對數(shù)據(jù)包的拆分，并行度理論上可以達(dá)到無限大，考慮此類問題，設(shè)大整數(shù)X作為可實(shí)現(xiàn)的最大并行度。

表2 典型密碼算法并行度統(tǒng)計(jì)

為方便研究，引入簡化條件對多核密碼處理器模型做定性分析。 假設(shè)當(dāng)i≠1，i≠2，i≠4，i≠8，i≠16，i≠X時(shí)Wi=0。式(5)可化簡為：

由公式分析可知，影響密碼多核處理器運(yùn)算效率的主要因素為密碼算法并行度i、通信/計(jì)算比 σ(i)、系統(tǒng)單位時(shí)間內(nèi)可傳輸數(shù)據(jù)量Ψ(N)。其中密碼算法并行度由算法本身決定，通信/計(jì)算比 σ(i)由密碼算法及算法任務(wù)映射共同決定。本文僅討論多核處理器中互聯(lián)方式對多核系統(tǒng)通信性能的影響，即對系統(tǒng)單位時(shí)間內(nèi)可傳輸數(shù)據(jù)量Ψ(N)的影響。

2.3 簇狀層次化多核互聯(lián)結(jié)構(gòu)設(shè)計(jì)

假設(shè)密碼算法中并行度i與通信/計(jì)算比 σ(i)為固定參數(shù)。此時(shí)，通信性能主要由傳遞延遲決定，設(shè)系統(tǒng)互連結(jié)構(gòu)里消息傳遞過程中跳步數(shù)為H(N)，消息經(jīng)過每個(gè)互聯(lián)節(jié)點(diǎn)的延遲為tdc，則一次通信所需時(shí)間tdi=H(N)·tdc。一次通信所完成的工作量Wdc與通信位寬為mbit、一次可傳輸n個(gè)數(shù)據(jù)有關(guān)，即一次通信完成的工作量Wdc(N)=mn。推導(dǎo)可得：

m與n的設(shè)計(jì)既要考慮硬件實(shí)現(xiàn)過程布局布線工藝又要考慮密碼算法任務(wù)間通信量。據(jù)統(tǒng)計(jì)密碼算法中任務(wù)間通信一般為32 bit的整數(shù)倍。同時(shí)考慮工藝技術(shù)，核間通信一般采用32位寬進(jìn)行通信。因此系統(tǒng)單位時(shí)間內(nèi)可傳輸數(shù)據(jù)量Ψ(N)的大小主要受通信延遲tdi影響，tdi又主要由核心間跳數(shù)H(N)與互聯(lián)節(jié)點(diǎn)中轉(zhuǎn)延遲tdc決定。

本文結(jié)合現(xiàn)有多核互聯(lián)結(jié)構(gòu)設(shè)計(jì)技術(shù)，通過減少多核系統(tǒng)內(nèi)運(yùn)算核心間跳步數(shù)的方法，優(yōu)化設(shè)計(jì)2D-Mesh結(jié)構(gòu)。

本文采用如圖1所示的簇狀層次化多核結(jié)構(gòu)設(shè)計(jì)密碼多核處理器。在整個(gè)多核系統(tǒng)內(nèi)部建立了三層結(jié)構(gòu)的立體多核系統(tǒng)。最底層分布著密碼運(yùn)算核心（標(biāo)記為PCore的一層），負(fù)責(zé)基本的密碼運(yùn)算操作。中間層分布著路由節(jié)點(diǎn)（標(biāo)記為R的一層），負(fù)責(zé)將最底層運(yùn)算核間所交付的通信數(shù)據(jù)進(jìn)行整個(gè)多核結(jié)構(gòu)的傳輸。最高層為多核系統(tǒng)對外接口層(標(biāo)記為輸入/輸出控制器的一層)，負(fù)責(zé)將路由節(jié)點(diǎn)層與外界的數(shù)據(jù)交互。

在該多核系統(tǒng)中，路由節(jié)點(diǎn)層的路由節(jié)點(diǎn)在連接過程中不再采用路由節(jié)點(diǎn)與運(yùn)算核心一一對應(yīng)的鏈接關(guān)系，而是采用一個(gè)路由節(jié)點(diǎn)掛接四個(gè)運(yùn)算處理核心的方式，以此減少運(yùn)算核心在整個(gè)多核系統(tǒng)內(nèi)部數(shù)據(jù)交互的跳數(shù)。同時(shí)，輸入/輸出控制器也采用同樣的方式鏈接路由節(jié)點(diǎn)，以改善多核系統(tǒng)外部與多核系統(tǒng)內(nèi)部數(shù)據(jù)交互的跳數(shù)。

圖1 多核密碼處理器整體互聯(lián)結(jié)構(gòu)示意圖

本文設(shè)計(jì)的層次化2D-Mesh結(jié)構(gòu)保留了簇狀2D-mesh結(jié)構(gòu)的優(yōu)點(diǎn)，同時(shí)利用輸入/輸出控制器增強(qiáng)了簇單元與高層網(wǎng)絡(luò)通信的靈活性。實(shí)現(xiàn)了處理核單元內(nèi)部通信與外部通信的分離，為有序、高效的通信提供了結(jié)構(gòu)上的支持。

3 性能評估

根據(jù)1.2節(jié)中Amdahl定律分析結(jié)論，對比改進(jìn)后與改進(jìn)前系統(tǒng)執(zhí)行效率即可衡量系統(tǒng)性能的提升?；诖耍疚膶⒉⑿胁糠炙急戎夭煌牟⑿卸葹?、8、16的密碼算法分別映射在本文設(shè)計(jì)的簇狀層次化密碼多核結(jié)構(gòu)與2D-Mesh多核密碼處理結(jié)構(gòu)上，對其執(zhí)行時(shí)間進(jìn)行對比。對比結(jié)果如圖2～圖4所示。

圖2 串并比為1:1時(shí)執(zhí)行時(shí)間提升對比

圖3 串并比為1:2時(shí)執(zhí)行時(shí)間提升對比

圖4 串并比為2:1時(shí)執(zhí)行時(shí)間提升對比

由圖2可知，在多核系統(tǒng)中運(yùn)算核心數(shù)目（橫軸）確定的情況下，改進(jìn)后的密碼多核系統(tǒng)相比于改進(jìn)前在執(zhí)行相同任務(wù)映射的密碼算法時(shí)所需時(shí)間（縱軸）較少，即運(yùn)算效率越高。在圖3、圖4中，映射不同串并比的密碼算法也可得到相同結(jié)論。

通過上述對比可知，隨著運(yùn)算核心數(shù)目的不斷擴(kuò)展，本文提出的簇狀層次化多核互聯(lián)結(jié)構(gòu)能夠有效提升多核系統(tǒng)運(yùn)算效率，明顯減少了系統(tǒng)內(nèi)部運(yùn)算核心間通信過程中傳遞延遲，達(dá)到了預(yù)期設(shè)計(jì)目標(biāo)。

4 結(jié)束語

針對密碼多核處理器設(shè)計(jì)，本文深入研究了對稱密碼算法的并行實(shí)現(xiàn)特征，利用Amdahl定律推導(dǎo)建立符合密碼并行運(yùn)算特征的多核處理器模型。通過參數(shù)分析，仿真得到硬件實(shí)現(xiàn)的理論依據(jù)。最后依據(jù)理論結(jié)合設(shè)計(jì)實(shí)際，本文提出了基于2D-Mesh擴(kuò)展結(jié)構(gòu)的簇狀層次化多核處理器互聯(lián)結(jié)構(gòu)。

通過與其他同類設(shè)計(jì)相比，本文設(shè)計(jì)的密碼多核處理器互聯(lián)結(jié)構(gòu)具有較高的密碼算法適應(yīng)性和較高的密碼處理性能。在統(tǒng)一的可重構(gòu)密碼多核處理器下不僅實(shí)現(xiàn)了對公開對稱密碼算法密碼處理性能的有效加速，而且還可以支持幾乎所有其他同類密碼算法。

[1]張曉豐，樊啟華，程紅斌.密碼算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(2)：179-180.

[2]HENNESSY J L，PATTERSON D A.Computer architecture：a quantitative approach[M].Elsevier，2012.

[3]YU Z，YOU K，XIAO R，et al.An 800 MHz 320 mW 16-core processor with message-passing and shared-memory inter-core communication mechanisms[C].Solid-State Circuits Conference Digest of Technical Papers(ISSCC)，2012 IEEE International，2012：64-66.

[4]KHANYILE N P，TAPAMO J R，DUBE E.An analytic model for predicting the performance of distributed applications on multicore clusters[J].IAENG International Journal of Computer Science，2012.

[5]AMDAHL G M.Validity of the single processor approach to achieving large scale computing capabilities[C].Proceedings of spring joint computer conference.ACM，1967：483-485.

[6]陳書明，陳勝剛，尹亞明.Amdahl定律在層次化片上多核處理器中的擴(kuò)展[J].計(jì)算機(jī)研究與發(fā)展，2012，49(1)：83-92.

[7]HILL M D，MARTY M R.Amdahl's law in the multicore era[J].Computer，2008(7)：33-38.

[8]BOSSUET L，GRAND M，GASPAR L，et al.Architectures of flexible symmetric key crypto engines—a survey：From hardware coprocessor to multi-crypto-processor system on chip[J].ACM Computing Surveys(CSUR)，2013，45(4)：41.

[9]BLAKE G，DRESLINSKI R G，MUDGE T.A survey of multicore processors[J].Signal Processing Magazine，IEEE，2009，26(6)：26-37.

[10]李文石，姚宗寶.基于阿姆達(dá)爾定律和蘭特法則計(jì)算多核架構(gòu)的加速比[J].電子學(xué)報(bào)，2012，40(2)：230-234.

[11]GRAND M，BOSSUET L，GOGNIAT G，et al.A reconfigurable multi-core cryptoprocessor for multi-channel communication systems[C].Parallel and Distributed Processing Workshops and Phd Forum(IPDPSW)，2011 IEEE International Symposium on，2011：204-211.