はじめに
この記事では「昔はこんなふうに回路を設計していたんだよ」という昔話を紹介します。その例として、多ビット入力 CRC 生成回路を２回にわけて説明します。今回はその１回目で、比較的簡単な方を説明します。２回目は、CRC をパイプライン処理で演算するための Walma のアルゴリズムについて説明する予定です。
CRC とは
CRC の正式名称は巡回冗長検査 ( C yclic R edundancy C heck) と言います。CRC は誤り検出符号の１種で、主にデータ転送やデータの保存などで、データの偶発的な誤りの検出によく使われています。特に CRC-32 と一般的に呼ばれている IEEE 802.3 の CRC はイーサネットや ZIP や PNG などに使われています。
この記事では、そのアルゴリズムの詳細な解説は行いません。
１ビット入力 CRC 生成回路
まずは１ビット入力の CRC-32 生成回路のブロック図を示します。CRC-32 は３種類存在しますが、ここではイーサネットなどで使用されている多項式(Polynomial)が0xEDB88320で右シフトのものを使います。
Fig.1 1ビット入力のCRC-32 生成回路のブロック図
CRC Register に初期値 0xFFFFFFFF を入れておきます。その後、データを１ビットずつ入力して生成した CRC の値を CRC Register に入力します。この処理をすべての入力データに行うと、CRC Register に最終的な CRC 値が格納されます。
多ビット入力 CRC 生成回路の実装例
前章で説明した CRC 生成回路は、１ビットずつ入力してその都度 CRC 演算を行うため、例えば 1Gbps で処理したい場合は 1GHz で動作させる必要があります。また、たいていの場合、入力はパラレル(8bit とか 32bit とか) であることが多く、そのたびにパラレルーシリアル変換するのは面倒です。
そのため、同時に多ビットを入力して CRC を生成する方法が求められます。この章では比較的簡単な多ビット CRC 生成回路の実装例を３つほど紹介します。
多ビット入力 CRC 生成回路 単純ループ版
もっとも単純な方法は、前章の１ビットずつ CRC 生成回路を必要な分だけ並べてしまうことです。
ブロック図
Fig.2 多ビット入力のCRC-32 生成回路(単純ループ版)のブロック図
VHDL の記述例
entity は次のようになります。CRC のビット幅(CRC_BITS)、CRC の多項式(CRC_POLY)、CRC の初期値(CRC_INIT)、演算時のシフト方向(CRC_RIGHT)、入力データのビット幅(DATA_BITS) を generic で指定しています。
library ieee;
use ieee.std_logic_1164.all;
entity CRC_GEN is
generic (
CRC_BITS : integer := 32;
CRC_POLY : string := "0xEDB88320";
CRC_INIT : string := "0xFFFFFFFF";
CRC_RIGHT : boolean := TRUE;
DATA_BITS : integer := 32
);
port (
CLK : in std_logic;
RST : in std_logic;
LOAD : in std_logic;
LAST : in std_logic;
DATA : in std_logic_vector(DATA_BITS-1 downto 0);
CRC : out std_logic_vector(CRC_BITS -1 downto 0);
VAL : out std_logic
);
end entity;
architecutre 部で、CRC 演算に使用する型(CRC_TYPE) を宣言します。さらに CRC_POLY と CRC_INIT を CRC_TYPE に変換しておきます。
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.util.all;
architecture RTL of CRC_GEN is
subtype CRC_TYPE is std_logic_vector(CRC_BITS-1 downto 0);
signal curr_crc : CRC_TYPE;
function CONV_CRC_TYPE(CRC_STR : string) return CRC_TYPE is
variable crc_bit : CRC_TYPE;
variable crc_len : integer;
begin
STRING_TO_STD_LOGIC_VECTOR(CRC_STR, crc_bit, crc_len);
return crc_bit;
end function;
constant CRC_POLY_BIT : CRC_TYPE := CONV_CRC_TYPE(CRC_POLY);
constant CRC_INIT_BIT : CRC_TYPE := CONV_CRC_TYPE(CRC_INIT);
まず、1ビット入力の CRC 演算を行う関数を定義します。
function CALC_CRC(CRC:CRC_TYPE;D:std_logic) return CRC_TYPE is
variable new_crc : CRC_TYPE;
variable sft_crc : CRC_TYPE;
variable crc_xor_d_bit : std_logic;
begin
if (CRC_RIGHT) then
for i in CRC_TYPE'range loop
if (i = CRC_TYPE'high) then
sft_crc(i) := '0';
else
sft_crc(i) := CRC(i+1);
end if;
end loop;
crc_xor_d_bit := CRC(CRC_TYPE'low ) xor D;
else
for i in CRC_TYPE'range loop
if (i = CRC_TYPE'low) then
sft_crc(i) := '0';
else
sft_crc(i) := CRC(i-1);
end if;
end loop;
crc_xor_d_bit := CRC(CRC_TYPE'high) xor D;
end if;
for i in CRC_TYPE'range loop
if (CRC_POLY_BIT(i) = '1') then
new_crc(i) := sft_crc(i) xor crc_xor_d_bit;
else
new_crc(i) := sft_crc(i);
end if;
end loop;
return new_crc;
end function;
多ビット入力の CRC 演算を行う関数は、前述の1ビット入力の CRC 演算関数を、入力データのビット幅分だけループで回します。
function CALC_CRC(CRC:CRC_TYPE;D:std_logic_vector) return CRC_TYPE is
variable new_crc : CRC_TYPE;
begin
new_crc := CRC;
for i in D'low to D'high loop
new_crc := CALC_CRC(new_crc, D(i));
end loop;
return new_crc;
end function;
architecutre の本体を次のようにします。
begin
process(CLK, RST)
variable next_crc : CRC_TYPE;
begin
if (RST = '1') then
curr_crc <= CRC_INIT_BIT;
CRC <= CRC_INIT_BIT;
VAL <= '0';
elsif (CLK'event and CLK = '1') then
if (LOAD = '1') then
next_crc := CALC_CRC(curr_crc, DATA);
if (LAST = '1') then
curr_crc <= CRC_INIT_BIT;
CRC <= next_crc;
VAL <= '1';
else
curr_crc <= next_crc;
CRC <= next_crc;
VAL <= '0';
end if;
else
VAL <= '0';
end if;
end if;
end process;
end RTL;
特徴
この方法の長所は、記述が簡単なことです。短所は、論理合成ツールによっては遅延時間が大きくなる可能性があることです。
多ビット入力 CRC 生成回路 crcgen 版
前節で紹介したような 1ビット入力 CRC 生成回路を単純に並べた場合は、論理合成ツールによっては遅延時間が大きくなる可能性があります。それなら最初から最適化(論理圧縮)された VHDL コードを外部ツールで生成すれば良いという発想です。
crcgen
CRC 生成回路を生成するツールはいくつかあるのですが、この記事では以下のURL で公開されている crcgen を使ってみます。
このツールは Python で記述されており、実行には Python 3.7 が必要です。
shell$ python3.7 crcgen -V -a CRC-32 -b 32 -n crc32_0032 -D d -C c -o o > crc32_0032.vhd
生成された VHDL コードの例
crcgen で生成した CRC 生成回路の VHDL コードはかなり大きなものになります。以下の URL にビット数ごとに生成した CRC 生成回路の VHDL コードを置いていますので参考にしてください。
多ビット入力 CRC 生成回路 テーブル生成版
前述の CRC 生成回路を外部ツールで VHDL コードを生成するのはなんか面倒臭いな〜とい言うことで、同様のコードを VHDL だけで記述してみました。具体的には、CRC 演算用に最適化されたテーブルを定数として用意しておきます。そしてそのテーブルを作成する関数は VHDL で記述されていて、論理合成ツールが VHDL コードを評価するときにその関数を実行してテーブルを作成します。
VHDL の記述例
entity は次のようになります。CRC のビット幅(CRC_BITS)、CRC の多項式(CRC_POLY)、CRC の初期値(CRC_INIT)、演算時のシフト方向(CRC_RIGHT)、入力データのビット幅(DATA_BITS) を generic で指定しています。
library ieee;
use ieee.std_logic_1164.all;
entity CRC_GEN is
generic (
CRC_BITS : integer := 32;
CRC_POLY : string := "0xEDB88320";
CRC_INIT : string := "0xFFFFFFFF";
CRC_RIGHT : boolean := TRUE;
DATA_BITS : integer := 32
);
port (
CLK : in std_logic;
RST : in std_logic;
LOAD : in std_logic;
LAST : in std_logic;
DATA : in std_logic_vector(DATA_BITS-1 downto 0);
CRC : out std_logic_vector(CRC_BITS -1 downto 0);
VAL : out std_logic
);
end entity;
architecutre 部で、CRC 演算に使用する型(CRC_TYPE) を宣言します。さらに CRC_POLY と CRC_INIT を CRC_TYPE に変換しておきます。
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.util.all;
architecture RTL of CRC_GEN is
subtype CRC_TYPE is std_logic_vector(CRC_BITS-1 downto 0);
signal curr_crc : CRC_TYPE;
function CONV_CRC_TYPE(CRC_STR : string) return CRC_TYPE is
variable crc_bit : CRC_TYPE;
variable crc_len : integer;
begin
STRING_TO_STD_LOGIC_VECTOR(CRC_STR, crc_bit, crc_len);
return crc_bit;
end function;
constant CRC_POLY_BIT : CRC_TYPE := CONV_CRC_TYPE(CRC_POLY);
constant CRC_INIT_BIT : CRC_TYPE := CONV_CRC_TYPE(CRC_INIT);
最適化されたテーブルの型を宣言しておきます。テーブルの大きさは CRC_BITS × (CRC_BITS+DATA_BIT) になります。テーブルの１要素には1ビットのフラグが格納されていて、このビットが '1' の時に、対応する位置の CRC または DATA が xor 演算されます。詳細は CALC_CRC 関数を参照してください。
type CALC_CRC_OPT_BIT_TYPE is record
CRC_BIT : std_logic_vector( CRC_BITS-1 downto 0);
DATA_BIT : std_logic_vector(DATA_BITS-1 downto 0);
end record;
type CALC_CRC_OPT_TABLE_TYPE is array(CRC_BITS-1 downto 0) of CALC_CRC_OPT_BIT_TYPE;
最適化されたテーブルを生成する関数は次のようになります。
function INIT_CALC_CRC_OPT_TABLE return CALC_CRC_OPT_TABLE_TYPE is
variable table : CALC_CRC_OPT_TABLE_TYPE;
variable carry : CALC_CRC_OPT_BIT_TYPE;
begin
for i in CRC_TYPE'range loop
for crc_pos in CRC_TYPE'range loop
if (crc_pos = i) then
table(i).CRC_BIT(crc_pos) := '1';
else
table(i).CRC_BIT(crc_pos) := '0';
end if;
end loop;
table(i).DATA_BIT := (others => '0');
end loop;
if (CRC_RIGHT) then
for i in 0 to DATA_BITS-1 loop
carry := table(CRC_TYPE'low );
carry.DATA_BIT(i) := '1';
for crc_pos in CRC_TYPE'low to CRC_TYPE'high-1 loop
table(crc_pos) := table(crc_pos+1);
end loop;
table(CRC_TYPE'high).CRC_BIT := (others => '0');
table(CRC_TYPE'high).DATA_BIT := (others => '0');
for crc_pos in CRC_TYPE'range loop
if (CRC_POLY_BIT(crc_pos) = '1') then
table(crc_pos).CRC_BIT := table(crc_pos).CRC_BIT xor carry.CRC_BIT;
table(crc_pos).DATA_BIT := table(crc_pos).DATA_BIT xor carry.DATA_BIT;
end if;
end loop;
end loop;
else
for i in 0 to DATA_BITS-1 loop
carry := table(CRC_TYPE'high);
carry.DATA_BIT(i) := '1';
for crc_pos in CRC_TYPE'high downto CRC_TYPE'low+1 loop
table(crc_pos) := table(crc_pos-1);
end loop;
table(CRC_TYPE'low ).CRC_BIT := (others => '0');
table(CRC_TYPE'low ).DATA_BIT := (others => '0');
for crc_pos in CRC_TYPE'range loop
if (CRC_POLY_BIT(crc_pos) = '1') then
table(crc_pos).CRC_BIT := table(crc_pos).CRC_BIT xor carry.CRC_BIT;
table(crc_pos).DATA_BIT := table(crc_pos).DATA_BIT xor carry.DATA_BIT;
end if;
end loop;
end loop;
end if;
return table;
end function;
最適化されたテーブルを定数として宣言します。
constant CALC_CRC_OPT_TABLE : CALC_CRC_OPT_TABLE_TYPE := INIT_CALC_CRC_OPT_TABLE;
最適化されたテーブルを使って CRC を生成する関数は次のようになります。
function CALC_CRC(CRC:CRC_TYPE;D:std_logic_vector) return CRC_TYPE is
variable new_crc : CRC_TYPE;
begin
for i in 0 to CRC_BITS-1 loop
new_crc(i) := '0';
for pos in 0 to CRC_BITS-1 loop
if (CALC_CRC_OPT_TABLE(i).CRC_BIT(pos) = '1') then
new_crc(i) := new_crc(i) xor CRC(pos);
end if;
end loop;
for pos in 0 to DATA_BITS-1 loop
if (CALC_CRC_OPT_TABLE(i).DATA_BIT(pos) = '1') then
new_crc(i) := new_crc(i) xor D(D'low+pos);
end if;
end loop;
end loop;
return new_crc;
end function;
architecutre の本体を次のようにします。
begin
process(CLK, RST)
variable next_crc : CRC_TYPE;
begin
if (RST = '1') then
curr_crc <= CRC_INIT_BIT;
CRC <= CRC_INIT_BIT;
VAL <= '0';
elsif (CLK'event and CLK = '1') then
if (LOAD = '1') then
next_crc := CALC_CRC(curr_crc, DATA);
if (LAST = '1') then
curr_crc <= CRC_INIT_BIT;
CRC <= next_crc;
VAL <= '1';
else
curr_crc <= next_crc;
CRC <= next_crc;
VAL <= '0';
end if;
else
VAL <= '0';
end if;
end if;
end process;
end RTL;
論理合成結果
前述の３種類の VHDL コードを実際に論理合成してみました。ここではその結果を示します。
論理合成環境
論理合成ツールは Xilinx 社の Vivado 2020.2 を使いました。論理合成時の対象デバイスは、Ultra96 でも使われているxczu3egsbva484-1 です。
| 項目 | 内容 | |
| ツール | ツール名 | Vivado |
| バージョン | v.2020.2 (lin64) Build 3064766 | |
| 動作環境 | Ubuntu 18.04.4 LTS | |
| ストラテジ | 論理合成時 | Vivado Synthesis Defaults |
| 配置配線時 | Performance_Explore | |
| 対象デバイス | デバイス名 | xczu3egsbva484 |
| スピード | 1 | |
なお、論理合成/配置配線時に指定するクロックの周波数は、合成後の slack が負の値にならないような、かつ slack の値が0.1 未満になるような、これ以上速くならないギリギリの値を設定しています。
使用リソース
| ビット数 | 使用リソース (CLB数) | ||
| 単純ループ版 | crcgen生成 | テーブル生成版 | |
| 32 bit | 165 | 175 | 163 |
| 64 bit | 270 | 266 | 275 |
| 128 bit | 652 | 423 | 468 |
| 256 bit | 1019 | 738 | 1019 |
| 512 bit | 1416 | 1337 | 1354 |
| 1024 bit | 2597 | 2396 | 2522 |
| 2048 bit | 7081 | 4414 | 4837 |
| 4096 bit | 9104 | 8927 | |
動作速度
下の表で示す動作周波数は、設定したクロックの周期の逆数です。 配置配線した結果が slack が負にならないようかつ slack が 0.1 未満になるようにクロックの周期を設定したので、単純にこの周波数が最大動作周波数になると思われます。
| ビット数 | 動作周波数 [MHz] | ||
| 単純ループ版 | crcgen生成 | テーブル生成版 | |
| 32 bit | 854 | 847 | 851 |
| 64 bit | 752 | 752 | 751 |
| 128 bit | 641 | 625 | 641 |
| 256 bit | 552 | 552 | 552 |
| 512 bit | 454 | 476 | 476 |
| 1024 bit | 354 | 357 | 354 |
| 2048 bit | 256 | 233 | 256 |
| 4096 bit | 222 | 222 | |
この結果を見てもわかる通り、３種類のどの方法でも動作速度にほとんど違いがありませんでした。
また、どの方法でも、ビット数が増加するにしたがって動作周波数も落ちているのがわかります。
所感
実装方法による性能の比較と昔話
今回紹介した３種類の実装方法では、使用リソース(CLB数)および最大動作周波数に大きな違いはみられませんでした。それならば、比較的記述が簡単な単純ループ版が良いと思います。
今回の記事で、わざわざ性能的にはほとんど差が無い３種類の実装方法を紹介したのには理由があります。何故なら、今でこそ性能に差は見られませんでしたが、昔はそうではなかったからです。
これからは年寄りの昔話になって申し訳ありませんが、私は 2010 年頃、 FPGA で PCI-Express の IP を実装していました。当時、もっとも性能的にボトルネックになったのが PCI-Express の TLP(Transaction Layer Packet) の CRC-32 の演算でした。
当時はまだ PC の性能や論理合成ツールの制約もあって、単純ループ版だと想定していた性能が出ませんでした。『RTL設計スタイルガイド VHDL編 初版』の 「2.9.1 単純な繰り返し以外は for 文を使用しない」にも危険な記述例として for 文を用いたパリティチェック回路が記載されていますが、この CRC 生成回路も同様です。そのため、外部ツールを使って最適化済みの VHDL コードを生成したり、自己最適化テーブルを生成する VHDL を記述する必要があったのです。
しかし、10年以上の時を経て、現在の論理合成ツールはこのくらいの回路なら平気で最適化してしまいます。昔の常識が今の非常識になってしまったわけです。
だからと言って、10年前のあの努力を無駄だと思ったことはありません。今はともかく、当時は持てる手札を全部使わないと達成できない目標だったのですから。
もっと速くするには
この記事で紹介した CRC 生成回路はいずれも、データを入力した時に、それまで計算していた CRC の値を用いて次の CRC の値を計算するものでした。このように、次の演算を行う際に前の演算結果を用いるアルゴリズム は、並列に演算することが出来ません。そのため、ASIC/LSI/FPGA などの論理回路で高速化するのには、適していません。何故なら、並列処理出来ないということはパイプライン処理も出来ないため、論理回路による強味(大量の同時並列処理)が生かせないからです。
2010年当時、PCI-Express の IP 実装時も、結局、今日紹介した何れの手法でもFPGA では目標の転送レート(確か当時は PCI-Express 2.0で 5GBps) を達成することは出来ませんでした。同時に入力するビット数を増やして Bps を稼ごうにも、それ以上に遅延時間を増えてしまったのです。
途方にくれていたころ、CRC 演算を並列処理するアルゴリズムが存在することが分かりました。
- "Pipelined Cyclic Redundancy Check (CRC) Calculation", M. Walma, IEEE Computer Communications and Networks, 2007
次回はこのアルゴリズムの説明します。
参考
- http://github.com/ikwzm/CRC32_VHDL_TEST
- https://github.com/mbuesch/crcgen
- https://ja.wikipedia.org/wiki/巡回冗長検査
- 『RTL設計スタイルガイド VHDL編 初版』 (2003年) STARC 監修
- 『CRC 演算を並列処理するための Walma のアルゴリズムの紹介』 @Qiita