2分決定グラフのための変数順決定アルゴリズムとその評価

IPSJ 8 Citations

Bibliographic Information

Other Title
  • An Ordering Algorithm for Binary Decision Diagrams and Its Evaluation
  • ハードウェア

Search this article

Abstract

Bryantは論理関数を効率的に処理する手法として 場合分けの変数順をすべてのパスで固定した2分決定グラフ(BDD)を提案し BDDの効率的な演算アルゴリズムを示した.64ビツトのALUが表現できる等.BDDは従来の論理関数表現手段と比べ 極めて強力であることが示されたが 場合分けの変数l頂によって BDDの大きさが大きく変化するという問題点がある・そこで本稿では BDDの変数順についての各種実験結果と それらから得られた変数順決定アルゴリズムについて述べる.まず ベンチマーク回路に対する実験結果から 人が描く回路図上に現れる変数を上から順に順序付けしたものが極めてよい結果をもたらすことを示す.次に これの根拠となる定理を幾つか示し それらの定理に基づく変数順決定アルゴリズムとその評価を示す.この変数順決定アルゴリズムは回路図から得られる順よりもよい結果をもたらし 100入力 3 000ゲート以上の回路をBDDで表現できるようになった.

Journal

Citations (8)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top