A comparison of parallelization approaches for numerical linear algebra

Abstract: The efficiency of numerical libraries for a given computation is highly dependent on the size of the inputs. For very small inputs it is expected that LAPACK combined with BLAS is the superior alternative, while the new generation of parallelized numerical libraries (such as PLASMA and SuperMatrix) is expected to be superior for large inputs. In between these two extremes in input sizes, there might exist a niche for a new class of numerical libraries.In this thesis a prototype library, targeting medium sized inputs, is presented. The prototype library uses a mixed data and task parallel approach, with the Static BFS Scheduling of M-tasks (SBSM) algorithm, and provides lightweight scheduling for numerical computations. The aim of the prototype library is to explore the competitiveness of such an approach, compared to the more traditional parallelization approaches (data and task parallelism). The competitiveness is measured in a set of synthetic benchmarks using matrix multiplication as the reference computation.The results show that the prototype library exhibits potential for superseding the performance of today’s libraries for medium sized inputs. To give a conclusive answer as to whether the approach is worth pursuing with large research and development efforts, further investigation of the scheduling algorithm, as well as the numerical computations, should be examined through additional benchmarks.