并行循環(huán)冗余校驗算法

作者：劉歡，來源：網(wǎng)絡(luò)交換FPGA 微信公眾號

另外，F(xiàn)PGA LUT可編程的內(nèi)容也可以參考本公眾號之前的文章《【重磅干貨】手把手教你動態(tài)編輯Xilinx FPGA內(nèi)LUT內(nèi)容》。

循環(huán)冗余碼校驗（CRC）是一種眾所周知的錯誤檢測代碼，已廣泛用于以太網(wǎng)，PCIe和其他傳輸協(xié)議中?，F(xiàn)有的基于FPGA的實現(xiàn)解決方案在高性能場景中會遇到資源過度利用的問題。填充零問題和可編程性的引入進一步加劇了這個問題。在本文中，提出了stride-by-5算法，以實現(xiàn)FPGA資源的最佳利用。提出了pipelining go back算法來解決填充零問題。提出了使用HWICAP進行重編程的方法，以實現(xiàn)資源占用少且恒定的可編程性。實驗結(jié)果表明，所提出的非分段架構(gòu)的資源利用率與兩種基于FPGA的最新CRC實現(xiàn)相比，降低80.7％-87.5％和25.1％-46.2%，并且所提出的分段架構(gòu)具有比兩種最新狀態(tài)更低的資源利用率，分別降低了81.7％-85.9％和2.9％-20.8％藝術(shù)建筑。此外，保證了吞吐量和可編程性。源代碼已在GitHub開源。

1. 引言

“在硬件加速計算時代，識別并卸載通用的抽象和原語，而不是單獨的算法和協(xié)議?！?/p>

隨著網(wǎng)絡(luò)吞吐量的不斷增加，越來越多的數(shù)據(jù)包處理任務(wù)被轉(zhuǎn)移到基于現(xiàn)場可編程門陣列的智能網(wǎng)卡上，包括循環(huán)冗余校驗的生成和驗證。400G等技術(shù)和即將到來的多太比特以太網(wǎng)要求更快的CRC計算［5］，而基于FPGAs的高性能CRC計算的實現(xiàn)必須滿足三個要求：1）降低并行化成本。Dennard縮放［2］的結(jié)束導(dǎo)致了提高集成電路頻率的瓶頸，更高的吞吐量意味著芯片中更寬的總線。4切片和8切片算法是在［3］中提出的并行處理算法，適用于CPU，但不適用于FPGAs ［4］。2）解決補零問題。并行化意味著事務(wù)的最后一個字由有效字節(jié)和填充零組成。填充零的數(shù)量是不確定的，并且使用完整的最終字的循環(huán)冗余校驗計算將導(dǎo)致錯誤的結(jié)果，這被稱為填充零問題。［5］說明解決這個問題的最新方案。最后一個字對應(yīng)的表是以流水線的方式組織的，每個流水線步驟對應(yīng)于一個二叉查找樹層。介紹了一種O（n）資源利用方式。3）保持可編程性。循環(huán)冗余校驗算法的可編程實現(xiàn)可以實現(xiàn)更好的可重用性；因此，無需修改電路即可支持廣泛的應(yīng)用。需求可以在iSCSI ［6］和P4 ［7］找到。使用特定的電路架構(gòu)來保證可編程性［8］，但不適用于FPGAs。［4］是適用于FPGAs的最先進的方案，但它需要復(fù)雜的配置電路，導(dǎo)致資源利用率隨著總線寬度的增加而大幅提高。

上述三個要求導(dǎo)致了可觀的資源利用率。盡管slicing［3］ ［4］、aggressive strides、多個流的同時處理［5］以及支持循環(huán)冗余校驗加速的許多其他原則是眾所周知的，但它們不能同時實現(xiàn)低成本、高性能和可編程性。采用英特爾循環(huán)冗余校驗指令［9］的多核多插槽系統(tǒng)可以實現(xiàn)高吞吐量，但在數(shù)據(jù)包處理應(yīng)用中會面臨高延遲和高功耗的問題。簡單地說，提出了兩種算法和一種對應(yīng)于這三種要求的方法，以在保證吞吐量和可編程性的情況下降低資源利用率。首先，提出了stride-by-5算法，與slicing-by-4和slicing-by-8算法相比，該算法的資源利用率降低了79.69%-79.98%。其次，提出了pipelining go back算法來解決填充零問題，這將引入一個O （log2 n）資源利用率。最后，硬件內(nèi)部配置訪問端口（HWICAP）用于實現(xiàn)動態(tài)可編程性，無論總線寬度如何，它都可以實現(xiàn)小而恒定的資源利用率。

本文的其余部分組織如下。第二節(jié)介紹了一些基礎(chǔ)知識。第三節(jié)討論了系統(tǒng)架構(gòu)和三個創(chuàng)新。第四節(jié)顯示了綜合結(jié)果。第五節(jié)是本文的結(jié)尾。

2. 基礎(chǔ)知識

2.1 并行循環(huán)冗余校驗算法

并行循環(huán)冗余校驗算法可以同時處理多個數(shù)據(jù)輸入位［10］。并行處理的位數(shù)設(shè)為，這也是本文剩余部分中內(nèi)部總線的寬度。并行輸入數(shù)據(jù)為

。在Bn進入之前，循環(huán)冗余校驗寄存器的值為Ck。Cn+k和Ck的關(guān)系是：

3. 設(shè)計思路

3.1 非分段系統(tǒng)架構(gòu)

所提出的非分段系統(tǒng)架構(gòu)如圖1所示。在非分段系統(tǒng)架構(gòu)中，單個字中應(yīng)該有一個幀，分段系統(tǒng)架構(gòu)可以同時處理多個幀［13］。區(qū)域1和2對應(yīng)于（1）中WlnBn的計算。區(qū)域1消耗大部分查找表，消耗的查找表數(shù)量線性地取決于Wln的大小。在第二節(jié)中討論的stride-by-5算法是為了減少區(qū)域1的LUT消耗而提出的。區(qū)域2通過異或樹而不是一級異或函數(shù)來實現(xiàn)，以獲得更高的性能。區(qū)域3完成了公式（1）的計算。區(qū)域4解決了填充零問題，并在第五節(jié)中提出和討論了導(dǎo)致O（log2n）資源利用率的pipelining go back算法。區(qū)域5是一個HWICAP控制器，可以動態(tài)修改查找表的內(nèi)容。操作程序在第四節(jié)中討論。分段系統(tǒng)架構(gòu)在第五節(jié)中提出。上述建議的實施細節(jié)可訪問［1］。

3.2 stride-by-5算法

在這一部分中，建立了資源利用模型，證明了對于不同的總線寬度，5步是最佳的步幅（stride），stride-by-5算法在算法1中描述。顧名思義，Stride是指單個邏輯表處理的位數(shù)。邏輯表可以用FPGA LUTs實現(xiàn)，可以加載一個函數(shù)的真值表。例如，八輸入函數(shù)定義為：

步幅為8和4的等式（3）和（4）可以分別如圖2（a）和圖2（b）所示實現(xiàn)。較小的步長意味著較小的邏輯表可以通過單個LUT或級聯(lián)查找表來實現(xiàn)。步長等于1可以認為是FPGA實現(xiàn)的最佳步距嗎？我們將建立資源利用模型并確定答案。

stride-by-5算法對于FPGAs中的5輸入查找表是最佳的。與slicing-by-4和slicing-by-8算法中使用的stride-by-8相比，stride-by-5將資源利用率降低了79.69%-79.98%。對于具有非5輸入查找表的FPGAs（Xilinx Virtex-5或Altera Stratix II之前），應(yīng)使用由LUT輸入數(shù)定義的步長，并應(yīng)利用LUT共享機制。stride-by-5算法在算法1中描述；它在這里處理區(qū)域1中的計算，但是該算法也可以在區(qū)域3和4中使用。

3.3 Pipelining Go Back算法

在這一部分中，提出了一種資源利用率為O（log2n）的pipelining go back算法，并給出了算法的推導(dǎo)和描述。

q可以表示為：

3.4 通過HWICAP進行重編程

圖1中的區(qū)域5代表一個HWICAP IP核，它可以動態(tài)修改查找表的內(nèi)容。對于任何總線寬度，它消耗186個查找表。相比之下，邏輯資源實現(xiàn)的配置邏輯導(dǎo)致n ≥ 1024 ［4］時消耗幾千個lut，資源利用率隨著總線寬度的增加而增加。使用HWICAP IP核重新編程的操作程序如下所述：

1. 完成初始設(shè)計，使用Vivado生成比特流，并將比特流下載到FPGA

2. 提取所用查找表的位置；

3. 當需要重新編程時，使用（1）和（12）計算查找表的新內(nèi)容；

4. 將查找表的內(nèi)容映射到查找表的初始值；

5. 使用HWICAP IP核的AXI Lite 接口將初始值寫入查找表。

重編程方法在工程上是有用的。我們的貢獻如下：

1. 我們驗證了使用HWICAP IP核對循環(huán)冗余校驗算法的現(xiàn)場可編程門陣列實現(xiàn)進行重新編程的可行性。不考慮總線寬度，導(dǎo)致資源利用率小且恒定；

2. 該方法可以直接改變循環(huán)冗余校驗多項式，無需重新編碼和合成；

3. 上述程序的代碼可作為整個項目的一部分在［1］中訪問。據(jù)我們所知，這是第一個涵蓋上述整個過程的開源代碼。

3.5 分段系統(tǒng)架構(gòu)

非分段系統(tǒng)架構(gòu)無法在一個字（時鐘）中處理多個幀，這降低了短幀或未對齊幀的吞吐量。這就是總線效率問題。針對這一問題，提出了一種分段的系統(tǒng)架構(gòu)?？偩€格式與［5］中的相同，［5］中的塊（block）是［13］中段（segment）的另一個名稱。比如一條4096位總線可以同時處理8個完整的幀；因此，總線可以分為八個區(qū)域［5］。區(qū)域的數(shù)量僅取決于總線寬度。不同的段寬度是可行的，如果選擇64位的段寬度，一個區(qū)域可以分成八個段（塊）。圖3示出了所提出的分段系統(tǒng)架構(gòu)。與建議的非分段系統(tǒng)架構(gòu)相比，建議的分段系統(tǒng)架構(gòu)具有稍微更復(fù)雜的區(qū)域1和區(qū)域2以及區(qū)域3和區(qū)域4的多個副本。重復(fù)的數(shù)量只是單個字中處理的最大幀數(shù)。

在圖4中可以找到所提出的分段系統(tǒng)架構(gòu)和所提出的非分段系統(tǒng)架構(gòu)之間的比較。紅色長方體代表非分段系統(tǒng)架構(gòu)。藍色長方體表示建議的分段系統(tǒng)架構(gòu)和建議的非分段系統(tǒng)架構(gòu)之間的增量。黃色切片（總線寬度= 1024，段寬度=512） 表示兩種體系結(jié)構(gòu)之間的減量。圖4a示出了資源利用率的增加主要取決于總線寬度而不是段寬度。這是因為資源利用率的增加主要取決于區(qū)域3和4的副本數(shù)量，而區(qū)域3和4的副本數(shù)量僅取決于總線寬度。圖4b顯示，在大多數(shù)情況下，65字節(jié)幀吞吐量的增加是明顯的。當總線寬度為1024位，段寬度為512位時，吞吐量只會下降，其中兩種架構(gòu)對于65字節(jié)幀吞吐量具有相同的總線效率，而非分段架構(gòu)的頻率略高。因此，在本文的其余部分，選擇64位作為段寬。分段和非分段架構(gòu)之間的詳細比較可以在本簡報的擴展版本中找到［11］。

4. 實驗結(jié)果

有三個最先進的研究［5］［4］［14］。［4］［14］中的體系結(jié)構(gòu)可以重新編程，而［5］中的體系結(jié)構(gòu)不能重新編程。提出的兩種架構(gòu)分別用Virtex-7 XC7VX690T實現(xiàn)，［5］［4］［14］使用Virtex-7 XCVH870T、Virtex-6 XC6VLX550T和Stratix-V 5SGSED6N1F45I2。在本節(jié)中，從資源利用率和最大吞吐量的角度將兩種建議的體系結(jié)構(gòu)與這些工作進行了比較。就各種幀長度的吞吐量而言，將所提出的分段架構(gòu)與［5］進行了比較。還報告了兩種建議架構(gòu)的功耗。在下文中，我們使用SA來指代分段架構(gòu)。

綜合結(jié)果如圖5所示。圖5a示出了建議的非SA的資源利用率較分別比［4］和［5］中的體系結(jié)構(gòu)低80.7%-87.5%和25.1%-46.2%，SA的分別為81.7%-85.9%和2.9%-20.8%。資源利用率較低是由于實施了第三節(jié)中描述的算法和方法，這也可以保證高性能和可編程性。［14］中的體系結(jié)構(gòu)的資源利用率比非SA體系結(jié)構(gòu)低74.4%-81.3%。［14］資源利用率較低的原因如下：1）。［14］只需要處理半滿和全滿的數(shù)據(jù)包。換句話說，補零問題得到了部分解決。相比之下，兩個建議的架構(gòu)和［5］［4］可以完全解決填充零問題。2）。Nios II IP核的成本在［14］中沒有考慮。相比之下，兩種建議的體系結(jié)構(gòu)都考慮了HWICAP的成本。此外，很難將［14］的總線寬度擴展到1024位。

圖5b顯示，所提出的非SA的最大吞吐量分別比［4］［5］［14］中的架構(gòu)高24.2%-37.9%、37.4%-75.0%和259.4%-284.5%。提出的SA的最大吞吐量分別比［4］［5］中的架構(gòu)高28.7%-30.2%和32.2%-80.2%。更高的頻率導(dǎo)致更高的吞吐量，并且兩個建議的架構(gòu)可以為區(qū)域1、2和4中排列良好的流水線實現(xiàn)更高的頻率。

幀長度從64字節(jié)到256字節(jié)的吞吐量可以在圖5c中找到。只有［5］和提議的SA被比較，因為它們在一個字中處理多個幀的能力。這兩種架構(gòu)使用4096位總線寬度和64位段寬度；因此，它們具有相同的總線效率。提議的SA的頻率和吞吐量比［5］高80.2%。當幀長度為65字節(jié)時，最低吞吐量為1933.9 Gbps。

兩種提出架構(gòu)的功耗如圖5d所示。它們以500Mhz運行。數(shù)據(jù)集來自vivado生成的實施后功耗報告。功耗由靜態(tài)功耗和動態(tài)功耗組成。靜態(tài)功耗從0.32 W到0.48 W不等，動態(tài)功耗隨著總線寬度的增加而線性增加。提議的SA的功耗比提議的非SA的功耗增長更快。這是因為提議的SA的資源消耗比提議的非SA的資源消耗增加得更快。

板級實現(xiàn)和與其他作品的比較可以在本文的擴展版本中找到［11］。

5. 結(jié)論和未來工作

本文提出了兩種算法和一種方法來實現(xiàn)低成本、高性能和可編程的循環(huán)冗余校驗計算。這些算法和所提出的方法可用于分段或非分段架構(gòu)。綜合結(jié)果表明，與現(xiàn)有的兩種體系結(jié)構(gòu)相比，所提出的體系結(jié)構(gòu)可以實現(xiàn)更低的資源利用率和更高的吞吐量。源代碼可以在［1］中訪問。我們未來的工作將集中在使硬件重配置方法（HWICAP）技術(shù)獨立。

審核編輯：何安