Mapping realistic data sets on parallel computers

Abstract

Mapping data to parallel computers aims at minimizing the execution time of the associated application. However, it can take an unacceptable amount of time in comparison with the execution time of the application if the size of the problem is large. The authors propose reducing the problem size by a mapping-oriented graph contraction technique. They present a graph contraction (GC) heuristic algorithm that yields a smaller representation of the problem, to which mapping is then applied. The experimental results show that the GC algorithm still leads to good quality mapping solutions to the original problem, while producing remarkable reductions in mapping time. The GC algorithm allows large-scale mapping to become efficient, especially when slow but high-quality mappers are used.