Conwayのライフゲームで学ぶFPGAエンコーディング選択の実践ガイド

FPGA設計に最適なエンコーディングを選択する方法を、3つの実験を通じて解説

FPGAロジック設計時、合成ツールが通常エンコーディングを選択しますが、一般的にその判断を信頼するのがベストです。しかし、バイナリ、グレイ、ワンホット表現のニュアンスを理解しておくと、コンパイラがいつどのエンコーディングを好むかを予測できます。

本記事では、Conwayのライフゲームをテストベンチとして用いた実践実験を通じ、大規模な有限状態マシン（FSM）アレイに各エンコーディングを適用した際に生じるトレードオフをハイライトします。

このシリーズでは、VerilogでのFSM構築、初期状態とメモリがエンコーディングに与える影響、バイナリ・ワンホット・グレイ方式の高レベル比較をカバーしてきました。

テスト対象システム

ハードウェアの差を拡大するため、23×23グリッド上にステートマシンを数十回インスタンス化し、バイナリ、グレイ、ワンホットエンコーディングを直接比較できるようにしました。

Conwayのライフゲームは、長方形の2次元格子上でのセルの誕生、生存、死をモデル化する古典的なセルラーオートマトンです。各セルは各サイクルで以下の3つのシンプルなルールに従います：

1. 生存セルで、生存隣接セルが2つまたは3つの場合、生存継続
2. 死滅セルで、生存隣接セルが3つの場合、生存セルになる
3. その他のすべてのセルは死滅または死滅状態を維持

これらのルールから豊かな創発パターンが生まれ、エンコーディング戦略の評価に適した、明確でよく理解されたワークロードを提供します。

以下は、ライフゲームで人気のパターンであるBill GosperのグライダーガンのGIFです。

Conwayのライフゲームのバリエーション、Bill Gosperのグライダーガン。Lucas Vieira作 [CC BY-SA 3.0]

Verilogコード

セルロジックは8状態FSMとしてモデル化。ライフゲームのセル単位計算は1サイクルで完結しますが、8状態設計によりエンコーディング間の顕著な差異が生まれます。以下のVerilogモジュールは元のバイナリエンコーディングを示します。

`define STATE_0 3'b000
`define STATE_1 3'b001
`define STATE_2 3'b010
`define STATE_3 3'b011
`define STATE_4 3'b100
`define STATE_5 3'b101
`define STATE_6 3'b110
`define STATE_7 3'b111

module LifeCell( input clk, input nrst, input seed, input [7:0] neighbors, output reg alive); reg [2:0] state; always @ (posedge clk) if (nrst == 0) state <= `STATE_0; else case(state) `STATE_0: begin // ... state <= `STATE_1; end `STATE_1: begin // ... state <= `STATE_2; end // ... `STATE_7: begin // ... state <= `STATE_1; end endcase endmodule

コードの詳細を知りたい方は、GitHubでフルプロジェクトを公開しています。

FPGAエンコーディング実装

設計は23×23セルグリッドで合成され、27の異なる実装が生成されました：3つのFSMバリエーション、それぞれをバイナリ、グレイ、ワンホットエンコーディングでコンパイル、3つのターゲットFPGAで実施。

FSM #1: オリジナルモデル

このFSMは初期状態を1回実行後、残り7状態を巡回—グレイエンコーディングが有利そうなシーケンスです。

FSM #2: シーケンス

シンプルな3ビットカウンタとして動作し、グレイエンコーディングの優位性をさらに裏付ける期待を強めました。

FSM #3: 任意のタングル

このバリエーションはFSM #1とクリティカルパスを共有しますが、隣接数が3を超えると非線形ルートを取ります。こうした不規則な遷移にはワンホットエンコーディングが自然な適合と思われました。

ターゲットアーキテクチャ

実装は以下のベンダーツールチェーンで構築：

• Xilinx Vivado Suite on Artix-7 FPGA
• Intel Quartus Prime on Cyclone-V FPGA
• Lattice Diamond on LatticeXP2 FPGA

結果の比較

FPGA設計のベンチマークは本質的にメトリクス駆動です。ロジックリソース使用量、レジスタ数、推定最大周波数、オンチップ電力の4つの主要指標を選び、重み付けスコアを割り当てました。各指標で最高性能は+1（重み付け指標は+2）、最低は-1（重み付け指標は-2）、中間は0としました。

• ロジックユニット: LUT（Xilinx/Lattice）またはALM（Intel）。重み1。
• レジスタ: 重み1。
• 最大周波数: 重み2。
• オンチップ電力: 重み2。

27実装すべての累積スコアを以下に示します。

全27実装の結果テーブル。緑が最良エンコーディング、赤が最悪、黄が中央値（タイなし）。

全体的にワンホットエンコーディングは下位2行に現れ、他方式と同等だったのはわずか2ケースのみ。対照的に、グレイエンコーディングが一貫してトップパフォーマーとして浮上、特に周波数と電力を重く重み付けした場合に顕著です。

勝者をハイライトするため、各バリエーションの主要エンコーディングを隔離したテーブルを以下に示します。

結論

データはこの特定のライフゲームワークロードではグレイエンコーディングに傾いていますが、結果はどのメトリクスを優先するかに依存します。リソース使用量をパフォーマンスより重視すれば、異なるランキングが浮上する可能性があります。ここでの目的は、万能ルールを処方することではなく、実証的エビデンスがいかにエンコーディング選択を導けるかを示すことです。

ソースコード、27の合成実装、ライブライフゲームシミュレーションは、プロジェクトのGitHubリポジトリで自由に探索できます。