基于Amdahl定律的多核密碼處理器性能模型研究

馮 曉 戴紫彬 李 偉② 蔡路亭

?

基于Amdahl定律的多核密碼處理器性能模型研究

馮 曉①戴紫彬①李 偉*①②蔡路亭①

①(解放軍信息工程大學 鄭州 450000)②(復旦大學專用集成電路與系統國家重點實驗室 上海 201203)

該文構建面向密碼應用的多核處理器性能模型，對多核密碼處理器設計提供理論支持和有效建議。通過引入密碼并行處理特征、數據傳輸時間、同步時間等因素，建立基于Amdahl定律擴展的多核密碼處理器性能模型，基于提出的性能模型，對多核密碼處理器設計空間進行搜索。

密碼處理器；多核處理器；Amdahl定律；性能模型；通信/計算比

1 引言

密碼算法作為保證信息安全的重要措施，在整個信息系統中占有非常重要的地位。密碼處理器具有密碼專用指令及相應的密碼專用運算單元，能夠高效靈活地實現密碼處理任務，成為實現密碼算法的主要方式之一[1]。然而，隨著信息網絡的飛速發展，對密碼處理器性能提出了更高的要求，而受限于功耗、線延時、設計復雜度等因素，依賴于傳統的單核架構提升密碼處理性能變得越來越困難[2]。

相對于傳統單核處理器，多核處理器可以提供更強的處理能力，成為許多高性能計算平臺的首選解決方案。結合多核處理器設計技術和密碼處理器技術，設計面向高速密碼應用的多核密碼處理器，不僅能夠有效滿足信息安全領域日益增長的需求，同時也具有創新性和理論研究價值。然而，目前面向高速密碼應用的多核密碼處理器研究尚處于起步階段，理論體系尚不完備。本文擬基于并行系統加速比定律Amdahl定律，結合密碼并行處理特征、處理器規模、通信消耗等性能因素對定律進行擴展，通過建模及參數分析，構建多核密碼處理器性能模型，為多核密碼處理器結構設計提供一定的理論支持和建議。

2 Amdahl定律研究

Amdahl定律由IBM大型機之父Amdahl博士在1967年首次進行描述[6]。Amdahl指出系統采用并行化技術后所能獲得的性能提升受限于系統中并行化部分所占比例。該論述在并行計算領域得到充分肯定和廣泛應用[7]，逐漸成為描述并行系統加速比的基本定律，Amdahl定律可抽象為

國內外提出了許多基于Amdahl定律的多核處理器性能模型。文獻[8]定義了算法中的關鍵程序段(critical section)，充分考慮并行進程通過關鍵程序段的同步問題，并指出同步問題是影響多核系統性能的關鍵因素之一。文獻[9]將通信開銷引入到Amdahl定律中，提出了關于層次化片上多核處理器的Amdahl定律擴展。文獻[10]將程序的并行度引入到Amdahl定律中，建立了多級并行計算(multi- level parallel)的加速比模型，該模型假定了并行度對通信開銷沒有影響，雖然指出了處理器數目會對算法可執行并行度有影響，但是未對其做進一步研究，模型精確度有待提高。文獻[11]建立了面積-性能模型，用于評估處理器規模受限時可達到的最高性能。文獻[12]將通信開銷引入Amdahl定律，建立了基于面向廣域分布式系統通信特征的多核性能模型。文獻[13]將算法分解為多個部分，每部分可以以不同比例進行加速。文獻[14]充分討論了核間通信時間及并行串行部分的數據同步時間對多核系統性能影響并對Amdahl定律進行了修正。文獻[15]基于任務并行特征建立了進程級封閉式排隊網絡模型(thread-level closed-queuing network model)，用于評估多進程多核處理器的并行計算能力

Amdahl定律中有3個假設：(1)應用程序中只存在一種可開發并行度；(2)無論應用程序中的可并行部分并行度多大，系統都能夠實現；(3)應用程序并行化實現不會引入額外的通信開銷。然而在實際應用中，這3點假設是不準確的。為更精確地評估系統性能，需將以上3點補充進Amdahl定律。目前，尚無綜合考慮以上3種因素的多核處理器性能模型[16]。針對上述不足，本文將密碼算法并行特征、處理器規模、數據傳輸時間、同步時間等因素引入Amdahl定律，建立基于Amdahl定律的多核密碼處理器性能模型。

3 基于Amdahl定律擴展的多核密碼處理器性能模型

3.1 多核密碼處理器性能模型

多核處理器一般采用已有的成熟的單核處理器作為計算核心，本文研究基于成熟的密碼處理器(單核)，為簡化研究復雜度，計算核心為相同的密碼處理器，即研究對象為同構多核密碼處理器結構。設同構多核密碼處理器共個核，借鑒等價基本核模型，每個核抽象為等價的基本核BCE(Base Core Equivalents)[17]，BCE通過某種互連方式連接為一個系統。設多核處理器BCE數目為，單個BCE單位時間內可完成的運算量為，下面根據Amdahl定律，分析多核密碼處理器性能，構建多核密碼處理器性能模型。

(1)并行比例及并行度： 密碼算法可分解為串行執行部分及多種并行度的并行執行部分。如圖1(a)所示為某密碼程序段執行順序的分解圖，由圖中可知，該段程序有串行執行部分及并行度分別為2, 3, 4, 5的并行執行部分。將圖1(a)程序中相同并行度的任務組合在一起，則該密碼程序段可重新分解為如圖1(b)所示結構，分別表示密碼程序中并行度為5, 4, 3, 2和1的部分。

圖1 密碼程序分解圖

密碼處理器主要面向具有某種特征的一類算法，由于密碼算法的差異性，密碼處理器類型呈現多樣化特征。而并行度是一個相對量，可消除這些差異性帶來的影響。通過引入并行度參數不僅能夠提高模型準確度，還能夠擴展性能模型的適用范圍。

(2)可實現并行度： 多核密碼處理器系統不可能集成無限多個密碼處理核心，當時，多核處理器完成工作量的時間；當時，最快只能以并行度完成。因此，多核處理器完成工作量的時間為

通信開銷： 并行計算中BCE間會有通信開銷，主要包括數據傳輸時間和數據同步時間。

應用程序中通信量與計算量有關[18]，密碼程序中計算量較為固定，設密碼程序通信計算比為，則多核處理器完成計算量所需通信量為。單位時間內數據傳輸量是與多核處理器拓撲結構有關的函數，設核處理器單位時間內可傳輸數據量為，則完成并行度任務所需數據傳輸時間：

并行計算中，數據同步直接決定了整體計算結果的正確與否。設設并行度為時通信次數為，同步機制每次通信的同步開銷為，則完成所需的同步時間為有

基于以上分析，多核密碼處理器完成任務W所需時間，可用式(7)表示：

3.2 多核密碼處理器性能模型參數分析

密碼算法特點是數據運算比較整齊，算法內并行度變化較少，并行度一般為=1, 2, 4, 8，例如AES輪運算并行度取值為1或4(S盒可開發=16并行度)，DES輪運算并行度取值為1或8, IDEA輪運算并行度取值為1或4, MD5輪運算并行度取值為1或4, A5算法中移位寄存器次態信息受其前一狀態控制，其并行度為1。

以密碼協議方式處理數據分組，各個密碼算法間可實現并行，可開發并行度與協議所包含的密碼算法數目相等。如SSL(Secure Sockets Layer)協議中包括非對稱加密、對稱加密、單項雜湊3個步驟，3個步驟可通過流水方式并行執行，可開發并行度為3。

操作模式主要有ECB(Electronic CodeBook)，CBC(Cipher Block Chaining), CFB(Cipher FeedBack), OFB(Output FeedBack)和CTR (CounTer Mode)等。除ECB工作模式外，其余工作模式中都是反饋工作模式，存在很強的數據相關，開發并行性難度很大。由于安全原因，ECB模式極少使用，因此數據包內各個分組間的可開發并行度有限。

不同數據包間一般不存在數據相關，理論上存在無限大的可開發并行度。

以2D-Mesh結構為例，在常規2D-Mesh結構中，消息的平均跳步數為[9]，消息經過每個互連節點延遲一個時鐘周期。由于吞吐率要求，目前設計的密碼處理器中，密碼算法程序執行時間一般控制在102~103數量級的運算周期，若互連網絡的位寬為32 bit，一次可傳輸1~32個數據，代入式(8)可得

以AES為例，若不采用并行結構，即=1，此時=0，多核密碼處理器BCE間無通信；若采用密鑰生成部分與輪運算部分并行的結構，即=2，多核密碼處理BCE間有通信，且通信次數為1，通信量等于密鑰長度；若輪運算部分采用4核并行，即=4，多核BCE間有通信且通信量每輪為128 bit，每輪通信3次，完成輪運算需通信36次?？梢姡捎谒惴ê陀成浞绞降牟煌?，通信計算比及通信次數變化較大，當密碼算法及算法映射固定時，通信計算比及通信次數固定。在第4節設計空間搜索中，為盡量覆蓋算法映射情況，通信計算比及通信次數盡量設計變化較大的取值范圍。

4 多核密碼處理器設計空間搜索

本節將基于第3節多核密碼處理器性能模型參數的分析結果，對多核密碼處理器設計空間進行搜索，分析其設計原則并給出設計建議。

設單個BCE完成任務所需時間為單位1。首先，分析通信性能對多核密碼處理器性能的影響。將(假設只存在1, 2, 4, 8, 16并行度，且各部分所占比例相同)，(設為0.01)，,(設為)等參數固定，模擬不同取值下，多核密碼處理器性能與BCE數目的關系。如圖2所示，橫坐標表示多核密碼處理器BCE數目，縱坐標表示多核密碼處理器運算時間。

由圖2中可以發現，6條曲線基本重合，可見，對于多核密碼處理器，BCE互連結構對多核密碼處理器的性能影響并不大。 同時，由曲線趨勢可以發現，在BCE數目為2, 4和8時，多核密碼處理器性能提升幅度較大，而當BCE數目大于8時，處理器性能提升很少。可見，多核密碼處理器性能并非隨BCE數目增加而增加。

圖2 對多核密碼處理器性能影響 圖3 對多核密碼處理器性能影響 圖4 對多核密碼處理器性能影響

圖5 對多核密碼處理器性能影響

1和4，任務計算量比例由1:1遞減到1:6。圖5(c)為密碼應用場景3，密碼應用中可開發并行度為1和8，任務計算量比例由1:1遞減到1:6。圖5(d)為密碼應用場景4，密碼應用可開發并行度為16。

分別觀察圖5(a)~圖5(c)，可以看出，多核密碼處理器結構相同時，密碼程序并行部分比例越大，完成密碼運算所需時間越少。如圖5(a)中，BCE數目相同情況下，密碼程序串行并行部分比例為1:6(比例6)時，多核處理器運算時間明顯小于串行并行比例為1:1(比例1)時。同時，當多核密碼處理器集成的BCE數目超過密碼程序中的最大并行度后，BCE數目增加不會提高密碼處理器性能。如當圖5(a)中BCE數目大于2、圖5(b)中BCE數目大于4及圖5(c)中BCE數目大于8時，提高BCE數目并不能減少多核密碼處理器完成運算任務的時間?？梢缘贸鼋Y論，多核密碼處理器可達到的最高性能主要是由密碼算法可開發并行度及并行部分所占比例決定的。

圖5(d)中密碼應用無串行部分，用于模擬密碼算法數據包級并行的情況。由圖中可以看出，雖然多核密碼處理器運算時間隨著BCE數目增多而逐漸降低，但其下降趨勢逐漸平緩，圖中虛線為其擬合函數?？梢?，即使對于理論上可以無限并行的密碼算法，多核密碼處理器集成的BCE數目也并非越多越好。

通過以上設計空間搜索可得出多核密碼處理器的基本設計原則：根據并行度及各并行度所占比例，確定集成的處理器數目(BCE)，算法映射中盡量減少核間通信次數。文獻[8]從軟件設計方面提出了關鍵程序部分對系統性能的影響，但未將關鍵程序段與硬件設計進行對應，也未對關鍵程序部分進行深入研究。本文則對關鍵部分進行了更深入的分析，指出了通信次數是影響性能的關鍵因素之一。文獻[9]深入研究了不同層次片上數據通信延遲對多核處理器性能的影響，提出層次化設計的多核處理器具有更好的性能，本文從通信特點角度出發得出了相同的結論。文獻[10]主要修訂了應用程序具有多級并行度時的Amdahl定律，模型中做了大量理想化假設，并略去了通信因素的影響，與實際情況具有一定偏差。文獻[11]提出的模型中，假設應用程序的并行度隨著處理器核心數成一定比例關系()，實質上這是對通信開銷等的簡化處理，本文的研究更深入，更有說服力。文獻[13]提出了程序分段加速的思想，將程序分解為多個獨立加速的部分，其分段原則較為模糊，本文是按照并行度對待完成任務進行分解。文獻[14]以FFT等3種典型應用為例，深入分析了通信開銷對多核處理器性能的影響，并未探討密碼類應用的通信特點。文獻[15]基于排隊論建立了多進程多核處理器的性能模型，該模型主要用于研究多進程多核處理器可實現的最高加速比，探討了不同同步類型及不同通信特征應用下多進程多核處理器性能隨處理器數目的變化特征，該論文對應用特征等參數的提取并非基于實際應用。 此外，上述論文都忽略了應用程序可實現并行度對多核密碼處理器設計的重要影響。

對比于其他基于Amdahl 定律的多核處理器性能模型，可以發現，由于引入了更完備的參數，并且在設計空間搜索時參數選取了更為貼近實際情況的取值范圍，本文提出的模型對影響性能的關鍵因素得出了不同的結論，能夠對多核密碼處理器設計提供更準確的指導意見。不同與其他模型偏重于理論性，本文實現了理論性與應用性的統一。

5 結束語

多核密碼處理器是未來密碼處理器的發展方向，然而，目前對多核密碼處理器研究的理論還不完善。在現有Amdahl定律及擴展的研究基礎上，本文建立了面向密碼應用的多核密碼處理器性能模型，并對影響多核密碼處理器處理性能的參數行了詳細分析。通過對各個參數的模擬得出，多核密碼處理器適用于可開發并行度高且并行部分比例大的密碼應用。對于多核密碼處理器，互連結構及通信計算比對處理器性能的影響較小，通信次數對多核密碼處理器性能的影響較大，而多核密碼處理器可到達的最高性能及對應的BCE數目主要由密碼算法取值決定。

密碼算法不同并行層次的操作特點不同。算法內各操作的數據相關性較大，具有較大的取值；密碼協議中，各算法間一般僅需傳遞密碼運算結果，取值較小；數據包及任務間并行，存在并行性的各個分組/任務間一般無數據相關，取值基本為0。若充分發揮多核密碼處理器優勢，必須充分發掘密碼應用的并行性，減少各運算部分的通信次數，依據不同并行層次的通信特征，優化密碼應用多核映射方案。

[1] BOSSUET L, GRAND M, GASPAR L,. Architectures of flexible symmetric key crypto engines-a survey: from hardware coprocessor to multi-crypto-processor system on chip[J].(), 2013, 45(4): 1-32. doi: 10.1145/2501654.2501655.

[2] 馮曉靜. 面向服務的異構多核片上系統的關鍵技術研究及實現[D]. [博士論文], 中國科學技術大學, 2013.

FENG Xiaojing. Study and implementation of service oriented heterogeneous multi processor system-on-chip[D]. [Ph.D. dissertation], University of Science and Technology of China, 2013.

[3] 蔣驍辰, 李國平, 王國中, 等. 基于AVS+實時編碼的多核并行視頻編碼算法[J]. 電子與信息學報, 2014, 36(4): 810-816. doi: 10.3724/SP.J.1146.2013.00845.

JIANG Xiaochen, LI Guoping, WANG Guozhong,. Multi-core parallel video coding algorithm based on AVS+real-time encoding[J].&, 2014, 36(4): 810-816. doi: 10.3724/ SP.J. 1146.2013.00845.

[4] SHUKLA S K, MURTHY C N S, and Chande P K. A Survey of Approaches used in Parallel Architectures and Multi-core Processors, for Performance Improvement[M]. Switzerland, Springer International Publishing, 2015: 537-545.

[5] SILBERSTEIN M. GPUs: High-performance accelerators for parallel applications: the multicore transformation (ubiquity symposium)[J]., 2014, 2014: 1-13. doi: 10.1145/ 2618401.

[6] AMDAHL G M. Validity of the single processor approach to achieving large scale computing capabilities[C]. Proceedings of Spring Joint Computer Conference, New York, 1967: 483-485.

[7] 劉斌, 趙銀亮, 韓博, 等. 基于性能預測的推測多線程循環選擇方法[J]. 電子與信息學報, 2014, 36(11): 2768-2774. doi: 10.3724/SP.J.1146.2013.01879.

LIU Bin, ZHAO Yinliang, HAO Bo,. A loop selection approach based on performance prediction of speculative multithreading[J].&, 2014, 36 (11): 2768-2774. doi: 10.3724/SP.J.1146. 2013.01879.

[8] EYERMAN S and EECKHOUT L. Modeling critical sections in Amdahl's law and its implications for multicore design[C]. ACM SIGARCH Computer Architecture News, New York, 2010: 362-370.

[9] 陳書明, 陳勝剛, 尹亞明. Amdahl 定律在層次化片上多核處理器中的擴展[J]. 計算機研究與發展, 2012, 49(1): 83-92.

CHEN Shuming, CHEN Shenggang, and YIN Yaming. Revisting Amdahl’s law in the hierarchical chip multicore processors[J]., 2012, 49(1): 83-92.

[10] TANG S, LEE B S, and HE B. Speedup for multi-Level parallel computing[C]. Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), Shanghai, 2012: 537-546.

[11] JUURLINK B H H and MEENDERINCK C H. Amdahl's law for predicting the future of multicores considered harmful[J]., 2012, 40(2): 1-9. doi: 10.1145/2234336.2234338.

[12] KHANYILE N P, TAPAMO J R, and DUBE E. An analytic model for predicting the performance of distributed applications on multicore clusters[J]., 2012, 39(3): 312-320.

[13] CASSIDY A S and ANDEROU A G. Beyond Amdahl's law: an objective function that links multiprocessor performance gains to delay and energy[J]., 2012, 61(8): 1110-1126. doi: 10.1109/TC.2011. 169.

[14] YAVITS L, MORAD A, and GINOSAR R. The effect of communication and synchronization on Amdahl’s law in multicore systems[J]., 2014, 40(1): 1-16. doi: 10.1016/j.parco.2013.11.001.

[15] CHE H and NGUYEN M. Amdahl’s law for multithreaded multicore processors[J]., 2014, 74(10): 3056-3069. doi: 10.1016/j.jpdc. 2014.06.012.

[16] AL-BABTAIN B M, AL-KANDERI F J, Al-Fahad M F,. A survey on Amdahl's law extension in multicore architectures[J].(), 2013, 3(3): 30-46.

[17] HILL M D and MARTY M R. Amdahl's Law in the Multicore Era[J]., 2008, 41(7): 33-38. doi: 10.1109/MC.2008. 209.

[18] ASANOVI′C K, BODIK R, CATANZARO B C,. The landscape of parallel computing research: A view from Berkeley[R]. Technical Report ofComputer Sciences University of California at Berkeley, Berkeley: UC Berkeley, 2006: 8-11.

[19] BUCHTY R, HEINTAE N, and OLIVA D. Cryptonite-A Programmable Crypto Processor Architecture for High- bandwidth Applications[M]. Berlin Heidelberg Springer, 2004: 184-198.

[20] 徐衛志, 宋風龍, 劉志勇, 等. 眾核處理器片上同步機制和評估方法研究[J]. 計算機學報, 2010, 33(10): 1777-1787. doi: 10.3724/SP.J.1016. 2010.01777.

XU Weizhi, SONG Fenglong, LIU Zhiyong,. On synchronization and evaluation method of chipped many-core processor[J]., 2010, 33(10): 1777-1787. doi: 10.3724/SP.J.1016.2010.01777.

馮 曉： 女，1987年生，博士生，研究方向為多核處理器、可重構芯片等.

戴紫彬： 男，1966年生，博士生導師，研究方向為專用芯片設計、可重構芯片、可重構SoC設計等.

李 偉： 男，1983年生，博士生，研究方向為大規模集成電路設計、多核處理器、信息安全等.

蔡路亭： 男，1989年生，碩士生，研究方向為信息安全、安全通信、SoC設計等.

Performance Model of Multicore Crypto Processor Based on Amdahl’s Law

FENG Xiao①DAI Zibin①LI Wei①②CAI Luting①

①(PLA Information Engineering University, Zhengzhou 450000, China)②(State Key Laboratory of Special Integrated Circuit and System, Fudan University, Shanghai 201203, China)

This paper builds a performance model of multicore processor, which applies to the crypto algorithms, and some advisable suggestions and academic supports are given for its design. By introducing parallelism degree, transformation overhead and synchronization time, performance model of multicore crypto processor is built based on the Amdahl’s law and its extension, and accordingly the design space of multicore crypto processors is searched. Simulation analysis shows that the key factors influencing the performance model of multicore crypto processor are the exploitable parallelism of crypto application, the proportion of parallel part and the communication times in the process of operation.

Crypto processor; Multicore processor; Amdahl’s law; Performance model; Communication/computing ratio

National Natural Science Foundation of China (61404175)

TP309.7；TN492

A

1009-5896(2016)04-0827-07

10.11999/JEIT150474

2015-04-27；改回日期：2015-12-25；網絡出版：2016-02-18

李偉 try-1118@163.com

國家自然科學基金項目(61404175)