Communication efficient matrix multiplication on hypercubes

Himanshu Gupta; P. Sadayappan

doi:10.1145/181014.181434

Communication efficient matrix multiplication on hypercubes

Himanshu Gupta
, P. Sadayappan

Computer Science

Stony Brook University

Ohio State University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

In this paper we present an efficient dense matrix multiplication algorithm for distributed memory computers with a hypercube topology. The proposed algorithm performs better than all previously proposed algorithms for a wide range of matrix sizes and number of processors, especially for large matrices. We analyze the performance of the algorithms for two types of hypercube architectures, one in which each node can use (to send and receive) at most one communication link at a time and the other in which each node can use all communication links simultaneously.

Original language	English
Title of host publication	Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Publisher	Association for Computing Machinery, Inc
Pages	320-329
Number of pages	10
ISBN (Electronic)	0897916719, 9780897916714
DOIs	https://doi.org/10.1145/181014.181434
State	Published - Aug 1 1994
Event	6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 - Cape May, United States Duration: Jun 27 1994 → Jun 29 1994

Publication series

Name	Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

Conference

Conference	6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Country/Territory	United States
City	Cape May
Period	06/27/94 → 06/29/94

Keywords

3-D grids
Distributed algorithms
Hypercubes
Interprocessor communication
Matrix multiplication

Access to Document

10.1145/181014.181434

Cite this

Gupta, H., & Sadayappan, P. (1994). Communication efficient matrix multiplication on hypercubes. In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 (pp. 320-329). (Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994). Association for Computing Machinery, Inc. https://doi.org/10.1145/181014.181434

@inproceedings{8e617df064ac4882a4d3a967f4c2af7a,

title = "Communication efficient matrix multiplication on hypercubes",

abstract = "In this paper we present an efficient dense matrix multiplication algorithm for distributed memory computers with a hypercube topology. The proposed algorithm performs better than all previously proposed algorithms for a wide range of matrix sizes and number of processors, especially for large matrices. We analyze the performance of the algorithms for two types of hypercube architectures, one in which each node can use (to send and receive) at most one communication link at a time and the other in which each node can use all communication links simultaneously.",

keywords = "3-D grids, Distributed algorithms, Hypercubes, Interprocessor communication, Matrix multiplication",

author = "Himanshu Gupta and P. Sadayappan",

note = "Publisher Copyright: {\textcopyright} 1994 ACM.; 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 ; Conference date: 27-06-1994 Through 29-06-1994",

year = "1994",

month = aug,

day = "1",

doi = "10.1145/181014.181434",

language = "English",

series = "Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994",

publisher = "Association for Computing Machinery, Inc",

pages = "320--329",

booktitle = "Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994",

}

Gupta, H & Sadayappan, P 1994, Communication efficient matrix multiplication on hypercubes. in Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994. Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994, Association for Computing Machinery, Inc, pp. 320-329, 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994, Cape May, United States, 06/27/94. https://doi.org/10.1145/181014.181434

Communication efficient matrix multiplication on hypercubes. / Gupta, Himanshu; Sadayappan, P.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994. Association for Computing Machinery, Inc, 1994. p. 320-329 (Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Communication efficient matrix multiplication on hypercubes

AU - Gupta, Himanshu

AU - Sadayappan, P.

PY - 1994/8/1

Y1 - 1994/8/1

N2 - In this paper we present an efficient dense matrix multiplication algorithm for distributed memory computers with a hypercube topology. The proposed algorithm performs better than all previously proposed algorithms for a wide range of matrix sizes and number of processors, especially for large matrices. We analyze the performance of the algorithms for two types of hypercube architectures, one in which each node can use (to send and receive) at most one communication link at a time and the other in which each node can use all communication links simultaneously.

AB - In this paper we present an efficient dense matrix multiplication algorithm for distributed memory computers with a hypercube topology. The proposed algorithm performs better than all previously proposed algorithms for a wide range of matrix sizes and number of processors, especially for large matrices. We analyze the performance of the algorithms for two types of hypercube architectures, one in which each node can use (to send and receive) at most one communication link at a time and the other in which each node can use all communication links simultaneously.

KW - 3-D grids

KW - Distributed algorithms

KW - Hypercubes

KW - Interprocessor communication

KW - Matrix multiplication

UR - https://www.scopus.com/pages/publications/0039066274

U2 - 10.1145/181014.181434

DO - 10.1145/181014.181434

M3 - Conference contribution

T3 - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

SP - 320

EP - 329

BT - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

PB - Association for Computing Machinery, Inc

T2 - 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

Y2 - 27 June 1994 through 29 June 1994

ER -

Communication efficient matrix multiplication on hypercubes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this