Matrix-matrix multiplication on heterogeneous platforms
- 1 January 2000
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
International audienceIn this paper, we address the issue of implementing matrix-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 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 experimentKeywords
This publication has 6 references indexed in Scilit:
- Static tiling for heterogeneous computing platformsParallel Computing, 1999
- Globus: a Metacomputing Infrastructure ToolkitThe International Journal of Supercomputer Applications and High Performance Computing, 1997
- Customized Dynamic Load Balancing for a Network of WorkstationsJournal of Parallel and Distributed Computing, 1997
- ScaLAPACK Users' GuidePublished by Society for Industrial & Applied Mathematics (SIAM) ,1997
- A high-performance matrix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communicationIBM Journal of Research and Development, 1994
- Matrix algorithms on a hypercube I: Matrix multiplicationParallel Computing, 1987