Communication-sensitive heuristics and algorithms for mapping compilers
Bernd Stramm, Francine Berman · ACM SIGPLAN Notices · 1988
The mapping problem arises when parallel algorithms are implemented on parallel machines. When the number of processes exceeds the number of available processing elements, the mapping problem includes the contraction problem. In this paper, we identify communication-sensitive heuristics which promote good contractions for graph-based parallel algorithms on non-shared memory multiprocessors. We present algorithms which utilize these heuristics and discuss their performance on a group of diverse benchmarks.