クラスタ・システムによる二分決定グラフの並列処理

カテゴリ: 部門大会

論文No: MC2-7

グループ名: 【C】平成15年電気学会電子・情報・システム部門大会講演論文集

発行日: 2003/08/29

タイトル(英語): Parallel Processing of Binary Decision Diagrams on Cluster System

著者名: 平石 裕実(京都産業大学)

著者名(英語): Hiromi Hiraishi(Kyoto Sangyo University)

キーワード: 設計検証|二分決定グラフ|論理関数|並列処理|クラスタ・システムMPI|Design Verification|Binary Decision Diagram|Logic Function|Parallel Processing|Cluster SystemMPI

要約(日本語): 二分決定グラフ(BDD)に基づく論理関数処理は多くの分野で利用されているが、問題の規模が大きくなるにつれて、BDDの節点数が指数爆発しやすいという問題がある。本稿では、より大規模なBDDの処理を可能とするために、一部の論理変数の値を動的に固定していくことによりBDDを細分化し、それらのBDDをクラスタ・システム上で分散記憶する並列アルゴリズムを提案する。MPIを用いて本アルゴリズムをクラスタ・システム上に実装し評価を行った結果、64並列で17ビット乗算器のBDDを構築することが出来、また、乗算器のBDDの構築やBDDによる充足可能性判定で、一部スーパーリニア効果を得ることが出来た。

PDFファイルサイズ: 5,802 Kバイト