如何用FPGA實(shí)現(xiàn)算法的硬件加速

　　列表1：逐位執(zhí)行的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.傳統(tǒng)的軟件優(yōu)化

　　圖3：帶CRC外圍電路和DMA的系統(tǒng)模塊示意圖。

　　讓我們看一下如何利用傳統(tǒng)的軟件技巧來優(yōu)化CRC算法。因?yàn)镃RC操作中的一個(gè)操作數(shù)，即多項(xiàng)式(除數(shù))是常數(shù)，字節(jié)寬CRC操作的所有可能結(jié)果都可以預(yù)先計(jì)算并存儲(chǔ)在一個(gè)查找表中。這樣，通過一個(gè)讀查找表動(dòng)作就可讓操作按逐個(gè)字節(jié)執(zhí)行下去。

　　采用這一算法時(shí)，需要將這些預(yù)先計(jì)算好的值存儲(chǔ)在存儲(chǔ)器中。選擇ROM或RAM都可以，只要在啟動(dòng)CRC計(jì)算之前將存儲(chǔ)器初始化就行。查找表有256個(gè)字節(jié)，表中每個(gè)字節(jié)位置包含一個(gè)CRC結(jié)果，共有256種可能的8位消息(與多項(xiàng)式大小無關(guān))。

　　列表2示出了采用查找表方法的C代碼，包括生成查找表crcInit()中數(shù)值的代碼。

　　列表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è)計(jì)算減少為一個(gè)循環(huán)，每字節(jié)(不是每位)有兩個(gè)異或、兩個(gè)移位操作和兩個(gè)裝載指令?；旧希@里是用查找表的存儲(chǔ)空間來換取速度。該方法比逐位計(jì)算的方法要快9.9倍，這一提高對(duì)某些應(yīng)用已經(jīng)足夠。如果需要更高的性能，可以嘗試編寫匯編代碼或增加查找表容量以擠出更多性能來。但是，如果需要20、50甚至500倍的性能提高，就要考慮采用硬件加速來實(shí)現(xiàn)該算法了。

　　表1：各種規(guī)模的數(shù)據(jù)模塊下CRC算法測(cè)試比較結(jié)果。

　　2.采用定制指令方法

　　CRC算法由連續(xù)的異或和移位操作構(gòu)成，用很少的邏輯即可在硬件中簡(jiǎn)單實(shí)現(xiàn)。由于這一硬件模塊僅需幾個(gè)周期來計(jì)算CRC，采用定制指令來實(shí)現(xiàn)CRC計(jì)算要比采用外圍電路更好。此外，無須涉及系統(tǒng)中任何其它外圍電路或存儲(chǔ)器。僅需要一個(gè)微處理器來支持定制指令即可，一般是指可配置微處理器。

　　當(dāng)在硬件中實(shí)現(xiàn)時(shí)，算法應(yīng)該每次執(zhí)行16或32位計(jì)算，這取決于所采用的CRC標(biāo)準(zhǔn)。如果采用CRC-CCITT標(biāo)準(zhǔn)(16位多項(xiàng)式)，最好每次執(zhí)行16位計(jì)算。如果使用8位微處理器，效率可能不太高，因?yàn)檠b載操作數(shù)值及返回CRC值需要額外的周期。圖2示出了用硬件實(shí)現(xiàn)16位CRC算法的內(nèi)核。

　　信號(hào)msg(15..0)每次被移入異或/移位硬件一位。列表3示出了在64KB數(shù)據(jù)模塊上計(jì)算CRC的一些C代碼例子。該實(shí)例是針對(duì)Nios嵌入式處理器。

　　列表3：采用定制指令的CRC計(jì)算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í)，用于計(jì)算CRC值的代碼是一個(gè)函數(shù)調(diào)用，或宏。當(dāng)針對(duì)Nios處理器實(shí)現(xiàn)定制指令時(shí)，系統(tǒng)構(gòu)建工具會(huì)生成一個(gè)宏。在本例中為nm_crc()，可用它來調(diào)用定制指令。

　　在啟動(dòng)CRC計(jì)算之前，定制指令內(nèi)的CRC寄存器需要先初始化。裝載初始值是CRC標(biāo)準(zhǔn)的一部分，而且每種CRC標(biāo)準(zhǔn)都不一樣。接著，循環(huán)將為數(shù)據(jù)模塊中的每16位數(shù)據(jù)調(diào)用一次CRC定制指令。這種定制指令實(shí)現(xiàn)方式要比逐位實(shí)現(xiàn)的方法快27倍。

　　3.CRC外圍電路方法

　　如果將CRC算法作為硬件外圍電路來實(shí)現(xiàn)，并利用DMA將數(shù)據(jù)從存儲(chǔ)器轉(zhuǎn)移到外圍電路，這樣還可以進(jìn)一步提高速度。這種方法將省去處理器為每次計(jì)算而裝載數(shù)據(jù)所需要的額外周期。DMA可在此外圍電路完成前一次CRC計(jì)算的時(shí)鐘周期內(nèi)提供新的數(shù)據(jù)。圖3示出了利用DMA、CRC外圍電路來實(shí)現(xiàn)加速的系統(tǒng)模塊示意圖。

　　在64KB數(shù)據(jù)模塊上，利用帶DMA的定制外圍電路可獲得比逐位計(jì)算的純軟件算法快500倍的性能。要知道，隨著數(shù)據(jù)模塊規(guī)模的增加，使用DMA所獲得的性能也隨之提高。這是因?yàn)樵O(shè)置DMA僅需很少的開銷，設(shè)置之后DMA運(yùn)行得特別快，因?yàn)槊總€(gè)周期它都可以傳遞數(shù)據(jù)。因此，若只有少數(shù)字節(jié)的數(shù)據(jù)，用DMA并不劃算。

　　這里所討論的所有采用CRC-CCITT標(biāo)準(zhǔn)(16位多項(xiàng)式)的算法都是在Altera Stratix FPGA的Nios處理器上實(shí)現(xiàn)的。表1示出了各種數(shù)據(jù)長(zhǎng)度的測(cè)試比較結(jié)果，以及大致的硬件使用情況(FPGA中的存儲(chǔ)器或邏輯單元)。

　　可以看出，算法所用的硬件越多，算法速度越快。這是用硬件資源來換取速度。

　　FPGA的優(yōu)點(diǎn)

　　當(dāng)采用基于FPGA的嵌入式系統(tǒng)時(shí)，在設(shè)計(jì)周期之初不必為每個(gè)模塊做出用硬件還是軟件的選擇。如果在設(shè)計(jì)中間階段需要一些額外的性能，則可以利用FPGA中現(xiàn)有的硬件資源來加速軟件代碼中的瓶頸部分。由于FPGA中的邏輯單元是可編程的，可針對(duì)特定的應(yīng)用而定制硬件。因此，僅使用所需要的硬件即可，而不必做出任何板級(jí)變動(dòng)(前提是FPGA中的邏輯單元足夠用)。設(shè)計(jì)者不必轉(zhuǎn)換到