作者：劉歡，來源：網絡交換FPGA 微信公眾號

前段時間，本公眾號發布了《FPGA是網絡交換領域的不二選擇》的文章，文章引用了叢京生老師在2020年ASP-DAC會議上對于FPGA的一段有關硬件可定制計算具有巨大優勢的論述，而FPGA作為一種能夠實現可定制計算且靈活可編程的載體，具有無與倫比的天然優勢，對此，小編也深以為然。但是，換個角度來思考問題，FPGA是唯一實現可定制計算的載體嗎？當然不是。相對而言，FPGA作為一種所謂的萬能芯片，其靈活性已經足夠好，但對于某個具體的領域而言，為支持其靈活性而采用可編程SRAM硬件單元的方式就顯得顆粒度過于細小了，細小到已經嚴重影響定制硬件實現的PPA的程度。當然，對于大規模的應用場景，FPGA當然還是要轉為ASIC實現從而獲得足夠好的性價比，但ASIC天然的不靈活性也給算法或協議的升級帶來了障礙。那么，是否存在一種介于FPGA和ASIC之間，具有ASIC足夠的性能保障，同時又具有FPGA足夠好的可編程靈活性的可重構ASIC呢？這就是本文所關注的可重構計算領域。

可重構計算領域國內做的最好的團隊是清華大學魏少軍教授團隊，魏老師團隊曾開發過可重構的CPU芯片、可重構的密碼算法芯片以及可重構的深度學習芯片等。這些芯片都以同時具備ASIC的高性能和FPGA的靈活性作為最重要的優勢，當然，你也可以認為這些芯片都是相關領域可編程顆粒度較大的特殊的FPGA芯片。那么，除了上面的幾個領域之外，網絡交換領域是否存在類似的特殊的FPGA芯片呢？答案是肯定的。從2013年開始，斯坦福大學的Nick McKeown 教授為了充分解放數據平面的編程能力于2014 年首次設計并提出了數據平面特定領域編程語言P4，經提出就得到了學術界和工業界的廣泛關注和認可。工業界紛紛跟進并著手研制了一系列高性能的可編程硬件，其中主要包含Barefoot Tofino，Cavium XPliant以及Netronome NICs等。其中Barefoot Tofino 是目前業界數據分組轉發速度最快的可編程硬件，最高可以達到6.5Tbit/s 的線速數據分組轉發速率，性能遠超傳統交換機。一方面基于可編程設備的可定制化特性能夠快速實現和驗證一些新型的網絡架構、功能和協議，極大加速了網絡演進和創新；另一方面基于可編程設備的高性能特性，傳統上由靈活但低性能的中間件實現的一些比如防火墻，負載均衡等較為簡單的網絡功能可以卸載到可編程數據平面上實現來獲取可觀的性能提升。數據平面特定領域編程語言P4 具有如下3 點語言特性。1) 可重配置性：P4 支持轉發邏輯代碼經過編譯部署到具體平臺上之后動態修改報文的處理方式。這樣的話，運營商就可以在不更換硬件的前提下靈活定義數據平面的處理行為，極大降低了更換設備的資金成本和等待新設備開發的時間成本。2) 協議無關性：P4 并不綁定于某個特定的網絡協議。開發人員只需根據P4 語言定義的語法語義要素結合平臺的相關特性就可以自定義新協議，同時也能夠去除冗余的協議，按需使用協議，降低了額外開銷，提高了設備的資源利用率。3) 平臺無關性：開發人員可以獨立于特定的底層運行平臺來編寫數據報文處理邏輯。代碼能夠通過設備相關的后端編譯器快速地在硬件交換機、FPGA、SmartNIC、軟件交換機等不同平臺之間移植，減輕了開發人員的負擔，提高了開發效率。

好了，說了那么多，都是本文以下內容的鋪墊。本文介紹的主要內容是為了配合硬件實現可編程的PISA的包處理器，特別實現了一種在硬件實現時為支持不同數據位寬下靈活可編程的CRC架構。通俗點說，就是在實現可重構包處理器時，數據通路的CRC計算為了支持不同位寬時的一種低成本解決方案。本文作者是團隊博士生劉歡，相關研究已撰寫論文發表在TCASII雜志2021年1月的第一期雜志上（題目：Low-Cost and Programmable CRC Implementation Based on FPGA），源代碼已在GitHub開源（https://github.com/FPGA-Networking/Low-Cost-and-Programmable-CRC）。以下是文章的部分中文譯文。

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

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

1. 引言
“在硬件加速計算時代，識別并卸載通用的抽象和原語，而不是單獨的算法和協議。”

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

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

本文的其余部分組織如下。第二節介紹了一些基礎知識。第三節討論了系統架構和三個創新。第四節顯示了綜合結果。第五節是本文的結尾。

2. 基礎知識

2.1 并行循環冗余校驗算法
并行循環冗余校驗算法可以同時處理多個數據輸入位[10]。并行處理的位數設為，這也是本文剩余部分中內部總線的寬度。并行輸入數據為

3. 設計思路

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

3.2 stride-by-5算法

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

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

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之前)，應使用由LUT輸入數定義的步長，并應利用LUT共享機制。stride-by-5算法在算法1中描述；它在這里處理區域1中的計算，但是該算法也可以在區域3和4中使用。

3.3 Pipelining Go Back算法

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

q可以表示為：

3.4 通過HWICAP進行重編程

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

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

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

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

4. 將查找表的內容映射到查找表的初始值；

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

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

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

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

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

3.5 分段系統架構

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

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

4. 實驗結果

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

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

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

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

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

板級實現和與其他作品的比較可以在本文的擴展版本中找到[11]。

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

參考文獻

[1] S.C. of Low-Cost and Programmable CRC Implementation.Accessed: Apr. 24, 2020. [Online]. Available: https://github.com/FPGA-Networking/Low-Cost-and-Programmable-CRC.

[2] R. H. Dennard, F. H. Gaensslen, V. L. Rideout, E. Bassous, and A. R.LeBlanc, “Design of ion-implanted MOSFET’s with very small physicaldimensions,”IEEE J. Solid-State Circuits, vol. 9, no. 5, pp. 256–268,Oct. 1974.

[3] M. E. Kounavis and F. L. Berry, “Novel Table Lookup-Based Algorithmsfor High-Performance CRC Generation,”IEEE Trans. Comput., vol. 57,no. 11, pp. 1550–1560, Nov. 2008.

[4] A. Akagic and H. Amano, “High-speed fully-adaptable CRC accelera-tors,” IEICE Trans. Inf.& Syst., vol. 96, no. 6, pp. 1299–1308, 2013.

[5] L. Kekely, J. Cabal, and J. Koˇrenek, “Effective FPGA Architecturefor General CRC,” in International Conference on Architecture ofComputing Systems. Springer, 2019, pp. 211–223.

[6] C. Toal, K. McLaughlin, S. Sezer, and X. Yang, “Design and Implemen-tation of a Field Programmable CRC Circuit Architecture,” IEEE Trans.Very Large Scale Integr. (VLSI) Syst., vol. 17, no. 8, pp. 1142–1147,2009.

[7] The P4 Language Consortium. (Nov. 2018). The P4 Language Spec-ification, Version 1.0.5. [Online]. Available: https://p4.org/p4-spec/p4-14/v1.0.5/tex/p4.pdf.

[8] M. Grymel and S. B. Furber, “A Novel Programmable Parallel CRC Circuit,”IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 19,no. 10, pp. 1898–1902, Oct. 2011.

[9] S. Gueron, “Speeding up CRC32C computations with Intel CRC32instruction,” Information Processing Letters,vol. 112, no. 5, pp. 179–185, 2012.

[10] G. Campobello, G. Patane, and M. Russo, “Parallel CRC realization,”IEEE Trans. Comput., vol. 52, no. 10, pp. 1312–1319, Oct. 2003.

[11] H. Liu, Z. Qiu, W. Pan, J. Li, L. Zheng, and Y. Gao, “Low-Cost and Programmable CRC Implementation based on FPGA,” 42020. [Online]. Available: https://www.techrxiv.org/articles/Low-Costand Programmable CRCImplementation based on FPGA/12181494

[12] K. Vipin and S. A. Fahmy, “FPGA Dynamic and Partial Reconfiguration:A Survey of Architectures Methods and Applications,”ACM Comput.Surv., vol. 51, no. 4, pp. 1–39, 2018.

[13] P. Orosz, T. T′ othfalusi, and P. Varga, “FPGA-Assisted DPI Systems:100 Gbit/s and Beyond,”IEEE Commun. Surveys Tuts., vol. 21, no. 2,pp. 2015–2040, 2019.

[14] M. Jubin and T. Nayak, “Reconfigurable very high throughput lowlatency VLSI (FPGA) design architecture of CRC 32,” Integration,vol. 56, pp. 1–14, 2017.