A Set of New Mapping and Coloring Heuristics for Distributed-Memory Parallel Processors
C. Pommerell, Marco Annaratone, Wolfgang Fichtner · SIAM Journal on Scientific and Statistical Computing · 1992
New mapping and coloring heuristics are developed to parallelize preconditioned conjugate-gradient-like methods on distributed-memory parallel processors (DMPPs). All these heuristics are fast, with a “quasi” linear time complexity. These schemes are evaluated by solving several systems of linear equations from two-dimensional and three-dimensional semiconductor device simulation on irregular finite-element grids. The benchmarks have been carried out on a simulated 64-processor DMPP with fast communication channels that is under development at the Integrated System Laboratory of the Swiss Federal Institute of Technology. The linear systems involved had between 2000 and 75000 unknowns. Depending on the problem under consideration, speedups between 42 and 54 were obtained. Mapping heuristics that use geometric information given by the embedding of the problem graph into physical space were found to be superior to heuristics based solely on the topological information of adjacency structure. Coloring heuristics for vector computers or shared-memory parallel computers were not sufficient for effective parallelization on DMPPs. Coloring strategies for DMPPs had to balance the load for each color, taking into account the mapping and exploiting the locality corresponding to it.