VLSIとは？回路検証アルゴリズムの計算量と、オイラー回路・区間グラフによるレイアウト配置

VLSIとは何か

VLSI(Very Large Scale Integration、超大規模集積回路)とは、数万から数十億個規模のトランジスタを1つの半導体チップ上に集積する技術、およびその設計プロセス全体を指す言葉です。 SSI(小規模集積)・MSI(中規模集積)・LSI(大規模集積)と続く集積度の区分の延長線上にあり、この集積度の指数関数的な成長を経験則としてまとめたのがムーアの法則です。半導体の基礎的な仕組みについては別記事で解説しています。

VLSI設計は、大きく「論理設計(RTL記述からゲートレベルの回路を導くまで)」と「物理設計(ゲートレベルの回路を、実際にシリコン上のトランジスタ配置・配線に変換するまで)」の2段階に分かれます。本記事では、それぞれの段階で登場する代表的なアルゴリズムの問題と計算量を見ていきます。

回路検証はなぜ必要か

設計したチップが、意図した通りに動作するかを製造前に確認する工程が 回路検証(circuit verification)です。製造後に論理設計上のバグが見つかった場合、修正には再度のマスク製作(数億円規模)と数ヶ月単位のリードタイムが必要になるため、検証コストをかけてでも製造前に不具合を潰すことが強く動機づけられています。 1994年に発覚したIntel Pentiumプロセッサの浮動小数点除算バグ(FDIVバグ)は、検証不足が引き起こした実例として広く知られており、Intelは最終的に4億7500万ドルの引当金を計上する事態になりました。

回路検証の中心的な問題の一つが等価性検証(equivalence checking)です。 RTL(レジスタ転送レベル)で書かれた仕様と、それを論理合成して得られたゲートレベルの回路が、あらゆる入力に対して同じ出力を返すかどうかを確認します。

回路検証アルゴリズムの計算量

2つの回路が「等価でない」ことを示すのは簡単です ―― 出力が異なる入力の組を1つ見つければよいからです。しかし「あらゆる入力について等価である」ことを示すには、原理的にはすべての入力の組み合わせを調べ尽くす必要があり、入力ビット数がnであれば2^n通りの組み合わせが存在します。このため一般の回路等価性検証はcoNP完全に分類される問題です。これは、ブール充足可能性問題(SAT、ある論理式を真にする入力が存在するか)が Cook-Levinの定理(1971年)によってNP完全であることの裏返しの関係にあります。

指数爆発を実務上回避するための代表的な手法が、二分決定グラフ (Binary Decision Diagram、BDD)です。Randal Bryant(1986年)が提案した BDDは、ブール関数を変数順序に従ったDAG(有向非巡回グラフ)として正準(canonical)な形で表現する手法で、変数順序が適切であれば多くの実用回路をコンパクトに表現できます (ただし最悪ケースでは依然として指数的なサイズになりえます)。BDDに基づく 記号的モデル検査(symbolic model checking)は、Ken McMillanらによって 1990年前後に発展し、状態空間を明示的に列挙せずに検証する道を開きました。

近年ではむしろ、SATソルバーに基づく限定モデル検査(bounded model checking) (Biereらによって1999年頃に提案)が主流になっています。SAT自体はNP完全問題ですが、実務で現れる制約(構造を持ったブール式)に対しては驚くほど高速に解けるSATソルバーの実装技術が発展したことで、数百万ゲート規模の実回路の検証にも実用的に使われています。

物理設計：オイラー路によるトランジスタ配置

論理設計が完了した後は、実際にシリコン上にトランジスタを並べる物理設計の工程に進みます。 CMOSスタンダードセル(基本論理ゲート)のレイアウトでは、複数のトランジスタを 1本の拡散領域(ソース/ドレイン)を共有する形で一列に並べられると、レイアウト面積を削減できます。この「どの順序でトランジスタを並べれば拡散領域の共有(=分離のための余白の削減)を最大化できるか」という問題は、オイラー路(Euler path)を使って解くことができます。

具体的には、プルアップ網(PMOS)とプルダウン網(NMOS)それぞれについて、トランジスタをグラフの辺、ノードをそれらが接続される信号(拡散領域の接続点)としてグラフを構成します。このグラフにオイラー路(すべての辺をちょうど1回ずつ通る経路)が存在すれば、その経路の順序通りにトランジスタを配置することで、拡散領域の分断 (diffusion break)を一切生じさせずに1列にレイアウトできます。さらに、PMOS側と NMOS側の両方で同じ信号の並び順を持つ共通のオイラー路が見つかれば、ゲート同士の配線も最小化できます。この手法はVLSI物理設計の教科書で「Euler path技法によるセルレイアウト」として広く知られている古典的なアルゴリズムです。

チャネルルーティングと区間グラフモデル

セル同士を配置した後は、それらを配線でつなぐルーティングの工程に進みます。代表的な定式化がチャネルルーティング問題です。2列のセル群の間にある帯状の領域(チャネル)に、複数の配線(ネット)を、互いに交差・短絡させずに敷き詰める問題です。

ここで各ネットは、チャネル内で占める水平方向の区間(左端の列番号から右端の列番号まで) として表現できます。2つのネットが同じ水平トラック(配線層内の1本のレーン)を共有できるのは、それらの区間が重なっていない場合に限られます。この「区間の重なり」の構造は、グラフ理論における区間グラフ(interval graph)そのものです。区間グラフでは、頂点(ここでは各ネット)を区間の重なりに応じて辺で結び、同じ色(トラック)を割り当てられるのは互いに独立な(重ならない)頂点同士だけ、という彩色問題として定式化できます。

区間グラフの彩色数は、その区間グラフの最大クリークサイズ(同時に重なっている区間の最大数、チャネルルーティングではチャネル密度と呼ばれます)に一致することが知られており、区間グラフは完全グラフ(perfect graph)の一種であるため、一般のグラフ彩色問題(NP困難)とは異なり多項式時間で最適解を求められます。実務でよく使われるLeft-Edge法は、各ネットを区間の左端でソートし、貪欲にトラックへ割り当てていくアルゴリズムで、この区間グラフの構造的な性質を利用することで、チャネル密度と同じ本数のトラックで配線を完了できることを保証します。

まとめ

VLSIは数十億個規模のトランジスタを1チップに集積する技術で、設計は論理設計と物理設計に大別される
回路の等価性検証は一般にcoNP完全であり、SATがNP完全であることの裏返しの関係にある
BDD(1986年、Bryant)は正準なブール関数表現として記号的モデル検査を可能にし、近年はSATソルバーに基づく限定モデル検査が主流である
CMOSスタンダードセルのトランジスタ配置は、プルアップ/プルダウン網のグラフにオイラー路を見つける問題として定式化でき、拡散領域の共有を最大化できる
チャネルルーティングにおけるネットのトラック割り当ては区間グラフの彩色問題であり、区間グラフは完全グラフであるため多項式時間で最適解(チャネル密度)を求められる