Communication efficient matrix multiplication on hypercubes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Communication efficient matrix multiplication on hypercubes

Full text

Pdf (823 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures table of contents

Cape May, New Jersey, United States

Pages: 320 - 329

Year of Publication: 1994

ISBN:0-89791-671-9

Authors

Himanshu Gupta	Department of Computer and Information Science, Ohio State University, Columbus OH
P. Sadayappan	Department of Computer and Information Science, Ohio State University, Columbus OH

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 27, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/181014.181434 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. Bemtsen. Communication ei#iclent matrix multiplic#tion on hypercubes. Parallel Computing, 12:335- 342,1989.
	2	Lynn Elliot Cannon, A cellular computer to implement the kalman filter algorithm, 1969
	3	E. Dekel, D. Nassimi, and S. Sahni. Parallel matrix and graph algozithms. SIAM Journal of Computing, 10:657- 673, 1981.
	4	G. C. Fox, S. W. Otto, and A. J. G. Hey. Matrix algorithrns on a hypercube I: Matrix multiplication. Parallel Computing, 4:17-31,1987.
	5	A. Gupta and V. Kumar. Scalability of Parallel Algorithms for Matrix Multiplication. Proceedings of the 1993 International Conference on Parallel Processing, vol. 3, pp 115-123.
	6	Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	7	S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
	8	C. T. Ho, S. L. Jolmsson and A. Edelman. Matrix multiplication on hypercubes using full bandwidth and constant storage. In Proceeding of the Sizth Distributed Memory Computing Conference, 44%451, 1991.
	9	J. W. Demmel, M. T. Heath, and H. A. Van der Vorst. Parallel Linear Algebra. Acta Numerica. Vol. 2. Cambridge Press, New York, 1993.

CITED BY 2

	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	Manojkumar Krishnan , Jarek Nieplocha, Memory efficient parallel matrix multiplication operation for irregular problems, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy