Scalability Issues Affecting the Design of a Dense Linear Algebra Library

J. J. Dongarra, R. A. Vandegeijn, D. W. Walker

    Research output: Contribution to journalArticlepeer-review


    This paper discusses the scalability of Cholesky, LU, and QR factorization routines on MIMD distributed memory concurrent computers. These routines form part of the ScaLAPACK mathematical software library that extends the widely used LAPACK library to run efficiently on scalable concurrent computers. To ensure good scalability and performance, the ScaLAPACK routines are based on block-partitioned algorithms that reduce the frequency of data movement between different levels of the memory hierarchy, and particularly between processors. The block cyclic data distribution, that is used in all three factorization algorithms, is described. An outline of the sequential and parallel block-partitioned algorithms is given. Approximate models of algorithms′ performance are presented to indicate which factors in the design of the algorithm have an impact upon scalability. These models are compared with timings results on a 128-node Intel iPSC/860 hypercube. It is shown that the routines are highly scalable on this machine for problems that occupy more than about 25% of the memory on each processor, and that the measured timings are consistent with the performance model. The contribution of this paper goes beyond reporting our experience: our implementations are available in the public domain. © 1994 Academic Press. All rights reserved.
    Original languageEnglish
    Pages (from-to)523-537
    Number of pages14
    JournalJournal of Parallel and Distributed Computing
    Issue number3
    Publication statusPublished - Sept 1994


    Dive into the research topics of 'Scalability Issues Affecting the Design of a Dense Linear Algebra Library'. Together they form a unique fingerprint.

    Cite this