動的タスクスケジューリングエンジンStarPUによるKIFMMの実装と性能評価

概要

論文の詳細を見る
Fast Multipole Method (FMM) は, N 体問題のアルゴリズムで,近似計算により O(N) の計算量を実現する. FMM は,計算特性が異なり入力データによって負荷が変動する複数の計算ステップから構成される.本研究では,FMM の入力データ (粒子分布) による負荷変動に対して CPU/GPU 間の負荷分散を適切に行うことを目的とする.そのための手法として,動的タスクスケジューリングエンジンを採用し,そのためのライブラリである StarPU 上に Kernel Independent FMM (KIFMM) アプリケーションを実装し,性能を評価した.この実装を,入力データ毎の総当たりによって最適な静的スケジューリングを決定することができる実装と比較した.均一分散では単純なヒューリスティクスを 1 つ導入することにより静的スケジューリング実装に対して 137.9% ,球表面 (不均一) 分散においてはヒューリスティクスを用いずに同実装に対して 89.5% の性能を得た.このことから,動的タスクスケジューリングを用いることにより,最適な静的スケジューリング実装に対して競争的なパフォーマンスを発揮しつつ,入力データによる負荷変動に抗して負荷分散を実現することが可能であると言える.
2012-09-26