Parallel resolution of alternating-line processes by means of pipelining techniques

The aim of this paper is to present an easy and efficient method to implement alternating-line processes on current parallel computers. First we show how data locality has an important impact on global efficiency, which leads us to the conclusion that one-dimensional compositions are the most convenient ones for 2D problems. Once this is asserted, a parallel algorithm is presented for the solution of the distributed tridiagonal systems along the partitioned direction. The key idea is to pipeline the simultaneous resolution of many systems of equations, not parallelising each resolution separately. This approach presents good numerical and architectural properties, in terms of memory usage and data locality, and high parallel efficiencies are obtained. For the case of alternating-line processes, the election of the optimal decomposition is studied. The experimental results have been obtained on a Cray T3E