Better process mapping and sparse quadratic assignment

DOI10.4230/LIPICS.SEA.2017.4zbMATH Open1432.68040arXiv1702.04164OpenAlexW3112909468MaRDI QIDQ4580146FDOQ4580146

Jesper Larsson Träff, Christian Schulz

Publication date: 13 August 2018

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1702.04164

Recommendations

• Better Process Mapping and Sparse Quadratic Assignment
• High-quality hierarchical process mapping
• Solving large quadratic assignment problems in parallel
• A parallel branch and bound algorithm for the quadratic assignment problem
• Graph partitioning based methods and tools for scientific computing

zbMATH Keywords

graph algorithmsgraph partitioningprocess mappingrank reordering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14)

Cited In (4)

• Algorithms and Data Structures
• On the performance of sparse process structures in partial postponement production systems
• Better Process Mapping and Sparse Quadratic Assignment
• High-quality hierarchical process mapping

This page was built for publication: Better process mapping and sparse quadratic assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580146)