Evaluation of the performance of parallel sparse-matrix multiplication and the effect of dynamic load-balancing

被引：0

作者：

Nanri, Takeshi ^{[1
]}

Soga, Takeshi ^{[2
]}

Kurihara, Koji ^{[3
]}

Gu, Feng Long ^{[1
]}

Ishihata, Hiroaki ^{[4
]}

Murakami, Kazuaki ^{[1
,3
]}

机构：

[1] Kyushu Univ, Res Inst Informat Technol, 6-10-1 Hakozaki Fukuoka, Fukuoka 8128581, Japan

[2] IST, Fukuoka, Japan

[3] Kyushu Univ, Grad Sch Informat Sci & Elect Engn, Fukuoka 812, Japan

[4] Fujitsu Ltd, Fukuoka, Japan

来源：

COMPUTATION IN MODERN SCIENCE AND ENGINEERING VOL 2, PTS A AND B | 2007年 / 2卷

关键词：

sparse matrix; parallel computing; load balance; matrix multiplication; MPI;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper proposes and evaluates an algorithm of parallel matrix multiplication on compressed sparse-matrices. In addition to that, to overcome the problem of imbalanced distribution of non-zero elements over processors, a technology for dynamic load-balancing is examined. Measurements of the performance show that the algorithm achieves sufficient speed up. The experiments in this paper could not show the significant effect of the dynamic load-balancing. It requires more analysis to determine the reason of this.

引用

页码：106 / +

页数：2

共 50 条

[21] TileSpGEMM: A Tiled Algorithm for Parallel Sparse General Matrix-Matrix Multiplication on GPUs
Niu, Yuyao
Lu, Zhengyang
Ji, Haonan
Song, Shuhui
Jin, Zhou
Liu, Weifeng
PPOPP'22: PROCEEDINGS OF THE 27TH ACM SIGPLAN SYMPOSIUM ON PRINCIPLES AND PRACTICE OF PARALLEL PROGRAMMING, 2022, : 90 - 106
[22] Merge-based Parallel Sparse Matrix-Vector Multiplication
Merrill, Duane
Garland, Michael
SC '16: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE FOR HIGH PERFORMANCE COMPUTING, NETWORKING, STORAGE AND ANALYSIS, 2016, : 678 - 689
[23] Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks
Buluc, Aydin
Fineman, Jeremy T.
Frigo, Matteo
Gilbert, John R.
Leiserson, Charles E.
SPAA'09: PROCEEDINGS OF THE TWENTY-FIRST ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2009, : 233 - 244
[24] Performance Model for Parallel Matrix Multiplication with Dryad: Dataflow Graph Runtime
Li, Hui
Fox, Geoffrey
Qiu, Judy
SECOND INTERNATIONAL CONFERENCE ON CLOUD AND GREEN COMPUTING / SECOND INTERNATIONAL CONFERENCE ON SOCIAL COMPUTING AND ITS APPLICATIONS (CGC/SCA 2012), 2012, : 675 - 683
[25] Dynamic Load Balancing of Parallel SURF with Vertical Partitioning
Kim, Deokho
Kim, Minwoo
Kim, Kyungah
Sung, Minyong
Ro, Won Woo
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (12) : 3358 - 3370
[26] A two-dimensional data distribution method for parallel sparse matrix-vector multiplication
Vastenhouw, B
Bisseling, RH
SIAM REVIEW, 2005, 47 (01) : 67 - 95
[27] Dynamic Load Balancing in Parallel Execution of Cellular Automata
Giordano, Andrea
De Rango, Alessio
Rongo, Rocco
D'Ambrosio, Donato
Spataro, William
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2021, 32 (02) : 470 - 484
[28] Merge-based Parallel Sparse Matrix-Sparse Vector Multiplication with a Vector Architecture
Li, Haoran
Yokoyama, Harumichi
Araki, Takuya
IEEE 20TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS / IEEE 16TH INTERNATIONAL CONFERENCE ON SMART CITY / IEEE 4TH INTERNATIONAL CONFERENCE ON DATA SCIENCE AND SYSTEMS (HPCC/SMARTCITY/DSS), 2018, : 43 - 50
[29] Performance Improvement for CMT-SCTP via Load-Balancing Virtual Connections
Chen, Yu-Li
Chen, Po-Wei
Wang, Chia-Hui
2015 INTERNATIONAL CONFERENCE AND WORKSHOP ON COMPUTING AND COMMUNICATION (IEMCON), 2015,
[30] A locality-conscious load-balancing based on negotiations in dynamic unstructured mesh computations
Mohamed, AS
Baydogan, VS
PDPTA'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS 1-4, 2003, : 806 - 813

← 1 2 3 4 5 →