Direkt zum Inhalt

VaMoS

Die Grundidee der parallelen Datenverarbeitung ist, große Jobs in kleinere Tasks zu zerlegen, die von mehreren Servern parallel bearbeitet werden. Das Konzept ist intuitiv, jedoch gibt es ein Spektrum an verschiedenen Modellen paralleler Datenverarbeitung und scheinbar kleine Unterschiede im Verhältnis von Warteschlangen und Servern und in den Annahmen über Ankunfts- und Bedienprozesse können zu drastisch unterschiedlichen Skalierungsverhalten führen.

Beschreibung

Die aktuelle Vorherrschaft der MapReduce-Architektur und ihre vielfache Implementierung veranlassen uns, das grundlegende Verhalten und die Skalierbarkeit dieser Systeme zu ergründen. Es gibt eine Auswahl abstrakter Modelle paralleler Systeme, die vom Split-Merge Modell, das sehr ungünstige Skalierungseigenschaften hat, über das beliebte und vielfach analysierte Fork-Join Modell bis zu Non-Idling Single-Queue Modellen, die eher für MapReduce Task Manager repräsentativ sind und sehr gute Gewinne durch Lastbalancierung realisieren, reichen. Tatsächlich hängt es von der Implementierung eines MapReduce-Programms ab, ob es ein Skalierungsverhalten im Bereich von Split-Merge bis zu Non-Idling Single-Queue aufweist  Im Idealfall würde die Bearbeitung eines Jobs durch k parallele Server um ein k-faches beschleunigt, jedoch ist dieser Idealfall sowohl in der Theorie als auch in der Praxis schwierig zu erreichen. Die entscheidende Eigenschaft, die verhindert, dass parallele Systeme dieses optimale Skalierungsverhalten aufweisen, ist eine irreguläre Aufteilung der Arbeit auf die einzelnen Tasks. In den meisten Modellen ist ein Job erst dann vollständig, wenn all seine Tasks erledigt sind. Folglich kann ein überproportionaler Task, oder ein ,,Nachzügler'', die Aufenthaltszeit eines Jobs dominieren. Entsprechend dominiert ein Task, der in der Warteschlange hinter einem Nachzügler-Task eines anderen Jobs stecken bleibt, die Aufenthaltszeit seines Jobs. Wenn alle Tasks identische Bedienzeiten hätten, würde ein paralleles System sich wie eine herkömmliche Warteschlange verhalten. Um eine Balance zwischen Lösbarkeit und Trivialität des Problems zu erreichen, wird in analytischen Modellen üblicherweise angenommen, dass die Task-Bedienzeiten unabhängige Zufallszahlen einer gebräuchlichen Verteilung sind.  Wir schlagen einen sowohl empirischen als auch theoretischen Forschungsplan vor, der die Anwendbarkeit verschiedener Modelle der parallelen Datenverarbeitung und die Aufteilung von Jobs in Tasks in realen MapReduce-Systemen untersucht. Wir werden die Resultate unserer Studien zum Entwurf neuer MapReduce Task und Ressource Manager einsetzen.

Team
Research area
Networks and Vision
Begin
End