GraphLab and GraphChi : Overview

GraphLab is an example of a Pregel-inspired system. It does not use the BSP model. Instead, it uses an asynchronous model suitable for computations with sparse data dependencies. GraphLab is written in C++ and was originally tailored for machine learning tasks. GraphLab provides an Update function which is analogous to the Map function in MapReduce. This function can read and update the sets of program state in a controlled fashion. It also provides an equivalent of the Reduce function the Sync
function which enables the simultaneous execution of reductions as well as computations.Look at current rank of your neighbors. If changed ask neighbors to update.Think Like a vertex.Update function automatically parallelise for you.

GraphLab1 :About Possibility.Asynchronous execution,Very Intutive. but Not Very Scalable.Did't work for web graph.High level of Communication. Split vertices across machine.
GraphLab2 : Powergraph. About Scalablity. GAS decomposition.Gather information from neighbors in a data parallel way.Local Mapreduce.Apply those value to Vertices.Scatter values around neighbors.Split edges across machine.Very High Performnce.Loss of usablity.Very Rigid Abstraction.
GraphLab3:WARP SYSTEM. About Usablity.Much more expressive.No problem with order GAS or SAG.WARP outperform GRPHLAB2.Access neighborhood through parallel iterators.Huge scale machine learning available to all.

GraphChi is a spinoff of the GraphLab project.
Unlike other systems which need to store the whole graph they are processing in memory, GraphChi is able to process a graph from persistent storage such as an SSD or hard drive. GraphChi uses a method called Parallel Sliding Window (PSW) to process very large graphs from disk. Using an asynchronous model of execution, GraphChi can execute various data mining and graph algorithms on a single computer. GraphChi is available for C++ and Java.Problem is Random access.PSW minimizes random access.


In one of the project I did last term we quantified and analyzed the performance and scalablity of Pregel clones and related systems. We compared various open source implementations of Pregel Giraph,GPS,GraphLab,GraphChi on basis of their runtime,Network I/O,Memory,CPU utilization etc to execute various algorithms like PageRank,Shortest Path ,etc.
I created a 1,4,8 nodes Amazon Ec2 (Amazon Elastic Comute Cloud) instances.We used EC2 large instances (2 EC2 Compute Units,3.75 GiB of RAM and moderate network perfomance) running Ubuntu 12.04.
We analyzed the runtime ,memory foorprint for all these algorithms based on data set of varying sizes ranging from 8 vertices ,70000 vertices, 1million vertices,10 million vertices,30 million vertices . The size of files varies from 10 kb to 200MB.
For Memory footprint we compared the peak memory usage of master node during execution of algorithm for each system.
The datasets were taken from
http://snap.stanford.edu/data/
http://algs4.cs.princeton.edu/44sp/
The datasets were converted to form required by the graphs.

To run algorithm on GraphLab following steps were followed

http://graphlab.org/projects/tutorials.html

We included GraphChi in our comparision because it is sufficiently different from other systems.GraphChi is capable of running very large graphs on a single  machine.To our surprise we found that there was a significant improvement in Runtime when we compared the graphs from HAMA GIRAPH graphChi,GPS and GraphLab. Though performance of the systems like GraphLab and GPS can be further imporved with few little tweeks like splitting the graph into smaller chunks or increasing no of pts for GPS for algorithms with larger supersteps.

This figures shows us the BarChart for various datasets on different systems . GraphLab showed signigicant lower runtimes as compared to Giraph.

A link to the blog is also posted at
http://bickson.blogspot.ca/2014/03/university-of-waterloo-evaluates.html