Ein algorithmisches Framework zur Lastbalancierung künftiger Exascale-Anwendungen auf massiv parallelen NUMA-Architekturen

• Antragsteller: Professor Dr. Henning Meyerhenke
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 244973876

Viele der heutigen Anwendungen für massiv parallele Rechnerarchitekturen leiden daran, dass ihre Kommunikationskosten unverhältnismäßig stark mit der Anzahl der Prozessoren wachsen. Dieses Problem wird sich wegen stetig steigender Prozessorzahlen noch verstärken. Somit besteht die Gefahr, dass Investitionen in aufkommende Exascale-Rechner nicht ihre volle Wirkung entfalten. Daher wollen wir neue Methoden entwickeln, die die Kommunikationskosten wichtiger Anwendungsklassen für massiv parallele NUMA-Architekturen deutlich senken.Meist modelliert man Kommunikation und/oder Abhängigkeiten von Daten durch einen sog. Applikationsgraphen. Um eine lastbalancierte und kommunikationsoptimierte Zuordnung von Prozessen und/oder Daten zu Prozessoren zu berechnen, partitioniert man den Applikationsgraphen geeignet in Teilgraphen und ordnet letztere den Prozessoren zu. Heutige parallele Software-Werkzeuge für diese Form der Partitionierung und des Mappings skalieren nicht ausreichend oder machen Abstriche bei der Qualität. Das Forschungsvorhaben zielt darauf ab, den Kompromiss zwischen Skalierbarkeit und Qualität signifikant zu verbessern und strebt eine Beschleunigung von kommunikationsintensiven Anwendungen um mehrere Faktoren an.Methodisch vereinheitlicht das Forschungsvorhaben das Partitionieren und das Mapping eines möglicherweise dynamischen Applikationsgraphen. Zu diesem Zweck nutzen wir graphentheoretische Eigenschaften typischer NUMA-Architekturen, um Kommunikationskosten zu modellieren. Wir verwenden zur Optimierung die Multilevelmethode, die sich in ähnlichen Zusammenhängen als sehr effektiv erwiesen hat. Im Gegensatz zu den üblichen Verfahren optimieren die zu entwickelnden Algorithmen unseres vereinheitlichten Ansatzes die Kommunikationskosten einer Anwendung in allen Phasen der Multilevelmethode.Unter den vielen Algorithmen, die bei der Multilevel-Graphpartitionierung und zum Mapping von Prozessen verwendet werden, haben wir zwei wichtige Klassen als Startpunkt ausgewählt: (i) streng lokale kombinatorische Optimierungsverfahren und (ii) globalere Verfahren, die auf Diffusion basieren. Durch unsere Vorarbeiten haben wir Expertise in beiden Klassen. Streng lokale Optimierungsmethoden sind kurzsichtig und lassen sich sehr oft nur schlecht parallelisieren. Globale Methoden sind trotz besserer Skalierbarkeit meist zu rechenintensiv. Daher möchten wir die wünschenswerten Eigenschaften beider Klassen kombinieren und zu semi-lokalen Optimierungsverfahren erweitern. Wir erwarten, dass diese Hybridisierung die oben aufgezeigten Probleme beseitigt, also qualitativ hochwertige Mappings für und auf massiv parallele Maschinen zur Verfügung stellt.Unsere neuen Methoden integrieren wir in die anerkannten Bibliotheken unseres externen Partners. Diese Bibliotheken sind derWissenschaftsgemeinde dauerhaft kostenlos zugänglich. Auf diese Weise finden unsere Ergebnisse unmittelbare Anwendung in praxisorientierter High-End-Simulationssoftware.

• DFG-Verfahren: Sachbeihilfen