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

1、如何用fpga实现算法的硬件加速当设计者试图从算法中获得最佳性能但软件办法已无计可施时，可以尝试通过硬件/软件重新划分来举行加速。易于实现软件模块和硬件模块的互相交换，且不必转变处理器或举行板级变动。本文阐述如何用fpga来实现算法的硬件加速。假如想从代码中获得最佳性能，办法包括优化算法、用法查找表而不是算法、将一切都转换为本地字长尺寸、用法注册变量、解开循环甚至可能采纳汇编代码。假如全部这些都不奏效，可以转向更快的处理器、采纳一个不同的处理器架构，或将代码一分为二通过两个处理器并行处理。不过，假如有一种办法可将那些对时光有严格要求的代码段转换为能够以5-100倍速度运行的函数调用，而且假如这

2、一办法是一种可供软件开发之用的标准工具，这可信吗？现在，利用可编程规律作为硬件加速的基础可使这一切都变成现实。图1：带定制命令的可配置处理器架构。低成本可编程规律在系统中应用得越来越普遍，这为系统设计者提供了一个无需对处理器或架构举行大的改动即可获得更高性能的可选计划。可编程规律可将计算密集型功能转换为硬件加速功能。从软件的角度看，这只是容易地将一个函数调用做进一个定制的硬件模块中，但运行速度要比通过汇编语言优化的相同代码或将算法转换为查找表要快得多。1 硬件加速首先探讨一下什么是硬件加速，以及将算法作为定制命令来实现与采纳硬件外围的区分。硬件加速是指利用硬件模块来替代软件算法以充分利用硬件所

3、固有的迅速特性。从软件的角度看，与硬件加速模块接口就跟调用一个函数一样。唯一的区分在于此函数驻留在硬件中，对调用函数是透亮的。取决于算法的不同，执行时光最高可加快100倍。硬件在执行各种操作时要快得多，如执行复杂的数学功能、将数据从一个地方转移到另一个地方，以及多次执行同样的操纵。本文后面将研究一些通常用软件完成的操作，经过硬件加速后这些操作可获得极大的性能提高。假如在系统设计中采纳fpga，那么在设计周期的任何时候都可以添加定制的硬件。设计者可以立即编写软件代码，并可在终于定稿之前在硬件部分上运行。此外，还可以实行增量法来打算哪部分代码用硬件而不是软件来实现。fpga供给商所提供的开发工具可

4、实现硬件和软件之间的无缝切换。这些工具可以为规律和中断规律生成hdl代码，并可按照系统配置定制软件库及include文件。2 带一些cisc的risc精简命令集计算(risc)架构的目标之一即是保持命令容易化，以便让命令运行得足够快。这与复杂命令集计算(cisc)架构正巧相反，后者普通不会同样快地执行命令，但每个命令可完成更多处理任务。这两种架构应用得都很普遍，而且各有所长。假如能按照特定的应用将risc的容易和迅速特性与cisc强大的处理能力结合起来，岂不两全其美？其实这正是硬件加速所要做的。加入为某种应用而定制的硬件加速模块可以提高处理能力，并削减代码复杂性和密度，由于硬件模块取代了软件模

5、块。可以这么说，是用硬件来换取速度和容易性。定制命令和硬件外围电路方式有两种硬件加速模块实现方式。其一是定制命令，它几乎可在每一个可配置处理器中实现，这是采纳可配置处理器的主要优点。1所示，定制命令是作为算术规律单元(alu)的扩展而添加的。处理器只知道定制命令就像其它命令一样，包括拥有自己的操作代码。至于c代码，宏可自动生成，从而使得用法该定制命令跟调用函数一样。假如定制命令需要几个时钟周期才干完成，而且要延续调用它，则可以流水线式定制命令来实现。这样可在每个时钟周期产生一个结果，不过开头时有些延迟。硬件加速模块的另一种实现方式是硬件外围电路。在这一方式下，数据不是传递给软件函数，而是写入存

6、储器映射的硬件外围电路中。计算是在cpu之外完成的，因此在外围电路工作的同时cpu可以继续运行代码。其实代替软件算法的只是一个一般的硬件外围电路。与定制命令的另一个不同之处是硬件外围电路可以拜访系统中的其它外围电路或存储器，而无须cpu介入。按照硬件需要做什么、怎么工作以及需要多长时光可以打算采纳是定制命令还是硬件外围电路更合适。对于那些在几个周期内就可完成的操作，定制命令普通更好些，由于它产生的开销要更少。对于外围电路，普通需要执行几个命令来写入控制寄存器、状态寄存器和数据寄存器，而且需要一个命令来读取结果。假如计算需要几个周期，实施外围电路比较好，由于它不会影响cpu流水线。或者，也可以实

7、施前面所述的流水线式定制命令。另一个区分是定制命令需要有限数目的操作数，并返回一个结果。按照处理器命令集架构的不同，操作数也各异。对某些操纵，这样可能显得很棘手。此外，假如需要硬件从存储器或存储器中的其它外围电路读出和写入，则必需采纳硬件外围电路，由于定制命令无法拜访总线。图2：16位crc算法的硬件实现。（optional）3 挑选代码当需要优化代码以满足某些速度要求时，可能要运行一个代码仿制工具，或亲手检查该代码以便了解代码的哪个部分导致系统停滞。固然，这需要认识代码以便知道瓶颈在哪儿。即便找出瓶颈所在，如何优化也是个挑战。有些计划采纳本地字大小的变量、带预先计算值的查找表，以及通用软件算

8、法优化。这些技巧可产生快几倍的执行速度效果。另一种优化c算法的办法是用汇编语言编写。过去这种办法可获得很好的提高，但现今的编译器在优化c算法上已做得很好，因此这种性能的提高是有限的。假如需要显著的性能提高，传统的软件算法优化技巧唯恐是不够的。然而，利用硬件实施的算法比软件实施要强100倍，这不足为奇。那么，如何确定将哪些代码转为硬件实施呢？大可不必将囫囵软件模块转换为硬件，而应挑选那些在硬件中运行得特殊快的操作，比如将数据从一处复制到另一处、大量的数学运算以及任何运行多次的循环。假如一个任务由几个数学运算组成，还可以考虑在硬件中加速囫囵任务。有些时候，仅加速任务中的一个操作就可满足性能要求。4

9、 实例：crc算法的硬件加速因为大量且重复的计算，循环冗余校验(crc)算法或任何“校验和”算法都是硬件加速的不错挑选。下面通过一个crc算法的优化过程来探讨如何实现硬件加速。首先，利用传统的软件技巧来优化算法，然后将其转向定制命令以加速算法。我们将研究不同实现办法的性能比较和折衷。crc算法可用来校验数据在传输过程中是否被破坏。这些算法很流行，由于它们具有很高的检错率，而且不会对数据吞吐量造成太大影响，由于crc校验位被添加进数据信息中。但是，crc算法比一些容易的校验和算法有更大的计算量要求。尽管如此，检错率的提高使得这种算法值得去实施。普通说来，发送端对要被发送的消息执行crc算法，并将

10、crc结果添加进该消息中。消息的接收端对包括crc结果在内的消息执行同样的crc操作。假如接收端的结果与发送端的不同，这解释数据被破坏了。crc算法是一种密集的数学运算，涉及到二元模数除法(modulo-2 division)，即数据消息被16或32位多项式(取决于所用crc标准)除所得的余数。这种操作普通通过异或和移位的迭代过程来实现，当采纳16位多项式时，这相当于每数据字节要执行数百条命令。假如发送数百个字节，计算量就会高达数万条命令。因此，任何优化都会大幅提高吞吐量。代码列表1中的crc函数有两个自变量(消息指针和消息中的字节数)，它可返回所计算的crc值(余数)。尽管该函数的自变量是一

11、些字节，但算要逐位来执行。该算法并不高效，由于全部操作(与、移位、异或和循环控制)都必需逐位地执行。列表1：逐位执行的crc算法c代码。/* the width of the crc calculation and result.* modify the typedef for a 16or32-bit crc standard.*/typedef unsigned char crc;define wh (8 * sizeof(crc)define topbit (1 0; "bit)/* try to divide the current data bit.*/if (remain

12、der &topbit)remainder = (remainder 1）.传统的软件优化图3：带crc外围电路和dma的系统模块暗示图。让我们看一下如何利用传统的软件技巧来优化crc算法。由于crc操作中的一个操作数，即多项式(除数)是常数，字节宽crc操作的全部可能结果都可以预先计算并存储在一个查找表中。这样，通过一个读查找表动作就可让操作按逐个字节执行下去。采纳这一算法时，需要将这些预先计算好的值存储在存储器中。挑选rom或ram都可以，只要在启动crc计算之前将存储器初始化就行。查找表有256个字节，表中每个字节位置包含一个crc结果，共有256种可能的8位消息(与多项式大小无

13、关)。列表2示出了采纳查找表办法的c代码，包括生成查找表crcinit()中数值的代码。crc crctable256;void crcinit(void)crc remainder;/* compute the remainder of each possible dividend.*/for (int dividend = 0; dividend 0; "bit)/* try to divide the current data bit.*/if (remainder &topbit)remainder = (remainder > (width - 8);rema

14、inder = crctabledata (remainder表1：各种规模的数据模块下crc算法测试比较结果。2）.采纳定制命令办法crc算法由延续的异或和移位操作构成，用很少的规律即可在硬件中容易实现。因为这一硬件模块仅需几个周期来计算crc，采纳定制命令来实现crc计算要比采纳外围电路更好。此外，无须涉及系统中任何其它外围电路或存储器。仅需要一个微处理器来支持定制命令即可，普通是指可配置微处理器。当在硬件中实现时，算法应当每次执行16或32位计算，这取决于所采纳的crc标准。假如采纳crc-ccitt标准(16位多项式)，最好每次执行16位计算。假如用法8位微处理器，效率可能不太高，由于

15、装载操作数值及返回crc值需要额外的周期。图2示出了用硬件实现16位crc算法的内核。信号msg(15.0)每次被移入异或/移位硬件一位。列表3示出了在64kb数据模块上计算crc的一些c代码例子。该实例是针对nios嵌入式处理器。列表3：采纳定制命令的crc计算c代码。unsigned short crccompute(unsigned short *data_block, unsigned int nwords)unsigned short* pointer;unsigned short word;/* initialize crc reg to 0xffff*/word = nm_crc

16、 (0xffff, 1); /* nm_crc() is the crc custom instruction */* calculate crc on block of data* nm_crc() is the crc custom instruction*/for (pointer = data_block; pointer 3）.crc外围电路办法假如将crc算法作为硬件外围电路来实现，并利用dma将数据从存储器转移到外围电路，这样还可以进一步提高速度。这种办法将省去处理器为每次计算而装载数据所需要的额外周期。dma可在此外围电路完成前一次crc计算的时钟周期内提供新的数据。图3示出了

17、利用dma、crc外围电路来实现加速的系统模块暗示图。在64kb数据模块上，利用带dma的定制外围电路可获得比逐位计算的纯软件算法快500倍的性能。要知道，随着数据模块规模的增强，用法dma所获得的性能也随之提高。这是由于设置dma仅需很少的开销，设置之后dma运行得特殊快，由于每个周期它都可以传递数据。因此，若惟独少数字节的数据，用dma并不划算。这里所研究的全部采纳crc-ccitt标准(16位多项式)的算法都是在 stratix fpga的nios处理器上实现的。表1示出了各种数据长度的测试比较结果，以及大致的硬件用法状况(fpga中的存储器或规律单元)。可以看出，算法所用的硬件越多，算法速度越快。这是用硬件资源来换取速度。5 fpga的优点当采纳基于fpga的嵌入式系统时，在设计周期之初不必为每个模块做出用硬件还是软件的挑选。假如在设计中间阶段需要一些额外的性能，则可以利用fpga中现有的硬件资源来加速软件代码中的瓶颈部分。因为fpga中的规律单元是可编程的，可针对特定的应用而定制硬件。因此，仅用法所需要的硬件即可，而不必做出任何板级变动(前提是fpga中的规律单元足够用)。设计者不必转换到另一个新的处理器或者编写汇编代码，就可做到这一点。用法带可配置处理器的fpga可获得设计灵便性。设计者可以挑选如何实现软件代码中的每个模块，如用定制命令，或硬件外围电路。此外，还