The challenges of heterogeneous computing discussed in this paper came to light during the development of ScaLAPACK and the NAG Numerical PVM Library ([&make_named_href('', "node12.html#McDonald:DMW:95","[17]")]).
ScaLAPACK is a library of high performance linear algebra routines for distributed memory MIMD machines. It is a continuation of the LAPACK project, which has designed and produced an efficient linear algebra library for workstations, vector supercomputers and shared memory parallel computers ([&make_named_href('', "node12.html#ABBDDDGHMOS:95","[1]")]). Both libraries contain routines for the solution of systems of linear equations, linear least squares problems and eigenvalue problems. The goals of the LAPACK project, which continue into the ScaLAPACK project, include efficiency so that the computationally intensive routines execute as fast as possible; reliability, including the return of condition estimates and error bounds; portability across machines; flexibility so that users may construct new routines from well designed components; and ease of use. Towards this last goal the ScaLAPACK software has been designed to look as much like the LAPACK software as possible. ScaLAPACK is naturally also concerned with scalability as the problem size and number of processors grow.
Many of these goals have been attained by developing and promoting standards, especially specifications for basic computational and communication routines. Thus LAPACK relies on the BLAS ([&make_named_href('', "node12.html#LHKK:TOMS:79x","[16]"), &make_named_href('', "node12.html#DDHH:TOMS:88","[7]"), &make_named_href('', "node12.html#DDDH:TOMS:90","[6]")]), particularly the Level 2 and 3 BLAS for computational efficiency, and ScaLAPACK relies upon the BLACS ([&make_named_href('', "node12.html#DW:UTK-cs:95","[8]")]) for efficiency of communication and uses a set of parallel BLAS, the PBLAS ([&make_named_href('', "node12.html#CDOPWW:DMW:95x","[3]")]), which themselves call the BLAS and the BLACS. LAPACK and ScaLAPACK will run on any machines for which the BLAS and the BLACS are available. A PVM ([&make_named_href('', "node12.html#GBDJMS:94","[9]")]) version of the BLACS has been available for some time and the portability of the BLACS has recently been further increased by the development of a version that uses MPI ([&make_named_href('', "node12.html#SOHWD:96","[18]")]).
As the BLACS are perhaps not so widely known as the BLAS and LAPACK, we now give a brief description. The BLACS, which stands for Basic Linear Algebra Communication Subprograms, form a message passing library, specifically designed for dense linear algebra, in which the computational model consists of a one or two dimensional grid of processes, where each process stores matrices and vectors. The BLACS include synchronous send and receive routines to send a matrix or submatrix from one process to another, to broadcast submatrices to many processes, or to compute global reductions such as sums, maxima and minima. There are also routines to set up, change, or query the process grid. The BLACS permit a process to be a member of more than one, possibly overlapping, grids, each one labeled by a context. Some message passing systems also include the idea of a context; in MPI it is termed a communicator. See [&make_named_href('', "node12.html#DW:UTK-cs:95","[8]")] and [&make_named_href('', "node12.html#SOHWD:96","[18]")] for further details.
The NAG Numerical PVM Library is a library of numerical routines, also for distributed memory MIMD machines, that contains routines for dense and sparse linear algebra, including ScaLAPACK routines, quadrature, optimization, random number generation and various utility routines for operations such as data distribution and error handling. This library owes much to the ScaLAPACK development, uses essentially the same model for distributed memory computing as ScaLAPACK and was developed with the same goals in mind ([&make_named_href('', "node12.html#Hammarling:DT:94","[11]")]). Since the development of an MPI version the NAG Library is now known generically as the NAG Parallel Library.
Both ScaLAPACK and the NAG Numerical PVM Library use the BLACS computational model and utilize the BLACS context. In addition they both use an SPMD programming model.
ScaLAPACK and the NAG Numerical PVM Library were developed with heterogeneous
environments in mind, as well as standard homogeneous machines. But during
development it was realized that we could not guarantee the safe behavior of all
our routines in a heterogeneous environment and so, for the time being, both
libraries are only fully supported on homogeneous machines. ScaLAPACK, though,
is tested on networks of IEEE machines and is believed to work correctly in such
environments, and it is intended to be able to fully support other heterogeneous
environments in the near future. Any known heterogeneous failures are documented
in the file errata.scalapack on Netlib
. It is intended that the NAG
Parallel Libraries should also support heterogeneous environments in the future.
In this report we concentrate primarily on the ScaLAPACK experience.