SCHEDULING ALGORITHMS FOR PARALLEL GAUSSIAN-ELIMINATION WITH COMMUNICATION COSTS

We consider a graph theoretical model and study a parallel implementat ion of the well-known Gaussian elimination method on parallel distribu ted memory architectures, where the communication delay for the transm ission of an elementary data is higher than the computation time of an elementary instruction. We propose and analyze two low-complexity alg orithms for scheduling the tasks of the parallel Gaussian elimination on an unbounded number of completely connected processors. We compare these two algorithms with a higher-complexity general-purpose scheduli ng algorithm, the DSC heuristic, proposed by Gerasoulis and Yang.