Global Sources
電子工程專輯
 
電子工程專輯 > FPGA/PLD
 
 
FPGA/PLD  

使用基於可程式邏輯的硬體方法實現演算法加速

上網時間: 2005年01月16日     打印版  Bookmark and Share  字型大小:  

關鍵字:FPGA  CRC演算法  硬體加速  可配置微處理器 

當設計者試圖從演算法中獲得最佳性能但軟體方法已無計可施時,可以嘗試透過硬體/軟體重新劃分來進行加速。FPGA易於實現軟體模組和硬體模組的相互交換,且不必改變處理器或進行板級變動。本文闡述如何用FPGA來實現演算法的硬體加速

如果想從程式碼中獲得最佳性能,方法包括最佳化演算法、使用查找表而不是演算法、將一切都轉換為本地字長尺寸、使用註冊變量、解開循環甚至可能採用匯編程式碼。如果所有這些都不奏效,可以轉向更快的處理器、採用一個不同的處理器架構,或將程式碼一分為二透過兩個處理器平行處理。不過,如果有一種方法可將那些對時間有嚴格要求的程式碼段轉換為能夠以5-100倍速度執行的函數調用,而且如果這一方法是一種可供軟體開發之用的標準工具,這可信嗎?現在,利用可程式邏輯作為硬體加速的基礎可使這一切都變成現實。

低成本可程式邏輯在嵌入式系統中應用得越來越普遍,這為系統設計者提供了一個無需對處理器或架構進行大的改動即可獲得更高性能的可選方案。可程式邏輯可將運算密集型功能轉換為硬體加速功能。從軟體的角度看,這只是簡單地將一個函數調用做進一個定製的硬體模組中,但執行速度要比透過匯編語言最佳化的相同程式碼或將演算法轉換為查找表要快得多。

圖1:具定製指令的可配置處理器架構。

硬體加速

首先探討一下什麼是硬體加速,以及將演算法作為定製指令來實現與採用硬體周邊電路的區別。硬體加速是指利用硬體模組來替代軟體演算法以充分利用硬體所固有的快速特性。從軟體的角度看,與硬體加速模組介面就跟調用一個函數一樣。唯一的區別在於此函數駐留在硬體中,對調用函數是透明的。

取決於演算法的不同,執行時間最高可加速100倍。硬體在執行各種作業時要快得多,如執行複雜的數學功能、將數據從一個地方轉移到另一個地方,以及多次執行同樣的操縱。本文後面將討論一些通常用軟體完成的作業,經過硬體加速後這些作業可獲得極大的性能提高。

如果在系統設計中採用FPGA,那麼在設計周期的任何時候都可以添加定製的硬體。設計者可以立刻編寫軟體程式碼,並可在最終定稿之前在硬體部份上執行。此外,還可以採取增量法來決定哪部份程式碼用硬體而不是軟體來實現。FPGA供應商所提供的開發工具可實現硬體和軟體之間的無縫切換。這些工具可以為匯流排邏輯和中斷邏輯產生HDL程式碼,並可根據系統配置定製軟體庫及include文件。

帶一些CISC的RISC

精簡指令集運算(RISC)架構的目標之一既是保持指令簡單化,以便讓指令執行得足夠快。這與複雜指令集運算(CISC)架構正好相反,後者一般不會同樣快地執行指令,但每個指令可完成更多處理任務。這兩種架構應用得都很普遍,而且各有所長。

如果能根據特定的應用將RISC的簡單和快速特性與CISC強大的處理能力結合起來,豈不兩全其美?其實這正是硬體加速所要做的。加入為某種應用而定製的硬體加速模組可以提高處理能力,並減少程式碼複雜性和密度,因為硬體模組取代了軟體模組。可以這麼說,是用硬體來換取速度和簡單性。

定製指令和硬體周邊電路方式

有兩種硬體加速模組實現方式。其一是定製指令,它幾乎可在每一個可配置處理器中實現,這是採用可配置處理器的主要優點。如圖1所示,定製指令是作為算術邏輯單元(ALU)的擴展而添加的。處理器只知道定製指令就像其它指令一樣,包括擁有自己的作業程式碼。至於C程式碼,巨集可自動產生,因而使得使用該定製指令跟調用函數一樣。

如果定製指令需要幾個時脈周期才能完成,而且要連續調用它,則可以管線式定製指令來實現。這樣可在每個時脈周期產生一個結果,不過開始時有些延遲。

硬體加速模組的另一種實現方式是硬體周邊電路。在這一方式下,數據不是傳遞給軟體函數,而是寫入記憶體映射的硬體周邊電路中。運算是在CPU之外完成的,因此在周邊電路工作的同時CPU可以繼續執行程式碼。其實代替軟體演算法的只是一個普通的硬體周邊電路。與定製指令的另一個不同之處是硬體周邊電路可以存取系統中的其它周邊電路或記憶體,而無須CPU介入。

根據硬體需要做什麼、怎麼工作以及需要多長時間可以決定採用是定製指令還是硬體周邊電路更合適。對於那些在幾個周期內就可完成的作業,定製指令一般更好些,因為它產生的開銷要更少。對於周邊電路,一般需要執行幾個指令來寫入控制暫存器、狀態暫存器和數據暫存器,而且需要一個指令來讀取結果。如果運算需要幾個周期,實施周邊電路比較好,因為它不會影響CPU管線。或者,也可以實施前面所述的管線式定製指令。

另一個區別是定製指令需要有限數目的作業數,並返回一個結果。根據處理器指令集架構的不同,作業數也各異。對某些操縱,這樣可能顯得很麻煩。此外,如果需要硬體從記憶體或記憶體中的其它周邊電路讀出和寫入,則必須採用硬體周邊電路,因為定製指令無法存取匯流排。

選擇程式碼

當需要最佳化C語言程式碼以滿足某些速度要求時,可能要執行一個程式碼解析(code profiler)工具,或親自檢查該程式碼以便了解程式碼的哪個部份導致系統停滯。當然,這需要熟悉程式碼以便知道瓶頸在哪兒。

即便找出瓶頸所在,如何最佳化也是個挑戰。有些方案採用本地字大小的變量、帶預先運算值的查找表,以及通用軟體演算法最佳化。這些技巧可產生快幾倍的執行速度效果。另一種最佳化C演算法的方法是用匯編語言編寫。過去這種方法可獲得很好的提高,但目前的編譯器在最佳化C演算法上已做得很好,因此這種性能的提高是有限的。如果需要顯著的性能提高,傳統的軟體演算法最佳化技巧恐怕是不夠的。

然而,利用硬體實現的演算法比軟體實現強100倍,這不足為奇。那麼,如何確定將哪些程式碼轉為硬體實現呢?大可不必將整個軟體模組轉換為硬體,而應選擇那些在硬體中執行得特別快的作業,如將數據從一處複製到另一處、大量的數學運算以及任何執行多次的循環。如果一個任務由幾個數學運算組成,還可以考慮在硬體中加速整個任務。有些時候,僅加速任務中的一個作業就可滿足性能要求。

圖2:16位元CRC演算法的硬體實現。(Optional)

實例:CRC演算法的硬體加速

由於大量且重覆的運算,循環冗餘校驗(CRC)演算法或任何‘校驗和’演算法都是硬體加速的不錯選擇。下面透過一個CRC演算法的最佳化過程來探討如何實現硬體加速。

首先,利用傳統的軟體技巧來最佳化演算法,然後將其轉向定製指令以加速演算法。我們將討論不同實現方法的性能比較和折衷。

CRC演算法可用來校驗數據在傳輸過程中是否被破壞。這些演算法很流行,因為它們具有很高的檢錯率,而且不會對數據吞吐量造成太大影響,因為CRC校驗位元被添加進數據資訊中。但是,CRC演算法比一些簡單的校驗和演算法有更大的運算量要求。儘管如此,檢錯率的提高使得這種演算法值得去實施。

一般說來,發送端對要被發送的消息執行CRC演算法,並將CRC結果添加進該消息中。消息的接收端對包括CRC結果在內的消息執行同樣的CRC作業。如果接收端的結果與發送端的不同,這說明數據被破壞了。

CRC演算法是一種密集的數學運算,涉及到二元類比數位除法(modulo-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 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.傳統的軟體最佳化

讓我們看一下如何利用傳統的軟體技巧來最佳化CRC演算法。因為CRC作業中的一個作業數,即多項式(除數)是常數,位元組寬CRC作業的所有可能結果都可以預先運算並儲存在一個查找表中。這樣,透過一個讀查找表動作就可讓作業按逐個位元組執行下去。

採用這一演算法時,需要將這些預先運算好的值儲存在記憶體中。選擇ROM或RAM都可以,只要在啟動CRC運算之前將記憶體初始化就行。查找表有256個位元組,表中每個位元組位置包含一個CRC結果,共有256種可能的8位元消息(與多項式大小無關)。

圖3:具CRC周邊電路和DMA的系統模組示意圖。

列表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() */

整個運算減少為一個循環,每位元組(不是每位元)有兩個異或、兩個移位作業和兩個裝載指令。基本上,這?是用查找表的儲存空間來換取速度。該方法比逐位元運算的方法要快9.9倍,這一提高對某些應用已經足夠。如果需要更高的性能,可以嘗試編寫匯編程式碼或增加查找表容量以擠出更多性能來。但是,如果需要提升20、50甚至500倍的性能,就要考慮採用硬體加速來實現該演算法了。

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(),可用它來調用定製指令。

表1:各種規模的數據模組下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的優點

當採用基於FPGA的嵌入式系統時,在設計周期之初不必為每個模組做出用硬體還是軟體的選擇。如果在設計中間階段需要一些額外的性能,則可以利用FPGA中現有的硬體資源來加速軟體程式碼中的瓶頸部份。由於FPGA中的邏輯單元是可程式的,可針對特定的應用而定製硬體。因此,僅使用所需要的硬體即可,而不必做出任何板級變動(前提是FPGA中的邏輯單元足夠用)。設計者不必轉換到另一個新的處理器或者編寫匯編程式碼,就可做到這一點。

使用帶可配置處理器的FPGA可獲得設計靈活性。設計者可以選擇如何實現軟體程式碼中的每個模組,如用定製指令,或硬體周邊電路。此外,還可以透過添加定製的硬體而獲取比現成微處理器更好的性能。

另一點要知道的是,FPGA有充裕的資源,可配置處理器系統可以充分利用這一資源。

演算法可以用軟體,也可用硬體實現。出於簡便和成本考慮,一般利用軟體來實現大部份作業,除非需要更高的速度以滿足性能指標。軟體可以最佳化,但有時是不夠的。如果需要更高的速度,利用硬體來加速演算法是一個不錯的選擇。

FPGA使軟體模組和硬體模組的相互交換更加簡便,不必改變處理器或進行板級變動。設計者可以在速度、硬體邏輯、記憶體、程式碼大小和成本之間做出折衷。利用FPGA可以設計定製的嵌入式系統,以增加新的功能特性及最佳化性能。

作者:Lara Simsic


高級嵌入式應用工程師


Email:lsimsic@altera.com


Altera公司





投票數:   加入我的最愛
我來評論 - 使用基於可程式邏輯的硬體方法實現演算...
評論:  
*  您還能輸入[0]個字
*驗證碼:
 
論壇熱門主題 熱門下載
 •   將邁入40歲的你...存款多少了  •  深入電容觸控技術就從這個問題開始
 •  我有一個數位電源的專利...  •  磷酸鋰鐵電池一問
 •   關於設備商公司的工程師(廠商)薪資前景  •  計算諧振轉換器的同步整流MOSFET功耗損失
 •   Touch sensor & MEMS controller  •  針對智慧電表PLC通訊應用的線路驅動器
 •   下週 深圳 llC 2012 關於PCB免費工具的研討會  •  邏輯閘的應用


EE人生人氣排行
 
返回頁首