The sub-implicit method: New multiprocessor algorithms for old implicit codes

This paper presents a new approach to the parallel solution of an implicit system of difference equations. The sub-implicit method operates on sub-regions of the data which are evaluated at spatial points and synchronous times. Each sub-region has a border node which is shared with an adjacent sub-region (in one dimension). Values for this shared node are computed independently by the two solution processes for two adjacent sub-regions. Nodes outside the sub-region are treated as having fixed values during the solution. At the finish of the two sub-region solutions, the two sub-regions are blocked against further changes (a pairwise synchronization) and the two different values for the shared node are reconciled. This can be done in such a way that energy conservation is exact. Results for test problems for heat diffusion in one dimension are given and compared against standard methods and analytic results. Implementation of the method into a demonstration two-dimensional hydrodynamics code SIMPLE is described. The best speedups observed for parallel execution of this version of SIMPLE on a twelve CPU Sequent multiprocessor were 9.6 for 50 by 50 grid and 10.4 for a 95 by 95 grid. Some generalization of this approach are discussed.