Ein Framework zur Abbildung von nebenläufigen Programmen auf parallele Zielarchitekturen

In dieser Arbeit stellen wir ein generelles Framework zur Verbesserung der automatischen Abbildung von nebenläufigen Anwendungen auf parallele Architekturen vor. Die größte Herausforderung bei der notwendigen zeitlichen Planung der parallelen Tasks und bei deren Zuordnung zu Berechnungseinheiten der Zielarchitektur ist, vorab das erwartbare Laufzeitverhalten der Tasks zu bestimmen. Unser Framework löst dieses Problem durch Einsatz von Techniken des Maschinellen Lernens zur präzisen Vorhersage dieser Information. Dieses Wissen verwenden wir als schnelle und genaue Heuristik um ein Kostenmodell zu etablieren, welches die Qualität der Abbildung bewertet. Vorhersagen mit Hilfe von Techniken Maschinellen Lernens, die Informationen über das Laufzeitverhalten zur Verfügung stellen, lassen präzisere Ergebnisse erwarten als Vorhersagen, die auf rein statischen Analysen beruhen, welche das Laufzeitverhalten approximieren müssen. Dadurch erhöht sich das Optimierungspotential zur Verbesserung der Leistungsfähigkeit von Programmen zur Laufzeit. Das in dieser Arbeit entwickelte Framework besteht aus zwei voneinander getrennten Phasen: eine einmalige Trainingsphase pro Architektur vor der Anwendungsphase des Frameworks. Während der Trainingsphase werden mittels Maschinellem Lernen Verhaltensmodelle erzeugt, die einen Zusammenhang zwischen statischen Eigenschaften der Programme und deren Laufzeitverhalten herstellen. Während der Anwendungsphase des Frameworks werden diese dann verwendet, um den Berechnungsaufwand von Tasks und Kommunikationskosten zwischen Tasks vorherzusagen. Das entwickelte Framework ist für diverse parallele Programmiermodelle anwendbar. Im zweiten Teil der Dissertation stellen wir die Instanziierung des Framework für das Message Passing Programmiermodell vor. Wir haben dieses instanziierte Framework vollständig implementiert und Experimente durchgeführt, um die Qualität der Verhaltensvorhersagen zu ermitteln. Die Evaluierung der Experimente zeigt, dass wir nicht nur das betrachtete Laufzeitverhalten besser vorhersagen können als andere heuristische Verfahren, sondern auch die Laufzeit von Programmen mithilfe unseres Frameworks deutlich verkürzt werden kann.In this thesis, we present a general framework to improve the automatic mapping of concurrent applications to parallel architectures and we define its instantiation for mapping MPI programs to processor networks. For scheduling the parallelly executable tasks of applications and for their allocation to the processing elements of the target architecture, the major challenge is to analyze in advance the expected run-time behavior of applications. Our proposed framework solves this problem by utilizing Machine Learning (ML) techniques to derive precise predictions for this information. This knowledge is used as fast and accurate heuristics to establish a cost model that rates the gain of various mappings. Using cost models based on machine learned heuristics that include knowledge about the run-time behavior of programs one can expect an advantage over cost models based on purely static analyses, which must conservatively over-approximate the run-time behavior. As a result, optimization potential to improve program performance is increased. To improve the mapping, we define automatic analyses that statically determine the parallel structure of applications. Based on this, we introduce ML techniques to derive the most needed information for optimizing the mapping: knowledge about the execution times of parallelly executable tasks of applications and about the communication amount between tasks. These ML techniques have to be deployed only once per architecture in a training phase, which is decoupled from the compilations of applications. Hence, the compile time is not increased, thereby preserving an efficient and continuous compilation flow. To rate the gain of alternative mapping schemes, we also define a general cost model that is based on machine learned knowledge and that is parametrized by hardware-dependent information. Using this cost model enables a power-efficient and communication-aware mapping of applications to any parallel architectures. Our general framework is applicable to a wide diversity of parallel programming models and target architectures. In the second part of this thesis, we show how our general framework can be applied for improving the mapping of MPI programs to processor networks. We have fully implemented the instantiated framework and performed experiments to determine the accuracy of our approach. For our experiments, we have used a considerable number of programs from various benchmark suites that encompass different real-world application domains. This shows on the one hand the general applicability and on the other hand the high scalability of our framework. The evaluation of our experiments demonstrates that we are able to predict regarded run-time behavior more precisely compared to other heuristic approaches