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

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

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

　　圖1：帶定制指令的可配置處理器架構。

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

　　硬件加速

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

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

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

　　帶一些CISC的RISC

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

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

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

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

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

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

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

　　另一個(gè)區別是定制指令需要有限數目的操作數，并返回一個(gè)結果。根據處理器指令集架構的不同，操作數也各異。對某些操縱，這樣可能顯得很麻煩。此外，如果需要硬件從存儲器或存儲器中的其它外圍電路讀出和寫(xiě)入，則必須采用硬件外圍電路，因為定制指令無(wú)法訪(fǎng)問(wèn)總線(xiàn)。

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

　　選擇代碼

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

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

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

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

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

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

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

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

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

　　代碼列表1中的CRC函數有兩個(gè)自變量(消息指針和消息中的字