Towards developing robust algorithms for solving partial differential equations on MIMD machines

Methods are proposed for efficient computation of numerical algorithms on a wide variety of MIMD machines. These techniques reorganize the data dependency patterns so that the processor utilization is imporved. The model problem examined finds the time-accurate solution to a parabolic partial differential equation discretized in space and implicitly marched forward in time. The algorithms investigated are extensions of Jacobi and SOR. The extensions consist of iterating over a window of several timesteps, allowing efficient overlap of computation with communication. The methods suggested here increase the degree to which work can be performed while data are communicated between processors. The effect of the window size and of domain partitioning on the system performance is examined both analytically and experimentally by implementing the algorithm on a simulated multiprocessor system.