| 発表者名 | タイトル | ps.gz | |
|---|---|---|---|
| 岸本 芳典 | 不均一クラスタ上での並列Linpackの性能に関する検討 | 28 KB | 38 KB |
| 山本 昌治 | データ依存回路による部分グラフ同型判定 | 73 KB | 71 KB |
HPLは分散メモリ型並列計算機用のLinpackである．HPLは不均一な クラスタ上で実行すると負荷の不均衡により性能が低下するが，こ の問題は高速PE上で複数のプロセスを起動することにより改善でき る．複数プロセスの起動により高速PE上では性能オーバヘッドが生 じるが，実測例では性能ロスは3割以下であった(N≧3000)．このと きクラスタ全体の性能は，負荷不均衡が解消されることにより最大 2割程度改善された．最善の実行方法は問題サイズNやクラスタ構成 によって異るので，本研究では(1)高速PE上のプロセス数，(2)クラ スタのPE構成，(3)ネットワーク構成，などを変えて性能を測定し た．今後は自動的に最適な実行条件を選ぶ方法を検討する．
部分グラフ同型判定問題は一般にNP完全であり，計算困難である． Ullmannのアルゴリズムは論理回路で実現できるが, 回路規模が大 きく実装が難しい．一般に論理回路の入力が定まれば論理の簡単 化により回路規模を縮小できる．本研究では入力グラフに依存し た論理回路を生成することにより，判定回路の規模を縮小する手 法について検討した．FPGAを対象とした試験的評価結果では，入 力グラフの頂点数が32のとき回路規模が1/20に削減できた．この ときの同型判定時間は4秒で，性能はソフトウェアの460倍である． 回路生成時間は15分程度で，回路生成時間を含めてもソフトウェ アより高速な同型判定が可能である．