色数を抑えた改良Reverse Cuthill-McKee法による線形ソルバの並列化について

• Item type: SIG Technical Reports(1)
• 公開日: 2017-04-10
• タイトル: 色数を抑えた改良Reverse Cuthill-McKee法による線形ソルバの並列化について
• タイトル / 言語: en
• タイトル: An improved reverse Cuthill-McKee method for parallel linear solvers
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 行列計算
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸大学大学院システム情報学研究科
• 著者所属: 神戸大学大学院システム情報学研究科
• 著者名: 俵谷, 健太郎; 横川, 三津夫
• 著者名(英): Kentaro, Hyotani; Mitsuo, Yokokawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 偏微分方程式を有限差分法などで離散化する場合，大規模な連立一次方程式を解く問題に帰着される．連立一次方程式を解く時間は，全体計算時間の大部分を占めることが多く，計算時間短縮のため，前処理付き反復法がよく用いられる．前処理では，並列計算が可能となるようにループ内のデータ依存関係をなくす様々なマルチカラー法による変数のオーダリングが提案されてきた．本稿では，rereverse Cuthill-McKee 法 （RCM 法） に焦点をあて，並列化のオーバーヘッドを低減させる改良案として，一番最初の色付けを複数のノードから開始する複数初期点 RCM 法 （MIP-RCM 法） を提案した．対称ガウス ・ ザイデル前処理付共役残差法に対して，MIP-RCM 法と従来の RCM 法による計算時間の比較を行った結果，8 つの問題において MIP - RCM 法の計算時間が短かった．特に，thermal 2 の問題の thread 並列計算における反復計算時間の比較では，RCM 法の最も短い 2threads の計算時間に対し，MIP-RCM 法は 12threads で約 2.93 倍の時間短縮が達成され，提案手法の有効性が確認できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A large-scale linear system of equations often appears in solving partial differential equations by discretizing with finite difference method, etc. Since computation time for solvers of the system occupies the most of the whole calculation time, preconditioned iterative linear solvers are often used to reduce the calculation time. As for preconditioning methods, various multi-color ordering methods have been proposed to vanish data dependencies in the preconditioning procedure. In this paper, we proposed a multiple initial-points reverse Cuthill-McKee (MIP-RCM) method as an improvement of the RCM method to reduce the overhead of parallelization. Numerical experiments showed that the computation times of the MIP-RCM method was shorter than those of the RCM method for eight linear systems with different matrices. In particular, the computation time of the solver with MIP-RCM method was shorter than that with RCM method. We confirmed that MIP-RCM method is efficient compared to RCM method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2017-HPC-159, 号 3, p. 1-6, 発行日 2017-04-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8841
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会