Servicenavigation

Project Details

Back

Projekt Print View

Compiling and Optimizing Iterative Data Analysis Programs with Shared State on Evolving Datasets

Subject Area Security and Dependability, Operating-, Communication- and Distributed Systems
Term from 2013 to 2017
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 132320961
 
Final Report Year 2018

Final Report Abstract

Am Fachgebiet DIMA wurde innerhalb des Stratosphere Projekts an der Optimierung und Parallelisierung von deklarativen Datenflussprogrammen auf einer massiv parallelen, ausfallsicheren und adaptiven Architektur gearbeitet. Hierbei wurde das PACT (Parallelization Contracts) Programmiermodell eingeführt, welches die Ideen des map-reduce Modells weiter führt. Im Gegensatz zu map-reduce, ist der Anwender nicht an ein statisches Ausführungsmodell gebunden sondern kann beliebige azyklische Datenflussgraphen erstellen. Hierfür steht ein erweitertes Sortiment an Operatoren, insbesondere Operatoren mit mehreren Eingängen, wie z.B.: dem match Operator, welcher die Semantik eines relationalen joins abbildet. Für die deklarative beschriebenen, logischen Operatoren, wird anhand von Kostenbasierter Optimierung ein entsprechender physikalischer Ausführungsplan erstellt. Hierbei wird auch über die konkreten Implementierungen entschieden (z.B.: Sort-merge join vs. Hash-join). Vom Anwender definierte Funktionen innerhalb bilden eine Optimierungsbarriere für das Verschieben von Operatoren, um z.B.: Daten möglichst früh innerhalb des Datenflusses zu filtern. Innerhalb der Forschung, wurde ein Verfahren zur Analyse des vom Benutzer geschrieben Quellcodes entwickelt, dass es ermöglicht die jeweiligen Typen der Eingehenden und Ausgehenden Elemente eines Operators zu bestimmen und damit Operator neu Ordnung auch über Anwender spezifischen Code zu ermöglichen. Durch die immer wichtiger werdende Anwendung von Datenflussprogrammen im Bereich der Graphen Analyse und des maschinellen Lernens, ist die effiziente Ausführung von iterativen Programmen von hoher Wichtigkeit. Durch die Unterstützung von Iterationen innerhalb der Ausführungsumgebung von Stratosphere, wird das wiederholte Ausrollen des Programmplans pro Iterationsschritt vermieden und es besteht die Möglichkeit , bestimmte Programme über Fixpunkt Berechnungen auszudrücken und damit eine abnehmende Komplexität innerhalb der fortschreitenden Iterationsschritten zu erreichen. Auf Grundlage der gesammelten Erfahrungen bei der Entwicklung des PACT Modells und von Erfahrungsberichten von Anwendern, wurde die deklarative domänenspezifische Programmiersprache für Datenfluss Systeme, genannt Emma, erforscht und entwickelt. Basierend auf der Programmiersprache Scala, welche umfangreichen Möglichkeiten zur Metaprogrammierung bietet, verbindet Emma Erkenntnisse aus den Bereichen des Übersetzerbaus und der Datenbanken. Über die Darstellung von Datenflussprogrammen über Transformationen von Listen mit sogenannten forcomprehensions, welche ein natives Konstrukt in Scala darstellen, lassen sich die Programme, ohne Änderung lokal testen, und danach direkt auf dem Datenflusssystem ausführen. Vor der Verteilten Ausführung wird das Programm hierbei in der Zwischenrepräsentation optimiert. Hierbei kommen Techniken aus dem Übersetzerbau, wie das Entfernen von nicht erreichbaren Codepfaden und traditionelle Datenbank Optimierungen, wie Caching und das Neuordnen von Operatoren und spezielle Techniken für Datenflusssysteme um die Netzwerklast zu minimieren, zum Einsatz. Die auf Emma aufbauende Matrix Abstraktion Lara, ermöglicht das deklarative spezifizieren von u.a. Algorithmen für das maschinelles Lernen. Durch die Möglichkeit zur holistischen Betrachtung von Programmen mit relationalem und linearer Algebra, ermöglicht Lara Optimierungen über deren Grenzen.

Publications

 
 

Additional Information

© 2024 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung