Parallelizing Sequential Graph Computations

Ever since my undergraduate course on Databases started, I have been going through some recent and relevant work in the Database community, mostly from VLDB, KDD and PODS/SIGMOD. In this particular post, I would like to put across my thoughts on a particular work that won the best paper award in SIGMOD 2017.

In today’s world of social networks, modeling information flow, friendships, interactions have all become trivial with the use of graphs. Graphs are ubiquitous and the scale at which they’re growing is enormous. Facebook’s entire community of 2 billion users can be represented as a graph as friendships between various different users. This data is massive compared to what we had even in the early 2010s. The last decade has seen an enormous amount of growth in data available and it is not very surprising that the term Big Data has become commonplace. Given the huge amount of data, there are limitations that traditional databases face that more or less allow for only a certain level of parallelism and concurrency. We need to process multiple queries as well as do them quickly. This has forced researchers who usually store these huge graphs in their database to look for additional interfaces on top of their databases that can process various queries faster as well as quicker. This has lead to several parallel graph computation supporting systems such as Pregel, GraphLab, Giraph++and Blogel. A graph computation could mean checking if a node is connected to another, returning the value for SSSP amongst other things.

The authors propose a new parallel system, GRAPE, to perform these graph computations. The major idea behind Grape is partial evaluation and incremental computation. A major thing that sets GRAPE apart from other parallelizing systems mentioned above is the simplicity that it provides to the users. While other systems like Pregel need the users to think in terms “of a vertex”, and then recast a sequential algorithm into a parallel one, GRAPE provides more of a Plug and Play approach. The major work of the paper is to essentially come up with an end-to-end system that can take as input a sequential algorithm and parallelize computation across various cores without taking a huge hit in terms of performance as well as in the functionality of the above mentioned already existing systems.

Without any further adieu, I will get into the specifics of GRAPE.

GRAPE focusses mainly on four major things.

Figure 1 and Figure 2 show the programming interface, as well as the workflow of GRAPE.

As can be seen from the first figure, GRAPE provides a very simplistic GUI and as we can see from the second figure, we have a Partial Evaluation and an incremental computation phase, which are then finally assembled using an Assemble Algorithm. This process is repeated over and over in parallel as I shall shortly explain.

As mentioned previously, GRAPE builds upon incremental computation, as well as partial evaluation.

Let me now talk about partial evaluation and incremental computation.

In a partial evaluation phase, we take as arguments known inputs, as well as unknown inputs. Consider a graph G, spread across n processors, with each processor getting its share of the graph. You can view this as a partition of the graphs into a bunch of smaller graphs, with us removing the edges across different partitions and then putting them parallelly on the processor.

Now what we essentially end up doing is the following:

Plug in the 3 functions for parallelizing any sequential graph algorithm belonging to a particular class of algorithms, and Play! — Pick a graph partition strategy and the number of processors. Note that the user can decide the graph partitioning so as to make their work easier.

Given a particular query and the other needed information as in the number of processors, the ways of partitioning, GRAPE essentially parallelized the entire operation (PEVal, IncEVal and Assemble), all across n processors and computes Q(G) as in figure 2.

1. Each processor Pᵢ first executes PEval against its local data Fᵢ, to compute partial answers Q(Fᵢ ) in parallel. This felicitates data-partitioned parallelism via partial evaluation.

2. Then each Pᵢ may exchange partial results with other processors via synchronous message passing. Upon receiving message Mᵢ, Pᵢ computes Q(Fᵢ ⊕ Mᵢ ) by IncEval, the second algorithm that the user needs to provide, operating on local Fᵢ now “updated” by Mᵢ.

3. The incremental step iterates until no further updates.

Note — Mᵢ can be made to any Fⱼ, which is the same as telling we could send a message from any of the n processors to any of the remaining n-1 processors. At this point, the Assemble algorithm pulls partial answers Q(Fᵢ ⊕Mᵢ ), for i ∈ [1, n] and assembles the entire graph G (Q(G)).

The overall interpretation is that GRAPE parallelized all the sequential algorithms and conducts a simultaneous, fixed-point computation. It is guaranteed to converge to the correct answer. This comes with some assumptions that make the process of computation monotonic; that is, either strictly increasing, or, strictly decreasing. This holds when we describe the three algorithms correctly and properly. It supports Graph Level Optimisation over Fᵢ and also minimizes the iterative recomputation by IncEval. This is because we could simultaneously pass messages across processors. The entire picture is that we are able to do a fully sequential process, parallelly!

Just for the sake of clarity, let me walk you through an example.

Assume we are to compute the SSSP (Single Source Shortest Path), from some source node to any other node in a graph. Let me take the standard Dijkstra’s Algorithm. We know Dijkstra computes the SSSP correctly when all the edges have non-negative weights. Assume the edges have non-negative weights. Now do the following:

Split all the nodes using some partitioning method.

For each node — set its own distance to be 0 and to other nodes to be infinity.

Compute Dijkstra’s on all the individual parts of the code — parallelly — this is the partial evaluation phase.

Now, do incremental computation by considering those edges that cross across various different graph partitions. What I mean is that we update those graph partitions that share edges amongst them and consider as messages the changes that we would like to send across the partitions to update the distances from the source. To understand this — one can at any point in time only consider those edges that cross over partitions as edges that count. We iterate till we don’t update anymore.

Also, we finally assemble all the graph partitions’ results.

As the authors put it — “That is, we take sequential algorithms as PEval, IncEval and Assemble, and specify variables dist(s, v) for updating border nodes. GRAPE takes care of details such as message passing, load balancing as well as fault tolerance. There is no need to recast the entire algorithms into a new model.”

The idea of this blog post was to essentially bring about the major idea behind GRAPE. Interested people should sure go and give the paper a read. The authors have written the papers in a very lucid and solid manner giving very fine details into almost all aspects of implementation. An example would be how they discuss how messages are composed, how they are sent and the corresponding algorithms that are used. The correctness proof is very intuitive and should be easy once anyone gives it a read.

That’s it on GRAPE from me! Hope you got the central idea and had a productive reading time!

References:

[1] Wenfei Fan, Jingbo Xu, Yinghui Wu, Wenyuan Yu, Jiaxin Jiang, Zeyu Zheng, Bohan Zhang, Yang Cao, Chao Tian. Parallelizing Sequential Graph Computations, In SIGMOD 2017.

[2] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, 2010.

[3] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Distributed GraphLab: A framework for machine learning in the cloud. PVLDB, 5(8), 2012.

[4] P. Trinder. A Functional Database. PhD thesis, University of Oxford, 1989

[5] D. Yan, J. Cheng, Y. Lu, and W. Ng. Blogel: A block-centric framework for distributed computation on real-world graphs. PVLDB, 7(14):1981–1992, 2014

Related posts:

Before the year ends, entrepreneurs and small business owners should create a public relations strategy for the coming year. They should figure out what press releases to send and when to send them…

Turnkey digital asset mining operations; focuses on building, operating and maintaining crypto mining facilities. Merkle trees and Merkle roots are tools whose main purpose is to characterize…

Roof bugs are pests that live and breed in your roof or attic, such as roof rats, bats, raccoons, cluster flies, dust mites, carpet beetles, and more. These bugs can cause serious damage to your home…