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

書誌事項

タイトル別名
  • An Ordering Algorithm for Binary Decision Diagrams and Its Evaluation
  • ハードウェア

この論文をさがす

抄録

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

収録刊行物

被引用文献 (8)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1050001337889094272
  • NII論文ID
    110002764641
  • NII書誌ID
    AN00116647
  • ISSN
    18827764
  • Web Site
    http://id.nii.ac.jp/1001/00015048/
  • 本文言語コード
    ja
  • 資料種別
    journal article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ