FPGA實(shí)現(xiàn)算法硬件加速的方法與步驟

當(dāng)設(shè)計(jì)者試圖從算法中獲得最佳性能但軟件方法已無(wú)計(jì)可施時(shí)，可以嘗試通過(guò)硬件/軟件重新劃分來(lái)進(jìn)行加速。FPGA易于實(shí)現(xiàn)軟件模塊和硬件模塊的相互交換，且不必改變處理器或進(jìn)行板級(jí)變動(dòng)。本文闡述如何用FPGA來(lái)實(shí)現(xiàn)算法的硬件加速。

如果想從代碼中獲得最佳性能，方法包括優(yōu)化算法、使用查找表而不是算法、將一切都轉(zhuǎn)換為本地字長(zhǎng)尺寸、使用注冊(cè)變量、解開(kāi)循環(huán)甚至可能采用 匯編代碼。如果所有這些都不奏效，可以轉(zhuǎn)向更快的處理器、采用一個(gè)不同的處理器架構(gòu)，或?qū)⒋a一分為二通過(guò)兩個(gè)處理器并行處理。不過(guò)，如果有一種方法可將 那些對(duì)時(shí)間有嚴(yán)格要求的代碼段轉(zhuǎn)換為能夠以5-100倍速度運(yùn)行的函數(shù)調(diào)用，而且如果這一方法是一種可供軟件開(kāi)發(fā)之用的標(biāo)準(zhǔn)工具，這可信嗎？現(xiàn)在，利用可編程邏輯作為硬件加速的基礎(chǔ)可使這一切都變成現(xiàn)實(shí)。

圖1：帶定制指令的可配置處理器架構(gòu)。

低成本可編程邏輯在嵌入式系統(tǒng)中應(yīng)用得越來(lái)越普遍，這為系統(tǒng)設(shè)計(jì)者提供了一個(gè)無(wú)需對(duì)處理器或架構(gòu)進(jìn)行大的改動(dòng)即可獲得更高性能的可選方案?？删幊踢壿嬁蓪⒂?jì)算密集型功能轉(zhuǎn)換為硬件加速功能。從軟件的角度看，這只是簡(jiǎn)單地將一個(gè)函數(shù)調(diào)用做進(jìn)一個(gè)定制的硬件模塊中，但運(yùn)行速度要比通過(guò)匯編語(yǔ)言優(yōu) 化的相同代碼或?qū)⑺惴ㄞD(zhuǎn)換為查找表要快得多。

1. 硬件加速

首先探討一下什么是硬件加速，以及將算法作為定制指令來(lái)實(shí)現(xiàn)與采用硬件外圍電路的區(qū)別。硬件加速是指利用硬件模塊來(lái)替代軟件算法以充分利用 硬件所固有的快速特性。從軟件的角度看，與硬件加速模塊接口就跟調(diào)用一個(gè)函數(shù)一樣。唯一的區(qū)別在于此函數(shù)駐留在硬件中，對(duì)調(diào)用函數(shù)是透明的。

取決于算法的不同，執(zhí)行時(shí)間最高可加快100倍。硬件在執(zhí)行各種操作時(shí)要快得多，如執(zhí)行復(fù)雜的數(shù)學(xué)功能、將數(shù)據(jù)從一個(gè)地方轉(zhuǎn)移到另一個(gè)地方，以及多次執(zhí)行同樣的操縱。本文后面將討論一些通常用軟件完成的操作，經(jīng)過(guò)硬件加速后這些操作可獲得極大的性能提高。

如果在系統(tǒng)設(shè)計(jì)中采用FPGA，那么在設(shè)計(jì)周期的任何時(shí)候都可以添加定制的硬件。設(shè)計(jì)者可以立刻編寫(xiě)軟件代碼，并可在最終定稿之前在硬件部 分上運(yùn)行。此外，還可以采取增量法來(lái)決定哪部分代碼用硬件而不是軟件來(lái)實(shí)現(xiàn)。FPGA供應(yīng)商所提供的開(kāi)發(fā)工具可實(shí)現(xiàn)硬件和軟件之間的無(wú)縫切換。這些工具可 以為總線邏輯和中斷邏輯生成HDL代碼，并可根據(jù)系統(tǒng)配置定制軟件庫(kù)及include文件。

2. 帶一些CISC的RISC

精簡(jiǎn)指令集計(jì)算(RISC)架構(gòu)的目標(biāo)之一即是保持指令簡(jiǎn)單化，以便讓指令運(yùn)行得足夠快。這與復(fù)雜指令集計(jì)算(CISC)架構(gòu)正好相反，后者一般不會(huì)同樣快地執(zhí)行指令，但每個(gè)指令可完成更多處理任務(wù)。這兩種架構(gòu)應(yīng)用得都很普遍，而且各有所長(zhǎng)。

如果能根據(jù)特定的應(yīng)用將RISC的簡(jiǎn)單和快速特性與CISC強(qiáng)大的處理能力結(jié)合起來(lái)，豈不兩全其美？其實(shí)這正是硬件加速所要做的。加入為某 種應(yīng)用而定制的硬件加速模塊可以提高處理能力，并減少代碼復(fù)雜性和密度，因?yàn)橛布K取代了軟件模塊?？梢赃@么說(shuō)，是用硬件來(lái)?yè)Q取速度和簡(jiǎn)單性。

定制指令和硬件外圍電路方式

有兩種硬件加速模塊實(shí)現(xiàn)方式。其一是定制指令，它幾乎可在每一個(gè)可配置處理器中實(shí)現(xiàn)，這是采用可配置處理器的主要優(yōu)點(diǎn)。如圖1所示，定制指 令是作為算術(shù)邏輯單元(ALU)的擴(kuò)展而添加的。處理器只知道定制指令就像其它指令一樣，包括擁有自己的操作代碼。至于C代碼，宏可自動(dòng)生成，從而使得使 用該定制指令跟調(diào)用函數(shù)一樣。

如果定制指令需要幾個(gè)時(shí)鐘周期才能完成，而且要連續(xù)調(diào)用它，則可以流水線式定制指令來(lái)實(shí)現(xiàn)。這樣可在每個(gè)時(shí)鐘周期產(chǎn)生一個(gè)結(jié)果，不過(guò)開(kāi)始時(shí)有些延遲。

硬件加速模塊的另一種實(shí)現(xiàn)方式是硬件外圍電路。在這一方式下，數(shù)據(jù)不是傳遞給軟件函數(shù)，而是寫(xiě)入存儲(chǔ)器映射的硬件外圍電路中。計(jì)算是在 CPU之外完成的，因此在外圍電路工作的同時(shí)CPU可以繼續(xù)運(yùn)行代碼。其實(shí)代替軟件算法的只是一個(gè)普通的硬件外圍電路。與定制指令的另一個(gè)不同之處是硬件 外圍電路可以訪問(wèn)系統(tǒng)中的其它外圍電路或存儲(chǔ)器，而無(wú)須CPU介入。

根據(jù)硬件需要做什么、怎么工作以及需要多長(zhǎng)時(shí)間可以決定采用是定制指令還是硬件外圍電路更合適。對(duì)于那些在幾個(gè)周期內(nèi)就可完成的操作，定制 指令一般更好些，因?yàn)樗a(chǎn)生的開(kāi)銷(xiāo)要更少。對(duì)于外圍電路，一般需要執(zhí)行幾個(gè)指令來(lái)寫(xiě)入控制寄存器、狀態(tài)寄存器和數(shù)據(jù)寄存器，而且需要一個(gè)指令來(lái)讀取結(jié)果。如果計(jì)算需要幾個(gè)周期，實(shí)施外圍電路比較好，因?yàn)樗粫?huì)影響CPU流水線?；蛘撸部梢詫?shí)施前面所述的流水線式定制指令。

另一個(gè)區(qū)別是定制指令需要有限數(shù)目的操作數(shù)，并返回一個(gè)結(jié)果。根據(jù)處理器指令集架構(gòu)的不同，操作數(shù)也各異。對(duì)某些操縱，這樣可能顯得很麻煩。此外，如果需要硬件從存儲(chǔ)器或存儲(chǔ)器中的其它外圍電路讀出和寫(xiě)入，則必須采用硬件外圍電路，因?yàn)槎ㄖ浦噶顭o(wú)法訪問(wèn)總線。

圖2：16位CRC算法的硬件實(shí)現(xiàn)。（Optional）

3. 選擇代碼

當(dāng)需要優(yōu)化C語(yǔ)言代碼以滿足某些速度要求時(shí)，可能要運(yùn)行一個(gè)代碼仿制工具，或親自檢查該代碼以便了解代碼的哪個(gè)部分導(dǎo)致系統(tǒng)停滯。當(dāng)然，這需要熟悉代碼以便知道瓶頸在哪兒。

即便找出瓶頸所在，如何優(yōu)化也是個(gè)挑戰(zhàn)。有些方案采用本地字大小的變量、帶預(yù)先計(jì)算值的查找表，以及通用軟件算法優(yōu)化。這些技巧可產(chǎn)生快幾 倍的執(zhí)行速度效果。另一種優(yōu)化C算法的方法是用匯編語(yǔ)言編寫(xiě)。過(guò)去這種方法可獲得很好的提高，但現(xiàn)今的編譯器在優(yōu)化C算法上已做得很好，因此這種性能的提 高是有限的。如果需要顯著的性能提高，傳統(tǒng)的軟件算法優(yōu)化技巧恐怕是不夠的。

然而，利用硬件實(shí)施的算法比軟件實(shí)施要強(qiáng)100倍，這不足為奇。那么，如何確定將哪些代碼轉(zhuǎn)為硬件實(shí)施呢？大可不必將整個(gè)軟件模塊轉(zhuǎn)換為硬 件，而應(yīng)選擇那些在硬件中運(yùn)行得特別快的操作，比如將數(shù)據(jù)從一處復(fù)制到另一處、大量的數(shù)學(xué)運(yùn)算以及任何運(yùn)行多次的循環(huán)。如果一個(gè)任務(wù)由幾個(gè)數(shù)學(xué)運(yùn)算組成， 還可以考慮在硬件中加速整個(gè)任務(wù)。有些時(shí)候，僅加速任務(wù)中的一個(gè)操作就可滿足性能要求。

4. 實(shí)例：CRC算法的硬件加速

由于大量且重復(fù)的計(jì)算，循環(huán)冗余校驗(yàn)(CRC)算法或任何“校驗(yàn)和”算法都是硬件加速的不錯(cuò)選擇。下面通過(guò)一個(gè)CRC算法的優(yōu)化過(guò)程來(lái)探討如何實(shí)現(xiàn)硬件加速。

首先，利用傳統(tǒng)的軟件技巧來(lái)優(yōu)化算法，然后將其轉(zhuǎn)向定制指令以加速算法。我們將討論不同實(shí)現(xiàn)方法的性能比較和折衷。

CRC算法可用來(lái)校驗(yàn)數(shù)據(jù)在傳輸過(guò)程中是否被破壞。這些算法很流行，因?yàn)樗鼈兙哂泻芨叩臋z錯(cuò)率，而且不會(huì)對(duì)數(shù)據(jù)吞吐量造成太大影響，因?yàn)?CRC校驗(yàn)位被添加進(jìn)數(shù)據(jù)信息中。但是，CRC算法比一些簡(jiǎn)單的校驗(yàn)和算法有更大的計(jì)算量要求。盡管如此，檢錯(cuò)率的提高使得這種算法值得去實(shí)施。

一般說(shuō)來(lái)，發(fā)送端對(duì)要被發(fā)送的消息執(zhí)行CRC算法，并將CRC結(jié)果添加進(jìn)該消息中。消息的接收端對(duì)包括CRC結(jié)果在內(nèi)的消息執(zhí)行同樣的CRC操作。如果接收端的結(jié)果與發(fā)送端的不同，這說(shuō)明數(shù)據(jù)被破壞了。

CRC算法是一種密集的數(shù)學(xué)運(yùn)算，涉及到二元模數(shù)除法(modulo-2 division)，即數(shù)據(jù)消息被16或32位多項(xiàng)式(取決于所用CRC標(biāo)準(zhǔn))除所得的余數(shù)。這種操作一般通過(guò)異或和移位的迭代過(guò)程來(lái)實(shí)現(xiàn)，當(dāng)采用16位 多項(xiàng)式時(shí)，這相當(dāng)于每數(shù)據(jù)字節(jié)要執(zhí)行數(shù)百條指令。如果發(fā)送數(shù)百個(gè)字節(jié)，計(jì)算量就會(huì)高達(dá)數(shù)萬(wàn)條指令。因此，任何優(yōu)化都會(huì)大幅提高吞吐量。

代碼列表1中的CRC函數(shù)有兩個(gè)自變量(消息指針和消息中的字節(jié)數(shù))，它可返回所計(jì)算的CRC值(余數(shù))。盡管該函數(shù)的自變量是一些字節(jié)，但計(jì)算要逐位來(lái)執(zhí)行。該算法并不高效，因?yàn)樗胁僮?與、移位、異或和循環(huán)控制)都必須逐位地執(zhí)行。

列表1：逐位執(zhí)行的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 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);
}

4.1 傳統(tǒng)的軟件優(yōu)化

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

讓我們看一下如何利用傳統(tǒng)的軟件技巧來(lái)優(yōu)化CRC算法。因?yàn)镃RC操作中的一個(gè)操作數(shù)，即多項(xiàng)式(除數(shù))是常數(shù)，字節(jié)寬CRC操作的所有可能結(jié)果都可以預(yù)先計(jì)算并存儲(chǔ)在一個(gè)查找表中。這樣，通過(guò)一個(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)式大小無(wú)關(guān))。

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

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ǔ)空間來(lái)?yè)Q取速度。該方 法比逐位計(jì)算的方法要快9.9倍，這一提高對(duì)某些應(yīng)用已經(jīng)足夠。如果需要更高的性能，可以嘗試編寫(xiě)匯編代碼或增加查找表容量以擠出更多性能來(lái)。但是，如果 需要20、50甚至500倍的性能提高，就要考慮采用硬件加速來(lái)實(shí)現(xiàn)該算法了。

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

4.2 采用定制指令方法

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

當(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()，可用它來(lái)調(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倍。

4.3 CRC外圍電路方法

如果將CRC算法作為硬件外圍電路來(lái)實(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外圍電路來(lái)實(shí)現(xiàn) 加速的系統(tǒng)模塊示意圖。

在64KB數(shù)據(jù)模塊上，利用帶DMA的定制外圍電路可獲得比逐位計(jì)算的純軟件算法快500倍的性能。要知道，隨著數(shù)據(jù)模塊規(guī)模的增加，使用 DMA所獲得的性能也隨之提高。這是因?yàn)樵O(shè)置DMA僅需很少的開(kāi)銷(xiāo)，設(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ǔ)器或邏輯單元)。

可以看出，算法所用的硬件越多，算法速度越快。這是用硬件資源來(lái)?yè)Q取速度。

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

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

使用帶可配置處理器的FPGA可獲得設(shè)計(jì)靈活性。設(shè)計(jì)者可以選擇如何實(shí)現(xiàn)軟件代碼中的每個(gè)模塊，如用定制指令，或硬件外圍電路。此外，還可以通過(guò)添加定制的硬件而獲取比現(xiàn)成微處理器更好的性能。

另一點(diǎn)要知道的是，F(xiàn)PGA有充裕的資源，可配置處理器系統(tǒng)可以充分利用這一資源。

算法可以用軟件，也可用硬件實(shí)現(xiàn)。出于簡(jiǎn)便和成本考慮，一般利用軟件來(lái)實(shí)現(xiàn)大部分操作，除非需要更高的速度以滿足性能指標(biāo)。軟件可以優(yōu)化，但有時(shí)是不夠的。如果需要更高的速度，利用硬件來(lái)加速算法是一個(gè)不錯(cuò)的選擇。

FPGA使軟件模塊和硬件模塊的相互交換更加簡(jiǎn)便，不必改變處理器或進(jìn)行板級(jí)變動(dòng)。設(shè)計(jì)者可以在速度、硬件邏輯、存儲(chǔ)器、代碼大小和成本之間做出折衷。利用FPGA可以設(shè)計(jì)定制的嵌入式系統(tǒng)，以增加新的功能特性及優(yōu)化性能。

審核編輯：黃飛

?