動的負荷分散による階層型行列計算の並列化

• Item type: SIG Technical Reports(1)
• 公開日: 2015-02-23
• タイトル: 動的負荷分散による階層型行列計算の並列化
• タイトル / 言語: en
• タイトル: Parallel Hierarchical Matrix Arithmetics using Dynamic Load Balancing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 線形代数
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学情報学研究科
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学学術情報メディアセンター／JST CREST
• 著者所属: 北海道大学情報基盤センター／JST CREST
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University / JST CREST
• 著者所属(英): en
• 著者所属(英): Information Initiative Center, Hokkaido University / JST CREST
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者名: 棟形, 克己; 平石, 拓; 伊田, 明弘; 岩下, 武史; 中島, 浩
• 著者名(英): Katsumi, Munakata; Tasuku, Hiraishi; Akihiro, Ida; Takeshi, Iwashita; Hiroshi, Nakashima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 階層型行列 （H 行列） は，N 個の要素間の N×N 個の相互関係を表す密行列の圧縮表現の一つである．本研究では，H 行列の生成および H 行列ベクトル積の MPI/OpenMP ハイブリッド並列化を，動的負荷分散を用いて行った．H 行列の生成は，小行列 （葉行列） への行列の区分けと，各葉行列の要素計算により行われる．後者は葉行列単位のタスク並列化が可能だが，各コアにタスク集合を静的に割り当てる実装では，各タスクの計算負荷を正確には見積もれないこと，および全体に対する負荷割合が大きなタスクの存在により十分な負荷均衡が得られない．そこで，MPI および OpenMP の 2 レベルの階層型マスタワーカ方式による動的タスク割り当てを行い，さらに OpenMP レベルでは大きなタスクにプロセス内の全スレッドを割り当てることで負荷を均衡化した．H 行列ベクトル積でも同様のタスク並列化が可能だが，タスクのプロセス間移動のコストが大きいため，MPI レベルでは葉行列生成を担当したプロセスに引き続きその葉行列に関する部分計算を静的に割り当て，OpenMP レベルでのみ生成処理と同様の動的タスク割り当てを行った．生成処理の負荷均衡化の結果，この方式でプロセス間においても良好な負荷均衡が得られる．表面電荷法による係数行列生成およびその行列に対する行列ベクトル積を例題として性能評価を行った結果，32 プロセス×8 スレッドによる並列実行では，従来の負荷見積もりに基づく静的割当手法に対して，H行列生成では 3.4 倍，H 行列ベクトル積では 2.5 倍の性能が得られた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Hierarchical matrix (H-matrix) is an approximated form to represent N × N correlations of N objects, which usually requires a N × N huge dense matrix. This paper proposes hybrid MPI/OpenMP implementations of H-matrix generation and H-matrix-vector multiplication using dynamic load balancing. H-matrix generation is done by partitioning a matrix into submatrices called leaf matrices, followed by calculating element values of the leaf matrices. We can apply task parallelism to the latter operation by treating each leaf matrix as a parallelization unit. However, we cannot achieve a good speedup when assigning a set of tasks to each processor core statically, because (1) we cannot predict the computational amount of each task precisely and (2) there exist tasks whose ratios of the computational amounts to the total amount are too large. We solved these problems by (1) dynamic task assignment based on the hierarchical master-worker method with the MPI and OpenMP levels, and (2) dividing a large task and executing it in parallel using all threads in an MPI process. We can apply the same parallelization strategy to H-matrix-vector multiplication. However, because the task migration cost among processes is too high, we reused the same task assignment as in H-matrix generation on the MPI level, and performed dynamic task assignment only on the OpenMP level. We can get better load balance even among processes due to the dynamic load balancing used in H-matrix generation. We evaluated the performances of our implementations when generating a coefficient matrix used in the surface charge method as an H-matrix and multiplying the H-matrix by a vector. As a result, in an execution with 32 processes × 8 threads, we achieved a 3.4 times and 2.5 times better performance in H-matrix generation and H-matrix-vector multiplication respectively, than the existing implementations that perform static task assignment based on estimated computational amounts of tasks.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2015-HPC-148, 号 5, p. 1-15, 発行日 2015-02-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会