組み合わせ論理とルックアップテーブル

FPGAがデータに対して行うすべてのことは、2種類の回路から組み立てられています。メモリを持たず、入力が落ち着くとすぐに出力を生成する論理と、次のクロックエッジまで値を保持するレジスタです。本レッスンでは前者、すなわち組み合わせ論理と、それを実装するハードウェア要素であるルックアップテーブルを扱います。前提はレッスン01を読んでいることだけです。レッスン04でレジスタを扱います。

ブール関数と真理値表

組み合わせ回路は、入力ビットの集合を出力ビットの集合に写像し、過去に起きたことには一切依存しません。同じ入力を与えれば、短い遅延の後、毎回同じ出力が得られます。その背後にある数学はブール代数で、3つの基本演算があります。AND（すべての入力が1のときだけ出力1）、OR（いずれかの入力が1なら出力1）、NOT（反転）です。派生演算が2つ頻繁に登場します。XOR（1である入力の数が奇数なら出力1）と、後述するマルチプレクサです。

ブール関数を記述する最も直接的な方法は、あり得るすべての入力に対する出力を列挙することです。その一覧が真理値表です。n入力の関数では2のn乗行になります。次は3入力関数の例で、多数決関数と呼ばれ、入力のうち少なくとも2つが1のときに出力が1になります。

a	b	c	多数決
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

出力列を上から下へ読むと、8ビットの文字列00010111が得られます。この文字列が関数そのものです。他のどの3入力関数も別の8ビット文字列であり、文字列は2の8乗、すなわち256通りあるので、異なる3入力ブール関数はちょうど256個存在します。式で書けば多数決は(a AND b) OR (b AND c) OR (a AND c)ですが、表と式は同じ情報を持っています。

この観察が本レッスン全体の鍵です。n入力のブール関数は、2のn乗ビットの文字列にほかなりません。その文字列を格納し、入力をアドレスとして1ビットを選び出せれば、関数を実装したことになります。

ルックアップテーブル

ルックアップテーブル（LUT）はまさにそれです。アドレス線が関数の入力で、格納内容が真理値表の出力列である小さなメモリです。4入力LUTは16ビットのメモリで、65,536通りの関数のどれでも実装できます。6入力LUTは64ビットのメモリで、2の64乗、約1,800京通りの関数のどれでも実装できます。内容はビットストリームの読み込み時に一度だけ書き込まれ、その後LUTはコンフィギュレーションが続く限り純粋な組み合わせ論理として振る舞います。

図を例で追ってみましょう。入力がa=1、b=0、c=1、d=1だとします。マルチプレクサの第1列はdを使って各ペアの奇数番目のビットを選び、第2列はcを使ってペア間を選び、第3列はbを、最後のマルチプレクサはaを使います。全体としてアドレス1011、すなわち0から数えて表の11行目のビットが選ばれます。XORの例では、4入力のうち3つが1なので、そのビットは1です。回路は答えを計算したのではなく参照したのであり、遅延はどの関数でも同じで、最近のデバイスでは通常数百ピコ秒です。

設計者にとっての帰結は次のとおりです。

• LUTは関数がどれだけ複雑かを気にしません。6入力XORも6入力ANDも同じコストです。LUT1個、遅延1段。
• 7入力以上の関数には複数のLUTが2段以上必要で、段が増えるごとに遅延が加わります。12入力の関数には、2段に並べた6入力LUTが少なくとも3個必要です。経路の速度を決めるのは、頭の中で想像するゲート数ではなく、経路上のLUT段数です。
• LUTの入力数より少ない入力しか持たない関数は、余った入力を無駄にします。最近のデバイスが1つの6入力LUTを、入力を共有する2つの5入力LUTに分割できるのはこのためです。

AMDの7 Series以降のデバイスは6入力LUTを使います。AlteraのStratix、Arria、Cyclone、Agilexファミリーは、1つの6入力LUTまたはより小さな2つのLUTとして振る舞うアダプティブロジックモジュールを使います。Lattice iCE40とECP5は4入力LUTを使うため、ECP5の「LUT数」はArtix 7のそれと直接比較できません。大まかな目安として、6入力LUT1個は4入力LUT約1.5〜2個分の働きをします。

キャリーチェーン

加算は、LUTが苦手とする唯一の関数です。4ビット加算器の最上位の和ビットは8本の入力ビットすべてに依存し、32ビット加算器の最上位ビットは64本すべてに依存するため、多段のLUTが必要になります。そのため、すべての論理ブロックには専用のキャリーチェーンが含まれています。汎用配線を通らずに、各ビット位置から次の位置へキャリーを渡す、高速で幅の狭い経路です。和の各ビットは1個のLUT（プロパゲート信号とジェネレート信号を計算）と1個のキャリーセルを使い、キャリーは1ビットあたり数十ピコ秒でチェーンを上っていきます。Artix 7の32ビット加算器は縦に積まれた8スライスに収まり、約2 nsで加算します。

+、-、比較、カウンタを書くと合成が自動的にキャリーチェーンを見つけるので、名前で言及することはめったにありません。インプリメント済みの設計では論理セルの縦の列として見え、カウンタや加算器がフロアプラン上で縦一直線に配置される理由でもあります。

マルチプレクサ

2対1マルチプレクサ（mux）は、選択ビットに従って2つの入力のうち1つを選びます。out = sel ? b : a です。入力は3本なので、どのLUTにも余裕で収まります。4対1 muxは入力が6本（データ4本、選択2本）で、1つの6入力LUTに収まります。8対1 muxには6入力LUT2個に加えて、AMDがこの目的のためにすべてのスライスに置いている専用のmuxプリミティブが必要です。

muxが重要なのは、HDLのすべてのifとすべてのcaseがmuxになるからです。4つのソースのいずれかから読み込む32ビットレジスタは32個の4対1 mux、つまり32個のLUTです。32ビットの結果に対する16分岐のcase文は32個の16対1 mux、約160個のLUTです。初心者の設計が静かに大きくなるのはmuxのせいです。

VerilogとVHDLの組み合わせ論理ブロック

次は、加算器（キャリーチェーン）とmuxを使う、小さく完全で合成可能なモジュールです。2つの4ビット入力aとb、および選択ビットを受け取ります。selが1のとき出力は5ビットの和です。selが0のとき出力はaを5ビットにゼロ拡張したものです。両方のバージョンが同じハードウェアを記述しています。

module add_or_pass (
  input  wire [3:0] a,
  input  wire [3:0] b,
  input  wire       sel,
  output wire [4:0] y
);
  wire [4:0] sum = {1'b0, a} + {1'b0, b};
  assign y = sel ? sum : {1'b0, a};
endmodule

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity add_or_pass is
  port (
    a   : in  std_logic_vector(3 downto 0);
    b   : in  std_logic_vector(3 downto 0);
    sel : in  std_logic;
    y   : out std_logic_vector(4 downto 0)
  );
end entity;

architecture rtl of add_or_pass is
  signal sum : unsigned(4 downto 0);
begin
  sum <= resize(unsigned(a), 5) + resize(unsigned(b), 5);
  y   <= std_logic_vector(sum) when sel = '1' else '0' & a;
end architecture;

レッスン05で本格的に展開する注目点は次のとおりです。

• クロックがありません。モジュール内のすべてが連続代入（Verilogではassign、VHDLではプロセスの外に裸で書く<=）なので、出力は伝搬遅延の後に入力に追従します。それが組み合わせ論理の特徴です。
• どちらのバージョンも加算の前にオペランドを5ビットに広げており、ビット3からのキャリーアウトが失われずに結果のビット4になります。Verilogでは連結で、VHDLではresizeでこれを行います。この余分な1ビットを忘れるのが、最もよくある加算器のバグです。
• VHDLでは、加算する前にベクタが数値（unsigned）であると宣言しなければなりません。Verilogは、指定がない限りすべてのベクタを符号なし数として扱います。どちらも妥当な選択であり、どちらも人を引っかけます。

合成は、加算器にLUT4個とキャリーセル4個、次に5ビットの2対1 muxにLUT5個を生成し、良いツールはmuxを加算器のLUTに統合して全体をLUT5個とキャリーチェーン1本にします。数は合成レポートで確認できます。

シミュレーションのレッスンを読む前にIcarus Verilogで動かせるよう、Verilog版の短いテストベンチを示します。#1の遅延は、シミュレーション上で組み合わせ論理が落ち着く時間を与えるためのものです。シミュレータでは時間が進まなければ何も起きません。

`timescale 1ns/1ps
module add_or_pass_tb;
  reg  [3:0] a, b;
  reg        sel;
  wire [4:0] y;

  add_or_pass dut (.a(a), .b(b), .sel(sel), .y(y));

  initial begin
    a = 4'd9; b = 4'd7; sel = 1'b1; #1;
    if (y !== 5'd16) $display("FAIL: 9 + 7 gave %0d", y);
    sel = 1'b0; #1;
    if (y !== 5'd9) $display("FAIL: pass-through gave %0d", y);
    a = 4'd15; b = 4'd15; sel = 1'b1; #1;
    if (y !== 5'd30) $display("FAIL: 15 + 15 gave %0d", y);
    $display("done");
    $finish;
  end
endmodule

iverilog -g2012 -o add_or_pass.vvp add_or_pass.v add_or_pass_tb.vに続けてvvp add_or_pass.vvpで実行します。doneだけが表示されるはずです。

グリッチと、組み合わせ出力をそのまま信用してはいけない理由

次のレッスンに進む前に、組み合わせ論理のもう1つの性質が重要です。入力が変化すると、論理を通る異なる経路が異なる時刻に落ち着き、数百ピコ秒の間、出力は正しい値を取る前に誤った値を取ることがあります。この過渡的な変化をグリッチと呼びます。出力が別のLUTに入るなら無害です。2つ目のLUTも落ち着くからです。出力がクロックやリセットとして使われるなら危険です。クロック上のグリッチは余分なクロックエッジに見えるからです。ここから導かれる「論理からクロックを駆動してはならない」という規則は、レッスン04の同期設計の規則の1つであり、レジスタは、明確に定義された瞬間にだけサンプリングすることでグリッチを隠す素子です。

演習

1. 4入力関数「入力のうちちょうど2つが1」の16ビット真理値表を（アドレス0000を先頭とするビット列として）書いてください。含まれる1の数を数えてください。
2. 9入力の関数を6入力LUTで実装します。実現できる最小のLUT数はいくつで、クリティカルパスは何段のLUTを通りますか。理由も述べてください。
3. add_or_passを、selが0のときパススルーではなく5ビットの差a - bを出力するように変更してください。両言語の版を一致させたまま、テストベンチを9引く7と7引く9を検査するように更新し、2つ目の結果が5ビットでどう見えるかを書き留めてください。

まとめ

• n入力のブール関数は、2のn乗ビットの真理値表で完全に記述されます。
• LUTはその真理値表をコンフィギュレーションメモリに格納し、muxツリーで1ビットを選びます。4入力LUTは16ビット、6入力LUTは64ビットで、どちらも入力の任意の関数を1段の遅延で実装します。
• LUTより幅の広い関数には複数の段が必要で、段数が遅延を決めます。ゲートではなく、異なる入力を数えてください。
• 専用のキャリーチェーンが、加算器、減算器、比較器、カウンタを高速にします。合成は+、-、比較に対して自動的にそれを使います。
• すべてのifとcaseはマルチプレクサになり、幅の広いデータに対する幅の広いmuxが設計を大きくします。

さらに読む

• AMD UG474, 7 Series FPGAs Configurable Logic Block User Guide: 大半の入門ボードで使われるデバイスのLUT6、キャリーチェーン、muxプリミティブ。
• AMD UG901, Vivado Design Suite User Guide: Synthesis: 合成が加算器、mux、メモリとして認識するHDLパターン。
• Yosys manual: abcとsynth_*コマンドは、オープンソースツールが論理をLUTに割り当てる方法を示します。
• IEEE 1364-2005, Verilog Hardware Description LanguageとIEEE 1076-2019, VHDL Language Reference Manual: 言語規格。