0 引言

　　作为保障信息安全的重要手段之一，密码算法在整个信息系统中占有非常重要的地位[1]。随着用户对信息安全越来越重视，加密模式正朝着多协议配合完成的复杂加密模式发展，同时密码算法也正朝着大位宽、可重构的方向发展[2]。传统的单核密码处理器已经无法满足新型加密模式和复杂密码算法日益增长的性能需求。

　　相对于单核处理器而言，多核处理器可以提供更强的处理能力。采用多核处理器是解决当前复杂密码算法实现高性能计算的有效方案[3]。但是当前面向密码操作的专用多核处理器仍没有相对成熟的设计技术。结合多核处理器设计技术和密码算法硬件实现技术，设计一款面向多任务密码算法的多核密码处理器，不仅能够有效满足信息安全领域日益增长的需求，同时也有一定的理论研究价值。

　　本文基于多任务密码算法并行处理特点与多核互连结构设计技术，分析了密码算法处理特征，提出了密码多核处理器性能模型，设计了符合密码算法的密码多核处理器互联结构，并与通用多核处理器中广泛使用的2D-Mesh互联结构在密码算法执行性能方面进行了对比。

1 密码算法并行化分析及Amdahl定律的扩展

　　密码算法数据处理结构与数据处理过程具有不同于通用计算任务的特殊性，设计与密码处理特征相吻合的多核处理器互联结构势必能够提高密码的处理性能[4]。本文研究和分析了密码多核处理模型，为实现密码多核处理器互联结构的优化设计奠定基础。

1.1 密码算法统计分析

　　本文针对典型的对称密码算法的执行过程进行统计分析，分析结果如表1所示。

　　由分析结果可得如下结论：

　　(1)无论是分组算法、杂凑算法还是序列算法，其结构要素内部均存在大量的数据并行性可开发，其主要表现为大操作位宽下的小位宽操作并行执行。

　　(2)对称密码算法的不同结构要素间存在一定的数据并行性。例如分组密码算法中，结构要素间的数据并行性体现为各子块数据在同一算法执行阶段可执行不同类型的基本操作。在序列密码算法的不同结构要素中，反馈移位寄存器的更新函数和密钥流生成函数表现为当前时刻FSR状态序列中部分状态的不同函数，可以同时并行执行。钟控型和结构可变性的序列密码算法，其钟控/结构控制信号和密钥流生成函数，表现为某时刻一个或多个反馈移位寄存器状态序列中相关状态位的不同函数可以并行计算。基于分组原理设计的序列算法的FSR反馈函数的计算过程各操作间可并行计算。

　　由分析可知，密码算法在数据处理过程及数据处理特征上具备并行处理潜能，符合多核处理器并行处理特征。因此，可以通过设计密码多核处理器来提升密码算法的实现效率。

　　1.2 Amdahl定律分析及推论

　　Amdahl定律是研究如何提升系统性能的经典定律[5]。定律指出加快某部件执行速度所获得的系统性能提升受限于该部件在系统中被使用的频率或所占总执行时间的比例[6]。

　　由Amdahl定律可以确定系统中影响性能最大的部件，同时也可以衡量由于改进某些部件而获得的系统性能的提高[7]。假设改进系统某一部件，那么系统的性能提升比就是：

　　通过分析系统性能提升比的公式可知，影响系统性能提升比的两个主要因素为：(1)系统完成某任务的总时间中待改进部分的执行时间所占总时间的比重，记为f；(2)待改进部分改进后比改进前性能提高的倍数，记为n。基于上述分析可以得出如下推论：

　　推论1：设T0为系统改进前完成整个任务的总时间。改进后完成整个任务的时间Tn为：

　　其中，(1-f)表示不可改进部分。当f=0时，Sp为1，即没有可改进部分。当n→∞时，即可获得的性能改善的极限值受到f的约束。

　　推论3：改进后被改进部件执行时间占系统总运行时间比f′为：

　　当f′-f<0时，说明被改进部件在改进后的执行时间占系统运行时间比相较于改进前要少。

2 密码多核处理器互联结构研究与设计

　　2.1 密码多核处理器模型研究

　　密码算法映射在多核处理器上时，在假设映射的任务量是固定的情况下，处理器完成该固定任务量所需的时间越少则系统性能越高[8]。设任务工作量为W，W由W1，W2，W3…WM组成，其中Wi表示并行度为i的任务工作量，M表示任务工作量中最大的并行度，则任务工作量W可表示为W=wi。当系统有无限多个运算核心，且核心间无通信延迟时，完成Wi所需时间为ti=Wi/(·i)，其中为单个运算核心的运算能力。由Amdahl定律扩展推论1可知，完成W的时间为：

　　事实上，密码多核处理器系统不可能集成无限多个密码运算核心。当密码运算核心数目为N、任务工作量并行度为i，单个密码运算核心的运算能力为时，且N>i时，多核系统完成Wi工作量的时间ti=Wi/(·i)；当N

　　并行计算中运算核心间存在通信延迟，设完成Wi工作量的通信延迟为tdi，此时多核系统完成W工作量所需时间为：

　　通信时间消耗与通信任务量及通信网络结构有关，而通信任务量是与任务并行度i及计算任务Wi的函数[9]。设密码处理任务为Wi，任务并行度为i，N个密码运算核心的多核系统内单位时间可传输的数据量为Pd=(N)，并行度为i时通信/计算比为(i)，则通信任务总量Wdi=(i)Wi，且：

　　同样，考虑密码多核系统集成的计算核心数N可能小于密码算法中的任务并行度i，式(3)修订为：

　　式(5)给出了适用于密码多核处理器的结构模型。式(5)中，参数为常数；当密码应用确定时，参数Wi为固定值；多核密码处理器结构确定时(N)为固定值；(i)与处理器结构及密码应用有关[10]。

　2.2 模型参数分析

　　由2.1节推导模型可知，密码任务并行度及并行部分所占比例决定了密码处理器可达到的最高性能，通信延迟是影响密码多核处理器实现性能的主要因素之一。在设计面向该模型的密码多核处理器时，应该首先分析密码应用的可开发并行度，初步确定系统运算核心数目，然后设计互联结构等。设计互联结构时注意使?追(N)及?滓(i)尽量小，最后根据设计对N值微调直至最优。

　　表2给出了常见密码算法并行度的统计结果。由表2的统计结果分析可知：密码应用的特点是数据运算比较整齐，并行度变化较少。密码算法内并行度一般为i=1、2、4、8、16，例如AES轮运算并行度i取值为1或4(S盒可开发i=16并行度)，DES轮运算并行度i取值为1或8，IDEA轮运算并行度i取值为1或4，MD5轮运算并行度i取值为1或4。对于密码协议等应用，通过对数据包的拆分，并行度理论上可以达到无限大，考虑此类问题，设大整数X作为可实现的最大并行度。

　　为方便研究，引入简化条件对多核密码处理器模型做定性分析。假设当i≠1，i≠2，i≠4，i≠8，i≠16，i≠X时Wi=0。式(5)可化简为：

　　由公式分析可知，影响密码多核处理器运算效率的主要因素为密码算法并行度i、通信/计算比?滓(i)、系统单位时间内可传输数据量(N)。其中密码算法并行度由算法本身决定，通信/计算比(i)由密码算法及算法任务映射共同决定。本文仅讨论多核处理器中互联方式对多核系统通信性能的影响，即对系统单位时间内可传输数据量(N)的影响。

2.3 簇状层次化多核互联结构设计

　　假设密码算法中并行度i与通信/计算比(i)为固定参数。此时，通信性能主要由传递延迟决定，设系统互连结构里消息传递过程中跳步数为H(N)，消息经过每个互联节点的延迟为tdc，则一次通信所需时间tdi=H(N)·tdc。一次通信所完成的工作量Wdc与通信位宽为m bit、一次可传输n个数据有关，即一次通信完成的工作量Wdc(N)=mn。推导可得：

　　m与n的设计既要考虑硬件实现过程布局布线工艺又要考虑密码算法任务间通信量。据统计密码算法中任务间通信一般为32 bit的整数倍。同时考虑工艺技术，核间通信一般采用32位宽进行通信。因此系统单位时间内可传输数据量?追(N)的大小主要受通信延迟tdi影响，tdi又主要由核心间跳数H(N)与互联节点中转延迟tdc决定。

　　本文结合现有多核互联结构设计技术，通过减少多核系统内运算核心间跳步数的方法，优化设计2D-Mesh结构。

　　对于传统2D-Mesh结构而言，因为运算核心平铺在一个平面，随着多核系统的不断扩展，运算核心间数据交互跳数逐渐增多。由文献[11]可知，传统2D-Mesh结构中消息的平均跳步数H(N)为H(N)=(2)/3。因此本文在保留相同数目密码运算核心前提下，针对如何降低运算核心间跳数的问题进行优化设计。

　　本文采用如图1所示的簇状层次化多核结构设计密码多核处理器。在整个多核系统内部建立了三层结构的立体多核系统。最底层分布着密码运算核心（标记为PCore的一层），负责基本的密码运算操作。中间层分布着路由节点（标记为R的一层），负责将最底层运算核间所交付的通信数据进行整个多核结构的传输。最高层为多核系统对外接口层(标记为输入/输出控制器的一层)，负责将路由节点层与外界的数据交互。

　　在该多核系统中，路由节点层的路由节点在连接过程中不再采用路由节点与运算核心一一对应的链接关系，而是采用一个路由节点挂接四个运算处理核心的方式，以此减少运算核心在整个多核系统内部数据交互的跳数。同时，输入/输出控制器也采用同样的方式链接路由节点，以改善多核系统外部与多核系统内部数据交互的跳数。

　　本文设计的层次化2D-Mesh结构保留了簇状2D-mesh结构的优点，同时利用输入/输出控制器增强了簇单元与高层网络通信的灵活性。实现了处理核单元内部通信与外部通信的分离，为有序、高效的通信提供了结构上的支持。

3 性能评估

　　根据1.2节中Amdahl定律分析结论，对比改进后与改进前系统执行效率即可衡量系统性能的提升。基于此，本文将并行部分所占比重不同的并行度为4、8、16的密码算法分别映射在本文设计的簇状层次化密码多核结构与2D-Mesh多核密码处理结构上，对其执行时间进行对比。对比结果如图2～图4所示。

　　由图2可知，在多核系统中运算核心数目（横轴）确定的情况下，改进后的密码多核系统相比于改进前在执行相同任务映射的密码算法时所需时间（纵轴）较少，即运算效率越高。在图3、图4中，映射不同串并比的密码算法也可得到相同结论。

　　通过上述对比可知，随着运算核心数目的不断扩展，本文提出的簇状层次化多核互联结构能够有效提升多核系统运算效率，明显减少了系统内部运算核心间通信过程中传递延迟，达到了预期设计目标。

4 结束语

　　针对密码多核处理器设计，本文深入研究了对称密码算法的并行实现特征，利用Amdahl定律推导建立符合密码并行运算特征的多核处理器模型。通过参数分析，仿真得到硬件实现的理论依据。最后依据理论结合设计实际，本文提出了基于2D-Mesh扩展结构的簇状层次化多核处理器互联结构。

　　通过与其他同类设计相比，本文设计的密码多核处理器互联结构具有较高的密码算法适应性和较高的密码处理性能。在统一的可重构密码多核处理器下不仅实现了对公开对称密码算法密码处理性能的有效加速，而且还可以支持几乎所有其他同类密码算法。

参考文献

　　[1] 张晓丰，樊启华，程红斌.密码算法研究[J].计算机技术与发展，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-memoryinter-core communication mechanisms[C].Solid-State Cir-cuits Conference Digest of Technical Papers(ISSCC)，2012IEEE International，2012：64-66.

　　[4] KHANYILE N P，TAPAMO J R，DUBE E.An analyticmodel for predicting the performance of distributed applica-tions on multicore clusters[J].IAENG International Journalof Computer Science，2012.

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

　　[6] 陈书明，陈胜刚，尹亚明.Amdahl 定律在层次化片上多核处理器中的扩展[J].计算机研究与发展，2012，49(1)：83-92.

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

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

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

　　[10] 李文石，姚宗宝.基于阿姆达尔定律和兰特法则计算多核架构的加速比[J].电子学报，2012，40(2)：230-234.

　　[11] GRAND M，BOSSUET L，GOGNIAT G，et al.A reconfig-urable multi-core cryptoprocessor for multi-channel com-munication systems[C].Parallel and Distributed ProcessingWorkshops and Phd Forum(IPDPSW)，2011 IEEE Interna-tional Symposium on，2011：204-211.