Better process mapping and sparse quadratic assignment

Christian Schulz, Jesper Larsson Träff

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed


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 as well as 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 arrive at significantly more powerful algorithms for these special QAPs. Our multilevel construction algorithms employ recently developed, perfectly balanced graph partitioning techniques and excessively exploit the given communication system hierarchy. We present improvements to a local search algorithm of Brandfass et al. (2013), and decrease the running time by reducing the time needed to perform swaps in the assignment as well as by carefully constraining local search neighborhoods. 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.

Titel16th Symposium on Experimental Algorithms (SEA 2017)
Redakteure*innenSimon J. Puglisi, Solon P. Pissis, Rajeev Raman, Costas S. Iliopoulos
Herausgeber (Verlag)Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
ISBN (elektronisch)9783959770361
PublikationsstatusVeröffentlicht - 2017
VeranstaltungSEA 2017: 16th International Symposium on Experimental Algorithms - King's College London, London, Großbritannien / Vereinigtes Königreich
Dauer: 21 Juni 201723 Juni 2017


KonferenzSEA 2017
Land/GebietGroßbritannien / Vereinigtes Königreich

ÖFOS 2012

  • 102031 Theoretische Informatik