Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4098
Main Title: A framework for machine learning based mapping of concurrent applications to parallel architectures
Translated Title: Ein Framework zur Abbildung von nebenläufigen Programmen auf parallele Zielarchitekturen
Author(s): Tetzlaff, Dirk
Advisor(s): Glesner, Sabine
Referee(s): Glesner, Sabine
Marwedel, Peter
Knoop, Jens
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: 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.
URI: urn:nbn:de:kobv:83-opus4-53936
http://depositonce.tu-berlin.de/handle/11303/4395
http://dx.doi.org/10.14279/depositonce-4098
Exam Date: 24-Jun-2014
Issue Date: 4-Aug-2014
Date Available: 4-Aug-2014
DDC Class: 000 Informatik, Informationswissenschaft, allgemeine Werke
Subject(s): Statische Programmanalyse
Maschinelles Lernen
Task Allokation
Static analysis
machine learning
task mapping
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
tetzlaff_dirk.pdf7,65 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.