Memory efficient parallel matrix multiplication operation for irregular problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Memory efficient parallel matrix multiplication operation for irregular problems

Full text

Pdf (546 KB)

Source

Conference On Computing Frontiers archive
Proceedings of the 3rd conference on Computing frontiers table of contents

Ischia, Italy

SESSION: Applications I table of contents

Pages: 229 - 240

Year of Publication: 2006

ISBN:1-59593-302-6

Authors

Manojkumar Krishnan	Pacific Northwest National Laboratory, Richland, WA
Jarek Nieplocha	Pacific Northwest National Laboratory, Richland, WA

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 123, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1128022.1128054 What is a DOI?

ABSTRACT

Regular distributions for storing dense matrices on parallel systems are not always used in practice. In many scientific applicati RUMMA) [1] to handle irregularly distributed matrices. Our approach relies on a distribution independent algorithm that provides dynamic load balancing by exploiting data locality and achieves performance as good as the traditional approach which relies on temporary arrays with regular distribution, data redistribution, and matrix multiplication for regular matrices to handle the irregular case. The proposed algorithm is memory-efficient because temporary matrices are not needed. This feature is critical for systems like the IBM Blue Gene/L that offer very limited amount of memory per node. The experimental results demonstrate very good performance across the range of matrix distributions and problem sizes motivated by real applications.

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	M. Krishnan, J. Nieplocha, "SRUMMA: A Matrix Multiplication Algorithm Suitable for Clusters and Scalable Shared Memory Systems", Proc. IPDPS'04, 2004.
	2	Lynn Elliot Cannon, A cellular computer to implement the kalman filter algorithm, 1969
	3	G. C. Fox, S. W. Otto, A. J. G. Hey, "Matrix algorithms on a hypercube I: Matrix multiplication", Parallel Computing, vol. 4, pp. 17--31, 1987.
	4	Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	5	G.H. Golub, C.H Van Loan. Matrix Computations. Johns Hopkins University Press, 1989.
	6	J. Berntsen, Communication efficient matrix multiplication on hypercubes, Parallel Computing, vol. 12, 1989.
	7	A. Gupta and V. Kumar, "Scalability of Parallel Algorithms for Matrix Multiplication", ICPP'93, 1993.
	8	C. Lin and L.Snyder, "A matrix product algorithm and its comparative performance on hypercubes", SHPCC '92.
	9	Q. Luo and J. B. Drake, A Scalable Parallel Strassen's Matrix Multiply Algorithm for Distributed Memory Computers, http://citeseer.nj.nec.com/517382.html
	10	S. Huss-Lederman, E. M. Jacobson, and A. Tsao, "Comparison of Scalable Parallel Matrix Multiplication Libraries," in Proceedings of the Scalable Parallel Libraries Conference, 1994.
	11	C. T. Ho, S. L. Johnsson, A. Edelman, Matrix multiplication on hypercubes using full bandwidth and constant storage, Proc. 6 Distributed Memory Computing Conference. 1991.
	12	Himanshu Gupta , P. Sadayappan, Communication efficient matrix multiplication on hypercubes, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.320-329, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181434]
	13	J. Li, A. Skjellum, and R. D. Falgout, "A Poly-Algorithm for Parallel Dense Matrix Multiplication on Two-Dimensional Process Grid Topologies," Concurrency, Practice and Experience, vol. 9(5), pp. 345--389, 1997.
	14	E. Dekel, D. Nassimi, S. Sahni, Parallel matrix and graph algorithms, SIAM J. Computing, vol. 10, 1981.
	15	Sanjay Ranka , Sartaj Sahni, Hypercube algorithms: with applications to image processing and pattern recognition, Springer-Verlag New York, Inc., New York, NY, 1990
	16	J. Choi, J. Dongarra, and D. W. Walker, "PUMMA: Parallel Universal Matrix Multiplication Algorithms on distributed memory concurrent computers," Concurrency: Practice and Experience, vol. 6(7), 1994.
	17	S. Huss-Lederman, E. Jacobson, A. Tsao, and G. Zhang, "Matrix Multiplication on the Intel Touchstone DELTA", Concurrency: Practice and Experience, vol. 6 (7). Oct 1994.
	18	R. C. Agarwal , F. G. Gustavson , M. Zubair, A high-performance matrix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communication, IBM Journal of Research and Development, v.38 n.6, p.673-681, Nov. 1994
	19	R. van de Geijn, R. and J. Watts, "SUMMA: Scalable Universal Matrix Multiplication Algorithm," Concurrency: Practice and Experience, vol. 9(4), pp. 255--274, April 1997.
	20	J. Choi , J. Dongarra , S. Ostrouchov , A. Petitet , D. Walker, A Proposal for a Set of Parallel Basic Linear Algebra Subprograms, University of Tennessee, Knoxville, TN, 1995
	21	Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
	22	J. Choi, A Fast Scalable Universal Matrix Multiplication Algorithm on Distributed-Memory Concurrent Computers, Proceedings of the 11th International Symposium on Parallel Processing, p.310-314, April 01-05, 1997
	23	C. Addison and Y. Ren, "OpenMP Issues Arising in the Development of Parallel BLAS and LAPACK libraries", in Proceedings EWOMP'01. 2001.
	24	G.R. Luecke, W. Lin, "Scalability and Performance of OpenMP and MPI on a 128-Processor SGI Origin 2000", Concurrency and Computation: Practice and Experience, vol. 13, pp 905--928. 2001.
	25	Meng-Shiou Wu , Srinivas Aluru , Ricky A. Kendall, Mixed Mode Matrix Multiplication, Proceedings of the IEEE International Conference on Cluster Computing, p.195, September 23-26, 2002
	26	T. Betcke, "Performance analysis of various parallelization methods for BLAS3 routines on cluster architectures",John von Neumann-Instituts fur Computing, Tech. Rep. FZJ-ZAM-IB-2000-15, 2000.
	27	J. L. Träff, H. Ritzdorf, R. Hempel "The Implementation of MPI-2 One-Sided Communication for the NEC SX-5", in Proceedings of Supercomputing, 2000.
	28	Jiuxing Liu , Jiesheng Wu , Sushmitha P. Kini , Pete Wyckoff , Dhabaleswar K. Panda, High performance RDMA-based MPI implementation over InfiniBand, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782855]
	29	J. Nieplocha, V. Tipparaju, M. Krishnan, G. Santhanaraman, and D.K. Panda," Optimizing Mechanisms for Latency Tolerance in Remote Memory Access Communication on Clusters", IEEE CLUSTER'03, 2003.
	30	A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, Addison Wesley, 2003.
	31	Cray Online documentation. Optimizing Applications on the Cray X1TM System. http://www.cray.com/craydoc/20/manuals/S-2315-50/html-S-2315-50/S-2315-50-toc.html
	32	Jarek Nieplocha , Bryan Carpenter, ARMCI: A Portable Remote Memory Copy Libray for Ditributed Array Libraries and Compiler Run-Time Systems, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.533-546, April 12-16, 1999
	33	ARMCI Web page. http://www.emsl.pnl.gov/docs/parsoft/armci/
	34	Jarek Nieplocha , Edoardo Apra , Jialin Ju , Vinod Tipparaju, One-Sided Communication on Clusters with Myrinet, Cluster Computing, v.6 n.2, p.115-124, April 2003 [doi>10.1023/A:1022800521563 ]
	35	Jarek Nieplocha , Vinod Tipparaju , Amina Saify , Dhabaleswar K. Panda, Protocols and Strategies for Optimizing Performance of Remote Memory Operations on Clusters, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.275, April 15-19, 2002
	36	Manojkumar Krishnan , Jarek Nieplocha, Optimizing Parallel Multiplication Operation for Rectangular and Transposed Matrices, Proceedings of the Parallel and Distributed Systems, Tenth International Conference on (ICPADS'04), p.257, July 07-09, 2004 [doi>10.1109/ICPADS.2004.60]
	37	T.H. Dunning, Jr. J. Chem. Phys. 90, 1007 (1989).
	38	Y. Alexeev, M. Valiev, D. A. Dixon, T. L. Windus, "Ab initio study of catalytic GTP hydrolysis", J. of ACS, '04.
	39	I. Foster et al. "Toward High-Performance Computational Chemistry: I. Scalable Fock Matrix Construction Algorithms", Journal of computational chemistry, vol. 17, No. 1, 109--123, 1996.
	40	Ching-Hsien Hsu , Yeh-Ching Chung , Chyi-Ren Dow, Efficient Methods for Multi-Dimensional Array Redistribution, The Journal of Supercomputing, v.17 n.1, p.23-46, Aug. 2000 [doi>10.1023/A:1008167621154 ]
	41	Carter Edwards , Po Geng , Abani Patra , Robert van de Geijn, Parallel Matrix Distributions: Have we been doing it all wrong?, University of Texas at Austin, Austin, TX, 1995
	42	Hyuk-Jae Lee, J.A.B. Fortes, Toward data distribution independent parallel matrix multiplication, IPDPS, 1995.
	43	S. D. Kaushik , C.-H. Huang , R. W. Johnson , P. Sadayappan, An approach to communication-efficient data redistribution, Proceedings of the 8th international conference on Supercomputing, p.364-373, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181563]
	44	Banicescu, Ioana and R. Lu, Experiences with Fractiling in N-Body Simulations, HPC Symposium, 1998.
	45	Kendall et al, "High Performance Computational Chemistry: an Overview of NWChem a Distributed Parallel Application", Computer Phys. Comm., 2000, 128, 260--283.