  Partitioning graphs into blocks of roughly equal size such that few edges run
between blocks is a frequently needed operation when processing graphs on a
parallel computer. When a topology of a distributed system is known an
important task is then to map the blocks of the partition onto the processors
such that the overall communication cost is reduced. We present novel
multilevel algorithms that integrate graph partitioning and process mapping.
Important ingredients of our algorithm include fast label propagation, more
localized local search, initial partitioning, as well as a compressed data
structure to compute processor distances without storing a distance matrix.
Experiments indicate that our algorithms speed up the overall mapping process
and, due to the integrated multilevel approach, also find much better solutions
in practice. For example, one configuration of our algorithm yields better
solutions than the previous state-of-the-art in terms of mapping quality while
being a factor 62 faster. Compared to the currently fastest iterated multilevel
mapping algorithm Scotch, we obtain 16% better solutions while investing
slightly more running time.
