实现基于FPGA的硬件算法加速器

JournalofBaojiUniversityofArtsandSciences(NaturalScience),Vol.26,No.2,pp.1542155,Jun.2006

实现基于FPGA的硬件算法加速器

叶淑群,陈鸿鹏,梁士坤

(广东医学院物理与电子学实验室,广东湛江524023)

3

摘　要:目的　通过具体的方法和示例,说明使用FPGA来实现硬件算法加速是一种较好的方法。方法　通过采用FPGA实现CRC算法的硬件加速器与采用传统的软件优化相比较,说明FPGA的优越性。结果　基于FPGA的硬件算法加速器,既可提高系统的计算能力,也可节约成本,缩小系统体积。结论　根据目标系统的功能需求,使用FPGA来实现硬件算法加速是一种有效、简便、经济的方法。关键词:硬件算法加速器;FPGA处理器;CRC外围电路中图分类号:TP36　　　　文献标识码:A　　　　文章编号:100721261(2006)0220154202

ThehardwarearithmeticacceleratorbasedonFPGA

YEShu2qun,CHENHong2peng,LIANGShi2kun

(Dept.Phys.&ElectronicsLab.,GuangdongMedicalCollege,Zhanjiang524023,Guangdong,China)

Abstract:Aim　TodemonstratethatFPGAisabettermethodtoacceleratehardwarearithmeticthroughsomemethodsandexamples.Methods　TheadvantagesofFPGAwereillustratedthroughcomparingthetraditionalsoftwareandFPGA.Results　FPGAmethodcanimprovesystemcomputa2tionalabilities,economizethecostanddecreasethevolume.Conclusion　FPGAmethodisaneffec2tive,convenientandeconomicmethodtowarearithmetic.

Keywords:hardwarearithmeticaccelerator;FPGAprocessor;CRCexternalcircuit

　　当设计者无法从算法中获得最佳性能并且采用软件方法也行不通时,可以通过硬件和软件重新划分来进行加速。FPGA

[1]

1　硬件加速

硬件加速是指利用硬件模块来替代软件算法以充分利用硬件所固有的快速特性。从软件的角度看,与硬件加速模块接口就跟调用一个函数一样。唯一的区别在于此函数驻留在硬件中,对调用函数是透明的。硬件在执行各种操作时要快得多,如执行复杂的数学功能和将数据从一个地方转移到另一个地方,及多次执行同样的操纵。

系统设计中采用FPGA,在设计周期的任何时候都可以添加定制的硬件。设计者可以立刻编写软件代码,并在最终定稿之前在硬件部分上运行。还可以采取增量法来决定哪部分代码用硬件而不用软件。FPGA供应商所提供的开发工具可实现硬件和软件之间的无缝切换。这些都可为总线逻辑和中断逻辑生成HDL代码,并根据系统配置定制软件库及include文件。

实现软件模块和硬件模块的相互交换,而不

必改变处理器或进行板级变动。

从代码中获得最佳性能的方法包括优化算法、使用查找表法、将一切都转换为本地字长尺寸、使用注册变量、解开循环甚至可能采用汇编代码等。如果所有这些方法均不行,可以转向更快的处理器,采用一个不同的处理器架构,或将代码一分为二通过2个处理器并行处理。利用可编程逻辑作为硬件加速的基础[2],不仅可将那些对时间有严格要求的代码段转换为能够以5～100倍速度运行的函数调用,而且是一种可供软件开发之用的标准工具。

低成本可编程逻辑在嵌入式系统中应用得越来越普遍,这为系统设计者提供了一个无需对处理器或架构进行大的改动即可获得更高性能的可选方案。可编程逻辑可将计算密集型功能转换为硬件加速功能。从软件的角度看,这只是简单地将一个函数调用做进一个定制的硬件模块中,但运行速度要比通过汇编语言优化的相同代码或将算法转换为查找表要快得多。

2　定制指令和硬件外围电路方式

硬件加速模块有2种实现方式。其一是定制指令,它几乎可在每个可配置处理器中实现,这是采用可配置处理

3收稿日期:2005209227,修回日期:2006201211.E2mail:shuqunye@126.com;shuqunye@163.com

作者简介:叶淑群(19682),女,福建南安人,实验师,研究方向:物理学实验教学及其研究.

第2期叶淑群等　实现基于FPGA的硬件算法加速器155

器的主要优点。如图1所示,定制指令是作为算术逻辑单元(ALU)的扩展而添加的,处理器只知道定制指令就像其它指令一样,拥有自己的操作代码。至于C代码[3],宏可自动生成,使用该定制指令就跟调用函数一样。

如果定制指令需要几个时钟周期才能完成并要连续调用它,则可用流水线式定制指令来实现。这样可在每个时钟周期产生一个结果,只是开始时有些延迟。

硬件加速模块的另一种实现方式是硬件外围电路。在这一方式下,数据不是传递给软件函数,而是写入存储器映射的硬件外围电路中。计算是在CPU之外完成的,因此在外围电路工作的同时CPU可以继续运行代码,而代替软件算法的只是一个普通的硬件外围电路。与定制指令的不同之处是硬件外围电路可访问系统中其它外围电路或存储器,无须CPU介入。

模块转换为硬件,只选择那些在硬件中运行得特别快的操作,比如将数据从一处复制到另一处和大量的数学运算以及任何运行多次的循环。如果一个任务由几个数学运算组成,还可考虑在硬件中加速整个任务,有时,仅加速任务中的一个操作就可满足性能要求。下面用具体的实例加以说明。

4　实例:CRC算法的硬件加速

硬件加速可进行大量且重复的计算,循环冗余校验

(CRC)算法或任何\"校验和\"算法。下面通过一个CRC算

法的优化过程来探讨如何实现硬件加速。首先,利用传统的软件技巧来优化算法,然后将其转向定制指令以加速算法。CRC算法可用来校验数据在传输过程中是否被破坏。它们具有很高的检错率,且不会对数据吞吐量造成太大影响,因CRC校验位被添加进数据信息中。但CRC算法比一些简单的校验和算法有更大的计算量要求。一般来说,发送端对要被发送的消息执行

CRC算法,并将CRC结果添加进该消息中,消息的接收

端对包括CRC结果在内的消息执行同样的CRC操作。如果接收端的结果与发送端的不同,这说明数据被破坏了。CRC算法是一种密集的数学运算,涉及到二元模数除法(modulo22division),即数据消息被16或32位多项式(取决于所用CRC标准)除所得的余数。这种操作可通过异或和移位的迭代过程来实现,当采用16位多项式时,

图1　带定制指令的可配置处理器架构根据硬件需要做什么和怎么工作及需要的时间可决定采用那种方式。对于那些在几个周期内可完成的操作,定制指令更好些,因为它性价比高。对于需要执行几个指令来写入控制寄存器、状态寄存器和数据寄存器,且需要一个指令来读取结果。采用外围电路比较好,因它不会影响CPU流水线,也可采用前面所述的流水线式定制指令,外定制指令需要有限数目的操作数,并返回一个结果。根据处理器指令集架构的不同,操作数也各异,对某些操纵,这显得很麻烦,如果需要硬件从存储器或存储器中的其它外围电路读出和写入,则采用硬件外围电路,因定制指令无法访问总线。

相当于每数据字节要执行数百条指令,如果发送数百个字节,计算量就会高达数万条,因此,任何优化都会大幅提高吞吐量。

4.1　传统的软件优化

利用传统的软件技巧来优化CRC算法。因CRC操作中的一个操作数,即多项式(除数)是常数,字节宽CRC操作的所有可能结果都可以预先计算并存储在一个查找表中,通过一个读查找表动作就可让操作按逐个字节执行下去。采用这一算法时,需要将这些预先计算好的值存储在存储器中。选择ROM或RAM都可以,只在启动CRC计算之前将存储器初始化就行。查找表有256个字节,表中每个字节位置包含一个CRC结果,共有256种可能的8位消息(与多项式大小无关)。

3　选择代码

当需要优化C语言代码以满足某些速度要求时,要运行一个代码仿制工具,或亲自检查该代码以便了解代码哪个部分导致系统停滞[4]。这需要熟悉代码以便找出瓶颈所在及优化方法,一种方法是采用本地字大小的变量和带预先计算值的查找表,及通用软件算法优化。这可产生快几倍的执行速度。另一种方法是用汇编语言编写。过去这种方法可获得很好的提高,但现今的编译器在优化C算法上已能得到很好的效果,因此这种性能的提高是有限的。如果需要显著的性能提高,传统的软件算法优化技巧是不够的。利用硬件实施的算法比软件实施要强,要确定将哪些代码转为硬件,这涉及到系统的计算速度和消耗芯片面积的最优化问题,在实际的应用中可不必将整个软件

4.2　采用定制指令方法

CRC算法由连续的异或和移位操作构成,用很少的

逻辑即可在硬件中简单实现。由于这一硬件模块需几个周期来计算CRC,故采用定制指令来实现CRC计算要比采用外围电路更好。此外,无须涉及系统中任何其它外围电路或存储器。仅需要一个微处理器(可配置微处理器)来支持定制指令即可,在硬件中实现时,算法应该每次执行16或32位计算,这取决于所采用的CRC标准。如采用CRC2CCITT标准(16位多项式),最好每次执行16位计算。如采用8位微处理器,效率可能不太高,因装载操作数值及返回CRC值需要额外的周期。

(下转第168页)

168　　　　　宝鸡文理学院学报(自然科学版)2006年

和支持。对广大人民群众、企业主、普通职工、环保工作者进行可持续发展观念的教育,宣传国家环保方针、政策,使广大群众懂环保,支持环保,这对于统一的淮河流域水污染治理机构的建立和工作的开展都有帮助,对淮河流域水污染治理工作也有根本的促进作用。

[3]　平狄克,鲁宾费尔德.微观经济学[M].陈岱孙,梁

晶,海闻,等译.北京:中国人民大学出版社,1997.

5112513.

[4]　李锦秀,廖文根,陈敏建,等.我国水污染经济损失估

算[J].中国水利,2003,(11):62266.

[5]　李鸿昌,高万青.对淮河流域工业发展的思考[J].经

4　结束语

淮河流域水污染治理的任务是艰巨的,明确淮河水资源的产权对于淮河流域水污染的防治有重要意义,因此有必要建立一个统一的流域水污染治理机构。

济经纬,2000,(1):36241.

[6]　姜礼燔.英国治理泰晤士河的基本经验[J].中国渔

业经济研究,1999,(2):40.

[7]　戴倩,罗贻芬.国外流域综合治理中的组织保障及其参考文献:

[1]　中国国家环保局.淮河水系环境质量公报:中国环境

对我国的启示[J].水利经济,2003,21(1):48249.

[8]　汤建中,宋韬,江心英,等.城市河流污染治理的国际质量公报[R].中国国家环保局,1997～2004.

[2]　马中.环境与资源经济学概论[M].北京:高等教育经验[J].世界地理研究,1998,7(2):1142119.

(编校:李宗红)

出版社,1999.29.

(上接第155页)　　图2示出了用硬件实现16位CRC算法的内核。信号msg(15..0)每次被移入异或/移位硬件1位。图3示出了在64KB数据模块上计算CRC的一些C代码例子,该实例是针对Nios嵌入式处理器。

元是可编程的,可针对特定的应用而定制硬件,故仅使用所需要的硬件即可,不必做出任何板级变动(前提是FP2

GA中的逻辑单元足够用),设计者可直接转换到另一个

新的处理器或者编写汇编代码。使用带可配置处理器的

FPGA更灵活,设计者可选择实现软件代码中的每个模

块,如用定制指令或硬件外围电路,还可通过添加定制的硬件来获取比现成微处理器更好的性能。FPGA有充裕的资源,可配置处理器系统可充分利用这一资源,可在速度、硬件逻辑、存储器、代码大小和成本之间做出选择。利用FPGA可以设计定制的嵌入式系统,以增加新的功能特性及优化性能。

图2　16位CRC算法的硬件实现

参考文献:

[1]　丁黄胜.基于FPGA的HMAC_SHA1_96算法设计

与实现[J].半导体技术,2003,28(6):26228.

[2]　王金明,杨吉斌.数字系统设计与VERILOGHdl

[M].北京:电子工业出版社,2002.

[3]　SCHNEIERB.应用密码学(协议、算法与C源程序)

[M].吴世忠,祝世雄,张文政,等译.北京:机械工业

图3　带CRC外围电路和DMA的系统模块示意图出版社,2000.

[4]　STALLINGSW.密码编码学与网络安全:原理与实

5　FPGA的优点

采用基于FPGA的嵌入式系统[1]时,在设计周期前不必考虑每个模块是用硬件还是软件,在设计过程中如需要一些额外的性能,则可利用FPGA中现有的硬件资源来加速软件代码中的瓶颈部分。由于FPGA中的逻辑单

践[M].第2版.杨明,胥光辉,齐望东,等译.北京:电子工业出版社,2001.

(编校:李宗红)