The design and implementation of SOLAR, a portable library for scalable out-of-core linear algebra computations
Sivan Toledo, Fred G. Gustavson · 1996
SOLAR is a portable high-perfonnance library for out-of-core dense matrix computations.It combines portability with high perfonnance by using existing high-perfonnance in-core subroutine libraries and by using an optimized matrix input-output library.SOLAR works on parallel computers, workstations, and personal computers.It supports in-core computations on both shared-memory and distributed-memory machines, and its matrix input-output library supports both conventional 1/0 interfaces and parallel 110 interfaces.This paper discusses the overall design of SOLAR, its interfaces, and the design of several important subroutines.Experimental results show that SOLAR can factor on a single workstation an out-of-core positive-definite symmetric matrix at a rate exceeding 215 Mflops, and an out-of-core general matrix at a rate exceeding 195 Mflops.Less than 16% of the running time is spent on 110 in these computations.These results indicate that SOLAR's portability does not compromise its perfonnance.We expect that the combination of portability, modularity, and the use of a high-level 110 interface will make the library an important platfonn for research on out-of-core algorithms and on parallel 110. IntroductionThis paper describes the design and implementation of SOLAR, a high-perfonnance pmtable library for out-of-core dense matrix computations.SOLAR is designed to meet three main objectives.First, the library should deliver as much of the functionality of LAPACK [2], a public domain library for in-core matrix computations, as possible.Second, the library should be portable across a wide variety of architectures.Third, the library should deliver high perfonnance.The paper explains how the design allows us to achieve our objectives, and demonstrates that the implementation is indeed portable and achieves high perfonnance.Our current implementation does not yet include the full functionality of LAPACK for out-of-core matrices, but it does include both sequential and parallel solvers for general and positivedefinite symmetric linear systems as well as several support routines.Although current computers, especially parallel computers, have large amounts of memory, there is still a need for software for out-Permission to make digitnllhard copic• of all or part of thia material for pcraonal or classroom USt~ is granted without fcc provided that the copica a!C not ~de or ~istributc:d for J?TO~t or COf!UllCrcial advantage, the copynght nottce, the IItle of the pubhcahon and 1ta date appear, and notice is given tha~ copyright is by permission of~e.ACM, Inc.To copy otherwise, to repubhsh, to post on St~rvers or to redullnbute to lists, requires specific permission and/or fee.IOPADS'96, Philadelphia PA, USA 0 1996 ACM 0-89791 .. 813-4/96/05 .. $3.50 28 of-core matrix computations.Since DRAM is about 100 times more expensive than disk [18] and since out-of-core software for dense matrix computations can run at almost the rate of in-core software (see Section 4), out-of-core software can solve problems at a much lower cost-perfonnance ratio than in-core software.Out-of-core solvers can be used for the overnight solution of very large problems on workstations, for the solution of large problems in easy-to-use modeling environments such as Matlab, as well as for solving huge problems that do not fit within the primary memory of any existing computer.A testimony for the need for out-of-core software is the steady stream of implementations of such codes over the last 45 years [3,4,11,12,13,14,15,20,21,19,22,25], including a number of recent implementations (for example, [4, 12, 13, 15, 25]).Unfortunately, none of these codes appears to be portable, and all of them provide only a few subroutines that the implementors needed, rather than a full set of dense solvers.Consequently, many users cannot take advantage of these codes.Ubiquitous parallel computing in the fonn of scalable parallel computers, symmetric multiprocessors and networks of workstations provides two new incentives to use out-of-core algorithms.lflirst, it is often more cost-effective to speed up a computation that does not fit in core by adding processing units and continuing to use an outof-core solver than by than by adding enough memory to nm it in core.Second, it is now possible to increase the perfonnance of the 110 system using parallel 110 with disk arrays and parallel file systems.But parallel computing and parallel 110 also pose new challenges to out-of-core software.Current computer systems offer many different computing and 110 environments.The processing unit can be a uniprocessor, a symmetric multiprocessor with a shared memory, or a parallel computer with a distributed memory.The 1/0 can be perfonned by a conventional file system or a parallel file systc~m.and some of these file systems can use disk arrays or disks installed on several server nodes.A portable out-of-core library that aims to support all of these environments should therefore use flexible interfaces that can work in all of these environments.The interfaces sho1uld also enable the use of multiple alternative external software modules, such as multiple file systems and multiple in-core subroutine libraries.Besides providing users and application developers with a muchneeded functionality, SOLAR will serve as a research tool for two communities.The authors plan to use the library in research on outof-core numerical algorithms, and we hope that others will use it for research in algorithms as well.The history of linear algebra software indicates that libraries that support new architectures often advance the state of the art.We expect novel developments to emerge from SOLAR as well.Researchers working on 110 issues, such as parallel file systems and I/O-subsystem architecture will be able to use the library for empirical perfonnance evaluations.Using a full-featured