Network Performance Aware Graph Partitioning for Large Graph Processing Systems in the Cloud - Large Scale and Big Data: Processing and Management - page 243

G G 1 G 2

Coarsen

Uncoarsen
(refinement)

Partitioning

FIGURE 7.4 The three phases in graph bisection: coarsening , partitioning , and
uncoarsening .

using a sequential and high-quality partitioning algorithm such as GGGP (Greedy
Graph Growing Partitioning) [45]. In the uncoarsening phase, the partitions are
then iteratively projected back toward the original graph, with a local refinement
on each iteration.
The iterations are highly parallelizable, and their efficiency and scalability has
been evaluated on shared-memory architectures (such as Cray supercomputers)
[44,46]. However, in the coarsening and uncoarsening phases, all the edges may be
accessed, generating a lot of network traffic if the input graph is stored in distributed
machines.

7.5.3.2 Network Transfer due to Cross Edges
Given a set of machines to partition the graph, the graph is initially stored in those
machines (usually according to the simple hash function). At each bisection, all
edges and vertices are accessed multiple times for coarsening and uncoarsening. It
generates a lot of network traffic. Thus, bisection should be designed to be aware of
the network bandwidth unevenness.
Assume that the amount of network traffic sent along each cross-partition edge is
the same (denoted as b ). Denote the number of cross-partition edges from partition
G i to G j to be C ( G i , G j ), and the network bandwidth between the machines stored G i
and G j to be B i,j . Since network bandwidth is a scarce resource in the cloud environ-
ment [23,37], the bandwidth can be considered as the main indicator for network
performance, and it approximates the network data transfer time from G i to G j to
be cG Gb
B

(, ) × . This approximation is sufficient for large graph processing in both

i j

ij ,

private and public cloud environments. Assuming P graph partitions are stored on P
different machines, the total network data transfer time incurred in all partition pairs

CG Gb
B

(, ) ×

∑ ∑

P − 1 P − 1

i j

is .

i = 0 j = 0

ij ,