An overview of SymPLA

This document will describe the methods used to implement the prototype of the Symbolic Parallel Linear Algebra library (SymPLA).

SymPLA is organized in four layers, as shown in Figure : the application layer, the high level SymPLA layer, the implementation specific code, and the external libraries.

  
Figure: Structure of SymPLA

The application layer is the user's program, which uses the SymPLA high level layer to perform linear algebra operations. The high level layer organizes the operations into general operations, and then uses the implementation layer to handle storage and the interface with the external libraries in the lowest layer, which handles most of the actual linear algebra operations.

Of these layers, the middle two layers constitute the SymPLA library, and are discussed in this document. The lowest layer, the external libraries, will usually be third-party, but may also be completely integrated in the implementation layer.

Each layer communicates only with the layers immediately above and below itself, and the functionality is therefore completely hidden from layers higher up in the hierarchy.

SymPLA has the following general properties:

• SymPLA enables the developer to code the algorithm as close to the mathematical notation as possible, or when this is not possible, the expressions still make the meaning clear. The application code does not need to be changed when the application is moved to a different architecture or compiler.
• SymPLA treats matrices, transposed matrices and submatrices equally, and assignments to a submatrix affect all references to submatrices of the original matrix, including the original matrix itself. Vectors are handled in a similar manner.
• Storage and manipulation of matrix data are transparent to the SymPLA high level layer. This level uses flags and requests to the lower level to select operations on the data.
• SymPLA does not need modifications, except in the few classes that are architecture dependent when the class is moved to use an unsupported architecture or library.
• SymPLA has been implemented as a frontend/backend implementation for a single processor, the MasPar MP-2, the Intel Paragon, and workstation clusters, using either BLAS, LAPACK, native numerical libraries or ScaLAPACK, depending on the architecture.
• SymPLA is the only C++ linear algebra library known to us that allows a sequential computer running a sequential C++ program to use a parallel computer for calculation.

While exception handling might have been desirable, practical circumstances made this somewhat difficult, as the cfront compilers available for the MasPar and Intel Paragon architectures do not support exceptions. The library was therefore implemented with a skeleton exception-handling mostly turned over to macros and inline functions that let the application exit when an exception is thrown.

The implementation is restricted to a frontend design, because a multiple frontend or a complete SPMD distribution design as used in ScaLAPACK would have required much extra work. Among other things, a communication class had to be developed, and for some conceivable implementations, there was also need for features not yet supported by some of the desired support libraries, like thread-safe PVM. The organization of SymPLA is, however, such that it may easily be expanded into a fully parallel library, without much, or any modification to the high levels of the library.

Benchmarks have shown that SymPLA can achieve performance comparable to that of using the libraries SymPLA is based on directly, with very little overhead for the supporting operations. However, operations using random submatrices proved to have a very large overhead in arithmetic operations, due to the duplication of data necessary in the operation.