二次記憶に格納された共有二分決定グラフを効率良く処理するための幅優先アルゴリズム

概要

論文の詳細を見る
共有二分決定グラフによる論理関数の表現は比較的コンパクトであり、しかも表現が一意であるという優れた性質がある。この共有二分決定グラフに基づく論理関数の理処手続きは、サブルーチンパッケージとしてワークステーション上に実現され、論理照合、タイミング検証、テスト生成、論理合成、順序機械の設計検証などに広く応用されている。しかし、より大規模・複雑な集積回路を設計するため、より大きな共有二分決定グラフを効率良く操作するための手法の開発が切望されている。高速化のため、グラフの操作を並列化する試みはこれまでにもみられ、効果が確認されている。しかし、実用的には計算時間よりはむしろ計算機の主記憶容量の制的が問題となっている。本報告では、全ての情報を主記憶上に格納できないような大きなグラフを取り扱うため、大容量の二次記憶に格納された共有二分決行グラフを効率良く操作する手法を提案する。これは、ランダムアクセスを行なうとアクセス速度が著しく低下する二次記憶を効率良く利用するため、従来深さ優先で行なわれていた共有二分決定グラフの操作を幅優先の操作に置き換え、グラフの各レベルごとに、必要な情報を二次記憶から取り出し、操作を行ない、結果を格納しようというものである。
一般社団法人情報処理学会の論文
1992-09-28

二次記憶に格納された共有二分決定グラフを効率良く処理するための幅優先アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク