The Torus-Wrap Mapping for Dense Matrix Calculations on Massively Parallel Computers
Authors:
- Bruce A. HendricksonBHBruce A. Hendrickson
- David E. WombleDWDavid E. Womble
- 1 September 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 15 (5) , 1201-1226
Abstract
Dense linear systems of equations are quite common in science and engineering, arising in boundary element methods, least squares problems, and other settings. Massively parallel computers will be necessary to solve the large systems required by scientists and engineers, and scalable parallel algorithms for the linear algebra applications must be devised for these machines. A critical step in these algorithms is the mapping of matrix elements to processors. In this paper, the use of the torus-wrap mapping in general dense matrix algorithms is studied from both theoretical and practical viewpoints. Under reasonable assumptions, it is proved that this assignment scheme leads to dense matrix algorithms that achieve (to within a constant factor) the lower bound on interprocessor communication. It is also shown that the torus-wrap mapping allows algorithms to exhibit less idle time, better load balancing, and less memory overhead than the more common row and column mappings. Finally, practical implementation issues are discussed, such as compatibility with basic linear algebra subprograms (BLAS) levels 1, 2, and 3, and the results of implementations of several dense matrix algorithms are presented. These theoretical and experimental results are compared with those obtained from more traditional mappings.Keywords
This publication has 23 references indexed in Scilit:
- Parallel Triangular System Solving on a Mesh Network of TransputersSIAM Journal on Scientific and Statistical Computing, 1991
- QR Factorization of a Dense Matrix on a Hypercube MultiprocessorSIAM Journal on Scientific and Statistical Computing, 1990
- A set of level 3 basic linear algebra subprogramsACM Transactions on Mathematical Software, 1990
- Parallel LU decomposition on a transputer network1989
- $LU$ Factorization Algorithms on Distributed-Memory Multiprocessor ArchitecturesSIAM Journal on Scientific and Statistical Computing, 1988
- Development of Parallel Methods for a $1024$-Processor HypercubeSIAM Journal on Scientific and Statistical Computing, 1988
- Parallel Solution of Triangular Systems on Distributed-Memory MultiprocessorsSIAM Journal on Scientific and Statistical Computing, 1988
- A parallel Householder tridiagonalization stratagem using scattered square decompositionParallel Computing, 1988
- Communication efficient basic linear algebra computations on hypercube architecturesJournal of Parallel and Distributed Computing, 1987
- Implementation of some concurrent algorithms for matrix factorizationParallel Computing, 1986