fpga算法研究

⑴ 在FPGA上快速实现MD5算法的新方法论文

在FPGA上快速实现MD5算法的新方法论文

摘 要 文章介绍了一种在FPGA上快速实现MD5算法的新方法，给出了优化设计的原理、实现的具体方法及其重要模块的设计实现方案。

关键词 MD5；FPGA；Verilog语言；集成电路；关键路径

1 引言

随着电子商务和网络通信的发展，网络信息安全的重要性越来越显着，信息加密、数字签名、数据的完整性认证、身份验证等成为信息安全领域的重要内容。MD5算法本身是为数字签名应用而设计的，随后也应用在信息验证技术当中。作为应用最广泛的安全散列算法，MD5算法的高效实现就成为研究的需要，MD5算法本身可以采用软件实现，但其性能受到处理器件性能的制约不能满足网络通信带宽日益增长的要求，因而通过硬件实现高速MD5 运算就成为需要。

2 MD5算法介绍

MD5 算法可以对任何长度不超过 264二进制位的消息产生128 位的单向散列消息摘要输出， RFC1321 标准中的MD5 算法主要步骤如下：

在一些初始化处理后，MD5以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由四个32位分组组成，将它们级联形成一个128位散列值。

（1）附加填充比特：填充消息使其长度恰好为一个比512位的倍数仅小64位的数。即对报文进行填充使报文的长度(比特数)与448模512同余。填充方法是附一个1在消息后面接所要求的多个比特0。

（2）附加长度值：在其后附上64位的消息长度（填充前）。如果消息长度大于 264，仅使用该长度的低64比特。这样，该域包含的长度值为初始长度模264 的值。

这两步的作用是使消息长度恰好是512位的整数倍（算法的其余部分要求如此），同时确保不同的消息在填充后不相同。

（3）初始化寄存器：四个32位初始化变量为：

它们也被称为链接变量（chaining variable）

（4）进行算法的主循环：这一步是算法的核心，它是一个包含四个大循环的64步函数，四个大循环结构相同，但每次使用的逻辑函数不同，每一个大循环由对512比特的16步操作组成，即每16步为一轮大循环。

每次操作如下(设 Ai+1、Bi+1 、Ci+1 、Di+1 为第 +1个时钟周期时打入寄存器的值)：

以一下是每轮中用到的四个非线性函数（每轮一个）。

常数ti可以如下选择：在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。Wi是512位消息分组中的一个，Si是每次循环移位的次数。对每次而言也是固定的常数。

（5）结果输出：所有64步完成之后，将第64步的输出加到四个初始化变量上作为新的初始化变量，进行下一个512比特分组的运算，直到所有分组处理完毕，单次操作图如下：

图1. MD5算法单步操作图

3 算法优化

由上图可以看到，硬件实现时，MD5算法每一步操作中的关键路径在于B的求取（其他三个变量都是直接传递），这个关键路径包括了四个模 232加法运算、三输入变量的逻辑运算、"两个查找表运算及一个循环左移运算，而在FPGA设计中，加法运算最为耗时，四个加法运算至少需要三个加法器级联完成，加法运算严重制约了整个操作的速度，可见要加快算法运行速度就必须在简化这一关键路径上下工夫，经过观察我们发现，在

中 对每个周期都是已知的常数，是输入的512比特的一个32位分组，这样，在512比特输入初始化完成后，也可看作固定常数，

Ai是第i时钟周期里寄存器D 的值，而 Di的值又是第i-1周期里的Ci-1 ，即Ai 的`值是第i-1周期里Ci-1的值。

若在第i周期设中间寄存器变量 ，并令

那么在第i+1周期，

就可以表示为

操作就可以用下面几个式子代替：

其中， Ai+1没有参与任何运算，因此上式可以接着化简为

这样一来，原来一个周期内需要完成三级加法和相应的组合逻辑，现在只需要完成两级加法和部分组合逻辑就行了，大大提高了算法速度，只要在运算开始时加－个周期的初始化即可，简化后的系统框图如下：

图2. 改进后的单步操作图

4 结果比较

由上文中的算法分析部分不难看出，传统的实现方式关键路径是3级32比特加法器延迟和组合逻辑的延迟，而改进的实现方式减少了一级加法器的延迟，并把组合逻辑的延迟分散到不同路径上，因此，采用改进的实现方式大约可以将速度提高到原来的1.5倍左右。同时，为了实现数据的初始化，需要提前一个周期计算出寄存器A的值，因此整个算法的实现需要65个周期。我们采用 VerilogHDL 描述，选择Altera Stratix II EP2S15F672C5 FBGA芯片，在QuartusII6.0上验证通过。由于在FPGA中，连线延时也很关键，而这部分延时不能像加法延时那样通过预先计算并存储在寄存器中来消除一部分，所以实际的MD5改进算法与传统型相比较，速度的提高约为1.3，资源方面由于只是增加了一个时钟节拍，寄存器数量和组合逻辑并没有增加，所以改进型在资源方面和传统型相当。下表为算法改进前后在资源、频率、流量上的比较。

表1. 改进前后资源比较

5 结束语

由表1可见，改进型MD5算法实现，使用的资源并没有明显增加，但速度的改善十分明显，基本实现了用较少的资源得到较高速率的目标，证明了结构的正确性和合理性。实验结果也说明，这种利用寄存器来减少加法器级联从而减少关键路径的实现方法也可用于一般的FPGA硬件设计中。

参考文献

[1] R.Rivest. The MD5 Message-Digest Algorithm，RFC1321 1992。

[2] Jarvinen K， Tommiska M，Skytta J.Hardware implementation analysis of the MD5 hash algorithm.System Sciences，2005.HICSS’05.Proceedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:298

[3] Bruce Schneier. 应用密码学.北京：机械工业出版社，2000：188～194

[4] William Stallings. 密码编码学与网络安全：原理与实践.北京：电子工业出版社，2001: 216～222。

[5] 夏宇闻.Verilog 数字系统设计教程.航空航天大学出版社，2005

⑵ 如何使用FPGA加速机器学习算法

如何使用FPGA加速机器学习算法
当前，AI因为其CNN(卷积神经网络)算法出色的表现在图像识别领域占有举足轻重的地位。基本的CNN算法需要大量的计算和数据重用，非常适合使用FPGA来实现。上个月，Ralph Wittig(Xilinx CTO Office的卓越工程师) 在2016年OpenPower峰会上发表了约20分钟时长的演讲并讨论了包括清华大学在内的中国各大学研究CNN的一些成果。
在这项研究中出现了一些和CNN算法实现能耗相关的几个有趣的结论：
①限定使用片上Memory;
②使用更小的乘法器;
③进行定点匹配：相对于32位定点或浮点计算，将定点计算结果精度降为16位。如果使用动态量化，8位计算同样能够产生很好的结果。
在演讲中Wittig还提到了CNN相关的两款产品：CAPI-compatible Alpha DataADM-PCIE-8K5 PCIe加速卡和Auviz Systems提供的AuvizDNN(深度神经网络)开发库。
ADM-PCIE-8K5 PCIe加速卡
Alpha DataADM-PCIE-8K5 PCIe加速卡用于X86和IBM Power8/9数据中心和云服务，加速卡基于Xilinx Kintex UltraScale KU115 FPGA，支持Xilinx SDAcess基于OpenCL、C/C++的开发和基于Vivado HLx的HDL、HLS设计流程。

图1 Alpha DataADM-PCIE-8K5 PCIe加速卡

Alpha DataADM-PCIE-8K5 PCIe加速卡片上带32GB DDR4-2400内存(其中16GB含ECC)，双通道SFP+支持双通道10G以太网接入。提供包括高性能PCIe/DMA在内的板级支持包(BSP) 、OpenPOWER架构的CAPI、FPGA参考设计、即插即用的O/S驱动和成熟的API等设计资源。
AuvizDNN开发库
深度学习技术使用大量的已知数据来找出一组权重和偏置值来匹配预期结果。处理被称之为训练，训练的结果是大量的模型，这一事实促使工程师们寻求使用GPU之类的专用硬件来进行训练和分类计算。
随着未来数据量的巨幅增长，机器学习将会搬到云端完成。这样就急需一种既可以加速算法，又不会大规模增加功耗的处理平台，在这种情况下，FPGA开始登场。
随着一些列的先进开发环境投入使用，软件开发工程师将他们的设计在Xilinx FPGA上实现变得更加容易。Auviz Systems开发的AuvizDNN库为用户提供优化的函数接口，用户可以针对不同的应用创建自定义的CNN。这些函数可以方便的通过Xilinx SDAcess这样的集成开发环境调用。在创建对象和数据池后，就会调用函数创建每一个卷积层、然后是致密层，最后是 softmax层

⑶ 学习fpga需要多久多少程度才能搞到图像处理和图像算法

FPGA范围比较广，从编程到制版到调试到生产都可以算到里面。既然你是想搞算法，我就帮你尽量跳过FPGA费时费力不出成绩的底层钻研阶段。
如果你只是想做算法而不是做应用，只需要了解FPGA的优势和实现原理，10-30天学习FPGA基础语法，这部分跟C比较相似应该能很快入门，这时候你差不多就了解FPGA跟CPU的区别和优势了，然后把重点放在算法研究上。根据算法复杂度研究时间不定。
比如图像处理，FPGA的优势在于可以一个时钟周期处理多个点或者矩阵，这时候你的算法就要偏向于怎么让不同点或者矩阵之间的运算尽量独立没有前后相关性。速度上4Ghz的CPU一次处理16个点速度就是64G点每秒，FPGA看资源如果一次可以处理1000点，200MHZ的速度就是200G点每秒，这图像处理速度的优势就出来了。而且CPU可能还要跑系统还有宕机风险，FPGA说多快就多快，稳定高效能长时间运行。
之前我们做4K视频的采集和预处理，FPGA很轻松就实现了。设计的时候最好找个高手听一下你的设计方案，帮忙做一下时序约束和PipeLine规划，这样保证你的算法尽量稳定，或者干脆点你算法完成直接找人给你写代码，你把代码看懂之后再慢慢调参数就行了。
直接根据自己需求买个成品板卡，这样上面的外接器件什么的都有现成example可以使用，比如DDR控制、视频输入输出、引脚约束这之类的，你可以直接用板卡资料，不需要浪费时间去自己调试，专心做算法。

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

首先，利用传统的软件技巧来优化算法，然后将其转向定制指令以加速算法。我们将讨论不同实现方法的性能比较和折衷。
CRC算法可用来校验数据在传输过程中是否被破坏。这些算法很流行，因为它们具有很高的检错率，而且不会对数据吞吐量造成太大影响，因为CRC校验位被添加进数据信息中。但是，CRC算法比一些简单的校验和算法有更大的计算量要求。尽管如此，检错率的提高使得这种算法值得去实施。
一般说来，发送端对要被发送的消息执行CRC算法，并将CRC结果添加进该消息中。消息的接收端对包括CRC结果在内的消息执行同样的CRC操作。如果接收端的结果与发送端的不同，这说明数据被破坏了。
CRC算法是一种密集的数学运算，涉及到二元模数除法(molo-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 molo-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 molo-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 molo-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 const 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 FPGA的Nios处理器上实现的。表1示出了各种数据长度的测试比较结果，以及大致的硬件使用情况(FPGA中的存储器或逻辑单元)。
可以看出，算法所用的硬件越多，算法速度越快。这是用硬件资源来换取速度。

⑸ 有关fpga的图像处理算法

不管什么算法其实就是一些加、减、乘、除法；FPGA是天生的并行结构，它有很多硬件乘法器，所以决定了它是做高速算法运算的最佳选择。不同的FPGA运算速度不同，内部的硬件资源也不同，内部的DSP块也不同。

“怎样在FPGA里用硬件实现图像的算法”推荐你去看一下《现代DSP技术》，它介绍了用FPGA做数字信号处理的系统方法。结合DSPBuilder和Matlab等工具可以轻松完成图像处理算法。用FPGA做图像处理有现成的IPcore可以使用，比如FFT,FIR2D,CIC，CSC,MedianFilter2D，DhromaResmapler等等。其它没有的算法都可以通过工具软件用硬件实现。因为是并行结构其速度一般比DSP等快一些，比如在CYCLONII上做一个1024点16位的定点FFT只需要601个时钟周期。而一个16位的FIR只需要一个时钟.