PARALLELIZING STRASSENS METHOD FOR MATRIX MULTIPLICATION ON DISTRIBUTED-MEMORY MIMD ARCHITECTURES

被引：12

作者：

CHOU, CC ^{[1
]}

DENG, YF ^{[1
]}

LI, G ^{[1
]}

WANG, Y ^{[1
]}

机构：

[1] SUNY STONY BROOK,CTR SCI COMP,STONY BROOK,NY 11794

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 1995年 / 30卷 / 02期

基金：

美国国家科学基金会;

关键词：

MATRIX MULTIPLICATION; PARALLEL COMPUTATION; STRASSENS METHOD;

D O I：

10.1016/0898-1221(95)00077-C

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a parallel method for matrix multiplication on distributed-memory MIMD architectures based on Strassen's method. Our timing tests, performed on a 56-node Intel Paragon, demonstrate the realisation of the potential of the Strassen's method with a complexity of 4.7M(2.807) at the system level rather than the node level at which several earlier works have been focused. The parallel efficiency is nearly perfect when the processor number is the power of 7. The parallelized Strassen's method seems always faster than the traditional matrix multiplication methods whose complexity is 2M(3) coupled with the BMR method and the Ring method at the system level. The speed gain depends on matrix order M: 20% for M approximate to 100% and more than 100% for M approximate to 5000.

引用

页码：49 / 69

页数：21

共 50 条

[1] Parallelizing RRT on Distributed-Memory Architectures
Devaurs, Didier
Simeon, Thierry
Cortes, Juan
2011 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), 2011, : 2261 - 2266
[2] Parallelizing RRT on Large-Scale Distributed-Memory Architectures
Devaurs, Didier
Simeon, Thierry
Cortes, Juan
IEEE TRANSACTIONS ON ROBOTICS, 2013, 29 (02) : 571 - 579
[3] Communication lower bounds for distributed-memory matrix multiplication
Irony, D
Toledo, S
Tiskin, A
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2004, 64 (09) : 1017 - 1026
[4] COMPILING FOR DISTRIBUTED-MEMORY ARCHITECTURES
ROGERS, A
PINGALI, K
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (03) : 281 - 298
[5] THE COST OF EIGENVALUE COMPUTATION ON DISTRIBUTED-MEMORY MIMD MULTIPROCESSORS
CRIVELLI, S
JESSUP, ER
PARALLEL COMPUTING, 1995, 21 (03) : 401 - 422
[6] The PMESC programming library for distributed-memory MIMD computers
Crivelli, S
Jessup, ER
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1999, 57 (03) : 295 - 321
[7] A new parallel matrix multiplication algorithm on distributed-memory concurrent computers
Choi, J
CONCURRENCY-PRACTICE AND EXPERIENCE, 1998, 10 (08): : 655 - 670
[8] New parallel matrix multiplication algorithm on distributed-memory concurrent computers
Choi, Jaeyoung
Proceedings of the Conference on High Performance Computing on the Information Superhighway, HPC Asia'97, 1997, : 224 - 229
[9] A new parallel matrix multiplication algorithm on distributed-memory concurrent computers
Choi, J
HIGH PERFORMANCE COMPUTING ON THE INFORMATION SUPERHIGHWAY - HPC ASIA '97, PROCEEDINGS, 1997, : 224 - 229
[10] Parallelizing molecular dynamics programs for distributed-memory machines
Hwang, Yuan-Shin
Das, Raja
Saltz, Joel H.
Hodoscek, Milan
Brooks, Bernard R.
IEEE computational science & engineering, 2 (02): : 18 - 29

← 1 2 3 4 5 →