| 発表者名 | タイトル | 概要 (1ページ) | 本文 | ||||
|---|---|---|---|---|---|---|---|
| 日本語 | 英語 | ||||||
| ps.gz | ps.gz | ps.gz | |||||
| 藤村 佳克 | 並列数値シミュレーションの静的負荷分散法の拡張について | 25 KB | 53 KB | 24 KB | 80 KB | 120 KB | 216 KB |
| ラターナセンタン・ウドーン | 部分グラフ同型判定アルゴリズムのFPGAを用いた実装 | 160 KB | 70 KB | 120 KB | 59 KB | 2820 KB | 1520 KB |
| 斎藤 秀充 | Ullmannのアルゴリズムのハードウェアによる実装に関する研究 | 67 KB | 90 KB | 65 KB | 120 KB | 1120 KB | 440 KB |
市川らは並列PDE求解システムNSLの静的負荷分散問題 を組合せ最適化問題として定式化し，分枝限定法を用いて実用的に 最適解を求める方法を示した．しかしこの方法ではブロック数 $m$とプロセッサ数$n$の間に$m \ll n$の関係がある場合に しか適切な負荷分散ができない．この制限を緩和するため仮想プロ セッサを採用する方式も提案されたが，性能が改善可 能であることが示されただけで，具体的・実用的な解決法は未解決 のままであった． 本研究では$m \ge n$の場合について，静的負荷分散を一種の箱 詰め問題としてモデル化し，分枝限定法を用いて最適解を求める 方法を示す．実用時間内に最適解を求めることが困難となる大規模 な問題のために，短時間で精度の良い近似解が求まる近似アル ゴリズムも合わせて検討する．
部分グラフ同型判定は化学物質の構造活性推測やシーン解析など，広い範 囲に応用できる．しかしこの問題は一般にNP完全であり，実用的には計算困難 である．このような応用には専用回路による高速化[Buell96]が有効と期待さ れるが，部分グラフ同型判定問題を解くために広く用いられているUllmannの アルゴリズム[Ullmann76]は，ゲート数の点からハードウェアへの実装が困難 である． 小西[Konishi99]は，探索空間削減の効率はUllmannのアルゴリズムに劣るが， 構造が単純でハードウェアへの実装に適したアルゴリズムを提案した(以下， 小西のアルゴリズムとよぶ)．小西のアルゴリズムをFPGAに実装して33MHzで動 作させた場合，同じアルゴリズムのソフトウェアを333 MHzのPentium II上で 実行する場合と比べて，10〜50倍の性能が得られると予測される． そこで本研究では，Lucent社 ORCA 2C15A FPGAを搭載するOPERLボード [Ichikawa96]上に小西のアルゴリズムを実装し，実機上で小西のアルゴリズム の性能を評価する．
Ullmannのアルゴリズムは，代表的な部分グラフ同型判定アルゴリズムの1 つである．Ullmannはこのアルゴリズムを組合せ回路で実装することを提案し たが，組み合わせ回路では実行時間が短くなる代わりに回路規模が膨大になる． 順序回路により処理の一部を逐次処理すれば，実行時間は長くなるが回路規模 を縮小することができる．本研究ではUllmannのアルゴリズムを様々な方法で ハードウェアに実装して，回路規模と実行速度について比較検討した． Ullmannのアルゴリズムの性質を利用することにより，順序回路による実装で， 実用的な回路規模でUllmannの提案よりもAT積の良い実装を得ることができる ことがわかった．