Random Note

WireWorld Compiler — HDLからセルオートマトンへのコンパイラを作った

概要

wwc (WireWorld Compiler) は、Verilog で記述したデジタル回路をセルオートマトン（CA）上で動作するパターンへ自動コンパイルする実験的コンパイラです。 Yosys で論理合成した回路を、独自の CA ルール WireLevel 上に配置・配線し、最終的には GPU（WebGPU / Rust wgpu）上で高速にシミュレーションできます。

現在は SM83 CPU（ゲームボーイの LR35902）のサブセット（380 ゲート） のコンパイルに成功し、20 命令の動作を GPU 上で検証済みです。

なぜ作ったか

元々は Conway の WireWorld ルールをターゲットにしていましたが、WireWorld には本質的な制約がありました。 パルス方式の信号伝搬に起因する「バックファイア」（junc3 発火時の逆流）と、1 世代精度の厳密なタイミング制約が順序回路のスケールを阻んでいました。

そこで新たに WireLevel という独自 CA ルールを設計しました。

WireLevel の設計

WireLevel は以下の特徴を持つ、51 状態のセルオートマトンです：

  • レベル駆動（level-driven）: 各セルが bool 値を保持。グリッチは実ハードウェア同様に自然収束し、静的タイミング解析が不要

  • pull 型有向配線: 信号は一方向にのみ伝搬。逆流が構造的に不可能で、WireWorld 最大の問題だったバックファイアが根絶される

  • 専用 Cross セル: 配線交差が 1 セルで実現され、配線輻輳がほぼ消滅

  • 専用 DFF セル: クロック立ち上がりエッジで d → q のラッチを行う順序回路プリミティブ

コンパイラパイプライン

全体は F# (.NET 8) で実装され、Railway-oriented pipeline（各段が Result<T, Error> を返し bind で連結）で構成されています。

Verilog (.v)
  │  Yosys: read_verilog → synth → abc -g NAND → write_json
  ▼
Yosys JSON
  │  parseYosysJson
  ▼
Netlist (ゲートリスト)
  │  placeWL: 正方格子配置
  ▼
配置済みグリッド
  │  routeWL: A* BFS による配線
  ▼
配線済みグリッド
  │  balanceClockNet: クロックツリー均等化
  │  emitWL: バイトグリッド出力
  ▼
WireLevel Grid (.bin)
  │  WebGPU (WGSL) / Rust wgpu (Vulkan)
  ▼
GPU シミュレーション実行

成果

SM83 CPU のコンパイル

SM83 CPU（ゲームボーイの LR35902）のサブセット（380 ゲート、約 26.5 万セル）のコンパイルに成功。 NOP、LD、ADD、ADC、SUB、SBC、AND、OR、XOR、CP、INC、DEC、RLCA など 20 命令の動作を検証し、全フラグ（Z/N/H/C）のキャリー連鎖・ボローを含めて 20/20 PASS しました。

GPU 高速実行

WebGPU (WGSL) と Rust wgpu (Vulkan) の両方で GPU 実行を実現。 RTX 3060 環境でのベンチマークでは、F# リファレンス実装と比較して最大 280 倍の高速化を達成しています。

  • SM83 cyc0-high（13.9 万セル、2000 step）: 0.41 秒（F# 比 280x）

  • mincpu-clk1（10.5 万セル、3500 step）: 0.39 秒（F# 比 205x）

技術スタック

層 技術

コンパイラ言語

F# (.NET 8)

論理合成

Yosys

CA ルール

WireLevel (独自設計、51 状態)

データ構造

疎グリッド (Map<Coord, CellState>)

型システム

Units of Measure (世代を型安全に管理)

シミュレーション

F# リファレンス + WebGPU (WGSL) + Rust wgpu (Vulkan)

ビルド

dotnet CLI + Nix flake

可視化

Golly RLE / WebGPU Canvas / HTML デモ

今後の展望

残る大きなマイルストーンは ゲームボーイエミュレータへの統合 です。 バス・割り込みブリッジを実装し、CA 上で動く SM83 を実際のエミュレータに組み込むのが最終目標です。

また、SM83 フルセット（全命令対応）への拡張や、より大規模な回路（乗算器など）のコンパイルにも取り組んでいく予定です。

リポジトリ

github.com/m4k070/wwc — MIT ライセンス。 開発環境は nix develop で起動可能です。