NPAC Technical Report SCCS-459
Mapping Algorithms and Software Environment for Data Parallel PDE Iterative Solvers
Nikos Chrisochoides, Elias Houstis, John Rice
Submitted March 01 1993
Abstract
We consider computations associated with data parallel
iterative solvers used for the numerical solution of Partial
Differential Equations (PDEs). The mapping of such computations
into load balanced tasks requiring minimum synchronization and
communication is a difficult combinatorial optimization problem.
Its optimal solution is essential for the efficient parallel processing of PDE
computations. Determining data mappings that optimize a number
of criteria, like workload balance, synchronization and local
communication, often involves the solution of an NP-Complete problem.
Although data mapping algorithms have been known for a few
years there is lack of qualitative and quantitative comparisons
based on the actual performance of the parallel computation. In
this paper we present two new data mapping algorithms and evaluate them
together with a large number of existing ones using
the actual performance of data parallel iterative PDE solvers on the
nCUBE II. Comparisons on the performance of data parallel iterative
PDE solvers on medium and large scale problems demonstrate that some
computationally inexpensive data block partitioning algorithms are as
effective as the computationally expensive deterministic optimization
algorithms. Also, these comparisons demonstrate that the existing
approach in solving the data partitioning problem is inefficient for
large scale problems. Finally, a software environment for the solution
of the partitioning problem of data parallel iterative solvers is presented.