Overview

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 provide 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.

Mapping tasks onto processors. Image source LRZ.


VieM - Vienna Mapping and Sparse Quadratic Assignment -- is a family of mapping programs. It includes serveral heuristics to map a task graphs onto a specified processor graph. We provide them here as easy to use open source software.

News:
21st June 2017: We presented our paper "Better Process Mapping and Sparse Quadratic Assignment" at SEA 2017.
16th March 2017: Released VieM v1.00.
14th February 2017: Published ArXiv Report. Link to PDF.


Licence

The program is licenced under GPL 2.0. Please let us know if you need a commercial licence.
If you publish results using our algorithms, please acknowledge our work by quoting the following paper (PDF):

@inproceedings{schulztraeff2017,
             AUTHOR = {Schulz, Christian and Träff, Jesper Larsson},
             TITLE = {{Better Process Mapping and Sparse Quadratic Assignment}},
             BOOKTITLE = {{Proceedings of the 16th International Symposium on Experimental Algorithms (SEA'17)}},
             SERIES = {{LIPIcs}},
             PUBLISHER = {Dagstuhl},
             VOLUME = {75},
             PAGES = {4:1 -- 4:15},
             NOTE = {Technical Report, arXiv:1702.04164},
             YEAR = {2017}
}


The algorithms that are included for download are mainly based on the following publications:

  • Christian Schulz and Jesper Larsson Träff. Better Process Mapping and Sparse Quadratic Assignment. Proceedings of the 16th International Symposium on Experimental Algorithms (SEA'17). 2017. Download PDF.

Download

Support

  • Write us an email if you need support!
  • We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.

Other Open Source Projects

  • KaHIP -- Karlsruhe High Quality Partitioning
  • ParHIP -- Parallel High Quality Partitioning
  • KaMIS -- Karlsruhe Maximum Independent Sets
  • KaLP -- Karlsruhe Longest Paths
  • KaDraw -- Karlsruhe Graph Drawing