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

• Item type: Journal(1)
• 公開日: 1990-04-15
• タイトル: 2分決定グラフのための変数順決定アルゴリズムとその評価
• タイトル / 言語: en
• タイトル: An Ordering Algorithm for Binary Decision Diagrams and Its Evaluation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ハードウェア
• 著者所属: （株）富士通研究所
• 著者所属: （株）富士通研究所
• 著者所属: （株）富士通研究所
• 著者所属: （株）富士通研究所
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES LTD
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES LTD
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES LTD
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES Ltd
• 著者名: 藤田, 昌宏; 藤沢, 久典; 松永, 裕介; 角田多苗子
• 著者名(英): Fujita, Masahiro; Fujisawa, Hisanori; Matsunaga, Yusuxe; Kakuda, Taeko
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Bryantは論理関数を効率的に処理する手法として 場合分けの変数順をすべてのパスで固定した2分決定グラフ(BDD)を提案し BDDの効率的な演算アルゴリズムを示した.64ビツトのALUが表現できる等.BDDは従来の論理関数表現手段と比べ 極めて強力であることが示されたが 場合分けの変数l頂によって BDDの大きさが大きく変化するという問題点がある・そこで本稿では BDDの変数順についての各種実験結果と それらから得られた変数順決定アルゴリズムについて述べる.まず ベンチマーク回路に対する実験結果から 人が描く回路図上に現れる変数を上から順に順序付けしたものが極めてよい結果をもたらすことを示す.次に これの根拠となる定理を幾つか示し それらの定理に基づく変数順決定アルゴリズムとその評価を示す.この変数順決定アルゴリズムは回路図から得られる順よりもよい結果をもたらし 100入力 3 000ゲート以上の回路をBDDで表現できるようになった.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 31, 号 4, p. 532-541, 発行日 1990-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764