关 闭

新闻中心

EEPW首页 > 工控自动化 > 设计应用 > 如何用FPGA实现算法的硬件加速

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

作者:时间:2008-04-24来源:网络收藏
节数),它可返回所计算的值(余数)。尽管该函数的自变量是一些字节,但计算要逐位来执行。该算法并不高效,因为所有操作(与、移位、异或和循环控制)都必须逐位地执行。

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

  /*

  * The width of the calculation and result.

  * Modify the for a 16or32-bit CRC standard.

  */

   unsigned char crc;

  #define WIDTH (8 * sizeof(crc))

  #define TOPBIT (1 (WIDTH - 1))

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

  {

  crc remainder = 0;

  /*

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

  */

  for (int byte = 0; byte nBytes; ++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操作的所有可能结果都可以预先计算并存储在一个中。这样,通过一个读动作就可让操作按逐个字节执行下去。

  采用这一算法时,需要将这些预先计算好的值存储在存储器中。选择ROM或RAM都可以,只要在启动CRC计算之前将存储器初始化就行。有256个字节,表中每个字节位置包含一个CRC结果,共有256种可能的8位消息(与多项式大小无关)。

  列表2示出了采用查找表方法的C代码,包括生成查找表crcInit()中数值的代码。

  列表2:采用查找表方法的CRC算法C代码。

  crc crcTable[256];

  void crcInit(void)

  {

  crc remainder;

  /*

  * Compute the remainder of each possible dividend.

  */

  for (int dividend = 0; dividend 256; ++dividend)

  {

  /*

  * Start with the dividend followed by zeros.

  */

  remainder = dividend (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);

  }

  }

  /*

  * Store the result into the table.

  */

  crcTable[dividend] = remainder;

  }

  } /* crcInit() */

  crc crcFast(unsigned char message[], int nBytes)

  {

  unsigned char data;

  crc remainder = 0;

  /*

  * Divide the message by the polynomial, a byte at a time.

  */

  for (int byte = 0; byte nBytes; ++byte)

  {

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

  remainder = crcTable[data] ^ (remainder 8);

  }

  /*

  * The final remainder is the CRC.

  */

  return (remainder);

  } /* crcFast() */

  整个计算减少为一个循环,每字节(不是每位)有两个异或、两个移位操作和两个装载指令。基本上,这里是用查找表的存储空间来换取速度。该方法比逐位计算的方法要快9.9倍,这一提高对某些应用已经足够。如果需要更高的性能,可以尝试编写汇编代码或增加查找表容量以挤出更多性能来。但是,如果需要20、50甚至500倍的性能提高,就要考虑采用来实现该算法了。

  

  

  表1:各种规模的数据模块下CRC算法测试比较结果。

  2.采用定制指令方法

  CRC算法由连续的异或和移位操作构成,用很少的逻辑即可在硬件中简单实现。由于这一硬件模块仅需几个周期来计算CRC,采用定制指令来实现CRC计算要比采用外围电路更好。此外,无须涉及系统中任何其它外围电路或存储器。仅需要一个微处理器来支持定制指令即可,一般是指可配置微处理器。

  当在硬件中实现时,算法应该每次执行16或32位计算,这取决于所采用的CRC标准。如果采用CRC-CCITT标准(16位多项式),最好每次执行16位计算。如果使用8位微处理器,效率可能不太高,因为装载操作数值及返回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 (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 (data_block + nWords); pointer ++)

  word = nm_crc(*pointer, 0) return (word);

  }

  int main(void)

  {

  #define data_block_begin (na_onchip_memory)

  #define data_block_end (na_onchip_memory + 0xffff)

  unsigned short crc_result;

  unsigned int data_block_length = (unsigned short *)data_block_end - (unsigned short

  *)data_block_begin + 1;

  crc_result = crcCompute((unsigned short *)data_block_begin, data_block_length);

  }

  采用定制指令时,用于计算CRC值的代码是一个函数调用,或宏。当针对Nios处理器实现定制指令时,系统构建工具会生成一个宏。在本例中为nm_crc(),可用它来调用定制指令。

  在启动CRC计算之前,定制指令内的CRC寄存器需要先初始化。装载初始值是CRC标准的一部分,而且每种CRC标准都不一样。接着,循环将为数据模块中的每16位数据调用一次CRC定制指令。这种定制指令实现方式要比逐位实现的方法快27倍。

  3.CRC外围电路方法

  如果将CRC算法作为硬件外围电路来实现,并利用DMA将数据从存储器转移到外围电路,这样还可以进一步提高速度。这种方法将省去处理器为每次计算而装载数据所需要的额外周期。DMA可在此外围电路完成前一次CRC计算的时钟周期内提供新的数据。图3示出了利用DMA、CRC外围电路来实现加速的系统模块示意图。

  在64KB数据模块上,利用带DMA的定制外围电路可获得比逐位计算的纯软件算法快500倍的性能。要知道,随着数据模块规模的增加,使用DMA所获得的性能也随之提高。这是因为设置DMA仅需很少的开销,设置之后DMA运行得特别快,因为每个周期它都可以传递数据。因此,若只有少数字节的数据,用DMA并不划算。

  这里所讨论的所有采用CRC-CCITT标准(16位多项式)的算法都是在Altera Stratix 的Nios处理器上实现的。表1示出了各种数据长度的测试比较结果,以及大致的硬件使用情况(中的存储器或逻辑单元)。

  可以看出,算法所用的硬件越多,算法速度越快。这是用硬件资源来换取速度。

  的优点

  当采用基于FPGA的嵌入式系统时,在设计周期之初不必为每个模块做出用硬件还是软件的选择。如果在设计中间阶段需要一些额外的性能,则可以利用FPGA中现有的硬件资源来加速软件代码中的瓶颈部分。由于FPGA中的逻辑单元是可编程的,可针对特定的应用而定制硬件。因此,仅使用所需要的硬件即可,而不必做出任何板级变动(前提是FPGA中的逻辑单元足够用)。设计者不必转换到

fpga相关文章:fpga是什么




评论


相关推荐

技术专区

关闭