Exploitation of Multilevel Parallelism on Structured Linear Systems

In this paper we analyze the implementation of some bidiagonal solvers on a SGI Shared Memory Multiprocessor (SMM) Power Challenge. The objective of the work is to understand how the different levels of parallelism offered by present SMMs (i.e. coarse grain and fine grain) can be used adequately by library programmers on algorithms for structured linear systems. In particular, we analyze the sequential Gaussian Elimination and the parallel Divide and Conquer and R-Cyclic Reduction algorithms. On one side, we analyze the parallelism at a coarse level and show that the synchronization and parallelization techniques offered by the computer behave poorly. On the other side, at a fine grain level, we show that a knowledge of Software Pipelining can help to understand and improve programs for a specific computer. Along the paper, we prove that it is necessary for software designers and programmers to have a profound knowledge of the architecture and programming tools of present computers in ..