Reduction of the Effects of the Communication Delays in Scientific Algorithms on Message Passing MIMD Architectures

The efficient implementation of algorithms on multiprocessor machines requires that the effects of communication delays be minimized. The effects of these delays on the performance of a model problem on a hypercube multiprocessor architecture is investigated, and methods are developed for increasing algorithm efficiency. The model problem under investigation is the solution by red-black Successive Over Relaxation of the heat equation; most of the techniques to be described here also apply equally well to the solution of elliptic partial differential equations by red-black or multicolor SOR methods. This paper identifies methods for reducing communication traffic and overhead on a multiprocessor and reports the results of testing these methods on the Intel iPSC Hypercube. We examine methods for partitioning a problem’s domain across processors, for reducing communication traffic during a global convergence check, for reducing the number of global convergence checks employed during an iteration, and for concurrently iterating on multiple time-steps in a time dependent problem. Our empirical results show that use of these methods can markedly reduce a numerical problem’s execution time.