Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems

• Item type: Trans(1)
• 公開日: 2022-09-15
• タイトル: Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems
• タイトル / 言語: en
• タイトル: Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] task parallel language, hierarchical matrix, Tascell, tree construction
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Informatics, Kyoto University
• 著者所属: Department of Information and Computer Science, Faculty of Engineering, Kyoto Tachibana University
• 著者所属: Research Institute for Value-Added-Information Generation (VAiG), Japan Agency for Marine-Earth Science and Technology (JAMSTEC)
• 著者所属: Department of Computer Science and Networks, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science, Faculty of Engineering, Kyoto Tachibana University
• 著者所属(英): en
• 著者所属(英): Research Institute for Value-Added-Information Generation (VAiG), Japan Agency for Marine-Earth Science and Technology (JAMSTEC)
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Networks, Kyushu Institute of Technology
• 著者名: Zhengyang, Bai; Tasuku, Hiraishi; Akihiro, Ida; Masahiro, Yasugi
• 著者名(英): Zhengyang, Bai; Tasuku, Hiraishi; Akihiro, Ida; Masahiro, Yasugi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A hierarchical matrix (H-matrix) is an approximated form that represents N × N correlations of N objects. H-matrix construction is achieved by dividing a matrix into submatrices (partitioning), followed by calculating these submatrices' element values (filling). Matrix partitioning consists of two steps: cluster tree (CT) construction, where objects are divided into clusters hierarchically; and block cluster tree (BCT) construction, which involves observing all cluster pairs at the same CT level that satisfies the admissibility condition. This study proposes two parallel implementation methods of partitioning operations on distributed memory systems (DMSs): distributed cluster tree construction (DCTC) and redundant cluster tree construction (RCTC). In DCTC, both CT and BCT constructions are parallelized using workers in all computing nodes. In RCTC, CT is constructed in every computing node redundantly by employing only intra-node work stealing. The BCT is then constructed in parallel using workers in all computing nodes. RCTC cannot achieve speedup using multiple computing nodes, but can eliminate the data exchange cost incurred by DCTC. We used the task-parallel language Tascell, which employs both intra- and inter-node work stealing, to handle arbitrary unbalanced tree construction and traversal on DMSs. Our RCTC implementations achieved a 1.11-1.20-fold speedup using up to 8 nodes × 36 workers in numerical experiments with 3D electric field analyses and N ≃ 10 8.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.30(2022) (online); ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A hierarchical matrix (H-matrix) is an approximated form that represents N × N correlations of N objects. H-matrix construction is achieved by dividing a matrix into submatrices (partitioning), followed by calculating these submatrices' element values (filling). Matrix partitioning consists of two steps: cluster tree (CT) construction, where objects are divided into clusters hierarchically; and block cluster tree (BCT) construction, which involves observing all cluster pairs at the same CT level that satisfies the admissibility condition. This study proposes two parallel implementation methods of partitioning operations on distributed memory systems (DMSs): distributed cluster tree construction (DCTC) and redundant cluster tree construction (RCTC). In DCTC, both CT and BCT constructions are parallelized using workers in all computing nodes. In RCTC, CT is constructed in every computing node redundantly by employing only intra-node work stealing. The BCT is then constructed in parallel using workers in all computing nodes. RCTC cannot achieve speedup using multiple computing nodes, but can eliminate the data exchange cost incurred by DCTC. We used the task-parallel language Tascell, which employs both intra- and inter-node work stealing, to handle arbitrary unbalanced tree construction and traversal on DMSs. Our RCTC implementations achieved a 1.11-1.20-fold speedup using up to 8 nodes × 36 workers in numerical experiments with 3D electric field analyses and N ≃ 10 8.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.30(2022) (online); ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 15, 号 4, 発行日 2022-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会