Offline- und Online-Autotuning von Parallelen Programmen

Viele wissenschaftliche Anwendungen, z.B. Klima- oder Erdbebensimulationen, werden auf großen Parallelrechnern ausgeführt, um die Rechenzeit zu verkürzen. Diese Parallelrechner bestehen aus hunderten oder tausenden von Rechnerknoten, wobei jeder dieser Knoten einem normalen Desktop-Computer ähnlich ist. Die meisten dieser parallelen Anwendungen verwenden das Message Passing Interface (MPI) als Schnittstelle für die notwendige Datenkommunikation über das Netzwerk. Aus diesem Grund ist die Laufzeit von Anwendungen stark von der Güte der jeweiligen MPI-Bibliothek abhängig. Deshalb ist es wichtig, die bestmögliche MPI-Bibliothek für einen Rechner zur Verfügung zu stellen. In den letzten zwei Jahrzehnten wurden viele effiziente Algorithmen für MPI entwickelt, welche auch in den entsprechenden MPI-Bibliotheken zu finden sind. Das Problem ist jedoch, dass nicht jeder Algorithmus für jedes Problem geeignet ist. Aus diesem Grund muss man eine MPI-Bibliothek an ein System anpassen. Der Prozess der Optimierung soll natürlich möglichst automatisiert erfolgen. Aus diesem Grund hat unser Projekt das Ziel, die Parameter von MPI-Bibliotheken so zu optimieren, dass für jede Anwendung und Maschine effiziente Einstellungen gesetzt werden können. Das Problem hierbei ist, dass MPI-Bibliotheken mehrere hundert Parameter besitzen, welche diverse Systemeigenschaften und die Algorithmenauswahl steuern. Der Suchraum ist damit viel zu groß, um alle Parameterkombinationen mit vertretbarem Aufwand auszuprobieren. Statistische Methoden können uns helfen, die Anzahl der wichtigen Parameter zu verkleinern. Um die Auswahl der intern verwendeten Algorithmen zu optimieren, werden zusätzlich moderne Verfahren des maschinellen Lernens eingesetzt. Als Gesamtprodukt erhält man dann eine Software, die sich automatisiert an einen Parallelrechner anpasst.

Wissenschaftliche Anwendungen, die auf Supercomputern laufen, basieren fast ausschließlich auf dem Message Passing Interface (MPI), das eine Reihe von Funktionen definiert, mit denen Prozesse miteinander kommunizieren können. Eine spezielle Art der Kommunikation ist die kollektive Kommunikation, bei der eine Gruppe von Prozessen zusammenarbeitet, um eine Aufgabe zu lösen. Zum Beispiel ermöglicht die Broadcast-Operation einem Prozess, Daten an alle anderen Prozesse in der Gruppe zu senden. Das Autotune-Projekt konzentriert sich auf Strategien zur automatischen Optimierung kollektiver MPI-Operationen. Das Tuning einer kollektiven Operation bedeutet, den besten Algorithmus und die besten Parameter für eine gegebene Operation auszuwählen. Wir haben einen Tuning-Prototyp entwickelt, der die Leistung verschiedener Algorithmen und Parameter für kollektive Operationen überwacht und basierend auf der aktuellen Arbeitslast und den Hardwareeigenschaften die beste Variante auswählt. Zwei Hauptprobleme mussten gelöst werden: 1. Wie beeinflussen Prozessankunftsmuster die Leistung kollektiver Operationen? 2. Wie wirkt sich die Synchronisierung von Prozessen mittels Broadcast während des Benchmarkings auf die Benchmark-Ergebnisse aus? Benchmarking unter Berücksichtigung von Ankunftsmustern: Wir optimieren kollektive MPI-Operationen, indem wir Prozessankunftsmuster berücksichtigen. Ungleiche Prozessankunftszeiten kommen in realen Anwendungen häufig vor und beeinflussen die Leistung kollektiver Algorithmen erheblich. Mittels Simulationen und Mikro-Benchmarking zeigen wir, dass die Laufzeit von wurzelbasierten Operationen wie MPI_Reduce stärker als die von nicht-wurzelbasierten Operationen wie MPI_Allreduce durch Ankunftsmuster beeinflusst wird. Wir schlagen eine Methodik vor, um die Algorithmusauswahl zu verbessern, indem der leistungsstärkste Algorithmus für viele unterschiedliche Ankunftsmuster ermittelt wird. Anhand der FT-Anwendung der NAS Parallel Benchmarks zeigen wir, dass die Berücksichtigung von Ankunftsmustern die Leistung von Anwendungen deutlich verbessern kann. Benchmarking mit synchronisierten Uhren: Wir schlagen MPIX_Harmonize vor, eine Erweiterung des MPI-Standards, die Prozesse sowohl räumlich als auch zeitlich synchronisiert und dadurch Ankunftsmuster während des Benchmarkings eliminiert. Dieser Ansatz erreicht eine Synchronisationsgenauigkeit von etwa einer Mikrosekunde und ist damit erheblich besser geeignet als eine Prozesssynchronisation mittels MPI_Barrier. Durch die Eliminierung von Ankunftsmuster-Artefakten gewährleistet MPIX_Harmonize zuverlässigere Benchmarks für MPI-Kollektivoperationen. Unsere Analyse zeigt die Effektivität unseres Ansatzes bei der Erstellung genauer und konsistenter Leistungsbewertungen kollektiver MPI-Operationen. Optimierung von HPC-Anwendungen zur Laufzeit: Wir haben eine Online-Tuning-Strategie für MPI-Kollektivoperationen entwickelt, die kollektive Algorithmen dynamisch basierend auf Leistungsdaten auswählt, die während realer Anwendungsdurchläufe gesammelt werden. Dieser Ansatz eliminiert die Notwendigkeit vorherigen Offline-Benchmarkings und ist damit geeignet, in dynamischen Umgebungen eingesetzt zu werden. Ein zentraler Bestandteil dieser Strategie ist das globale Leistungsmodell, das zur Laufzeit iterativ aktualisiert wird. Das Modell überwacht die Leistung verschiedener Algorithmen und passt deren Auswahlwahrscheinlichkeiten an, um die Effizienz zu optimieren. Wenn beispielsweise ein bestimmter Algorithmus unter bestimmten Bedingungen konstant gut abschneidet, erhöht sich seine Wahrscheinlichkeit, ausgewählt zu werden. Unsere Experimente mit der miniAMR-Anwendung zeigten signifikante Leistungssteigerungen für MPI_Allreduce-Operationen.