Static mapping by dual recursive bipartitioning of process architecture graphs

摘要

The combinatorial optimization problem of assigning the communicating processes of a parallel program onto a parallel machine so as to minimize its overall execution time is referred to as static mapping. This problem is NP-complete in general. We introduce a mapping algorithm based on the recursive bipartitioning of both the source process graph and the target architecture graph, whose divide and conquer and modular approach allows the handling of many topologies and bipartitioning heuristics. Mapping results on hypercube, binary de Buijn, and bidimensional mesh graphs are presented in order to illustrate this feature.