如何用FPGA實(shí)現算法的硬件加速
加入技術(shù)交流群
列表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 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 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.傳統的軟件優(yōu)化
圖3：帶CRC外圍電路和DMA的系統模塊示意圖。
讓我們看一下如何利用傳統的軟件技巧來(lái)優(yōu)化CRC算法。因為CRC操作中的一個(gè)操作數，即多項式(除數)是常數，字節寬CRC操作的所有可能結果都可以預先計算并存儲在一個(gè)查找表中。這樣，通過(guò)一個(gè)讀查找表動(dòng)作就可讓操作按逐個(gè)字節執行下去。
采用這一算法時(shí)，需要將這些預先計算好的值存儲在存儲器中。選擇ROM或RAM都可以，只要在啟動(dòng)CRC計算之前將存儲器初始化就行。查找表有256個(gè)字節，表中每個(gè)字節位置包含一個(gè)CRC結果，共有256種可能的8位消息(與多項式大小無(wú)關(guān))。
列表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 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() */
整個(gè)計算減少為一個(gè)循環(huán)，每字節(不是每位)有兩個(gè)異或、兩個(gè)移位操作和兩個(gè)裝載指令?；旧?，這里是用查找表的存儲空間來(lái)?yè)Q取速度。該方法比逐位計算的方法要快9.9倍，這一提高對某些應用已經(jīng)足夠。如果需要更高的性能，可以嘗試編寫(xiě)匯編代碼或增加查找表容量以擠出更多性能來(lái)。但是，如果需要20、50甚至500倍的性能提高，就要考慮采用硬件加速來(lái)實(shí)現該算法了。
表1：各種規模的數據模塊下CRC算法測試比較結果。
2.采用定制指令方法
CRC算法由連續的異或和移位操作構成，用很少的邏輯即可在硬件中簡(jiǎn)單實(shí)現。由于這一硬件模塊僅需幾個(gè)周期來(lái)計算CRC，采用定制指令來(lái)實(shí)現CRC計算要比采用外圍電路更好。此外，無(wú)須涉及系統中任何其它外圍電路或存儲器。僅需要一個(gè)微處理器來(lái)支持定制指令即可，一般是指可配置微處理器。
當在硬件中實(shí)現時(shí)，算法應該每次執行16或32位計算，這取決于所采用的CRC標準。如果采用CRC-CCITT標準(16位多項式)，最好每次執行16位計算。如果使用8位微處理器，效率可能不太高，因為裝載操作數值及返回CRC值需要額外的周期。圖2示出了用硬件實(shí)現16位CRC算法的內核。
信號msg(15..0)每次被移入異或/移位硬件一位。列表3示出了在64KB數據模塊上計算CRC的一些C代碼例子。該實(shí)例是針對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);
}
采用定制指令時(shí)，用于計算CRC值的代碼是一個(gè)函數調用，或宏。當針對Nios處理器實(shí)現定制指令時(shí)，系統構建工具會(huì )生成一個(gè)宏。在本例中為nm_crc()，可用它來(lái)調用定制指令。
在啟動(dòng)CRC計算之前，定制指令內的CRC寄存器需要先初始化。裝載初始值是CRC標準的一部分，而且每種CRC標準都不一樣。接著(zhù)，循環(huán)將為數據模塊中的每16位數據調用一次CRC定制指令。這種定制指令實(shí)現方式要比逐位實(shí)現的方法快27倍。
3.CRC外圍電路方法
如果將CRC算法作為硬件外圍電路來(lái)實(shí)現，并利用DMA將數據從存儲器轉移到外圍電路，這樣還可以進(jìn)一步提高速度。這種方法將省去處理器為每次計算而裝載數據所需要的額外周期。DMA可在此外圍電路完成前一次CRC計算的時(shí)鐘周期內提供新的數據。圖3示出了利用DMA、CRC外圍電路來(lái)實(shí)現加速的系統模塊示意圖。
在64KB數據模塊上，利用帶DMA的定制外圍電路可獲得比逐位計算的純軟件算法快500倍的性能。要知道，隨著(zhù)數據模塊規模的增加，使用DMA所獲得的性能也隨之提高。這是因為設置DMA僅需很少的開(kāi)銷(xiāo)，設置之后DMA運行得特別快，因為每個(gè)周期它都可以傳遞數據。因此，若只有少數字節的數據，用DMA并不劃算。
這里所討論的所有采用CRC-CCITT標準(16位多項式)的算法都是在A(yíng)ltera Stratix FPGA的Nios處理器上實(shí)現的。表1示出了各種數據長(cháng)度的測試比較結果，以及大致的硬件使用情況(FPGA中的存儲器或邏輯單元)。
可以看出，算法所用的硬件越多，算法速度越快。這是用硬件資源來(lái)?yè)Q取速度。
FPGA的優(yōu)點(diǎn)
當采用基于FPGA的嵌入式系統時(shí)，在設計周期之初不必為每個(gè)模塊做出用硬件還是軟件的選擇。如果在設計中間階段需要一些額外的性能，則可以利用FPGA中現有的硬件資源來(lái)加速軟件代碼中的瓶頸部分。由于FPGA中的邏輯單元是可編程的，可針對特定的應用而定制硬件。因此，僅使用所需要的硬件即可，而不必做出任何板級變動(dòng)(前提是FPGA中的邏輯單元足夠用)。設計者不必轉換到
fpga相關(guān)文章:fpga是什么
評論