Multiple sequential staging of tasks: A new approach to parallel computations

Developing an efficient algorithm for solving a large linear system in a pa rallel computing environment is the major problem associated with the appli cation of parallel processing to the numerical solution of large-scale engi neering problems. This paper presents a new algorithm called Multiple Seque ntial Staging of Tasks (MSST) to speed up the solution of a large linear sy stem. The technique of Sequential Staging of Tasks (SST) is a highly effici ent approach to the parallel solution of a targe linear system, but it is n ot suitable for middle- and large-scale parallel computers due to the idle periods of processors. The MSST technique partitions processors into groups and makes each group start its operation from a different row of a large l inear system to remove the idle period. Therefore, MSST can be performed ef fectively on middle- and large-scale parallel computers and achieves a high er speed-up. Numerical results were obtained from computer experiments perf ormed with a numerical solution method of the Poisson equation on a Dawning -1000 supercomputer (a distributed-memory MIMD architecture). The parallel speed-up is satisfactory. Copyright (C) 1999 John Wiley & Sons, Ltd.