datasheet

如何用FPGA实现算法的硬件加速

2008-04-24来源: 电子系统设计 关键字:实现算法  CRC  硬件加速  FPGA  查找表  typedef  const  算术逻

  当设计者试图从算法中获得最佳性能但软件方法已无计可施时,可以尝试通过硬件/软件重新划分来进行加速。FPGA易于实现软件模块和硬件模块的相互交换,且不必改变处理器或进行板级变动。本文阐述如何用FPGA来实现算法硬件加速

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

  

  

  图1:带定制指令的可配置处理器架构。

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

  硬件加速

  首先探讨一下什么是硬件加速,以及将算法作为定制指令来实现与采用硬件外围电路的区别。硬件加速是指利用硬件模块来替代软件算法以充分利用硬件所固有的快速特性。从软件的角度看,与硬件加速模块接口就跟调用一个函数一样。唯一的区别在于此函数驻留在硬件中,对调用函数是透明的。

  取决于算法的不同,执行时间最高可加快100倍。硬件在执行各种操作时要快得多,如执行复杂的数学功能、将数据从一个地方转移到另一个地方,以及多次执行同样的操纵。本文后面将讨论一些通常用软件完成的操作,经过硬件加速后这些操作可获得极大的性能提高。

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

  带一些CISCRISC

  精简指令集计算(RISC)架构的目标之一即是保持指令简单化,以便让指令运行得足够快。这与复杂指令集计算(CISC)架构正好相反,后者一般不会同样快地执行指令,但每个指令可完成更多处理任务。这两种架构应用得都很普遍,而且各有所长。

  如果能根据特定的应用将RISC的简单和快速特性与CISC强大的处理能力结合起来,岂不两全其美?其实这正是硬件加速所要做的。加入为某种应用而定制的硬件加速模块可以提高处理能力,并减少代码复杂性和密度,因为硬件模块取代了软件模块。可以这么说,是用硬件来换取速度和简单性。

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

  有两种硬件加速模块实现方式。其一是定制指令,它几乎可在每一个可配置处理器中实现,这是采用可配置处理器的主要优点。如图1所示,定制指令是作为算术逻辑单元(ALU)的扩展而添加的。处理器只知道定制指令就像其它指令一样,包括拥有自己的操作代码。至于C代码,宏可自动生成,从而使得使用该定制指令跟调用函数一样。

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

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

  根据硬件需要做什么、怎么工作以及需要多长时间可以决定采用是定制指令还是硬件外围电路更合适。对于那些在几个周期内就可完成的操作,定制指令一般更好些,因为它产生的开销要更少。对于外围电路,一般需要执行几个指令来写入控制寄存器、状态寄存器和数据寄存器,而且需要一个指令来读取结果。如果计算需要几个周期,实施外围电路比较好,因为它不会影响CPU流水线。或者,也可以实施前面所述的流水线式定制指令。

  另一个区别是定制指令需要有限数目的操作数,并返回一个结果。根据处理器指令集架构的不同,操作数也各异。对某些操纵,这样可能显得很麻烦。此外,如果需要硬件从存储器或存储器中的其它外围电路读出和写入,则必须采用硬件外围电路,因为定制指令无法访问总线。

  图2:16位CRC算法的硬件实现。(Optional)

  选择代码

  当需要优化C语言代码以满足某些速度要求时,可能要运行一个代码仿制工具,或亲自检查该代码以便了解代码的哪个部分导致系统停滞。当然,这需要熟悉代码以便知道瓶颈在哪儿。

  即便找出瓶颈所在,如何优化也是个挑战。有些方案采用本地字大小的变量、带预先计算值的查找表,以及通用软件算法优化。这些技巧可产生快几倍的执行速度效果。另一种优化C算法的方法是用汇编语言编写。过去这种方法可获得很好的提高,但现今的编译器在优化C算法上已做得很好,因此这种性能的提高是有限的。如果需要显著的性能提高,传统的软件算法优化技巧恐怕是不够的。

  然而,利用硬件实施的算法比软件实施要强100倍,这不足为奇。那么,如何确定将哪些代码转为硬件实施呢?大可不必将整个软件模块转换为硬件,而应选择那些在硬件中运行得特别快的操作,比如将数据从一处复制到另一处、大量的数学运算以及任何运行多次的循环。如果一个任务由几个数学运算组成,还可以考虑在硬件中加速整个任务。有些时候,仅加速任务中的一个操作就可满足性能要求。

  实例:CRC算法的硬件加速

  由于大量且重复的计算,循环冗余校验(CRC)算法或任何“校验和”算法都是硬件加速的不错选择。下面通过一个CRC算法的优化过程来探讨如何实现硬件加速。

  首先,利用传统的软件技巧来优化算法,然后将其转向定制指令以加速算法。我们将讨论不同实现方法的性能比较和折衷。

  CRC算法可用来校验数据在传输过程中是否被破坏。这些算法很流行,因为它们具有很高的检错率,而且不会对数据吞吐量造成太大影响,因为CRC校验位被添加进数据信息中。但是,CRC算法比一些简单的校验和算法有更大的计算量要求。尽管如此,检错率的提高使得这种算法值得去实施。

  一般说来,发送端对要被发送的消息执行CRC算法,并将CRC结果添加进该消息中。消息的接收端对包括CRC结果在内的消息执行同样的CRC操作。如果接收端的结果与发送端的不同,这说明数据被破坏了。

  CRC算法是一种密集的数学运算,涉及到二元模数除法(modulo-2 division),即数据消息被16或32位多项式(取决于所用CRC标准)除所得的余数。这种操作一般通过异或和移位的迭代过程来实现,当采用16位多项式时,这相当于每数据字节要执行数百条指令。如果发送数百个字节,计算量就会高达数万条指令。因此,任何优化都会大幅提高吞吐量。

  代码列表1中的CRC函数有两个自变量(消息指针和消息中的字节数),它可返回所计算的CRC值(余数)。尽管该函数的自变量是一些字节,但计算要逐位来执行。该算法并不高效,因为所有操作(与、移位、异或和循环控制)都必须逐位地执行。

  列表1:逐位执行的CRC算法C代码。

  /*

  * The width of the CRC calculation and result.

  * Modify the typedef for a 16 or 32-bit CRC standard.

  */

  typedef unsigned char crc;

  #define WIDTH (8 * sizeof(crc))

  #define TOPBIT (1 <<(WIDTH - 1))

  crc crcSlow(unsigned char const message[], int nBytes)

  {

  crc remainder = 0;

  /*

  * Perform modulo-2 division, a byte at a time.

  */

  for (int byte = 0; byte

  {

  /*

  * Bring the next byte into the remainder.

  */

  remainder ^= (message[byte] <<(WIDTH - 8));

  /*

  * Perform modulo-2 division, a bit at a time.

  */

  for (unsigned char bit = 8; bit > 0; "bit)

  {

  /*

  * Try to divide the current data bit.

  */

  if (remainder &TOPBIT)

  {

  remainder = (remainder <<1) ^ POLYNOMIAL;

  }

  else

  {

  remainder = (remainder <<1);

  }

  }

  }

  /*

  * The final remainder is the CRC result.

  */

  return (remainder);

  }

  1.传统的软件优化

  

  

  图3:带CRC外围电路和DMA的系统模块示意图。

让我们看一下如何利用传统的软件技巧来优化CRC算法。因为CRC操作中的一个操作数,即多项式(除数)是常数,字节宽CRC

[1] [2]

关键字:实现算法  CRC  硬件加速  FPGA  查找表  typedef  const  算术逻

编辑:ssb 引用地址:http://www.eeworld.com.cn/gykz/2008/0424/article_844.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:四种常用FPGA/CPLD设计思想与技巧
下一篇:用数字隔离技术取代隔离放大器的应用实例

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

采用AVR单片机汇编语言实现AES加密算法及其优化

    AES是美国高级加密标准算法,将在未来几十年里代替DES在各个领域中得到广泛应用。本文在研究分析AES加密算法原理的基础上,着重说明算法的实现步骤,并结合AVR汇编语言完整地实现AES加密和解密。根据AES原理,提出几种列变化的优化算法,并根据实验结果分析和比较它们的优缺点。     随着对称密码的发展,DES数据加密标准算法由于密钥长度较小(56位),已经不适应当今分布式开放网络对数据加密安全性的要求,因此1997年NIST公开征集新的数据加密标准,即AES[1]。经过三轮的筛选,比利时Joan Daeman和Vincent Rijmen提交的Rijndael算法被提议
发表于 2018-03-19
采用AVR单片机汇编语言实现AES加密算法及其优化

采用ARM9微控制器实现上层控制算法解析方案

  引言  在很多嵌入式控制系统中,系统既要完成大量的信息采集和复杂的算法,又要实现精确的控制功能。采用运行有嵌入式Linux操作系统的ARM9微控制器完成信号采集及实现上层控制算法,并向DSP芯片发送上层算法得到控制参数,DSP芯片根据获得的参数和下层控制算法实现精确、可靠的闭环控制。  1 多机系统组成  该多机控制系统以ARM9微控制器s3c2440为核心,采用I2C总线挂载多个DSP芯片TMS320F28015作为协控制器,构成整个控制系统的核心。  1.1 S3C2440及TMS320F28015简介  Samsung公司的处理器S3C2440是内部集成了ARM公司ARM920T处理器内核的32位微控制器,资源丰富
发表于 2018-02-19
采用ARM9微控制器实现上层控制算法解析方案

单片机实现数字滤波的算法

    单片机主要作用是控制外围的器件,并实现一定的通信和数据处理。但在某些特定场合,不可避免地要用到数学运算,尽管单片机并不擅长实现算法和进行复杂的运算。下面主要是介绍如何用单片机实现数字滤波。    在单片机进行数据采集时,会遇到数据的随机误差,随机误差是由随机干扰引起的,其特点是在相同条件下测量同一量时,其大小和符号会现无规则的变化而无法预测,但多次测量的结果符合统计规律。为克服随机干扰引起的误差,硬件上可采用滤波技术,软件上可采用软件算法实现数字滤波。滤波算法往往是系统测控算法的一个重要组成部分,实时性很强。    采用数字滤波算法克服随机干扰
发表于 2017-11-18

单片机采用RLE算法实现液晶屏显示图片

由于需要用到液晶屏(320*240)显示图片,而且图片的数量比较多(好几百张),并且图片要求保存到16M的SPI FLASH里面,显然如果不处理 16M的FLASH明显是放不下去。后来同事说可以用压缩算法RLE,并且用C#给我做了个小的软件,压缩图片得到RLE压缩后的数据。点击打开链接  ---------- 详细的RLE算法可以参考次连接http://blog.csdn.net/orbit/article/details/7062218这个算法的缺点是  如果图片颜色复杂就不好,所以颜色尽量单调些。1、RLE算法小工具的使用2、我使用的RLE和上面连接的区别(改进)3、单片机里面实现的方法1、RLE算法小工具
发表于 2017-09-11
单片机采用RLE算法实现液晶屏显示图片

音频信号采集与AGC算法的DSP实现

实现方法具有实现简便、程序可移植行强、处理速度快等优点,特别是TI公司TMS320C54X系列在音频处理方面有很好的性价比,能够解决复杂的算法设计和满足系统的实时性要求,在许多领域得到广泛应用。在DSP的基础上对音频信号做AGC算法处理可以使输出电平保持在一定范围内,能够解决不同节目音频不均衡等问题。  音频信号采集  TI公司DSP芯片TMS320V  C5402具有独特的6总线哈佛结构,使其能够6条流水线同时工作,工作频率达到100MHz。利用VC5402的2个多通道缓冲串行口(McBSP0和McBSP1)来实现与AIC23的无缝连接。VC5402的多通道带缓冲的串行口在标准串口的基础上加了一个2K的缓冲区。每次串口发送数据时,CPU
发表于 2017-09-05
音频信号采集与AGC算法的DSP实现

通过这个神奇的算法,就能实现提供医疗级可穿戴产品方案

监测。CT404SG1模块基于TI AFE4404,包括AFE、MCU、G-sensor,iCareTech公司TrueSpO2/TrueHR专利算法且内置在模块中。它的尺寸仅为6mmx6mmx1.6mm功耗极低,PD/LED配置灵活,而且具有医疗级别的测量精度。大联大友尚借此还进一步推出了具备基于反射式血糖测量模块的,TI AFE4404的混合信号模块---ICT404SG1的个人健康智能手环解决方案。该方案具有连续脉率测量和连续血氧监测功能,可实现Led反射式血氧饱和度(SpO2)和脉率(PR)测量。其C+专利血氧心率算法提供了医疗级测量结果;凭借着大容量电池和超低功耗,该方案具有超长工作时间;通过蓝牙,配合云卫康手机APP
发表于 2017-04-19
通过这个神奇的算法,就能实现提供医疗级可穿戴产品方案

小广播

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved
pt type="text/javascript" src="//v3.jiathis.com/code/jia.js?uid=2113614" charset="utf-8">