Parallel Matrix Multiplication On a Cluster of PCs
Article Sidebar
Main Article Content
Abstract
This paper presents the implementation of the coarse-gained parallel matrix multiplication (c = A x B) with two ways of data partitioning on a cluster of PCs. In the past, most existing studies proposed the medium-grained parallel matrix multiplications on the hypercube-connected on mesh-connected parallel computers. We propose to study and implement the practical parallel matrix multiplication based on the MPMD model on the cluster of PCs using MPI (Message Passing Interface) standard. In particular, two data partitioning schemes for decomposing matrix A and matrix B with balancing workload are presented: 1) the row-block partitioning and 2) the checkerboard-block partitioning. Moreover, we also introduce a modified parallel matrix multiplication to cover an approach of the parallel all-pair shortest paths. Finally, the system performance of sequential and parallel processing of the matrix multiplication have been compared and evaluated in terms of response time, speedup, and efficiency. Based on our experimental results, the system performance of the matrix multiplication was improved up to 50% when the number of processors(p) were increased by one.
Keywords: Parallel matrix multiplication, data-block partitioning, an approach of parallel all-pair shortest paths, a cluster of PCs, MPMD (Multiple Program Multiple Data), MPI (Message Passing Interface)
Corresponding author: E-mail: s6063611@kmitl.ac.th
Article Details
Copyright Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
References
[2] Browne, S., Dongarra, J. and London, K. 1997 Review of Performance Analysis Tools for MPI Parallel rograms, http://www.cs.utk.edu/~browne/perftools-review/.
[3] Beaumont, O., Boudet, V., Rastello, F. and Robert, Y. 2001 Matrix Multiplication on Heterogeneous Platforms, IEEE Trans. On Parallel and Distributed Systems, v.12 (10), 1033-1051.
[4] Choi, J. 1997 A Fast Scalable Universal Matrix Multiplication Algorithm on Distributed-Memory Concurrent Computers, IEEE Trans. on Parallel and Distributed Systems 3, 310-314.
[5] Choi, J. 1997 A New Parallel Matrix Multiplication Algorithm on Distributed- Memory Concurrent Computers, HPC Asia’97 High Performance Computing on the Information Superhighway, 224-229.
[6] Li, K. 2000 Scalable Parallel Matrix Multiplication on Distributed Memory Parallel Computers, Parallel and Distributed Processing Symposium IPDPS 2000. Proceedings. 14th International, 307-314.
[7] Sengupta, A. and Raghavendra, C.S. 1998 All-To-All Broadcast and Matrix Multiplication in Faculty SIMD Hypercubes, IEEE Trans. on Parallel and Distributed Systems, v.9(6), 550-560.
[8] Tasic, J.F., Zajc, M. and Kosir, A. 1996 Comparison of Some Parallel Matrix Multiplication Algorithms, Electrotechnical Conference MELECON’ 96., 8th Mediterranean, v.1, 155-158.
[9] Typou, T., Stefanidis, V., Michailidis P. and Margaritis, K. 2004 Implementing Matrix Multiplication on an MPI Cluster of Workstations. The 1st Int’l Conference from Scientific Computing to Computational Engineering (IC-SCCE), Athens.
