文献

J-GLOBAL ID：201502207097638881   整理番号：15A0780961

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

Parallel Hierarchical Matrix Arithmetics using Dynamic Load Balancing

著者 (7件)： 棟形克己 (京大) ,  平石拓 (京大 学術情報メディアセ) ,  伊田明弘 (京大 学術情報メディアセ) ,  伊田明弘 (JST-CREST) ,  岩下武史 (北大 情報基盤セ) ,  岩下武史 (JST-CREST) ,  中島浩 (京大 学術情報メディアセ)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2015  号： HPC-148  ページ： VOL.2015-HPC-148,NO.5 (WEB ONLY)  発行年： 2015年02月23日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 階層型行列(H行列)は,N個の要素間のN×N個の相互関係を表す密行列の圧縮表現の一つである。本研究では,H行列の生成およびH行列ベクトル積のMPI/OpenMPハイブリッド並列化を,動的負荷分散を用いて行った。H行列の生成は,小行列(葉行列)への行列の区分けと,各葉行列の要素計算により行われる。後者は葉行列単位のタスク並列化が可能だが,各コアにタスク集合を静的に割り当てる実装では,各タスクの計算負荷を正確には見積もれないこと,および全体に対する負荷割合が大きなタスクの存在により十分な負荷均衡が得られない。そこで,MPIおよびOpenMPの2レベルの階層型マスタワーカ方式による動的タスク割り当てを行い,さらにOpenMPレベルでは大きなタスクにプロセス内の全スレッドを割り当てることで負荷を均衡化した。H行列ベクトル積でも同様のタスク並列化が可能だが,タスクのプロセス間移動のコストが大きいため,MPIレベルでは葉行列生成を担当したプロセスに引き続きその葉行列に関する部分計算を静的に割り当て,OpenMPレベルでのみ生成処理と同様の動的タスク割り当てを行った。生成処理の負荷均衡化の結果,この方式でプロセス間においても良好な負荷均衡が得られる。表面電荷法による係数行列生成およびその行列に対する行列ベクトル積を例題として性能評価を行った結果,32プロセス×8スレッドによる並列実行では,従来の負荷見積もりに基づく静的割当手法に対して,H行列生成では3.4倍,H行列ベクトル積では2.5倍の性能が得られた。(著者抄録)

シソーラス用語： *回路行列 ,  *負荷分散 ,  動的系 ,  並列化 ,  *並列処理 ,  数値計算 ,  性能評価 ,  行列
準シソーラス用語： *H行列 ,  階層型行列 ,  行列計算 ,  *動的負荷分散

分類 (2件)： ディジタル計算機方式一般  (JC02010O) ,  演算方式  (JC02020Z)

引用文献 (13件)：

• Börm, S., Grasedyck, L. and Hackbusch, W.: Hierarchical Matrices, Lecture note No. 21 of the Max Planck Institute for Mathematics in the Sciences (2003).
• Hackbusch, W. and Khoromskij, B. N.: A Sparse H-Matrix Arithmetic. Part II: Application to Multidimensional Problems, Computing, Vol. 64, No. 1, pp. 21-47 (2000).
• Hackbusch, W.: A Sparse Matrix Arithmetic Based on H-Matrices. Part I: Introduction to H-matrices, Computing, Vol. 62, No. 2, pp. 89-108 (1999).
• ppOpen-HPC Project: ppOpen-HPC: Open Source Infrastructure for Development and Execution of Large-Scale Scientific Applications on Post-Peta-Scale Supercomputers with Automatic Tuning. http://ppopenhpc.cc.u-tokyo.ac.jp.
• Ida, A., Iwashita, T., Mifune, T. and Takahashi, Y.: Parallel Hierarchical Matrices with Adaptive Cross Approximation on Symmetric Multiprocessing Clusters, Journal of Information Processing, Vol. 22, No. 4, pp. 642-650 (2014).

タイトルに関連する用語 (4件)： 動的負荷分散 ,  階層 ,  行列計算 ,  並列化