fpga實現演算法

Ⅰ fpga加速可以用在哪些演算法上

基本上所有演算法都是可以用FPGA來實現的，只是有些演算法基本上是串列的，用FPGA來實現，體現不出速度優勢。

Ⅱ FPGA實現排序有什麼常用的演算法嗎

排序之前，必須先對待排序的數據特性有所了解，根據其不同的特點，選擇不同的演算法。由於排序演算法都不是特別難，FPGA實現不會是問題所在，但數據量很大又要求排序速度很快的情況下，主要是簡化演算法。

Ⅲ 為什麼在FPGA實現需要演算法定點化

用FPGA實現演算法，簡單理解就像用C語言實現演算法一樣。不過FPGA用硬體描述語言，如verilog
等。可以根據演算法先用C實現，然後再用verilog實現。C和verilog有種一一對應的關系。綜合之後有需要可以進行布局，約束和優化等。因為FPGA可以並行執行，所以實現演算法要比CPU類型的器件（如DSP、MCU等）有優勢。

Ⅳ 如何用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上快速實現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的演算法實現與C的演算法有一定關聯 但有區別 有些黃金演算法在硬體語言描述時很費力，不一定好用 也只有理論聯系實踐，從實踐中來到實踐中去，