  Communication and topology aware process mapping is a powerful approach to
reduce communication time in parallel applications with known communication
patterns on large, distributed memory systems. We address the problem as a
quadratic assignment problem (QAP), and present algorithms to construct initial
mappings of processes to processors, and fast local search algorithms to
further improve the mappings. By exploiting assumptions that typically hold for
applications and modern supercomputer systems such as sparse communication
patterns and hierarchically organized communication systems, we obtain
significantly more powerful algorithms for these special QAPs. Our multilevel
construction algorithms employ perfectly balanced graph partitioning techniques
and exploit the given communication system hierarchy in significant ways. We
present improvements to a local search algorithm of Brandfass et al. (2013),
and further decrease the running time by reducing the time needed to perform
swaps in the assignment as well as by carefully constraining local search
neighborhoods. We also investigate different algorithms to create the
communication graph that is mapped onto the processor network. Experiments
indicate that our algorithms not only dramatically speed up local search, but
due to the multilevel approach also find much better solutions in practice.
