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 x4 x1 + x2 + x3 + x4 x1 x1 x2 x1 x2 x3 x3 x4 x4 1 0 0 (a) And 1 (b) Or x1 + x2 + x3 + x4 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 OR AND 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 • これを繰り返せば、任意の変数順へ変更できる • よく使われるヒューリスティック – 隣同士の２，３，４変数間での交換 – 各変数を最初から最後まですべて移動し、最適なところに置く（shiftヒューリスティック）回路から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 X3 X3 0 1 X1 X4 X4 0 X1 X1 X5 t 1 1 0 X2 X2 t t 0 1 1 0 Compose 演算の実行 t X1 X1 X3 X2 X2 X4 = composed with t X3 X5 X4 1 0 0 1 X5 1 0 BDDの拡張 • Multi-Terminal BDD (MTBDD) • Binary Moment Diagram (BMD) • Hybrid Decision Diagram (HDD) • … (すべてのアルファベットから始まる□DDというものが提案されている！） Multi-Terminal BDD (MTBDD) • 定数ノード（葉）を０，１だけではなく、任意の有限集合の要素を認めるようにする • BDDの基本的な性質（正規表現、apply演算など各種アルゴリズム）は保存される x1 x2 1 x1 x2 0 1 x2 3 x2 5 6 ベクトルや行列のMTBDDによる表現 • ベクトルや行列のインデックスを０，１の２値変数で表現する • ０からn-1までのインデックスは、 x1,x2,…,xlognで表現できる x1 x2 3 4 [3 3 3 4] MTBDDによる行列の操作 • x変数で行をｙ変数で列を表現する • 与えられた行例Mは次のように表現できる Mx1’y1’ Mx1’y1 M= Mx1y1’ Mx1y1 • Apply演算で行列の操作ができる x1 x1 + (plus) x2 3 4 [3 3 3 4] x1 x2 0 = 2 [0 2 2 2] x2 3 x2 5 [3 5 5 6] 6 内積の計算 • 各列ごとの内積（和）の計算 – Σy1y2…ymM(x, y1, y2, …, ym) = Σy1y2…ym-1ΣMym (x, y1, y2, …, ym) = Σy1y2…ym-1(M (x, y1, y2, …, 0) + M (x, y1, y2, …,1)) • ベクトルのソート – すべての定数は葉にある→葉の値をソート • 行列の掛算 – C(x, z) = ΣyA(x, y)・B(y, z) • すべてMTBDD上の演算として計算できる応用例：論理関数のスペクトル解析 • 論理関数解析の手法、フーリエ級数展開を論理関数上で行う • Walshスペクトル – 定数０関数との差（真理値表で同じ値の要素数から異なる値の要素数を引いたもの）：０次 – 関数x1との差：１次 – 関数x1 @ x2との差：２次 – ．．． • 閾値関数は、０次と１次だけのスペクトル値で判別できる Walshスペクトル解析の例 • 例： x1 + x2x3 • 真理値表で０はそのまま０、１は－１に置き換える 1 1 1 1 1 1 1 1 1 –1 1 –1 1 –1 1 –1 1 1 -1 –1 1 1 –1 -1 1 –1 -1 1 1 –1 –1 1 1 1 1 1 –1 –1 –1 -1 1 –1 1 –1 –1 1 –1 1 1 1 -1 –1 –1 –1 1 1 1 –1 -1 1 –1 1 1 -1 X3 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 1 -1 1 -1 1 -1 -1 -1 x1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 -1 1 -1 1 -1 -1 -1 = -2 6 2 2 2 2 -2 -2 Walshスペクトル解析結果の意味 -2 6 2 2 2 2 -2 -2 ーーーーーーーー０次：１次：１次：２次：１次：２次：２次：３次：定数０関数との差関数x1との差関数x2との差関数x1 @ x2との差関数x3との差関数x1 @ x3との差関数x2 @ x3との差関数x1 @ x2 @ x3との差 • 従来手法は、真理値表の要素ごとに１つずつ計算 – 大きな論理関数には適用不可能 Walsh行列は再帰的に定義可能 • Walsh行列 Wn: W1 = 1, Wn = Wn-1 Wn-1 Wn-1 －Wn-1 xn yn Wn-1 -Wn-1 Walshスペクトル解析の例 1 1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 1 -1 1 1 -1 X 1 -1 -1 -1 -1 1 1 1 0 0 0 0 -4 4 4 4 = x1 y1 x2 x2 y2 y2 y2 y3 -1 1 x3 x3 y3 y3 -1 y1 y1 1 -1 -1 y3 -1 0 y2 y2 y3 1 1 -4 4 4 Binary Moment Diargam (BMD) • 展開規則の変更 f = f0 + x fd ただし、fd = f1 – f0 • MTBDDでは大きくなる関数でもBMDでコンパクトになるものがある – 例：掛算器 xi xi 0 1 0 fxi=0 fxi=1 fxi=0 MTBDD 1 fxi=1 - fxi=0 BMD MTBDDとBMDの比較例 • Σ2i=0 xi・2iという関数の表現 x2 x2 x1 x0 x1 x1 x0 x0 x0 x0 4 2 BMD 0 1 2 3 4 MTBDD 5 6 7 0 1