同期点の少ない並列化ICCG法のためのブロック化赤─黒順序付け(<特集>並列処理)

概要

論文の詳細を見る
不完全コレスキー分解前処理付き共役勾配法(ICCG法)の代表的な並列化手法の1つとして,並列オーダリングの利用がある.これまでにも様々な並列オーダリングが提案されており,たとえば高い収束性と並列度を同時に実現する優れたオーダリングとして,大きな色数による多色順序付けがある.本論文では,収束性,並列度に加えて,並列化されたアルゴリズム中の同期点について考慮し,各代入計算の並列実行における同期点の数を1つにし,かつ前述の手法と同程度の高い収束性が得られる並列オーダリングとして,ブロック化赤一黒順序付けを新たに提案する.本手法は,節点のいくつかをブロック化し,そのブロックに対して赤一黒順序付けを適用するものである.各プロセッサがいくつかのブロックを担当することにより,代入計算が並列実行される.本手法の収束性,並列度,速度向上に関して,オーダリンググラフによる解析的検討,スカラ並列計算機上での数値解析的検討を行う.解析的検討では,ブロックサイズを増加させることにより収束性が改善されることを示し,実行計算機の並列度に合わせた最適なブロックサイズを導く.数値解析的検討では,提案手法がスカラ並列計算機上でめ実装において高い収束性とキャッシュデータの再利用性を持ち,約100万自由度を持つ差分解析の計算例において逐次型ICCG法と比べて16CPUで14.3倍の速度向上を得ることを示す.
2002-04-15

同期点の少ない並列化ICCG法のためのブロック化赤─黒順序付け(<特集>並列処理)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク