VLSI設計工学２ • ２分決定グラフ（Binary Decision Diagram, BDD） – 論理関数の計算機上でのコンパクトな表現と効率的な処理を実現するデータ構造 – VLSI用CADのうち、論理関数処理を行うものには広く利用されている – CAD以外への応用も進んでいる論理式の記法 • 論理変数は、基本的にアルファベット１文字か、アルファベット１文字に数字を付加したもの • 論理積は、省略する • 論理和は「＋」 • 否定は、否定を取るべき式の最後に「‘」を付けるか、アッパーラインを引く • 排他的論理和は「＠」であらわす２分決定グラフ（Binary Decision Diagram, BDD）とは？ • 真理値表は、２分決定木で表現できる • ２分決定木で、根から葉に至るすべてのパスで同じ変数順を使用する • 同型のサブ木を共有できる（グラフになる） • 論理関数の正規表現（Canonical form） – 論理関数が等価であれば、同型のグラフになる • 多くの実用的な論理関数をコンパクトに表現できる２分決定グラフ（Binary Decision Diagram, BDD）とは？ Removal of equivalent nodes X1 X2 X2 X3 0 X3 1 0 X3 1 0 X3 1 1 1 Removal of redundant nodes X1 0 X2 X2 X3 X3 1 X1 X2 X3 0 1 順序付BDDとFree BDD • 根から葉へのすべてのパスで同じ変数順ではなく、パスごとに異なる変数順→Free BDD • どのパスでどういう変数順を使うかを前もってきめていれば、論理関数の正規形という性質は保存される X1 X1 0 1 0 X2 X2 1 0 0 1 1 1 0 X5 0 0 1 OBDD X3 1 1 0 X4 0 1 X4 0 0 X5 0 X3 0 X4 1 0 1 X4 0 0 X3 1 X2 1 1 X4 0 1 X3 0 0 X2 0 X3 1 1 1 FBDD 1 1 BDDの例 x1 x2 x3 4x x1 + x2 + 3x + 4x x1 x1 x2 x1 x2 x3 x3 x4 x4 1 0 0 (a) And 1 (b) Or x1 + x2 + 3x + 4x x2 x2 x3 x3 x4 x4 0 1 (c) Ex-Or セレクタ関数に対応するBDD s2 s1 s0 s1 s0 s0 s0 d0 d1 d0 d1 d2 d3 Out d4 d7 d5 d6 d7 s0 s1 s2 0 1 BDD間の論理演算（apply演算） • h = f ◇ g = v’(fv=0 ◇ gv=0) + v(fv=1 ◇ gv=1) 1. fかgが定数の時やf=g, f=g’の時は、対応する演算を実行する例： f・0 = 0, f + f = f, f @ 1 = f’, … 2. fの変数とgの変数が同じならば、新しいノードを生成し、 h0←f0◇g0, h1←f1◇g1 とする 3. Fの変数がgの変数よりも順序が先ならば、新しいノードを生成し、 h0←f0◇g, h1←f1◇g とする Apply演算の例 x1 x1 x 2 + x3 x1 x1 x2 x3 x1 x 2 1 0 AND OR 0 x1 x2 x2 x3 0 1 x2 x3 0 1 0 1 1 複数の論理関数でBDDを共有：共有２分決定グラフ（Shared BDD） X2 1 0 x1’+x2 x1’ x1@x2 x1x2 X2 0 X2 0 1 1 X1 1 0 0 1 X1 0 1 否定エッジ x2 x1 x2 x2 0 x1 1 x1 x2 x2 0 0 1 0 0 x2 x2 1 1 x1 1 x1 x1 0 0 1 1 0 x1 BDDの大きさは、使用する変数順に大きく依存 X1 X2 X3 X4 X5 X6 Worst 1 0 Best 3 0 1 1 3 1 0 0 5 2 0 0 5 1 0 5 0 1 3 1 2 4 0 0 1 4 1 4 1 2 0 1 1 0 0 1 1 6 0 0 0 5 0 5 1 2 0 0 1 1 6 1 1 0 0 1 0 1 2 1 BDDの変数順決定最適変数順決定は、NP完全問題 • ヒューリスティックにおける基本的な考え方 – 互いに関連する変数は近づける – 制御系の変数は前にもってくる s2 s1 s0 s1 s0 s0 s0 d0 d1 d0 d1 d2 d3 Out d4 d7 d5 d6 s0, s1, s2は制御変数 d7 s0 s1 s2 0 1 BDDの変数順決定 • 回路から変数順の決定のためのヒューリスティックの考え方 – 回路を深さ優先で出力から入力へ辿る – 入力数の多いゲートを優先する – ファンアウト数の多いゲートを優先する x0 x1 x2 x3 x4 Depth first traversal: x0, x1, x2, x3, x4 or x2, x3, x0, x1, x4 (with fanout consideration) 変数順の改良 • 隣り同士の変数の交換はそこだけつなぎかえればよい i-1 (A) i+1 (B) i+1 i f1 i-1 i-1 (C) i+1 i f3 i f2 i-1 (D) i+1 (A) i i i+1 f4 f1 (B) i-1 i i-1 i i+1 f2 (E) i+1 (D) f3 f4 • これを繰り返せば、任意の変数順へ変更できる • よく使われるヒューリスティック – 隣同士の２，３，４変数間での交換 – 各変数を最初から最後まですべて移動し、最適なところに置く（siftヒューリスティック）回路からBDDの生成 X1 X2 X2 0 X2 1 1 X1 0 0 X2 X1 1 1 1 0 1 1 1 X1 0 0 0 0 X2 1 1 0 X2 0 0 X1 0 0 1 X1 1 0 0 1 0 1 1 1 X1 0 1 BDDの計算機上での表現変数０エッジ１エッジ 0 1 2 3 4 5 6 ーーーーーー１０１１１０２０３２２３２２１ ← ← ← ← ← ← ← ０１ x1 x1’ x2x1’ x1 @ x2 x1’ + x2 回路からBDDを生成するもう１つの方法 • BDDを入力から出力へ順に作っていくと、途中で BDDが大きくなりすぎることがある • そこで、ある程度大きくなったら、そこで回路を仮に切断し、そこから先は新たな変数を導入して、 BDDを作っていく • 回路の出力のBDDが作れたら、先ほど導入した変数をcompose演算で取り除く • Applyでうまくいかない時でも、BDDを作成できることも多い回路から、applyに基づくBDDの生成 X1 X3 X4 X5 X2 X3 X4 0 X3 X1 X1 X4 1 X2 X5 0 X1 X3 1 X3 X4 X3 X4 X5 1 X2 X4 X5 0 0 X5 1 1 0 新規中間変数の導入 Cut here and introduce an intermidiate var: t X1 X3 X X4 X5 X2 X2 0 X2 1 1 X1 0 0 X2 X1 1 1 1 0 1 1 1 X1 0 0 0 0 X2 1 1 0 X2 0 0 X1 0 0 1 X1 1 0 0 1 0 1 1 1 X1 0 1 Compose 演算の実行 t X1 X1 X3 X2 X2 X4 = composed with t X3 X5 X4 1 0 0 1 X5 1 0 宿題 • 次の関数の２分決定グラフ（BDD）を作成して、図示せよ。ただし、変数順はx1, x2とする – F1 = x1・x2’ + x1’・x2 – F1 = x1’・x2’ + x1・x2 • 次の関数を２分決定グラフで表現したときに、ノード数が最大となる変数順と、最少となる変数順の例を示せ。 – F3 = x1・x2・x3・x4 + x5’・x6’・x7’・x8’