文献

J-GLOBAL ID：202002238810850378   整理番号：20A0555306

タスク並列言語を用いた階層行列の構築における行列分割の並列化

Parallelization of Matrix Partitioning in Construction of Hierarchical Matrices using Task Parallel Languages

著者 (5件)： Bai Zhengyang (Graduate School of Informatics, Kyoto University) ,  Hiraishi Tasuku (Academic Center for Computing and Media Studies, Kyoto University) ,  Nakashima Hiroshi (Academic Center for Computing and Media Studies, Kyoto University) ,  Ida Akihiro (Information Technology Center, the University of Tokyo) ,  Yasugi Masahiro (Department of Computer Science and Networks, Kyushu Institute of Technology)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 27  ページ： 840-851(J-STAGE)  発行年： 2019年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 階層行列(H行列)はN個のオブジェクトのN×N個の相関を表す近似形式である。行列を部分行列に分割し,続いてこれらの部分行列の要素値を計算することにより,H行列の構築を達成した。本論文では,タスク並列言語であるCilk PlusとTascellを用いた行列分割の実装を提案した。行列分割は,オブジェクトを階層に分割することによるクラスタツリー構築と,許容条件を満たすクラスタツリーの同じレベルの全クラスタペアを観察することによるブロッククラスタツリー構築の2つのステップに分けた。これらのステップで構築し,トラバースした2つのタイプのツリーは予測以上にアンバランスなので,タスク並列言語を用いてこれらのステップの両方を効率的に並列化できることが期待できる。クラスタツリー構築において十分な並列性を得るために,並列に再帰呼び出しを実行するだけでなく,各再帰ステップの内部を並列化した。ブロッククラスタツリー構築では,作業者がロックを使用せずにクラスタツリーを保存できるように,専用の空間を各社業者に割り当てた。結果として,C言語の逐次実装と比較して,Cilk Plusを用いた場合は最大11.5倍,Tascellを用いた場合は12.6倍のクラスタツリー構築高速化を達成した。ブロッククラスタツリー構築では,Cilk Plusを用いた場合は37.7倍,Tascellを用いた場合は38.8倍の高速化を達成した。行列分割の全プロセスについては,Cilk Plusを用いた場合は最大12.2倍,Tascellを用いた場合は14.5倍の高速化を達成した。全ての実験は,実データセットを用いて2台の18コアXeonプロセッサ上で実行し,表面電荷法で使用される係数行列を生成した。(翻訳著者抄録)

シソーラス用語： 並列化 ,  *分割 ,  *行列 ,  *プログラミング言語 ,  木構造 ,  高速化 ,  クラスタ分割 ,  クラスタ ,  階層構造 ,  係数行列 ,  社会階層
準シソーラス用語： 階層 ,  *並列言語

著者キーワード (3件)： タスク並列言語 ,  階層的行列 ,  木の建設

分類 (2件)： 計算理論  (JB02000A) ,  代数学  (AB02000R)

引用文献 (28件)：

• [1] 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).
• [2] Hackbusch, W. and Khoromskij, B.N.: A sparse H-matrix arithmetic, part II: Application to multi-dimensional problems, Computing, Vol.64, No.1, pp.21-47 (2000).
• [3] Börm, S., Grasedyck, L. and Hackbusch, W.: Hierarchical matrices, lecture note (2005).
• [4] Ida, A.: Lattice H-matrices on distributed-memory systems, 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp.389-398 (May 2018).
• [5] Hoshino, T., Ida, A., Hanawa, T. and Nakajima, K.: Design of parallel BEM analyses framework for SIMD processors, Shi, Y., Fu, H., Tian, Y., Krzhizhanovskaya, V.V., Lees, M.H., Dongarra, J. and Sloot, P.M.A. (Eds.), Computational Science - ICCS 2018, pp.601-613, Springer International Publishing (2018).

タイトルに関連する用語 (6件)： タスク ,  並列言語 ,  階層 ,  行列 ,  構築 ,  並列化