Towards Exascale Application Mapping - An algorithmic framework for load balancing on non-uniform, massively parallel machines

• Applicant: Professor Dr. Henning Meyerhenke
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 244973876

• Final Report Year: 2018

Final Report Abstract

Das Projekt hatte sich zum Ziel gesetzt, die Skalierbarkeit von kommunikationsgebundenen Anwendungen zu steigern. Dazu sollten verbesserte Algorithmen zur Partitionierung von Graphen und zum Mapping von Prozessen auf Rechenkerne entwickelt werden. Vorherige parallele Software-Werkzeuge zu diesem Zweck skalierten entweder nicht ausreichend oder boten keine gute Lösungsqualität. Um den Kompromiss aus Qualität und Skalierbarkeit zu verbessern, entwarfen und implementierten wir mehrere neue Algorithmen. Einer davon basiert auf dem Graphclustering-Algorithmus Label Propagation. Mit unseren Anpassungen für einen MPI-parallelen Graphpartitionierer ist der neue Multilevel-Algorithmus besonders auf komplexe Netzwerke zugeschnitten (die oft eine ausgeprägte Cluster-Struktur aufweisen). Der neue Algorithmus skaliert zu mehr Rechenkernen als der vorherige Stand der Technik zur Partitionierung komplexer Netzwerke, benötigt erheblich weniger Speicher und verbessert die durchschnittliche Lösungsqualität deutlich. Ein Web-Graph mit 3,3 Milliarden Kanten konnte bspw. mit 512 Rechenkernen innerhalb von 16 Sekunden mit hoher Lösungsqualität von unserem Algorithmus partitioniert werden. Keines der bisher existierenden Tools konnte diesen Graphen auf unserem HPC-Cluster verarbeiten. Unser neuer Algorithmus bildet den Kern der parallelen Version von KaHIP, einem erfolgreichen Open-Source-Tool zur Graphpartitionierung, zu dem wir im Rahmen des TEAM-Projekts beigetragen haben. Die zweite Klasse wichtiger Eingabedaten sind Meshes – geometrische Graphen, die typischerweise aus numerischen Simulationen stammen. Hierfür kombinierten wir einen neuen geometrischen Ansatz (skalierbares balanciertes k-means) mit etablierten Methoden (raumfüllende Kurven, Diffusion, lokale Verfeinerung mittels Fiduccia-Mattheyses (FM)) im Toolkit GEOGRAPHER, welches auf der parallelen LAMA-Bibliothek aufbaut. Durch die Initialisierung mit raumfüllenden Kurven konvergiert balanciertes k-means deutlich schneller und robuster. Ein optionaler graph-basierter Verfeinerungsschritt mittels Diffusion und/oder FM führt zu besserer Qualität, aber leicht höherer Laufzeit. Experimente zur starken Skalierung zeigen gute Ergebnisse bis mindestens 4096 Prozesse. Zudem führt die implizite Formoptimierung der resultierenden Partitionen zu einer hohen Lösungsqualität. Somit lässt sich festhalten, dass GEOGRAPHER Meshes mit Milliarden von Kanten in wenigen Sekunden mit hoher Qualität partitioniert. Für das Mapping von parallelen Prozessen auf Rechenkerne haben wir TiMEr entwickelt, eine randomisierte und multi-hierarchische lokale Suchmethode. TiMEr verbessert ein gegebenes Mapping und nutzt dabei aus, dass viele Rechnertopologien die partial cube-Eigenschaft besitzen und somit Teilgraph eines Hyperwürfels (hypercubes) sind. Dies erlaubt es uns, die Knoten eines Applikationsgraphen (z.B. eines komplexen Netzwerks oder eines Meshes) so mit Bitvektoren zu beschriften, dass die Hamming- Distanz zwischen den Labels mit der graphentheoretischen Distanz der Knoten im Prozessorgraphen übereinstimmt. Labelvertauschungen können dann benutzt werden, um ein Mapping - und so auch die Kommunikationskosten der zugrundeliegenden Applikation – zu verbessern. In unseren Experimenten konnte so die Qualität von Mappings, die von Algorithmen des bisherigen Stands der Technik erzeugt wurden, noch deutlich verbessert werden. Das Projekt erzielte außerdem mehrere Nebenbeiträge, von denen zwei kurz erwähnt werden sollen: (i) Eine neue Kantenbewertung, welche den Vergröberungsprozess des Multilevel-Ansatzes für die Graphpartitionierung steuert; es kombiniert mehrere graphentheoretische Konzepte und benutzt eine im Projekt entwickelten Linearzeitalgorithmus, um die conductance von allen fundamentalen Schnitten eines Spannbaumes zu berechnen; (ii) neue theoretische Erkenntnisse über den Zusammenhang zwischen partial cubes, konvexen Schnitten sowie der Djoković -Relation und einer ähnlichen Relation, insbesondere aber nicht ausschließlich für bipartite und planar eingebettete Graphen.

Publications

• Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering. J. Heuristics, 22(5):759–782, 2016
  H. Meyerhenke, P. Sanders, and C. Schulz
  
• Tree-based coarsening and partitioning of complex networks. ACM Journal of Experimental Algorithmics, 21(1):1.6:1–1.6:20, 2016
  R. Glantz, H. Meyerhenke, and C. Schulz
  
• On finding convex cuts in general, bipartite and plane graphs. Theor. Comput. Sci., 695:54–73, 2017
  R. Glantz and H. Meyerhenke
  
• Parallel graph partitioning for complex networks. IEEE Trans. Parallel Distrib. Syst., 28(9):2625–2638, 2017
  H. Meyerhenke, P. Sanders, and C. Schulz
  
• Balanced k-means for parallel geometric partitioning
  M. von Looz, C. Tzovas, and H. Meyerhenke
  
• Topology-induced enhancement of mappings. In 47th International Conference on Parallel Processing
  R. Glantz, M. Predari, and H. Meyerhenke