{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00220215","sets":["934:935:10774:10993"]},"path":["10993"],"owner":"44499","recid":"220215","title":["Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-09-15"},"_buckets":{"deposit":"263895a8-934f-48ea-9e97-2cda3f7ac085"},"_deposit":{"id":"220215","pid":{"type":"depid","value":"220215","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems","author_link":["575513","575511","575509","575515","575516","575512","575510","575514"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems"},{"subitem_title":"Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[通常論文] task parallel language, hierarchical matrix, Tascell, tree construction","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2022-09-15","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Informatics, Kyoto University"},{"subitem_text_value":"Department of Information and Computer Science, Faculty of Engineering, Kyoto Tachibana University"},{"subitem_text_value":"Research Institute for Value-Added-Information Generation (VAiG), Japan Agency for Marine-Earth Science and Technology (JAMSTEC)"},{"subitem_text_value":"Department of Computer Science and Networks, Kyushu Institute of Technology"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Informatics, Kyoto University","subitem_text_language":"en"},{"subitem_text_value":"Department of Information and Computer Science, Faculty of Engineering, Kyoto Tachibana University","subitem_text_language":"en"},{"subitem_text_value":"Research Institute for Value-Added-Information Generation (VAiG), Japan Agency for Marine-Earth Science and Technology (JAMSTEC)","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science and Networks, Kyushu Institute of Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/220215/files/IPSJ-TPRO1504003.pdf","label":"IPSJ-TPRO1504003.pdf"},"date":[{"dateType":"Available","dateValue":"2024-09-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1504003.pdf","filesize":[{"value":"2.7 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"da007733-58f8-41d1-a667-9beee1c4ee80","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Zhengyang, Bai"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tasuku, Hiraishi"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akihiro, Ida"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Masahiro, Yasugi"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Zhengyang, Bai","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tasuku, Hiraishi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akihiro, Ida","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Masahiro, Yasugi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464814","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7802","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2022-09-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicVolumeNumber":"15"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":220215,"updated":"2025-01-19T14:38:45.843017+00:00","links":{},"created":"2025-01-19T01:20:15.672402+00:00"}