基于BSV的高性能并行CRC硬件電路生成器設(shè)計(jì)

[ ]01、引 言

循環(huán)冗余校驗(yàn)碼，即Cyclic Redundancy Check (CRC), 是一種在各種通信系統(tǒng)中廣泛應(yīng)用的檢錯(cuò)機(jī)制。CRC算法的工作原理和哈希函數(shù)類似，具體來(lái)說(shuō)，其對(duì)任意長(zhǎng)度的數(shù)據(jù)計(jì)算出一段唯一的標(biāo)識(shí)（校驗(yàn)和）, 然后根據(jù)這個(gè)標(biāo)識(shí)來(lái)判斷該數(shù)據(jù)在傳輸過(guò)程中是否發(fā)生變化。

CRC檢錯(cuò)碼在實(shí)際生活中有著廣泛的應(yīng)用，諸如網(wǎng)絡(luò)通信，存儲(chǔ)系統(tǒng)等場(chǎng)景下都需要CRC來(lái)保證數(shù)據(jù)傳輸?shù)恼_性。而不同的應(yīng)用場(chǎng)景往往需要采用不同的CRC配置參數(shù)，同時(shí)對(duì)計(jì)算的性能也有不同的需求。例如，在基于Ethernet協(xié)議的網(wǎng)絡(luò)傳輸中需要采用IEEE802-3協(xié)議所規(guī)定的CRC參數(shù)，同時(shí)需要高吞吐率的CRC實(shí)現(xiàn)以和網(wǎng)絡(luò)帶寬相匹配。

對(duì)于一個(gè)具體的通信系統(tǒng)，CRC既可以通過(guò)軟件編程也可以硬件電路的形態(tài)來(lái)實(shí)現(xiàn)。相較于網(wǎng)絡(luò)上豐富的軟件庫(kù)，開(kāi)源的CRC硬件實(shí)現(xiàn)卻相對(duì)落后，尤其是面向高性能的應(yīng)用場(chǎng)景。例如，下述鏈接都提供了參數(shù)可配置的CRC硬件電路生成器，但這些實(shí)現(xiàn)方式都是直接將CRC算法映射到組合邏輯電路上，這往往會(huì)導(dǎo)致較長(zhǎng)的組合邏輯延時(shí)進(jìn)而降低電路的整體工作頻率，無(wú)法滿足高吞吐率的需求。

而另外一些開(kāi)源的電路實(shí)現(xiàn)雖然引入了流水線技術(shù)對(duì)時(shí)序進(jìn)行優(yōu)化，但其實(shí)現(xiàn)只針對(duì)某一特定的CRC配置參數(shù)，應(yīng)用場(chǎng)景相對(duì)有限：

• Pipelined Implementation

針對(duì)現(xiàn)有CRC開(kāi)源硬件實(shí)現(xiàn)的不足，blue-crc項(xiàng)目基于Bluespec SystemVerilog硬件描述語(yǔ)言實(shí)現(xiàn)了一個(gè)參數(shù)可配置同時(shí)滿足高吞吐率需求的CRC硬件電路生成器。blue-crc在架構(gòu)和功能上的具體特點(diǎn)包括:

• 支持完整的CRC配置參數(shù)包括：polynominal (生成多項(xiàng)式)，initial_value (初始CRC值)，finalXor (與輸出CRC值異或)， reverseInput (是否翻轉(zhuǎn)每個(gè)輸入字節(jié)的比特順序)，reverseOutput (是否翻轉(zhuǎn)輸出CRC結(jié)果的比特順序);
• 標(biāo)準(zhǔn)I/O接口: 輸入端支持AxiStream協(xié)議 (位寬可配置), 輸出端基于valid-ready握手機(jī)制傳輸CRC校驗(yàn)和;
• 并行計(jì)算+流水線: 每個(gè)周期可處理多個(gè)字節(jié)數(shù)據(jù)，在Xilinx xcvu9p FPGA上可達(dá)到500MHz的運(yùn)行頻率;
• 高吞吐率: 在256-bit輸入數(shù)據(jù)總線的配置下吞吐率可達(dá)128Gb/s;
• 計(jì)算模式: 支持發(fā)送端CRC生成和接收CRC檢測(cè)兩種不同的計(jì)算模式

下文將分別從算法和架構(gòu)兩個(gè)方面介紹blue-crc背后的實(shí)現(xiàn)原理及其具體的使用方式。

02、算法原理

CRC計(jì)算的定義

生成CRC校驗(yàn)和本質(zhì)上是在計(jì)算基于多項(xiàng)式的模2除法。將原始數(shù)據(jù)每個(gè)比特所確定的多項(xiàng)式除以一個(gè)通信雙方規(guī)定好的生成多項(xiàng)式，得到的余數(shù)即為校驗(yàn)和。生成CRC校驗(yàn)值算法的詳細(xì)定義如下:對(duì)于m-bit原始數(shù)據(jù)

可以表示為如下多項(xiàng)式:

若需要生成n-bit的CRC校驗(yàn)值, 則通信雙方需要規(guī)定一個(gè) (n+1)-bit的生成多項(xiàng)式:

則原始數(shù)據(jù)的CRC校驗(yàn)值為多項(xiàng)式A(x)乘上x(chóng)^n 后除以G(x)得到的余數(shù)，具體表達(dá)式為：

生成的CRC校驗(yàn)值附加在原始數(shù)據(jù)的尾部后傳輸至接收端, 即實(shí)際發(fā)出的數(shù)據(jù)為

基于CRC的生成原理，數(shù)據(jù)接收端可以采用兩種不同的方式完成校驗(yàn): 1) 提取出附加在發(fā)送數(shù)據(jù)尾部的校驗(yàn)值后生成新的CRC校驗(yàn)值，將該值與提取出的進(jìn)行比較，如果二者相同則表明數(shù)據(jù)在傳輸過(guò)程中沒(méi)有出錯(cuò)；2）由于校驗(yàn)值為除法運(yùn)算中得到的余數(shù)，這就意味著附加上檢驗(yàn)值后的發(fā)送數(shù)據(jù)可被生成多項(xiàng)式整除，因此也可以直接對(duì)接收數(shù)據(jù)進(jìn)行模2除法，若得到的余數(shù)為0則表明數(shù)據(jù)傳輸成功。

在基于多項(xiàng)式的模2算術(shù)運(yùn)算中，變量的取值范圍只有0和1，且運(yùn)算過(guò)程不存在進(jìn)位或借位。因此，加減法都可以視為異或運(yùn)算, 而乘除法可以由加減法構(gòu)成，因此實(shí)際上也等同于一系列的異或運(yùn)算。下圖展示了一個(gè)具體的模2除法取余數(shù)計(jì)算CRC校驗(yàn)和的例子，其中原始數(shù)據(jù)為101001，生成多項(xiàng)式為1101。由該例子可見(jiàn)，模2除法的運(yùn)算法則和普通的除法類似，不同點(diǎn)在于模2除法用異或操作替換了減法且不存在借位。

從另外一個(gè)角度理解，模二除法取余數(shù)的過(guò)程實(shí)際上是逐位地對(duì)原始數(shù)據(jù)進(jìn)行縮減: 當(dāng)輸入數(shù)據(jù)的最高位為1時(shí)，原始數(shù)據(jù)和除數(shù)左對(duì)齊異或后移除最高位，得到下一輪縮減的輸入；當(dāng)最高位為0時(shí)，直接移除最高位得到下一輪縮減的輸入。不斷重復(fù)上述縮減步驟直至輸入數(shù)據(jù)的位寬小于除數(shù)位寬，該輸入值即為所求余數(shù)。根據(jù)上述取模步驟，可以很容易地將CRC算法映射到基于線性負(fù)反饋移位寄存器 (LFSR) 結(jié)構(gòu)的硬件上，一種具體的實(shí)現(xiàn)如下圖所示, 其對(duì)應(yīng)的生成多項(xiàng)式為11011。原始數(shù)據(jù)從最高位開(kāi)始逐位從Din輸入，當(dāng)所有數(shù)據(jù)都傳入后，寄存器中的值即為所要求的校驗(yàn)和。

上圖展示的電路結(jié)構(gòu)是一種非常經(jīng)典的CRC算法的硬件實(shí)現(xiàn)方式，其可以用極小的面積和功耗生成校驗(yàn)值，但由于每個(gè)周期只能處理1-bit輸入數(shù)據(jù)，其很難達(dá)到較高的吞吐率。為了提升CRC校驗(yàn)電路的計(jì)算性能，很多面向硬件的CRC并行算法被提出。blue-crc項(xiàng)目的實(shí)現(xiàn)主要參考了論文[1]和[2]中提出的并行算法和電路架構(gòu), 并在此基礎(chǔ)上進(jìn)一步優(yōu)化流水線結(jié)構(gòu)以提升工作頻率，同時(shí)提供了參數(shù)可配置的設(shè)計(jì)以及標(biāo)準(zhǔn)的輸入輸出接口。

并行算法

blue-crc項(xiàng)目所采用的并行算法主要是建立在模2除法(取余)運(yùn)算的兩個(gè)定理之上，這兩個(gè)定理分別是（備注:下文所列公式中的算術(shù)運(yùn)算都是在模2域下完成，即加減法都等同于異或運(yùn)算）:

1. 若多項(xiàng)式

則

由定理1可知, 對(duì)于任意長(zhǎng)度的輸入數(shù)據(jù), 都可以將其拆分成若干小段，每小段數(shù)據(jù)的CRC校驗(yàn)值可以獨(dú)立地并行計(jì)算，然后通過(guò)異或操作將所有校驗(yàn)值累加在一起，即可得到完整數(shù)據(jù)對(duì)應(yīng)的CRC校驗(yàn)值。在blue-crc的實(shí)現(xiàn)中，每小段數(shù)據(jù)Ai(x)的長(zhǎng)度為8-bit, 設(shè)原始數(shù)據(jù)A(x)的總長(zhǎng)度為8n-bit, 則:

根據(jù)定理1，我們可以并行地計(jì)算每個(gè)輸入字節(jié)Ai(x)的校驗(yàn)值

，然后將每個(gè)字節(jié)對(duì)應(yīng)的校驗(yàn)和累加在一起就可得到完整數(shù)據(jù)的校驗(yàn)和，即

對(duì)于每個(gè)輸入字節(jié)的CRC校驗(yàn)和的計(jì)算，除了依照算法實(shí)現(xiàn)對(duì)應(yīng)的硬件電路， 另一種更加高效的方式是: 提前計(jì)算好8-bit數(shù)所有可能值對(duì)應(yīng)的CRC輸出并制作成硬件查找表，當(dāng)電路運(yùn)行時(shí)，以輸入數(shù)據(jù)為地址從查找表中取出對(duì)應(yīng)的表項(xiàng)即可得到校驗(yàn)和。若輸入原始數(shù)據(jù)有n個(gè)字節(jié)，則需要制作n張長(zhǎng)度為

的查找表，其中第

張查找表的第x個(gè)表項(xiàng)的值即為

的CRC校驗(yàn)和。

雖然有了定理1我們可以在一個(gè)周期內(nèi)并行處理多個(gè)字節(jié)數(shù)據(jù)，但基于此還不能夠完成CRC的硬件實(shí)現(xiàn)。在實(shí)際電路中數(shù)據(jù)總線的位寬是有限的，對(duì)于較長(zhǎng)的輸入數(shù)據(jù)，需要根據(jù)總線位寬將其分成多個(gè)幀并分配到多個(gè)周期進(jìn)行傳輸。因此，我們還需要基于定理2累加不同周期計(jì)算得到的CRC校驗(yàn)值進(jìn)而獲得最終結(jié)果。

在blue-crc的實(shí)現(xiàn)中，數(shù)據(jù)以大端字節(jié)序進(jìn)行傳輸，即高位數(shù)據(jù)先傳入進(jìn)行處理, 假設(shè)輸入數(shù)據(jù)總線位寬為256-bit, 當(dāng)前周期輸入數(shù)據(jù)對(duì)應(yīng)的多項(xiàng)式為A(x), 該周期之前已經(jīng)輸入的數(shù)據(jù)為A'(x), 每個(gè)周期我們除了計(jì)算CRC[A(x)]，還需要將該值累加到已經(jīng)計(jì)算好的中間校驗(yàn)和CRC[A'(x)]上，得到數(shù)據(jù)

的校驗(yàn)和。根據(jù)定理1和2，可以推導(dǎo)出累加的計(jì)算公式如下:

即需要將中間校驗(yàn)和CRC[A'(x)]左移256-bit，對(duì)其再次計(jì)算CRC校驗(yàn)值后和CRC[A(x)]相加。同樣我們可以通過(guò)硬件查找表的方式完成這里校驗(yàn)和的計(jì)算。

實(shí)際CRC的計(jì)算中原始數(shù)據(jù)的長(zhǎng)度并不一定都是256-bit的整數(shù)倍，因此在處理最后一幀輸入時(shí)不能直接使用上面的公式進(jìn)行累加。我們需要?jiǎng)討B(tài)地計(jì)算每個(gè)數(shù)據(jù)包最后一幀的有效數(shù)據(jù)的寬度，設(shè)寬度為m, 則可以采用如下公式進(jìn)行累加:

03、電路架構(gòu)與性能

架構(gòu)設(shè)計(jì)

基于上述并行算法，CRC硬件電路的架構(gòu)設(shè)計(jì)如下圖所示。為了提升吞吐率，電路設(shè)計(jì)時(shí)將CRC算法需要的組合邏輯實(shí)現(xiàn)劃分成了八級(jí)單向傳遞的流水線, 其中前五級(jí)流水線計(jì)算每個(gè)周期輸入數(shù)據(jù)的CRC校驗(yàn)和并累加到CRC中間值上，后三級(jí)流水線用于處理最后一幀數(shù)據(jù)非對(duì)齊（數(shù)據(jù)位寬非總線位寬的整數(shù)倍）情況下CRC校驗(yàn)值的累加。每一級(jí)流水線的完成的具體功能如下:

• Stage-1: 對(duì)AXI-Stream總線輸入數(shù)據(jù)進(jìn)行預(yù)處理，包括大小端轉(zhuǎn)換、根據(jù)CRC配置參數(shù)reverse_input調(diào)換比特順序、根據(jù)AXI-Stream總線tkeep字段計(jì)算數(shù)據(jù)總線上有效的字節(jié)數(shù)（用于處理數(shù)據(jù)長(zhǎng)度非總線位寬整數(shù)倍的情況）；
• Stage-2: 對(duì)于數(shù)據(jù)長(zhǎng)度非總線位寬整數(shù)倍的情況，需要對(duì)最后一幀數(shù)據(jù)進(jìn)行移位和下一級(jí)的查找表對(duì)齊；
• Stage-3: 從查找表中取出輸入數(shù)據(jù)每個(gè)字節(jié)對(duì)應(yīng)的CRC校驗(yàn)值；
• Stage-4: 通過(guò)樹(shù)狀結(jié)構(gòu)將各個(gè)字節(jié)的CRC值進(jìn)行異或合并得到該周期輸入數(shù)據(jù)對(duì)應(yīng)的CRC校驗(yàn)和；
• Stage-5: 根據(jù)上文提到的定理2，將輸入數(shù)據(jù)CRC校驗(yàn)和累加到中間校驗(yàn)和之上。最后一幀輸入數(shù)據(jù)（有效數(shù)據(jù)位寬可能小于總線位寬）需要特殊的處理，因此不在該流水級(jí)直接進(jìn)行累加，需要將中間CRC值和上一級(jí)傳來(lái)的CRC校驗(yàn)和傳遞到后續(xù)流水級(jí)進(jìn)行處理;
• 中計(jì)算的最后一幀數(shù)據(jù)的實(shí)際有效位寬對(duì)中間CRC值進(jìn)行移位和下一級(jí)的查找表對(duì)齊;

• 中計(jì)算的最后一幀數(shù)據(jù)的實(shí)際有效位寬對(duì)中間CRC值進(jìn)行移位和下一級(jí)的查找表對(duì)齊;
• Stage-7: 從查找表中取出中間CRC值移位后對(duì)應(yīng)的校驗(yàn)和;
• Stage-8: 將上一級(jí)的查找表輸出和Stage-5傳遞來(lái)的最后一幀輸入數(shù)據(jù)的CRC校驗(yàn)和通過(guò)樹(shù)狀結(jié)構(gòu)進(jìn)行異或合并得到全部數(shù)據(jù)的校驗(yàn)和

性能與面積

CRC硬件電路的實(shí)際性能和資源開(kāi)銷與具體的配置參數(shù)有關(guān)。大部分情況下，硬件電路的吞吐率隨輸入總線數(shù)據(jù)位寬增大而提升，硬件資源開(kāi)銷則同時(shí)和總線寬度以及CRC校驗(yàn)和寬度有關(guān)。以IEEE 802-3協(xié)議規(guī)定的32位CRC校驗(yàn)和為例，其在256位輸入總線位寬的配置下，可在Xilinx xcvu9p FPGA器件上達(dá)到500MHz的工作頻率，總吞吐率達(dá)128Gb/s，實(shí)際的硬件資源開(kāi)銷如下。

相較于其他硬件實(shí)現(xiàn)方式，blue-crc主要關(guān)注于計(jì)算性能上的提升，因此在硬件資源上的開(kāi)銷相對(duì)較大。其中最主要的開(kāi)銷來(lái)源于用于實(shí)現(xiàn)CRC計(jì)算的查找表，其容量大小隨數(shù)據(jù)總線位寬以及校驗(yàn)和位寬的增大而增大，具體的查找表容量的計(jì)算方式如下（設(shè)總線字節(jié)寬度為m, CRC校驗(yàn)和字節(jié)寬度為n）:

對(duì)于上文提到的IEEE 802-3協(xié)議規(guī)定的 32-bit CRC校驗(yàn)，在256-bit輸入總線位寬的配置下，理論上所需的查找表容量為36KB.

04、使用指南

本文的最后一部分將介紹blue-crc項(xiàng)目的使用指南，包括CRC電路的配置參數(shù)、輸入輸出接口、面向BlueSpec SystemVerilog的使用接口，以及面向Verilog的使用接口。

配置參數(shù)

在blue-crc中，CRC硬件電路完整的配置參數(shù)如下表所示:

輸入輸出接口

在blue-crc項(xiàng)目中，CRC硬件電路基于AXI-Stream總線協(xié)議接收上游模塊傳入的數(shù)據(jù)，校驗(yàn)和輸出端口采用valid-ready握手機(jī)制和下游模塊進(jìn)行交互。電路頂層模塊生成的Verilog端口如下:

module mkCrcRawAxiStreamCustom(    input CLK,    input RST_N,        input s_axis_tvalid,    input s_axis_tdata,    input s_axis_tkeep,    input s_axis_tlast,    input s_axis_tuser,    output s_axis_tready,        output m_crc_stream_data,    output m_crc_stream_valid,    input  m_crc_stream_ready);

發(fā)起CRC計(jì)算時(shí)原始數(shù)據(jù)需要按照大端字節(jié)序進(jìn)行傳輸，即高位字節(jié)需要優(yōu)先傳輸。假設(shè)CRC電路輸入AXI-Stream總線數(shù)據(jù)位寬為32-bit (4-byte), 若要傳輸80-bit (10-byte)的數(shù)據(jù)，那么每一幀需要傳輸?shù)膬?nèi)容如下圖所示:

BSV使用接口

blue-crc項(xiàng)目基于Bluespec SystemVerilog硬件描述語(yǔ)言實(shí)現(xiàn)，因此對(duì)于使用BSV的設(shè)計(jì)者，可以直接通過(guò)實(shí)例化的方式使用CRC模塊。詳細(xì)的使用步驟如下:

1. 獲取blue-crc源碼: blue-crc使用了blue-wrapper項(xiàng)目提供的AXI-Stream接口，克隆時(shí)需要加上--recursive選項(xiàng)獲得這部分代碼:

git clone --recursive https://github.com/datenlord/blue-crc.git

2. 在代碼中導(dǎo)入所需模塊:

import CrcDefines :: *;import CrcAxiStream :: *;import AxiStreamTypes :: *;

3. 確定CRC配置參數(shù):CrcConfig結(jié)構(gòu)體封裝了電路的各項(xiàng)配置參數(shù), CrcConfig結(jié)構(gòu)體的定義如下, 其中每個(gè)字段的具體含義可參考前文列出的表格。其中，revInput和revOutput字段為IsReverseBitOrder枚舉類型，可選取值包括BIT_ORDER_REVERSE 和 BIT_ORDER_NOT_REVERSE; crcMode字段為CrcMode枚舉類型, 可選取值包括CRC_MODE_RECV和CRC_MODE_SEND。

typedef struct {    Bit#(crcWidth) polynominal;    Bit#(crcWidth) initVal;    Bit#(crcWidth) finalXor;    IsReverseBitOrder revInput;    IsReverseBitOrder revOutput;    String memFilePrefix;    CrcMode crcMode;} CrcConfig#(numeric type crcWidth) deriving(Eq, FShow);typedef enum {    CRC_MODE_RECV,    CRC_MODE_SEND} CrcMode deriving(Eq, FShow);typedef enum {    BIT_ORDER_REVERSE,    BIT_ORDER_NOT_REVERSE} IsReverseBitOrder deriving(Eq, FShow);

4. 實(shí)例化mkCrcAxiStream模塊: 頂層模塊接口CrcAxiStream的定義如下，數(shù)據(jù)的輸入和輸出分別由Get和Put接口實(shí)現(xiàn)

typedef Bit#(width) CrcResult#(numeric type width);typedef Get#(CrcResult#(crcWidth)) CrcResultGet#(numeric type crcWidth);typedef Put#(AxiStream#(keepWidth, AXIS_USER_WIDTH)) AxiStreamPut#(numeric type keepWidth);interface CrcAxiStream#(numeric type crcWidth, numeric type axiKeepWidth);    interface AxiStreamPut#(axiKeepWidth) crcReq;    interface CrcResultGet#(crcWidth) crcResp;endinterface

以IEEE 802-3協(xié)議中規(guī)定的32-bit CRC為例，若要實(shí)現(xiàn)輸入位寬為256-bit的CRC校驗(yàn)值生成電路，則實(shí)例化碼如下:

CrcConfig#(32) conf = CrcConfig {    polynominal: 32'h04C11DB7,    initVal    : 32'hFFFFFFFF,    finalXor   : 32'hFFFFFFFF,    revInput   : BIT_ORDER_REVERSE,    revOutput  : BIT_ORDER_REVERSE,    memFilePrefix: "mem_tab",    crcMode: CRC_MODE_SEND};CrcAxiStream#(32, 256) crc < - mkCrcAxiStream(conf);

5. 生成查找表文件: 查找表文件的生成腳本為scripts/gen_crc_tab.py, 使用該腳本前需要先配置.json格式的CRC配置文件，該文件的內(nèi)容需要和BSV代碼中的配置一致:

{    "crc_width": 32,    "axi_keep_width": 32,    "polynomial": "0x04C11DB7",    "init_value": "0xFFFFFFFF",    "final_xor": "0xFFFFFFFF",    "reverse_input": true,    "reverse_output": true,    "mem_file_prefix": "crc_tab",    "crc_mode": "CRC_MODE_SEND"}

配置好.json文件后，使用python執(zhí)行該腳本（需要傳入.json配置文件路徑和輸出文件路徑）:

python3 gen_crc_tab.py JSON文件路徑 文件輸出路徑

6. 編譯項(xiàng)目時(shí)需要在編譯選項(xiàng)中加入blue-crc源代碼的路徑, 假設(shè)blue-crc的根目錄為$(ROOT), 則需要在編譯選項(xiàng)中加上:

bsc -p +:$(BLUE_CRC)/src:$(ROOT)/lib/blue-wrapper/src

Verilog使用接口

雖然blue-crc項(xiàng)目基于BSV實(shí)現(xiàn)，但同時(shí)也提供了生成可配的Verilog代碼的腳本scripts/gen_crc.py。該腳本需要在blue-crc項(xiàng)目的根目錄下執(zhí)行，同時(shí)需要傳入.json格式的CRC配置文件（具體文件格式見(jiàn)上文）:

python3 scripts/gen_crc.py JSON配置文件 [Verilog生成路徑] [查找表生成路徑]

若在執(zhí)行腳本時(shí)沒(méi)有配置Verilog代碼和查找表文件生成路徑，那么這些文件會(huì)默認(rèn)生成到根目錄下的verilog文件夾。生成Verilog代碼需要使用到BSV編譯器，因此在執(zhí)行腳本前還需要保證已經(jīng)安裝并配置好該編譯工具。