Mapping Strategies in Data Parallel Programming Models; the Projection Methods

Abstract

We analyze data parallel programming of some general purpose methods in linear algebra. Specifically, the projection methods to solve very large linear system and/or eigenproblem. The expensive parts of these methods are their projection phases. This portion of these algorithms has generally, a very simple structure for such a programming model. It is composed essentially of matrix-vector multiplications and inner-products. Then, we simply need to find a good data distribution in order to obtain a well adapted communication pattern and not lose too much storage space. We begin with a survey of data parallel behavior of some projection methods such as Arnoldi, GMRES, Lanczos, PRR,… After analyzing some methods of data mapping onto virtual processors we point out that for a fixed number of physical processors, the performances are a function of the mapping method. We will see also that the maximum size of the problems which can be solved on the architectures supporting the data parallel programming model is a function of the data mapping method. In conclusion we present the performances obtained on a Connection Machine 5 (CM5).