Bilkent University
Department of Computer Engineering
CS 590 SEMINAR
Analyzing Graph Analytics Algorithms for Performance
Funda Atik
MS Student
Computer Engineering Department
Bilkent University
Graph analytics applications has received considerable attention recently due to its applicability to different domains such as web graphs, social networks and protein networks. Designing a large scale efficient graph processing systems is a challenging task due to the large volume and the irregularity of communication between computations at each vertex or edge. As a result, several graph analytics frameworks (GraphLab, Giraph, CombBlas, SociaLite, Galois, Pregel) adopting different programming models have been developed. These frameworks process graphs either synchronously or asynchronously. The former case is easy to program since it processes data simultaneously and iteratively; whereas, the latter case needs to order data updates carefully, and updates data using latest available dependent state. Moreover, many graph applications are executed until a convergence criteria is satisfied. This behavior is implemented simply by executing all vertices iteratively until the convergence criteria is met. However, it is shown that there is no need to execute all vertices in every iteration because some vertices may converge faster than others. This property is called asymmetric convergence. In this work, we mainly focus on asymmetric convergence and asynchronous execution. We discuss how convergence criterion and different modes of execution affect the performance by using different implementations of iterative graph-parallel algorithms. As an initial work, we test several implementations of PageRank algorithm with a variety of input graphs which is either taken from existing graphs or created synthetically.
DATE: 05 December, 2016, Monday @ 17:00
PLACE: EA-409