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] An Efficient Dynamic Load-Balancing Large Scale Graph-Processing System [J].

Kuo, Ming-Chia ;

Liu, Pangfeng ;

Wu, Jan-Jan .

PROCEEDINGS OF 2018 VII INTERNATIONAL CONFERENCE ON NETWORK, COMMUNICATION AND COMPUTING (ICNCC 2018), 2018, :294-298

[22] TileSpGEMM: A Tiled Algorithm for Parallel Sparse General Matrix-Matrix Multiplication on GPUs [J].

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

[23] Merge-based Parallel Sparse Matrix-Vector Multiplication [J].

Merrill, Duane ;

Garland, Michael .

SC '16: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE FOR HIGH PERFORMANCE COMPUTING, NETWORKING, STORAGE AND ANALYSIS, 2016, :678-689

[24] Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks [J].

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

[25] Performance Model for Parallel Matrix Multiplication with Dryad: Dataflow Graph Runtime [J].

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

[26] Dynamic Load Balancing in Parallel Execution of Cellular Automata [J].

Giordano, Andrea ;

De Rango, Alessio ;

Rongo, Rocco ;

D'Ambrosio, Donato ;

Spataro, William .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2021, 32 (02) :470-484

[27] Dynamic Load Balancing of Parallel SURF with Vertical Partitioning [J].

Kim, Deokho ;

Kim, Minwoo ;

Kim, Kyungah ;

Sung, Minyong ;

Ro, Won Woo .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (12) :3358-3370

[28] A two-dimensional data distribution method for parallel sparse matrix-vector multiplication [J].

Vastenhouw, B ;

Bisseling, RH .

SIAM REVIEW, 2005, 47 (01) :67-95

[29] Merge-based Parallel Sparse Matrix-Sparse Vector Multiplication with a Vector Architecture [J].

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

[30] Performance Improvement for CMT-SCTP via Load-Balancing Virtual Connections [J].

Chen, Yu-Li ;

Chen, Po-Wei ;

Wang, Chia-Hui .

2015 INTERNATIONAL CONFERENCE AND WORKSHOP ON COMPUTING AND COMMUNICATION (IEMCON), 2015,

← 1 2 3 4 5 →