IEEE Transactions on Parallel and Distributed Systems · 2001 · 161 citations · 26 references
ComputingComputer ScienceHigh-performance ComputingHeterogeneous ComputingParallel AlgorithmsParallel ComputingCluster ArchitectureData ParallelismDistributed ComputingHeterogeneous System ArchitectureMatrix ComputationParallel Numerical Linear AlgebraHeterogeneous Cluster ArchitectureHeterogeneous Computing SystemsHeterogeneous NetworksMatrix MultiplicationParallel Matrix AlgorithmsParallel Matrix ComputationParallel Matrix MultiplicationParallel Matrix-vector Multiplication
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.
26
Introduction to parallel computing
Choice Reviews Online · 2004 · 1.9K citations
Henri Casanova, Jack Dongarra · 1996 · 392 citations