講演する湊真一氏 Tech\-On!が撮影。
講演する湊真一氏
Tech-On!が撮影。
[画像のクリックで拡大表示]
図1●BDD 湊氏のスライド。
図1●BDD
湊氏のスライド。
[画像のクリックで拡大表示]
図2●圧縮したBDD同士の演算が可能 湊氏のスライド。
図2●圧縮したBDD同士の演算が可能
湊氏のスライド。
[画像のクリックで拡大表示]
図3●論理式と組み合わせ集合 湊氏のスライド。
図3●論理式と組み合わせ集合
湊氏のスライド。
[画像のクリックで拡大表示]

 等価性検証やモデル・チェッキング,論理合成/最適化,テスト・パターン自動生成など,さまざまなEDAツールで基盤技術として使われているBDD(binary decision diagram)。BDDはグラフ理論のグラフ構造を使って,論理式を表現したり,演算したりするための技術である。そのBDDの進化形や,EDA以外の分野への展開について,北海道大学の湊真一氏(大学院情報研究科 教授)が語った。

 同氏は,「DAシンポジウム2011」(情報処理学会 システムLSI設計技術研究会が8月31日と9月1日に岐阜県で開催)の招待講演で登壇した(写真)。EDA分野では,BDDは論理機能や論理式を表現したり,演算したりするのに使われてきた(図1)。表現する対象に規則性があったり,スパース性があったりすると,BDDは圧縮が可能で,メモリを節約できたり,演算時間が短くなったりする。うまくいくと,o(2n)のBDDが,o(n)のBDDに圧縮できる(nは変数の個数。)。

圧縮したままで演算可能

 湊氏によればBDDは1950年代からある技術だが,EDAツールに実際に使われるようになったのは,米Carnegie Mellon University教授のRandal Bryant氏が1986年に発表したBDDの演算手法が登場してからである。Bryant氏は,展開することなしに,圧縮されたBDD同士を直接に論理演算する手法を編み出した(図2)。この手法はデータが計算機の主記憶に収まる限りは,データ量にほぼ比例する時間で演算ができるという特徴がある。半導体プロセスの微細化によるDRAMの大容量化に支えられて,論理を扱う多くのEDAツールでBDDは実用化された。

 こうして1990年代にEDAツールでBDDが実用化されたのと時を合わせて,研究対象としての魅力が下がっていったという。ただし,BDDが完全に研究者の興味から外れたのかというと,そうではなかった。BDDは基盤技術であり,それに少し工夫を加えると,さまざまな分野へ展開できそうなことが分かってきた(新天地を求めた,とも言える)。

 BDDの進化形の1つが,湊氏自身が1993年に開発したZDD(Zero-suppressed BDD)である。オリジナルのBDDでは論理式を対象にしていたが,ZDDでは「組み合わせ集合」(combinatorial itemset)を扱う。

 ここでいう,「組み合わせは」,昔,学校で習った「順列,組み合わせ」の組み合わせと同じである。例えば,商店に多数の種類の品物があり,お客Aは品物aと品物bを,お客Bは品物aと品物cを,お客Cは品物cだけを買ったとする。各お客の買った品物のセットが組み合わせで,その組み合わせの集合が,組み合わせ集合となる(図3)。