ウエーブフロント型並列処理におけるタイルサイズの決定方式

概要

論文の詳細を見る
科学技術分野の計算の大半は大規模配列データを扱うループ計算で占められ、このようなループを超並列計算機で実行するには、データパラレル方式にもとづいたループ並列処理が一般的である。つまり、配列データやループの各イタレーショシをプロセッサエレメント(以下PEと呼ぶ)に分散し、各PEが互いに通信しながら並列処理を行う。ここで問題となるのは、PE間通信が処理全体のボトルネックになることである。特にデータ転送の起動オーバーへツドが非常に大きいので、ループ運搬依存をもつ多重ループをウェーブフロント型並列処理する場合、イタレーション一回ごとにデータ転送を行うと性能がでない.この問題を解決するため、数回~数百回のイタレーションに一回の割合でデータ転送をまとめて行う研究がいくつか発表されている。そこでの基本的な手法は、ループのイタレーション空間を、「タイル」と呼ばれるイタレーションの集まりで分割し(これをタイリングと呼ぶ)、各タイルをPEに割り付け、データ転送はタイルを単位として行うものである。タイリング方式には、タイルを大きくとれば、通信回数は少なくてすむが、他のPEの開始が遅れて並列性が十分に生かせないというトレードオフがある。このため、タイルの大きさが全実行時間にどのような影響を及ぼすかを解析して最適なタイルサイズを決定する必要がある。Ramamujamらは、タイルの各辺の長さが等しいなどの特殊な条件下での最適なタイルサイズを示した。Hiranandaniらもいくつかの特別な場合について最適タイルサイズを示している。しかし、一般的な条件下での最適タイルサイズの決定方式は、これまで提案されていなかった。本報告では、依存ベクタの方向が任意の場合に二次元タイリングを適用し、必ずしもタイルの各辺の長さが等しくなくてもよいという条件下で、最適タイルサイズを決定する方法を提案する。
社団法人情報処理学会の論文
1994-03-07

ウエーブフロント型並列処理におけるタイルサイズの決定方式

スポンサーリンク

概要

著者

関連論文

スポンサーリンク