Matrix multiplication on heterogeneous platforms
- 1 October 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 12 (10) , 1033-1051
- https://doi.org/10.1109/71.963416
Abstract
We address the issue of implementing matrix multiplication on heterogeneous platforms. We target two different classes of heterogeneous computing resources: heterogeneous networks of workstations and collections of heterogeneous clusters. Intuitively, the problem is to load balance the work with different speed resources while minimizing the communication volume. We formally state this problem in a geometric framework and prove its NP-completeness. Next, we introduce a (polynomial) column-based heuristic, which turns out to be very satisfactory: We derive a theoretical performance guarantee for the heuristic and we assess its practical usefulness through MPI experiments.Keywords
This publication has 21 references indexed in Scilit:
- Block data decomposition for data-parallel programming on a heterogeneous workstation networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Complexity and ApproximationPublished by Springer Nature ,1999
- The Legion vision of a worldwide virtual computerCommunications of the ACM, 1997
- Tiling a Rectangle with the Fewest SquaresJournal of Combinatorial Theory, Series A, 1996
- Array Decompositions for Nonuniform Computational EnvironmentsJournal of Parallel and Distributed Computing, 1996
- Approximation algorithms for partitioning a rectangle with interior pointsAlgorithmica, 1990
- Improved bounds for rectangular and guillotine partitionsJournal of Symbolic Computation, 1989
- The Decomposition of a Rectangle into Rectangles of Minimal PerimeterSIAM Journal on Computing, 1988
- Compiler optimizations for enhancing parallelism and their impact on architecture designIEEE Transactions on Computers, 1988
- Matrix algorithms on a hypercube I: Matrix multiplicationParallel Computing, 1987