Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Graph partitioning for Signal/Collect
Organization Unit
Authors
  • Thomas Keller
Supervisors
  • Coralia-Mihaela Verman
  • Abraham Bernstein
Language
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 45
Date 2013
Abstract Text Signal/Collect is a vertex-centric programming model and framework for graph processing. The communication between the vertices of a graph impairs the performance of distributed framework executions due to message serializations and network limitations. In this thesis, Signal/Collect is extended to support algorithms that reduce the number of remote messages by moving vertices between compute nodes during the computation. Several algorithms are evaluated and the best performing candidate is discussed in detail. The evaluation results indicate an improvement of the runtime performance in one of two cases. However, the performed evaluations are not sufficient to draw final conclusions about the implemented approach.
Zusammenfassung Signal/Collect ist ein Programmiermodell und System zur Ausführung von Algorithmen auf Graphen. Wird ein Graph auf mehrere Rechner verteilt, erhöht die Kommunikation zwischen den Knoten des Graphen die Laufzeit des Systems. In dieser Arbeit wird Signal/Collect erweitert, um Algorithmen zu ermöglichen, welche die Knoten während der Laufzeit zwischen den ausführenden Rechnern so verschieben, dass die Zahl der Nachrichten zwischen den Rechnern reduziert wird. Von mehreren Algorithmen wird der beste eingehend diskutiert. Weiterführende Evaluationen zeigen, dass jener Algorithmus die Laufzeit in einem von zwei Fällen reduziert. Allerdings sind die durchgeführten Untersuchungen nicht ausreichend, um ein abschliessendes Urteil zu fällen.
PDF File Download
Export BibTeX