On the efficiency of scheduling algorithms for parallel Gaussian elimination with communication delays

Abstract

We consider the Gaussian elimination method on parallel distributed memory computers. A theoretical model for the performance prediction is developed. It takes into account the workload distribution and the communication overhead. We investigate the efficiency of the parallel Gaussian algorithm with matrices distributed in 1D and 2D block and cyclic layouts. The results are generalized for block-block and block- cyclic distributions. We find the condition when communications are overlapped by the computations. Using this analysis we propose a simple heuristic for scheduling Gaussian elimination tasks. We compare the efficiency of this scheduling algorithm with the efficiency of the block and cycling data distributions.