Generic topology mapping strategies for large-scale parallel architectures

Torsten Hoefler, Marc Snir

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The steadily increasing number of nodes in high-performance computing systems and the technology and power constraints lead to sparse network topologies. Efficient mapping of application communication patterns to the network topology gains importance as systems grow to petascale and beyond. Such mapping is supported in parallel programming frameworks such as MPI, but is often not well implemented. We show that the topology mapping problem is NP-complete and analyze and compare different practical topology mapping heuristics. We demonstrate an efficient and fast new heuristic which is based on graph similarity and show its utility with application communication patterns on real topologies. Our mapping strategies support heterogeneous networks and show significant reduction of congestion on torus, fat-tree, and the PERCS network topologies, for irregular communication patterns. We also demonstrate that the benefit of topology mapping grows with the network size and show how our algorithms can be used in a practical setting to optimize communication performance. Our efficient topology mapping strategies are shown to reduce network congestion by up to 80%, reduce average dilation by up to 50%, and improve benchmarked communication performance by 18%.

Original languageEnglish (US)
Title of host publicationICS'11 - Proceedings of the 2011 ACM International Conference on Supercomputing
Number of pages10
StatePublished - 2011
Event25th ACM International Conference on Supercomputing, ICS 2011 - Tucson, AZ, United States
Duration: May 31 2011Jun 4 2011

Publication series

NameProceedings of the International Conference on Supercomputing


Other25th ACM International Conference on Supercomputing, ICS 2011
Country/TerritoryUnited States
CityTucson, AZ


  • mpi graph topologies
  • topology mapping

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Generic topology mapping strategies for large-scale parallel architectures'. Together they form a unique fingerprint.

Cite this