The PLAPACK library

PLAPACK is a production-quality library for coding parallel linear algebra algorithms in C. It consists of approximately 40,000 lines of C code and provides parallel versions of the same kernel routines found in the BLAS [11] and LAPACK [2]. At the highest level, it provides an interface that hides much of the parallelism from the programmer.

A PLAPACK application operates on linear algebra objects, such as matrices and vectors, that are partitioned and distributed over the processors of the target computer. The application manipulates these objects indirectly though handles called views. A view specifies an index range that selects some or all of a distributed object for subsequent computations. PLAPACK contains routines to create new views, shift views, and split views into pieces. The following figure shows a four-way split that logically divides a matrix into four smaller ones:

 

A typical algorithm starts with an entire object, like A, and splits it into manageable pieces. It computes directly on A₁₁, A₁₂ and A₂₁, and then continues recursively by splitting the large remaining piece, A₂₂, until the entire data set has been visited.

Often, a view captures part of a matrix or vector that has special properties. Understanding and exploiting these properties can lead to significant performance improvements. For example, a view can select a region that resides entirely on one processor. Any computations on the data within this local view can be performed locally, without involving other processors. In the figure above, the four-way split yields one local view (A₁₁), one column panel (A₂₁), which resides on a column of processors, one row panel (A₁₂), which resides on a row of processors, and a large fully-distributed matrix (A₂₂). A view might also specify a region that is in tridiagonal form, allowing the use of specialized compute functions.

Our goal is to identify the library-specific properties that are relevant to optimization, and track them through the application program. For example, if an application splits a local view into two pieces, we can infer that the two new views are also local. The result of this analysis describes how the application manipulates objects with respect to library-specific properties such as distribution or data content. We can use this information to customize the library, or to select library routines that are better suited to the application.

Figure  shows a fragment of the annotations for PLAPACK. It specifies the two properties described above (distribution and data content) and gives the semantics of three PLAPACK routines: PLA_Matrix_create, which creates a new matrix, PLA_Obj_vert_split_2 which splits a view into left and right pieces, and PLA_Gemm, which multiplies matrices.²