Skip to main content
Mapping Algorithms and Software Environment for Data Parallel
Northeast Parallel Architecture Center
  • Nikos Chrisochoides, Syracuse University, Northeast Parallel Architectures Center
  • Elias Houstis, Purdue University, Computer Science Department
  • John Rice, Purdue University, Computer Science Department
Document Type
Working Paper
  • mapping algorithms,
  • data parallel iterative solvers,
  • PDE,
  • Partial Differential Equations

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.

Citation Information
Nikos Chrisochoides, Elias Houstis and John Rice. "Mapping Algorithms and Software Environment for Data Parallel" (1994)
Available at: