■平成15年度 修士論文

●岸本 芳典

既存の科学技術計算応用の多くは計算負荷をPEに均等に割り当てるため，不均一クラスタ上で実行すると負荷不均衡による性能低下を生ずる．不均一クラスタ上で負荷を均衡化する手法の一つに，高速PE上に複数のプロセスを起動する手法(マルチプロセス法)がある．マルチプロセス法は実現が容易で，幅広い応用に適用可能である．

一般に，不均一クラスタ内の全てのプロセッサを使用しても，通信時間の発生により実行時間が最小になるとは限らない．マルチプロセス法で実行時間を最小化するには，(1) 最適なPEセットと，(2) 各PE上の最適なプロセス数を求める必要がある．本研究では，最適な実行方法(構成)を求める問題を組合せ最適化問題としてモデル化する．モデル化には，構成から実行時間を予測する近似式が必要である． 本研究では，HPL (High Performance Linpack)を応用例として，実行時間の実測値から予測モデルを構築し，(準)最適なPE構成およびマルチプロセス数の予測が可能であることを示す．HPLのテストケースについて実行時間の測定を複数行ない，その測定結果から実行時間予測モデルを構築する．HPLのアルゴリズムから実行時間の近似式が求まるので，実測値を最小二乗法で処理して係数項を求める．このようなモデル化は実装や応用に依存しないため幅広い応用に適用可能である．

本研究では可能な構成の組み合わせ数を削減するため，(1) 等価なPEのマルチプロセス数を同一とし，(2) さらに通信時間は通信相手に依存しないと仮定した．2種類のPEからなる不均一クラスタについて問題サイズN=400〜6400の範囲でモデル構築を行ない， 予測により得られた最良構成をN=1600〜9600の実測における最良構成と比較した．その結果，N≧3200で誤差0〜7.4%の(準)最適構成の予測に成功した．実測値の測定方法とモデルの精度の関係についても前述のクラスタ上で検討した．まず計算時間と通信時間について別々に構築したモデルについて評価した．その結果，通信時間の予測誤差が大きく実用的な精度は得られなかった．実装依存の手法を用いればこの誤差は削減できるが本研究の目的に反するため棚上げとした．次にテストケース数の削減とモデル精度への影響について検討した．サイズNの測定点数を9点〜5点まで変化させたところ，Nの測定範囲が十分に大きい場合には5点の測定で9点の場合と同様の精度を得られることが分かった．また3種類のPEからなる不均一クラスタについても評価を行い，クラスタの制約によりあるPEのモデル構築に十分なテストケースを測定できない場合でも，精度の良い他種PEモデルを性能比で定数倍して代用することによりN≧4800で誤差17.3%の構成を得られた． 今後はモデル精度の一層の向上，分枝限定法などによる探索空間の制限や近似解法の検討，HPL以外の応用についても研究を進める必要がある．

●山本 昌治

部分グラフ同型判定は化学物質の構造活性推測など幅広い応用を持つが，一般にNP完全で計算は困難である． 部分グラフ同型判定の専用回路には，Ullmannの提案と小西の提案があるが，どちらの提案も回路規模の制限により実装可能な頂点数には限界がある．

本研究では、部分グラフ同型判定のためのデータ依存回路について述べる． 評価では，実際に存在するFPGAボードを利用して実測した値を用いた． データ依存回路とは入力データ毎に最適化した論理回路である． データ依存回路は元になった論理回路よりも回路規模が小さく，信号遅延が小さいため元になった回路よりも高速である． しかし，他の入力データに対して再利用が出来ないため入力データ毎に回路を生成してやる必要がある． また，FPGAのような再構成可能論理素子への実装が前提となる．

本研究では, 部分グラフ同型判定のためのデータ依存回路を設計して，Xilinx XC2V3000 FPGAに実装して評価した． 25MHzシステムクロックにてデータ依存回路の動作を確認した． ランダムグラフを入力グラフとした場合，最大動作周波数のときデータ依存回路の実行時間はソフトウェアの7.0\%である(頂点数16)． 回路生成時間を含めて考えてもデータ依存回路はソフトウェアの14.4倍高速である． 頂点数が大きくなれば，データ依存回路の優位性はより高くなる．

本研究ではUllmannのアルゴリズムと小西のアルゴリズムの2つのアルゴリズムについてデータに依存した設計手法を評価して，両方のアルゴリズムに対して効果があることを確認した． 評価では複数のデータセットを用いて平均値を用いて結果を示した．

本研究で行ったことと得られた知見を以下に示す．

• データに依存した手法は回路生成時間を含んでも，最新プロセッサで動作させたソフトウェアより性能面で優位性がある．
• データ依存回路をXilinx XC2V FPGAを用いて実際に実装し，FPGAボード上の25MHzシステムクロックで動作を確認した．
• データに依存した手法の優位性は特定のデータセットやアルゴリズムによるものではない． 2つのアルゴリズムと複数のデータセットによりデータに依存した手法の優位性を確認した．

※アブストラクトと学位論文の実験結果は異なっているのは，違う条件で再実験したためである．