【VC++开源代码栏目提醒】:以下是网学会员为您推荐的VC++开源代码-高性能MD5算法IP核的设计空间探索与分析 - 会议论文,希望本篇文章对您学习有所帮助。
CN43—1258/TP 计算机工程与科学 2009年第31卷第11期 ISSN 1007—130X COMPUTER ENGINEERING&SCIENCE V01.31.No.11.2009 文章编号:1007—130X(2009)1卜0058—04 高性能MD5算法IP核的设计空间探索与分析 Design Space Exploration and Analysis of H igh Performance MD5 IP Core 原昊。
吴东。
谢向辉 YUAN ltao,WU Dong。
XIE Xiang-hui (江南计算技术研究所,江苏无锡214083) (Jiangnan Institute of Computing Technology-Wuxi 214083。
China) 摘要:本文以Bluespec SystemVerilog高层硬件描述语言为工具,对MD5核心算法进行了设计空间探索,实现了全展开组合逻辑、全展开流水线、循环迭代、流水化的循环迭代四种结构,测试和分析了各种结构的性能和面积指标,完整掌握了MD5 IP核的设计空间的各项参数。
Abstract:This paper uses a high-level hardware description language called Bluespec SystemVerilog as the basic tool,takes a design space exploration of the hardware implementation of the MD5 algorithm,implements four different architee—tures,tests and analyzes the performance and area occupation of the four architectures,and gets the complete parameters ofthe design space for晒IP Cores. 关键词:MD5;Bluespec SystemVerilog;高性能加速计算 Key words:溉:Bluespec SystemVerilog;high perfermance accelerated computing doi:10.3969/j.issn.1007—130X 2009.11.015 中图分类号:TP309 文献标识码:A 来表示状态变化的动作(Action)。
一个Bluespec
程序的运1 引言 行过程可以描述为规则执行的序列,由于规则具有原子性, 因此在保证语义正确的前提下,多条规则可以并行地执行。
MD5报文摘要算法是目前应用最广泛的安全散列算 在Bluespec中,模块的接口并不是由端口(Port)来表爪的,法,广泛应用于
网络消息认证、完整性检测等方面。
随着网 而是用方法(method)描述接口的行为以及实施的条件,络
通信带宽的日益增长,对高效MD5算法实现的需求日 Bluespec通过方法的条件来保证方法是否可以被调用。
方益增长,而传统的软件实现越来越难以满足迅速增长的性 法的使用提高了设计的抽象层次,并减少了对于模块的错能需求,因此通过硬件来实现高速MD5算法就成为必然。
误使用。
目前Bluespee已经应用于一些大型的设计〔1〕中, 目前主要的硬件设计方法是基于RTL级的Verilog等硬件 一些现有的工作〔2〕表明,Bluespec实现的设计与RTL级的描述语言的,但由于其抽象层次较低,设计和调试的难度都 设计在性能和资源上基本相当。
比较大,开发周期因而也相对较长,在这种传统设计模式下 本文的主要工作是使用Bluespec SystemVerilog这一进行设计空间探索是非常困难的,因此就需要具有更高抽 工具对MD5算法IP核的设计空间进行探索、实现和测试。
象层次的工具和
设计流程。
Bluespec SystemVerilogr〔u是一种基于GAA(Guarded 2相关
工作Atomic Action,简称GAA)模型的高层次硬件描述语言,它可以方便地对设计进行仿真,并可以编译出可综合的Ver- 目前,国内外现有关于MD5算法IP核的实现基本都ilog
代码。
Bluespec中的基本操作被称为规则(Rule),每条 是在RTL级设计与实现的。
SatohZ朝等在0.13微米工艺规则包含一个布尔条件来指定规则是否有效,以及一个用 下实现的MD5的ASIC算核共占用了17 700门电路,频率 ·收稿日期:2009—07—13;修订El期:2009—09—10 基金项目:国家973计划资助项日(2007CB310907);国家863计划资助项目(2007AAOlZll7) 作者简介:原吴(1984一),男.山西太原人,硕上生。
研究方向为高性能
计算机体系结构和可蘑构计算。
通讯地址:214083江苏省无锡市35信箱031号;Tel:(0510)85155639;E-mail:yuanha02003@tsinghu丑org.cn Address:P.O.Box 35—03l,Wuxi,Jiangsu 214083.P.R China 58可以达到277MHz,吞吐量为2 091Mbps。
但是,限于 3.2全展开流水电路实现ASIC的成本,大部分研究还是采用FPGA作 IVID5算法的64步运算是非常规则的,非常适合进行为实现平台。
如Deepakumar的设计〔43在全迭代模式下可 流水,以提高资源的利用率。
将之前的全组合电路的结构以达到165Mbps的吞吐量,在全展开模式下则可以达到 加以改造,在每一步运算之间以及输入端和输出端加入寄354Mbps。
而Jarvinen〔53等人使用VertexlI实现的MD5算 存器,就形成了一个65级的流水线。
但是,综合后发现,这核的吞吐量达到了725Mbps。
国内方面,戴紫彬教授等人 样的设计需要46 000多个LE(Logic Element,简称LE),在Altera的ACEXlK平台上实现了308Mbps的吞吐 远远超过了芯片上的资源。
造成这种情况的主要原冈是流量邛〕。
张九华在Virtex XVC50芯片上实现了366Mbps的 水线中的每一级都各有一个512位和128位的寄存器保存吞吐量〔7〕。
目前,已有的实现都是在传统的RTL级设计 分组和中间结果,整个流水线有65级,因而消耗了大量的的,开发时间长,调试难度大,因此作者一般都只是根据自 芯片资源。
因此,必须对结构进行改进,减少寄存器的使己的理解实现的特定结构,缺乏对于整个设计空间的研究 用。
FPGA上除了LE和Register之外,还有丰富的存储和探索,这也是本文工作所需解决的主要问题。
器资源,如果能够将这些资源利用起来,就可以解决之前的
问题。
通过分析算法发现,算法中每一步的计算实际上只3 MD5算法IP核的设计空间探索 需要分组中的一个32位的子分组,而且在每一轮中每个子 与实现 分组只需要参与一次运算。
因此,如果可以对消息分组的 保存和传递方式进行改造,就可以大大减少寄存器的占用。
MD5算法〔8〕可以对任意长度的消息生成一个128位 图2就是改进后的单个流水级的结构。
的单向散列输出。
在对消息进行一定的预处理之后,它以512位分组为单位来处理消息,输出为四个32位子分组级联形成的128位散列值。
MD5算法的核心部分主要分为四轮运算,每二轮各使用一种非线性函数对消息的子分组做16步运算,其中单步所做的运算如下: a=b+((口+(F(6,c,d)+Mf+正)<<<s) 图2改进后的全流水设计中单个流水级的结构其中,a,b、c、d为变量}M表示一个子分组;正为一个与步 在对流水级结构改进中,取消了原本在流水级之间的数i相关的常数l<<<s表示循环左移s位。
对于IvID5 512位的寄存器,保留了保存中间结果的128位寄存器,在算法中某一步来说,正和s是固定的常数。
F(b。
C,d)为对 每个流水级上增加了一个32位宽的FIF0。
当一个分组送应的线性函数,分别如下: 人算核之后,它的16个子分组会分别送入第一轮运算的 F(X,Y,Z)=(X&y)l((一X)&Z) 16个流水级的FIFo中,每一个流水级在运算时从FIFo G(X,Y,Z)=(艇Z)f(y&(~乃) 中取出32位的子分组进行运算,同时将这个子分组送入下 H(X,Y,Z)=X.Y2 一轮对应流水级的FIFo中。
这些FIF_o可以被综合成为 j(X;y,Z)=y^(X I(~乃) FPGA的片上存储器。
因而节约了寄存器资源,通过测试, 当四轮64步运算完成之后,将第64步之后得到的口、 改进后所需要的LE降到了24 000左右。
6、f、d分别加上四个初始化值就是算法的最终结果。
3.3循环迭代实现 MD5算法的硬件实现可有多种结构,各种结构所占用的资源、运行速度、吞吐率及与外界的接口都不尽相同。
下 前面两种结构的基础都是将MD5的64级运算完全展面对MD5算法的硬件结构进行设计空间探索和实现。
开,每一步运算都实例化了相应的组合电路,这样占用的芯 片面积比较大。
而且每一拍至少需要送入一个512位的分3.1全展开组合电路实现 组,输出为128位。
不适合对芯片的面积和接口有约束的情 IVlD5算法中相邻两步之间都是有数据依赖关系的,因 况。
原始的MD5算法实际上是串行的算法,每一轮的16此64步运算必须串行地完成。
纯组合电路方式就是将 步运算除了循环左移的s位之外,其它部分都是固定的,因IVlD5算法的64步运算完全展开,完全使用组合电路来实 此可以进行资源复用,通过循环迭代的方式来实现算法。
现。
在这种结构下,整个电路中每轮只有一个非线性函数 的实例,对于一个分组输入,按照算法进行64轮循环计算, 每一轮根据循环变量的不同,选择不同计算模块和参数如 图3所示。
这种结构使电路的规模达到最小,同时接口的 图1纯组合电路IVID5算法实现的结构 宽度也可以减小,每拍只需要送入本轮所需的32位子分组 在这种结构下,数据依次流过64级运算的组合电路, 即可,绍果的输出也可以通过依次输出4个32位分组实得到最终结果。
由于算法中每一步的运算量都比较大,数 现。
这种结构实现了资源的最小化,但吞吐率只有同样频据完全通过64步组合电路的延时将非常大,同时由于对每 率全流水实现的t/64。
一步运算都实现了相应的组合电路,所占用的资源也比较 3.4循环迭代流水化实现大。
因此,这种结构没有太大的实用价值,但可以在资源占 循环迭代实现了资源利用的最小化,但吞吐率下降了用和延时等方面作为其它结构的参考。
64倍。
通过对其结构进行观察发现,当进行某一轮的运算 59 来保证数据的输入和输出。
全迭代结构所占用的资源是最少的,但最高频率只能 达到52.7MHz,这主要是由算法流程的调度所带来的额外 开销所造成的。
四级流水占用的资源比全迭代增加较多, 主要原因是每一级流水内部都需要独立的流程控制部件, 外部还需要对四级流水线整体进行控制,因此资源开销增 图3循环迭代实现的基本结构 加较大。
但是,相对全流水结构面积还是小得多,性能比全时,其它三轮对应的计算资源是处于空闲状态的,因此可以 迭代提高了4倍,32位的输入输出接口在实际应用中具有对这四轮运算实现流水化。
以每一轮作为一级流水,在两 较大优势。
级之间加入寄存器,实现了四级循环迭代的流水线,如图4 4.2与同类研究的比较所示。
为了考查Bluespec生成的硬件的性能,在公开发表的 资料中选择三组RTI.实现作为参考,利用Bluespec在相 同器件上实现相同的结构,得到的测试结果如表2所示。
从表2可以看出,对于同样的硬件结构,使用131uespec 所综合出的电路,在资源占用和时钟频率上都与经过人工 图4四级流水的循环迭代结构 优化的RTI,级设计基本相当,在某些方面还略高一点,这 这是一种比较均衡的结构,既保持了芯片资源的低占 充分证明了Bluespec在硬件描述卜的性能。
而在开发效用率,又能够充分利用已有的资源,32位的输入接口可以 率上,Bluespec则具有更大的优势,我们将MD5算法核心不停地送入数据,最大程度地利用r现有资源。
部分实现的
代码量进行了对比,如表3所示。
表3 MD5核心算法
代码■比较4测试数据与分析 本文所采用的测试方法是,将BIuespec生成的Verilog
代码在Elba工具中对某个目标芯片进行综合,可以得到 表3中Bluespec的
代码量为本文实现循环迭代结构的设计所占用的资源和最高运行频率。
本文的测试环境为: 源
代码行数,总共174行。
而
开源网站OpenCores所提供
软件为Ahera Quartus II 8.0 SPl,硬件采用Altera公司的 的实现相同功能的Verilog
代码【lo〕要390行。
RFCCyclone II EP2C35F672C6芯片。
1321【12j中给出的MD5算法的C语言参考实现中,实现相4.1 四种结构的比较与分析 应功能的核心
代码长度约为350行。
这组数据充分说明了 本文所实现的四种结构在上述环境下的测试结果如表 Bluespec
代码描述的高效性,这主要得益于151uespec有较1所示。
高的抽象层次,以及对行为的原子性约束,既具备了较强的 全组合电路的实现可以作为一个基本的参考,由总延 描述能力,又保证了
代码的高效性。
Bluespec所提供的模时785ns可以算出平均每一步运算的延时大约为12ns,因 拟工具Bluesim叮以快速地对电路进行功能验证,并得到此在其它结构下周期不呵能小于这个延时。
输出波形,这对于提高设计效率也有很大的帮助。
通过以 全流水结构综合的结果最小周期约为12.5ns,已经非 .