分散記憶型並列計算機に対する並列二分決定グラフ構成アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
論理回路システム設計の基礎技術である論理関数処理に計算機を援用する手段として、論理関数を計算機上で効率よく表現することができる二分決定グラフ(Binary Decision Diagram;BDD)[1]が考案され、理論と実用の両面から広く研究されている。しかし設計規模の増大にともない、問題によっては多くの計算時間を要する処理が生じ、それらはしばしば逐次計算機の能力を超えるものとなる。本稿では分散記憶型並列計算機を用いてBDDを構成する効率的な手法を示す。分散記憶型の場合、各プロセッサヘの負荷分散を処理と記憶領域の両面から考慮することが必要であるが、その手法としてShannon展開によるグラフの分割手法と多出力回路の各出力をプロセッサに振り分ける手法が提案されている。これらを組み合わせた手法について富士通のAP-1000を用いて実現と評価を行なった。
一般社団法人情報処理学会の論文
1993-09-27

著者

関連論文

もっと見る

スポンサーリンク