Mat r ix-Mat r ix Multiplication on Heterogeneous Plat forms

In this paper, we address the issue of imple-menting matrix-matrix multiplication on heteroge-neous platforms. We target two different classes of heterogeneous computing resources: heterogeneous networks of workstations, and collections of het-erogeneous clusters. Intuitively, the problem is to load balance the work with different-speed re-sources while minimizing the communication vol-ume. We formally state this problem and prove its NP-completeness. Next we introduce a (poly-nomial) column-based heuristic, which turns out to be very satisfactory: we derive a theoretical perfor-mance guarantee for the heuristic, and we assess its practical usefulness through MPI experiments.