Universität Duisburg-Essen
Verteilte Systeme
Hybrides Spawn and Merge mit Platform as a Service Anbindung
Prüfer Prof. Dr.-Ing. Torben Weis
Betreuer Dipl.-Inform. Christopher Boelmann
Bearbeiter Axel Strümper
Art Masterarbeit
Abgabe April 2016

Spawn and Merge ist eine Programmierabstraktion für deterministische multi-threaded Programme. Funktionen (Tasks) werden über die Funktion Spawn gestartet, und fortan parallel ausgeführt. Jeder Task kopiert die Datenstrukturen, die er verwendet, so dass kein Locking bei paralleler Bearbeitung notwendig ist. Nach der Durchführung der Funktion werden die Veränderungen an den kopierten Datenstrukturen an den Eltern-Task übergeben und dieser übernimmt sie deterministisch im Rahmen der Merge Funktion in die eigenen Datenstrukturen. Der Grad an Parallelität ist variabel und abhängig von der Task-Hierarchie, die durch das Spawnen entsteht. So kann es sein, dass ein Programm zu einem Zeitpunkt eine sehr niedrige Parallelität aufweist und zu einem anderen Zeitpunkt eine sehr hohe Parallelität.

In dieser Masterarbeit soll das Konzept der Spawn and Merge Programmierabstraktion so erweitert werden, dass der Programmierer die Möglichkeit hat einzelne Tasks in die Cloud auszulagern. Dadurch soll das Spawn and Merge Programm bei einer hohen Parallelität von Tasks dynamisch Rechenkapazitäten der Cloud nutzen können. Dazu soll das lokale Spawn and Merge Konzept zu einem hybriden Konzept erweitert werden, in dem längere Tasks lokal ausgeführt werden und kurze Tasks in die Cloud ausgelagert werden können. Dieser Ansatz soll verhindern, dass ein Spawn and Merge Programm aufgrund der Laufzeitbeschränkungen für einzelne Funktionen in aktuellen Cloud Systemen (z.B. 60 Sekunden für Amazon Lambda Events) nicht ausgeführt werden kann. Das Ziel ist es, dass viele kurze Tasks parallel in der Cloud abgearbeitet werden können, wodurch ein Zeitvorteil gegenüber der lokalen Implementierung entstehen soll. Die Entscheidung welcher Task ausgelagert wird obliegt dem Programmierer, dem eine zusätzliche Spawn-Funktion angeboten werden soll. Zur Vereinfachung brauchen die Tasks in der Cloud keine weiteren Tasks spawnen können.

Zur Bearbeitung dieser Aufgabe soll zum einen erarbeitet werden wie sich das Spawn and Merge Konzept mit der Cloud verbinden lässt und ob es abgesehen von der Laufzeitbeschränkung noch weitere Punkte gibt die eine komplette Verschiebung in die Cloud verhindern. Anschließend soll das Konzept prototypisch umgesetzt werden anhand des Beispiels Amazon Lambda. Dazu soll eine neue SpawnLambda Funktion angelegt werden, die in einer Lambda-Funktion einen Task in der Cloud ausführt. Das Ergebnis des LambdaTasks soll anschließend wieder zurückgegeben und lokal entgegengenommen und verarbeitet werden. LambdaTasks müssen ihrerseits nicht neue Tasks spawnen können, und brauchen dementsprechend auch nicht die Funktionalität um Task-Ergebnisse ihrerseits zusammenführen (Merge) zu können.

Die prototypische Implementierung soll anschließend evaluiert werden mit dem Hauptaugenmerk auf der Frage ob und wann sich eine Nutzung der Cloud für Spawn and Merge lohnt. Dazu sollen unterschiedliche Beispiel-Szenarien implementiert und die Auswirkungen der Auslagerung einzelner Tasks in die Cloud untersucht werden.

Literatur: Christopher Boelmann, Lorenz Schwittmann, Torben Weis: Deterministic Synchronization of Multi-Threaded Programs with Operational Transformation, 19th International Workshop on High-Level Parallel Programming Models and Supportive Environments, HIPS 2014,held in conjunction with the 28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014,Phoenix, AZ, USA, May 19 - 23, 2014.

 

© Universität Duisburg-Essen, Verteilte Systeme - Kontakt: webmaster@vs.uni-due.de

Impressum - Datenschutz