Algorithm Engineering für Prozess Mapping

Die Kommunikationsleistung zwischen Anwendungsprozessen in Hochleistungsrechnersystemen hängt von zahlreichen Faktoren ab. Zum Beispiel von der Leistung oder der Topologie des zugrunde liegenden Kommunikationssystems, von der erforderlichen Kommunikation zwischen Prozessen in den gegebenen Anwendungen und der Software sowie den Algorithmen zur Realisierung der entsprechenden Kommunikation. Beispielsweise ist Kommunikation in der Regel schneller, wenn kommunizierende Prozesse auf demselben physikalischen Prozessorknoten liegen, im Vergleich zu dem Fall, in denen sich die Prozesse auf verschiedenen, entfernten, Knoten befinden. Dieser Effekt verstärkt sich auf großen Systemen bei denen Prozessoren in hierarchische Einheiten organisiert sind, die Kommunikationsverbindungen gleicher Qualität aufweisen, z.B. in Inseln, Racks, Knoten, ..., . Wenn nun ein Kommunikationsmuster zwischen Prozessen und eine Beschreibung der Topologie der Hardware gegeben ist, so sucht man also eine Zuweisung von Prozessen zu Prozessoren so dass viel kommunizierende Prozesspaare nah~beieinander~liegen. Das Projekt wendet in erster Linien die Algorithm Engineering Methode auf das Prozessmappingproblem an und verbessert dadurch bekannte Verfahren -- insbesondere für große Rechensysteme und Anwendungen. Es werden zwei zentrale Annahmen getroffen, die typischerweise für moderne Supercomputer und darauf laufenden Anwendungen gültig sind. Erstens, nehmen wir an das die zugrundeliegenden Kommunikationsmuster dünn sind, da nicht alle Prozesse miteinander kommunizieren müssen. Zweitens, nehmen wir an das die untersuchte Hardwaretopologie hierarchisch organisiert ist, und zwar so das Verbindungen auf dem gleichen Level der Hierarchie die gleiche Kommunikationsleistung haben. Die im Projekt entstehenden Algorithmen und Implementierungen werden robuster und flexibler sein, bessere Lösungen berechnen, auf massiv parallelen Maschinen skalieren, und in der Lage sein Instanzen zu bearbeiten, die vorher nicht bearbeitet werden konnten. Insgesamt werden wir deutlich bessere Algorithmen für Prozessmappingprobleme sowie für dünn besetzte quadratische Zuweisungsprobleme entwickeln. Die erfolgreichsten Implementierungen werden als einfach zu benutzende Open-Source Software zur Verfügung gestellt.

Moderne Hochleistungsrechnensysteme sind stark inhomogen aufgebaut, selbst wenn die einzelnen Prozessor-kerne alle gleich aussehen: die Zugriffszeiten auf den Haupt- und Zwischenspeicher sind stark davon abhängig, welche Teile im Speicher von welchem Prozessor-kern adressiert werden, und insbesondere auch davon, wie und wie viele Prozessoren überhaupt gleichzeitig arbeiten. Ebenso unterscheiden sich die Kommunikationszeiten zwischen den Prozessoren, da diese vom Aufbau des Kommunikationsnetzwerk und der Kommunikationsmuster der parallelen Anwendungen abhängen. Das Projekt hatte als Ziel, Lastunterschiede bei Kommunikationsoperationen zu untersuchen und diese ggf. auszugleichen, insbesonders für hoch-parallelisierte Anwendungen auf großen HPC-Systemen. Für die Entwicklung dieser Anwendungen wird typischerweise die Kommunikationsschnittstelle MPI (das "Message-Passing Interface") verwendet, welche eine Anzahl von Möglichkeiten bietet, das Kommunikationsnetzwerk besser und strukturierter zu nutzen, z.B. können Prozesse in mehrere, kleinere Gruppen aufgeteilt werden, um diese dann an vorhandene Prozessoren zuzuordnen. Zu Projektbeginn wurde dieses traditionelle Zuordnungsproblem von Prozessen auf Ressourcen untersucht. Dafür wurden mehrere Heuristiken für bestimmte, sogenannte kartesische Kommunikationsmuster vorgeschlagen. Heuristiken waren nötig, da es sich um schwierige Optimierungsprobleme handelt, für die eine bestmögliche Lösung oft nicht in praktikabler Zeit gefunden werden kann. Um nachträglich die Güte der Lösungen in der Praxis zu evaluieren, wurde ein Analysewerkzeug ("Profiler") entwickelt. Mit diesem Werkzeug war es möglich, die Kommunikationlast in parallelen Anwendungen für einzelne Prozessgruppen zu analysieren. In der zweiten Hälfte des Projekt wurde das gleichzeitige Ausführen mehrerer paralleler Anwendungen auf HPC-Systemen untersucht. Es zeigt sich, dass, wenn die Rechenressourcen (Kerne) effizient zwischen den verschiedenen Anwendungen aufgeteilt sind, sich die Systemauslastung erhöhen und die Gesamtlaufzeit der Anwendungen reduziert werden kann. Diese Ergebnisse bilden eine gute Grundlage, um in weiterer Folge, die automatisierte Auswahl und Anpassung von gleichzeitig laufenden Anwendungen auf HPC-Systeme zu untersuchen und zu ermöglichen.