Asynchronous and Corrected-Asynchronous Numerical Solutions of Parabolic PDEs on MIMD Multiprocessors.

摘要

A major problem in achieving significant speed-up on parallel machines is the overhead involved with synchronizing the concurrent processes. Removing the synchronization constraint has the potential of speeding up the computation. We present asynchronous (AS) and corrected-asynchronous (CA) finite difference schemes for the multi-dimensional heat equation. Although our discussion concentrates on the Euler scheme for the solution of the heat equation, it has the potential of being extended to other schemes and other parabolic partial differential equations. These schemes are analyzed and implemented on the shared memory multi-user Sequent Balance machine . Numerical results for one and two dimensional problems are presented. It is shown experimentally that synchronization penalty can be about 50% of run time: in most cases, the asynchronous scheme runs twice as fast as the parallel synchronous scheme. In general, the efficiency of the parallel schemes increases with processor load, with the time-level, and with the problem dimension. The efficiency of the AS may reach 90% and over, but it provides accurate results only for steady-state values. The CA, on the other hand, is less efficient but provides more accurate results for intermediate (non steady-state) values.