同期点の少ない並列化ICCG法のためのブロック化赤－黒順序付け

• Item type: Journal(1)
• 公開日: 2002-04-15
• タイトル: 同期点の少ない並列化ICCG法のためのブロック化赤－黒順序付け
• タイトル / 言語: en
• タイトル: Block Red-Black Ordering for Parallelized ICCG Solver with Fewer Synchronization Points
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：並列処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 高性能計算
• 著者所属: 京都大学大型計算機センター
• 著者所属: 京都大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Data Processing Center, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Kyoto University
• 著者名: 岩下, 武史; 島崎, 眞昭
• 著者名(英): Takeshi, Iwashita; Masaaki, Shimasaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 不完全コレスキー分解前処理付き共役勾配法（ICCG法）の代表的な並列化手法の1つとして，並列オーダリングの利用がある．これまでにも様々な並列オーダリングが提案されており，たとえば高い収束性と並列度を同時に実現する優れたオーダリングとして，大きな色数による多色順序付けがある．本論文では，収束性，並列度に加えて，並列化されたアルゴリズム中の同期点について考慮し，各代入計算の並列実行における同期点の数を1つにし，かつ前述の手法と同程度の高い収束性が得られる並列オーダリングとして，ブロック化赤?黒順序付けを新たに提案する．本手法は，節点のいくつかをブロック化し，そのブロックに対して赤?黒順序付けを適用するものである．各プロセッサがいくつかのブロックを担当することにより，代入計算が並列実行される．本手法の収束性，並列度，速度向上に関して，オーダリンググラフによる解析的検討，スカラ並列計算機上での数値解析的検討を行う．解析的検討では，ブロックサイズを増加させることにより収束性が改善されることを示し，実行計算機の並列度に合わせた最適なブロックサイズを導く．数値解析的検討では，提案手法がスカラ並列計算機上での実装において高い収束性とキャッシュデータの再利用性を持ち，約100万自由度を持つ差分解析の計算例において逐次型ICCG法と比べて16CPUで14.3倍の速度向上を得ることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A use of parallel ordering is one of typical strategies for parallel processing of the Incomplete Choleskey Conjugate Gradient (ICCG) method. While various parallel ordering techniques have been proposed, ``the large-numbered multi-color ordering method,'' which is one of the most effective techniques, achieves both fast convergence and high parallelism. In addition to convergence and parallelism, the present paper considers synchronization points in parallelized ICCG method. Consequently, a new parallel ordering, ``block red-black ordering,'' is proposed for a parallelized ICCG solver with fewer synchronization points and a high convergence rate. The new method, which has only one synchronization point in each substitution, attains approximately the same convergence as the large-numbered multi-color ordering method. In the method, nodes in an analyzed grid are divided into several blocks, and red-black ordering is applied to the blocks. Several blocks are assigned to each processor and the substitution is carried out in parallel. For evaluation of the new method, we perform analytical investigation by means of the ordering graph theory and computational tests on a scalar parallel computer. The analytical investigation shows that a convergence rate can be improved by an increase in the block size. The analytical study also presents the optimal block size that depends on the number of processors. Computational tests show that the proposed method attains both fast convergence and effective utilization of data cache on scalar parallel computers and that it achieves a 14.3-fold speed-up by 16 processors on an finite difference analysis with approximately 10 6 degrees of freedom.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 43, 号 4, p. 893-904, 発行日 2002-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764