Static LU Decomposition on Heterogeneous Platforms

Abstract

In this paper, the authors deal with algorithmic issues on heterogeneous platforms. They concentrate on dense linear algebra kernels, such as matrix multiplication or LU decomposition. Block-cyclic distribution techniques used in ScaLAPACK are no longer sufficient to balance the load among processors running at different speeds. The main result of this paper is to provide a static data distribution scheme that leads to an asymptotically perfect load balancing for LU decomposition, thereby providing solid foundations toward the design of a cluster-oriented version of ScaLAPACK.

Get full access to this article

View all access options for this article.

References

Agarwal, R. , Gustavson, F. , and Zubair, M. 1994. A high performance matrix multiplication algorithm on a distributed-memory parallel computer, using overlapped communication . IBM J. Research and Development 38 (6): 673-681 .

Beaumont, O. , Boudet, V. , Legrand, A. , Rastello, F. , and Robert, Y. 2000. Heterogeneity considered harmful to algorithm designers. Technical Report RR-2000-24, LIP, ENS Lyon [On-line]. Available: www.ens-lyon.fr/LIP/.

Beaumont, O. , Boudet, V. , Rastello, F. , and Robert, Y. 2000a. Matrix-matrix multiplication on heterogeneous platforms. Technical Report RR-2000-02, LIP, ENS Lyon .

Beaumont, O. , Boudet, V. , Rastello, F. , and Robert, Y. 2000b. Partitioning a square into rectangles: NP-completeness and approximation algorithms. Technical Report RR-2000-10, LIP, ENS Lyon .

Berman, F. 1998. High-performance schedulers. In The Grid: Blueprint for a New Computing Infrastructure, edited by I. Foster and C. Kesselman , 279-309. San Francisco: Morgan Kaufmann .

Blackford, L. S. , Choi, J. , Cleary, A. , D’Azevedo, E. , Demmel, J. , Dhillon, I. , Dongarra, J. , Hammarling, S. , Henry, G. , Petitet, A. , Stanley, K. , Walker, D. , and Whaley, R. C. 1997. ScaLAPACK users’ guide. Philadelphia: SIAM .

Boulet, P. , Dongarra, J. , Rastello, F. , Robert, Y. , and Vivien, F. 1999. Algorithmic issues on heterogeneous computing platforms . Parallel Processing Letters 9 (2): 197-213 .

Crandall, P. E. , and Quinn, M. J. 1993. Block data decomposition for data-parallel programming on a heterogeneous workstation network . In 2nd International Symposium on High Performance Distributed Computing, pp. 42-49 .

Foster, I. , and Kesselman, C. , eds. 1998. The Grid: Blueprint for a New Computing Infrastructure. San Francisco: Morgan Kaufmann .

10.

Fox, G. , Otto, S. , and Hey, A. 1987. Matrix algorithms on a hypercube i: Matrix multiplication . Parallel Computing 3: 17-31 .

11.

Kaddoura, M. , Ranka, S. , and Wang, A. 1996. Array decomposition for nonuniform computational environments . Journal of Parallel and Distributed Computing 36: 91-105 .

12.

Kalinov, A. , and Lastovetsky, A. 1999. Heterogeneous distribution of computations while solving linear algebra problems on networks of heterogeneous computers. In HPCN Europe 1999, LNCS 1593, edited by P. Sloot , M. Bubak , A. Hoekstra , and B. Hertzberger , 191-200. New York: Springer-Verlag .

13.

Kumar, V. , Grama, A. , Gupta, A. , and Karypis, G. 1994. Introduction to parallel computing. New York: Benjamin/Cummings .