Accelerating PageRank using Partition-Centric Processing
Kartik Lakhotia, Rajgopal Kannan, Viktor Prasanna
Ming Hsieh Department of Electrical Engineering, University of Southern California
{klakhoti, rajgopak, prasanna}@usc.edu

arXiv:1709.07122v3 [cs.DC] 7 Feb 2018

Abstract

ther allows in-memory processing of large graphs on a
single server [31, 29, 33]. However, efficient utilization
of compute power is challenging even on a single node
because of the (1) low computation-to-communication
ratio and, (2) irregular memory access patterns of graph
algorithms. The growing disparity between CPU speed
and DRAM bandwidth, termed memory wall [38], has
become a key issue in high performance graph analytics.
PageRank is a quintessential algorithm that exemplifies the performance challenges posed by graph
computations. It iteratively performs Sparse MatrixVector (SpMV) multiplication over the adjacency matrix of the target graph and the current PageRank vec−
→
tor PR to generate new PageRank values. The irregularity in adjacency matrices leads to random accesses to
−
→
PR with poor spatial and temporal locality. The resulting cache misses and communication volume become
the performance bottleneck for PageRank computation.
Since many graph algorithms can be similarly modeled
as a series of SpMV operations [33], optimizations on
PageRank can be easily generalized to other algorithms.
Recent works have proposed the use of Gather-ApplyScatter (GAS) model to improve locality and reduce
communication for SpMV and PageRank [39, 10, 5].
This model splits computation into two phases: scatter
current source node values on edges and gather propagated values on edges to compute new values for destination nodes. The 2-phased approach restricts access
−
→
−
→
to either the current PR or new PR at a time. This provides opportunities for cache-efficient and lock-free parallelization of the algorithm.
We observe that although this approach exhibits several attractive features, it also has some drawbacks leading to inefficient memory accesses, both quantitative as
well as qualitative. First, we note that while scattering, a
vertex repeatedly writes its value on all outgoing edges,
resulting in large number of reads and writes. We also
observe that the Vertex-centric graph traversal in [10, 5]
results in random DRAM accesses and the Edge-centric
traversal in [30, 39] scans edge list in coordinate format
which increases the number of reads.
Our premise is that by changing the focus of computation from a single vertex or edge to a cacheable group

PageRank is a fundamental link analysis algorithm that
also functions as a key representative of the performance
of Sparse Matrix-Vector (SpMV) multiplication. The traditional PageRank implementation generates fine granularity random memory accesses resulting in large amount
of wasteful DRAM traffic and poor bandwidth utilization. In this paper, we present a novel Partition-Centric
Processing Methodology (PCPM) to compute PageRank,
that drastically reduces the amount of DRAM communication while achieving high sustained memory bandwidth. PCPM uses a Partition-centric abstraction coupled with the Gather-Apply-Scatter (GAS) programming
model. By carefully examining how a PCPM based
implementation impacts communication characteristics
of the algorithm, we propose several system optimizations that improve the execution time substantially. More
specifically, we develop (1) a new data layout that significantly reduces communication and random DRAM accesses, and (2) branch avoidance mechanisms to get rid
of unpredictable data-dependent branches.
We perform detailed analytical and experimental evaluation of our approach using 6 large graphs and demonstrate an average 2.7× speedup in execution time and
1.7× reduction in communication volume, compared to
the state-of-the-art. We also show that unlike other GAS
based implementations, PCPM is able to further reduce
main memory traffic by taking advantage of intelligent
node labeling that enhances locality. Although we use
PageRank as the target application in this paper, our approach can be applied to generic SpMV computation.

1

Introduction

Graphs are the preferred choice of data representation
in many fields such as web and social network analysis [8, 3, 25, 9], biology [16], transportation [14, 4] etc.
The growing scale of problems in these areas has generated substantial research interest in high performance
graph analytics. A large fraction of this research is focused on shared memory platforms because of their low
communication overhead compared to distributed systems [22]. High DRAM capacity in modern systems fur1

of vertices (partition), we can effectively identify and reduce redundant edge traversals as well as avoid random
accesses to DRAM, while still retaining the benefits of
GAS model. Based on these insights, we develop a new
Partition-Centric approach to compute PageRank. The
major contributions of our work are:

PageRank is computed iteratively. In each iteration,
all vertex values are updated by the new weighted sum
of their in-neighbors’ PageRank, as shown in equation 1.
PRi+1 (v) =

1. We propose a Partition-Centric Processing Methodology (PCPM) that propagates updates from nodes
to partitions and reduces the redundancy associated
with GAS model.

(1)

To assist visualization of some techniques and optimizations, we also use the Linear Algebraic perspective
where a PageRank iteration can be re-written as follows:
1−d
−−→
−
→
PRi+1 =
· 1|V |×1 + AT · SPRi
|V |

2. By carefully evaluating how a PCPM based implementation impacts algorithm behavior, we develop
several system optimizations that substantially accelerate the computation, namely, (a) a new data
layout that drastically reduces communication and
random memory accesses, (b) branch avoidance
mechanisms to remove unpredictable branches.

(2)

The most computationally intensive term that dictates the
performance of computing this equation is the Sparse
−−→
Matrix-Vector (SpMV) multiplication AT · SPRi . Henceforth, we will focus on the SpMV term to improve the
performance of PageRank algorithm.
PageRank is typically computed in pull direction [31,
34, 33, 26] where each vertex pulls the value of its inneighbors and accumulates into its own value, as shown
in algorithm 1. This corresponds to traversing A in a
column-major order and computing the dot product of
−−→
each column with the scaled PageRank vector SPR.

3. We demonstrate that PCPM can take advantage of
intelligent node labeling to further reduce the communication volume. Thus, PCPM is suitable even
for high locality graphs.
4. We conduct extensive analytical and experimental
evaluation of our approach using 6 large datasets.
On a 16-core shared memory system, PCPM
achieves 2.1×−3.8× speedup in execution time and
1.3×−2.5× reduction in main memory communication over state-of-the-art.

Algorithm 1 Pull Direction PageRank (PDPR) Iteration
1:
2:
3:
4:

5. We show that PCPM can be easily extended
to weighted graphs and generic SpMV computation (section 3.5) even though it is described in the
context of PageRank algorithm in this paper.

5:
6:

2

1−d
PRi (u)
+d ∑
|V |
u∈Ni (v) No (u)

for v ∈ V do
temp = 0
for all u ∈ Ni (v) do
temp+ = PR[u]
PRnext [v] =

(1−d)×|V |−1 + d×temp
|No (v)|

swap(PR, PRnext )

Background and Related Work

2.1

In the pull direction implementation, each column
completely owns the computation of the corresponding
element in the output vector. This enables all columns of
A to be traversed asynchronously in parallel without the
need to store partial sums in memory. On the contrary, in
the push direction, each node updates its out-neighbors
by adding its own value to them. This requires a rowmajor traversal of A and storage for partial sums since
each row contributes partially to multiple elements in the
output vector. Further, synchronization is needed to ensure conflict-free processing of multiple rows that update
the same output element.
Performance Challenges: Sparse matrix layouts like
Compressed Sparse Column (CSC) store all non-zero elements of a column sequentially in memory allowing fast
column-major traversal of A [32]. However, as shown in
fig. 2, the neighbors of a node (non-zero columns in adjacency matrix) can be scattered anywhere in the graph

PageRank Computation

In this section, we describe how PageRank is calculated
and what makes it challenging for the conventional implementation to achieve high performance. Table 1 lists
a set of notations that we use to mathematically represent
the algorithm.
Table 1: List of graph notations
G(V, E)
A
Ni (v)
No (v)
−
→
PRi
−−→
SPR
d

Input directed graph
adjacency matrix of G(V, E)
in-neighbors of vertex v
out-neighbors of vertex v
PageRank value vectorafter ith iteration 

scaled PageRank vector SPR(v) =

PRi (v)

|No (v)|
damping factor in PageRank algorithm

2

Percentage of DRAM Communication

100

tractable by reordering transformations because of their
skewed degree distribution.
Cache Blocking (CB) is another technique used to accelerate graph processing. CB attempts to induce locality by restricting range of randomly accessed nodes to
blocks that can fit in the cache [37, 28, 41]. CB partitions A along rows, columns or both into multiple block
matrices. Each block matrix can be stored in CSR or coordinate (COO) format. However, SpMV computation
with CB requires the partial sums to be re-read for each
block. The extremely sparse nature of these block matrices also reduces the locality in partial sum accesses [27].
Gather-Apply-Scatter (GAS) is another popular model
incorporated in many graph analytics frameworks [20,
30, 12]. It splits the analytic computation into scatter
and gather phases. In the scatter phase, source vertices
transmit updates on all of their outgoing edges and in the
gather phase, these updates are processed to compute
new values for corresponding destination vertices. The
updates for PageRank algorithm correspond to scaled
PageRank values defined earlier in section 2.1.
Binning exploits the 2-phased computation model by
storing the updates in a semi-sorted manner. This induces spatio-temporal locality in access patterns of the
algorithm. Binning can be used in conjunction with
both Vertex-centric or Edge-centric paradigms. Zhou
et al. [39, 40] use a custom sorted edge list with Edgecentric processing to reduce DRAM row activations and
improve memory performance. However, their sorting
mechanism introduces a non-trivial pre-processing cost
and imposes the use of COO format. This results in
larger communication volume and execution time than
the CSR based Vertex-centric implementations [5, 10].
GAS model is also inherently sub-optimal when used
with either Vertex-centric or Edge-centric abstractions.
This is because it traverses the entire graph twice in
each iteration. Nevertheless, Binning with Vertex-centric
GAS (BVGAS) is the state-of-the-art methodology on
shared memory platforms [5, 10] and we use it as baseline for comparison in this paper.

80

60

40

20

0
gplus

pld

web

kron

twitter

sd1

Datasets

Figure 1: Percentage contribution of vertex value accesses to the total DRAM traffic in a PageRank iteration.

Adjacency Matrix Transpose (AT)

SPRi

PRi+1

−−→
Figure 2: Access locations into SPR are derived from
non-zero column indices in rows of AT and tend to be
highly irregular.

and reading their values results in random accesses (sin−−→
gle or double word) to SPR in pull direction computation. Similarly, the push direction implementation uses
a Compressed Sparse Row (CSR) format for fast rowmajor traversal of A but suffers from random accesses
to the partial sums vector. These low locality and fine
granularity accesses incur high cache miss ratio and contribute a large fraction to the overall memory traffic as
shown in fig. 1.

2.2

Related Work

The performance of PageRank depends heavily on the
locality in memory access patterns of the graph (which
we refer to as graph locality). Since node labeling
has significant impact on graph locality, many prior
works have investigated the use of node reordering or
clustering [7, 19, 6, 2] to improve the performance
of graph algorithms. Recently, a relabeling algorithm
GOrder [35] was proposed that improves spatial locality and outperforms the well known clustering and treebased techniques. Such sophisticated algorithms provide
significant speedup but also introduce substantial preprocessing overhead which limits their practicability. In
addition, scale-free graphs like social networks are less

3

Partition-Centric Processing

We propose a new Partition-Centric Processing Methodology (PCPM) that significantly improves the efficiency
of processor-memory communication over that achievable with current Vertex-centric or Edge-centric methods. We define partitions as disjoint sets of contiguously labeled nodes. The Partition-Centric abstraction
then perceives the graph as a set of links from each node
to the partitions corresponding to the neighbors of the
node. We use this abstraction in conjunction with the
2-phased Gather-Apply-Scatter (GAS) model.
3

During the PCPM scatter phase, each thread processes
one partition at a time. Processing a partition p means
propagating messages from nodes in p to the neighboring partitions. A message to a partition p0 comprises of
the update value of source node (PR[v]) and the list of
out-neighbors of v that lie in p0 . PCPM caches the vertex
data of p and streams the messages to the main memory.
The messages from p are generated in a Partition-centric
manner i.e. messages from all nodes in p to a neighboring partition p0 are generated consecutively and are not
interleaved with messages to any other partition.
During the gather phase, each thread scans all messages destined to one partition p at a time. A message
scan applies the update value to all nodes in the neighbor
list of that message. Partial sums of nodes in p are cached
and messages are streamed from the main memory. After all messages to p are scanned, the partial sums (new
PageRank values) are written back to DRAM.
With static pre-allocation of distinct memory spaces
for each partition to write messages, PCPM can asynchronously scatter or gather multiple partitions in parallel. In this section, we provide a detailed discussion on
PCPM based computation and the required data layout.

3.1

into update bins[0] is 0 (since partitions P0 and P1 do not
write to bin 0). Similarly, its offset into update bins[1]
and update bins[2] is 1 (since P1 writes one update to
bin 1 and P0 writes one update to bin 2). Offset computation provides each partition fixed and disjoint locations
to write messages. This allows PCPM to parallelize partition processing without the need of locks or atomics.
5

4

8

6

2

3

7

P0
0
1
2

0

Partitions
P1
3
4
5

P2
6
7
8

1

(a) Example graph with partitions of size 3
Updates Dest. ID
PR[6]
2
PR[7]

0
1

Updates
PR[3]

Dest. ID
4

Updates

Dest. ID

PR[2]

8

3
4

PR[7]

8

PR[6]

2
Bin 0

5

Bin 2

Bin 1

(b) Bins store update value and list of destination nodes

Figure 3: Graph Partitioning and messages inserted in
bins during scatter phase

Graph Partitioning

We employ a simple approach to divide the vertex set
V into partitions. We create equisized partitions of size
q where partition Pi owns all the vertices with index
∈ [i ∗ q, (i + 1) ∗ q) as shown in fig. 3a. As discussed
later, the PCPM abstraction is built to easily take advantage of more sophisticated partitioning schemes and
deliver further performance improvements (the trade-off
is time complexity of partitioning versus performance
gains). As we show in the results section, even the simple partitioning approach described above delivers significant performance gains over state-of-the-art methods.
Each partition is also allocated a contiguous memory
space called bin to store updates (update bins) and corresponding list of destination nodes (destID bins) in the
incoming messages. Since each thread in PCPM scatters or gathers only one partition at a time, the random
accesses to vertex values or partial sums are limited to
address range equal to the partition size. This improves
temporal locality in access pattern and in turn, overall
cache performance of the algorithm.
Before beginning PageRank computation, each partition calculates the offsets (address in bins where it must
start writing from) into all update bins and destID bins.
Our scattering strategy dictates that the partitions write
to bins in the order of their IDs. Therefore, the offset for
a partition Pi into any given bin is the sum of the number
of values that all partitions with ID < i are writing into
that bin. For instance, in fig. 3, the offset of partition P2

Note that since the destination node IDs written in the
first iteration remain unchanged over the course of algorithm, they are written only once and reused in subsequent iterations. The reuse of destination node IDs along
with the specific system optimizations discussed in section 3.2 and 3.3 enables PCPM to traverse only a fraction
of the graph during scatter phase. This dramatically reduces the number of DRAM accesses and gets rid of the
inherent sub-optimality of GAS model.

3.2

Partition-Centric Update Propagation

The unique abstraction of PCPM naturally leads to transmitting a single update from a node to a neighboring partition. In other words, even if a node has multiple neighbors in a partition, it inserts only one update value in
the corresponding update bins during scatter phase (algorithm 2). Fig. 4 illustrates the difference between
Partition-Centric and Vertex-centric scatter for the example graph shown in fig. 3a.
PCPM manipulates the Most Significant Bit (MSB)
of destination node IDs to indicate the range of nodes
in a partition that use the same update value. In the
destID bins, it consecutively writes IDs of all nodes
in the neighborhood of same source vertex and sets
the MSB of first ID in this range to 1 for demarcation (fig. 4b). Since MSB is reserved for this functionality, PCPM supports graphs with upto 2 billion nodes
4

instead of 4 billion for 4 Byte node IDs. However, to the
best of our knowledge, this is enough to process most of
the large publicly available datasets.
Propagate Updates
on all Edges
6

specific data layout.
Algorithm 2 PageRank iteration in PCPM using CSR
format. Writing of destID bins is not shown here.

Updates Dest. ID

7

PR[6]

2

PR[7]

0

PR[7]

1

PR[7]

2

1:
2:
3:
4:
5:
6:
7:

Bin 0

8:
9:
10:
11:

(a) Scatter in Vertex-centric GAS
Non-redundant
updates only

Updates

6

PR[6]

7

PR[7]

8
P2

MSB Dest. ID

{

1

2

1

0

0

1

0

2

12:
13:
14:
15:

Bin 0

16:

q → partition size, P → set of partitions
for all p ∈ P do
. Scatter
for all v ∈ p do
prev bin ← ∞
for all u ∈ No (v) do
if bu/qc =
6 prev bin then
insert PR[v] in update bins[bu/qc]
prev bin ← bu/qc
PR[:] ← 0
for all partitions p ∈ P do
. Gather
while destID bins[p] 6= 0/ do
pop id from destID bins[p]
if MSB(id) 6= 0 then
pop update from update bins[p]
PR[id & bitmask] += update
for all v ∈ V do
. Apply
+ d×PR[v]
PR[v] ← (1−d)/|VN| (v)
| o |

(b) Scatter in PCPM

Figure 4: PCPM decouples update bins and destID bins
to avoid redundant update value propagation

3.3

Data Layout Optimization

In this subsection, we describe a new bipartite PartitionNode Graph (PNG) data layout that brings out the true
Partition-Centric nature of PCPM. During the scatter
phase, PNG prevents unused edge reads and ensures that
all updates to a bin are streamed together before switching to another bin.
We exploit the fact that once destID bins are written,
the only required information in PCPM is the connectivity between nodes and partitions. Therefore, edges going
from a source to all destination nodes in a single partition can be compressed into one edge whose new destination is the corresponding partition number. This gives
rise to a bipartite graph G0 with disjoint vertex sets V and
P (where P = {P0 , . . . , Pk−1 } represents the set of partitions in the original graph), and a set of directed edges
E 0 going from V to P. Such a transformation has the
following effects:

The gather phase starts only after all partitions are processed in the scatter phase. PCPM gather function sequentially reads updates and node IDs from the bins of
the partition being processed. When gathering partition
Pi , an update value PR[v] should be applied to all outneighbors of v that lie in Pi . This is done by checking the
MSB of node IDs to determine whether to apply the previously read update or to read the next update, as shown
in algorithm 2. The MSB is then masked to generate the
true ID of destination node whose partial sum is updated.
Algorithm 2 describes PCPM based PageRank computation using a row-wise partitioned CSR format for adjacency matrix A. Note that PCPM only writes updates
for some edges in a node’s adjacency list, specifically the
first outgoing edge to a partition. The remaining edges to
that partition are unused. Since CSR stores adjacencies
of a node contiguously, the set of first edges to neighboring partitions is interleaved with other edges. Therefore,
we have to scan all outgoing edges of each vertex during scatter phase to access this set, which decreases efficiency. Moreover, the algorithm can potentially switch
bins for each update insertion, leading to random writes
to DRAM. Finally, the manipulation of MSB in node
indices introduces additional data dependent branches
which hurts the performance. Clearly, CSR adjacency
matrix is not an efficient data layout for graph processing
using PCPM. In the next section, we propose a PCPM-

1. Eff1 → the unused edges in original graph are removed
2. Eff2 → the range of destination IDs reduces from |V |
to |P|.
The advantages of Eff1 are obvious but those of Eff2 will
become clear when we discuss the storage format and
construction of PNG.
The compression step reduces memory traffic by eliminating unused edge traversal. However note that scatters
5

ter phase with little pre-processing overhead.

P0
P2

2

Graph between P
and nodes in P0

P1

3

Graph between P
and nodes in P1

P1
P2

6

Algorithm 3 PCPM scatter phase using PNG layout

7

Graph between P
and nodes in P2

1:
2:
3:

Figure 5: Partition-wise construction of PNG G0 (P,V, E 0 )
for graph G(V, E) (fig. 3a). E 0 is much smaller than |E|.

4:

to a bin from source vertices in a partition are still interleaved with scatters to other bins. This can lead to
random DRAM accesses during the scatter phase processing of a (source) partition. We resolve this problem
by transposing the adjacency matrix of bipartite graph
G0 . The rows of the transposed matrix represent edges
grouped by destination partitions which enables streaming updates to one bin at a time. This advantage comes at
the cost of random accesses to source node values during
the scatter phase. To prevent these random accesses from
going to DRAM, we construct PNG on a per-partition basis i.e. we create a separate bipartite graph for each partition Pi with edges between P and the nodes in Pi (fig. 5).
By carefully choosing q to make partitions cacheable, we
ensure that all requests to source nodes are served by the
cache resulting in zero random DRAM accesses.
Eff2 is crucial for transposition of bipartite graphs in
all partitions. The number of offsets required to store a
transposed matrix in CSR format is equal to the range
of destination node IDs. By reducing this range, Eff2 reduces the storage requirement for offsets of each matrix
from O(|V |) to O(|P|). Since there are |P| partitions, each
having one bipartite graph, the total storage requirement
for edge offsets in PNG is O(|P|2 ) instead of O(|V | ×|P|).
Although PNG construction looks like a 2-step approach, we actually merge compression and transposition into a single step. We first scan the outgoing edges
of all nodes in a partition and individually compute the
in-degree of all the destination partitions while discarding unused edges. A prefix sum of these degrees is carried out to compute the offsets array for CSR matrix. The
same offsets can also be used to allocate disjoint writing
locations into the bins of destination partitions. In the
next scan, the edge array in CSR is filled with source
node IDs completing both compression and transposition. PNG construction can be easily parallelized over
all partitions to accelerate the pre-processing effectively.
Algorithm 3 shows the pseudocode for PCPM scatter
phase using PNG layout. Unlike algorithm 2, the scatter function in algorithm 3 does not contain data dependent branches to check and discard unused edges. Using
PNG provides drastic performance gains in PCPM scat-

3.4

G0 (P,V, E 0 ) → PNG, Nip (p0 ) → in-neighbors of partition p0 in bipartite graph of partition p
for all p ∈ P do
. Scatter
for all p0 ∈ P do
for all u ∈ Nip (p0 ) do
insert PR[u] into update bins[p0 ]

Branch Avoidance

Data dependent branches have been shown to have significant impact on performance of graph algorithms [13]
and PNG removes such branches in PCPM scatter phase.
In this subsection, we propose a branch avoidance mechanism for the PCPM gather phase. Branch avoidance enhances the sustained memory bandwidth but does not impact the amount of DRAM communication.
Note that the pop operations shown in algorithm 2 are
implemented using pointers that increment after reading an entry from the respective bin. Let destID ptr
and update ptr be the pointers to destID bins[p] and
update bins[p], respectively. Note that the destID ptr
is incremented in every iteration whereas the update ptr
is only incremented if MSB[id] 6= 0.
To implement the branch avoiding gather function, instead of using a condition check over MSB(id), we add it
directly to update ptr. When MSB(id) is 0, the pointer
is not incremented and the same update value is read
from cache in the next iteration; when MSB(id) is 1,
the pointer is incremented executing the pop operation
on update bins[p]. The modified pseudocode for gather
phase is shown in algorithm 4.
Algorithm 4 Branch Avoiding gather function in PCPM
PR[:] = 0
for all partitions p ∈ P do
. Gather
{destID ptr, update ptr} ← 0
while destID ptr < size(destID bins[p]) do
id ← destID bins[p][destID ptr ++]
update ptr += MSB(id)
7:
id ← id & bitmask
8:
PR[id] += update bins[p][update ptr]
1:
2:
3:
4:
5:
6:

3.5

Weighted Graphs and SpMV

PCPM can be easily extended for computation on
weighted graphs by storing the edge weights along with
destination IDs in destID bins. These weights can be
read in the gather phase and applied to the source node
6

Table 2: List of model parameters

value before updating the destination node. PCPM can
also be extended to generic SpMV with non-square matrices by partitioning the rows and columns separately.
In this case, the outermost loops in scatter phase (algorithm 3) and gather phase (algorithm 4) will iterate over
row partitions and column partitions of A, respectively.

3.6

Original Graph G(V, E)
no. of vertices ( |V | )
no. of edges ( |E| )
Architecture
cache miss ratio for source
cmr
value reads in PDPR
l
sizeof (cache line)
n
m

4

4:
6:
7:
8:
9:
10:

dv

sizeof (updates/PageRank value)

di

sizeof (node or edge index)

Analytical Evaluation

We derive performance models to compare PCPM
against conventional Pull Direction PageRank (PDPR)
and BVGAS. Our models provide valuable insights into
the behavior of different methodologies with respect to
varying graph structure and locality. Table 2 defines the
parameters used in the analysis. We use a synthetic kronecker graph [24] of scale 25 (kron) as an example for
illustration purposes. We analyze the amount of data
exchanged with main memory per iteration of PageRank. We assume that data is accessed in quantum of one
cache line and BVGAS exhibits full cache line utilization. Since destination indices are written only in the first
iteration for PCPM and BVGAS, they are not accounted
for in this model.
PDPR: The pull technique scans all edges in the graph
once (algorithm 1). For a CSR format, this requires reading n edge offsets and m source node indices. PDPR
also reads m source node values that incur cache misses
generating mcmr l Bytes of DRAM traffic. Outputting
new PageRank values generates ndv Bytes of writes to
DRAM. The total communication volume for PDPR is:

Algorithm 5 PageRank Iteration using BVGAS

5:

PNG layout G0 (P,V, E 0 )
no. of partitions ( |P| )
compression ratio ( |E| / E 0 )
Software

Comparison with Vertex-centric GAS

The Binning with Vertex-centric GAS (BVGAS)
method allocates multiple bins to store incoming messages ((update, destID) pairs). If bin width is q, then
all messages destined to v ∈ [i ∗ q, (i + 1) ∗ q) are written in bin i. The scatter phase traverses the graph in
a Vertex-centric fashion and inserts the messages in respective bins of the destination vertices. Number of bins
is kept small to allow insertion points for all bins to fit in
cache, providing good spatial locality. The gather phase
processes one bin at a time as shown in algorithm 5, and
thus, enjoys good temporal locality if bin width is small.

1:
2:
3:

k
r

q → bin width, B → no. of bins
for v ∈ V do
. Scatter
PR[v] = PR[v]/ No (v)
for all u ∈ No (v) do
insert (PR[v], u) into bins[bu/qc]
PR[:] = 0
for b = 0 to B − 1 do
. Gather
for all (update, dest) in bins[b] do
PR[dest] = PR[dest] + update
for all v ∈ V do
. Apply
PR[v] = (1−d)
+
d
×
PR[v]
|V |

PDPRcomm = m(di + cmr l) + n(di + dv )

(3)

BVGAS: The scatter phase (algorithm 5) scans the graph
and writes updates on all outgoing edges of the source
node, thus communicating (n + m)di + (n + m)dv Bytes.
The gather phase loads updates and destination node IDs
on all the edges generating m(di + dv ) Bytes of read traffic. At the end of gather phase, ndv Bytes of new PageRank values are written in the main memory. Total communication volume for BVGAS is therefore, given by:

Unlike algorithm 5, in our BVGAS implementation,
we write the destination IDs only in the first iteration.
We also use small cached buffers to store updates before
writing to DRAM. This ensures full cache line utilization
and reduces communication during scatter phase [5].
Irrespective of all the locality advantages and optimizations, BVGAS inherently suffers from redundant
reads and writes of a vertex value on all of its outgoing
edges. This redundancy manifests itself in the form of
BVGAS’ inability to utilize high locality in graphs with
optimized node labeling. PCPM on the other hand, uses
graph locality to reduce the fraction of graph traversed in
scatter phase. Unlike PCPM, the Vertex-centric traversal
in BVGAS can also insert consecutive updates into different bins. This leads to random DRAM accesses and
poor bandwidth utilization. We provide a quantitative
analysis of these differences in the next section.

BV GAScomm = 2m(di + dv ) + n(di + 2dv )

(4)

PCPM with PNG: Number of edge offsets in bipartite
graph of each partition is k. Thus, in the scatter phase (algorithm 3), a scan of PNG reads (k × k + m/r)di Bytes.
The scatter phase further reads n PageRank values and
writes updates on m/r edges. The gather phase (algorithm 4) reads m destination IDs and m/r updates followed
by n new PageRank value writes. Net communication
7

volume in PCPM is given by:
DRAM communication (GB)



1
2dv
PCPMcomm = m di 1 +
+
r
r

24

!
2

+ k di + 2ndv

(5)
Comparison: Performance of pull technique depends
heavily on cmr . In the worst case, all accesses are
cache misses i.e. cmr = 1 and in best case, only cold
misses are encountered to load the PageRank values in
cache i.e. cmr = ndv/ml . Assuming k2  n  m, we get
PDPRcomm ∈ [mdi , m(di + l)]. On the other hand, communication for BVGAS stays constant. With θ (m) additional loads and stores, BV GAScomm can never reach the
lower bound of PDPRcomm . Comparatively, PCPMcomm
achieves optimality when for every vertex, all outgoing
edges can be compressed into a single edge i.e. r = m/n.
In the worst case when r = 1, PCPM is still as good as
BVGAS and we get PCPMcomm ∈ [mdi , m(2di + 2dv )].
Unlike BVGAS, PCPMcomm achieves the same lower
bound as PDPRcomm .
Analyzing equations 3 and 4, we see that BVGAS is
profitable compared to PDPR when:
cmr >

di + 2dv
l

di + 2dv
rl

12

r=3.13 for
original labeling

8
4

0

5

10

15

20

25

30

35

Compression Ratio r

Figure 6: Predicted DRAM traffic for kron graph with
n = 33.5 M, m = 1070 M, k = 512 and di = dv = 4 Bytes.
PDPR: Reading edge offsets and source node IDs in pull
technique is completely sequential because of the CSR
format. However, all accesses to source node PageRank
values served by DRAM contribute to potential random
accesses resulting in:
PDPRra = O(mcmr )

(8)

BVGAS: In scatter phase of algorithm 5, updates can
potentially be inserted at random memory locations. Assuming full cache line utilization for BVGAS, for every
l Bytes written, there is at most 1 random DRAM access.
In gather phase, all DRAM accesses are sequential if we
assume that bin width is smaller than the cache. Total
random accesses for BVGAS are then given by:


mdv
BV GASra = O
(9)
l

(6)

(7)

The RHS in eq. 6 is constant indicating that BVGAS
is advantageous for low locality graphs. With optimized
node ordering, we can reduce cmr and outperform BVGAS. On the contrary, r ∈ [1, m/n] in the RHS of eq. 7
is a function of locality. With an optimized node labeling, r also increases and enhances the performance of
PCPM. Fig. 6 shows the effect of r on predicted DRAM
communication for the kron graph. Obtaining an optimal
nodel labeling that makes r = m/n might be very difficult
or even impossible for some graphs. However, as can
be observed from fig. 6, DRAM traffic decreases rapidly
for r ≤ 5 and converges slowly for r > 5. Therefore, a
node reordering that can achieve r ≈ 5 is good enough to
optimize communication volume in PCPM.

4.1

16

0

In comparison, PCPM offers a more relaxed constraint
on cmr (by a factor of 1/r) becoming advantageous when:
cmr >

20

PCPM: With the PNG layout (algorithm 3), there are
at most k bin switches when scattering updates from a
partition. Since there are k such partitions, total number
of random accesses in PCPM is bound by:
PCPMra = O(k ∗ k) = O(k2 )

(10)

Comparison: BVGAS exhibits less random accesses
than PDPR. However, PCPMra is much smaller than
both BV GASra and PDPRra . For instance, in the kron
dataset with dv = 4 Bytes, l = 64 Bytes and k = 512,
BV GASra ≈ 66.9 M whereas PCPMra ≈ 0.26 M.
Although it is not indicated in algorithm 5, the number of data dependent unpredictable branches in cache
bypassing BVGAS implementation is also O(m). For
every update insertion, the BVGAS scatter function has
to check if the corresponding cached buffer is full (section 3.6). In contrast, the number of branch mispredictions for PCPM (using branch avoidance) is O(k2 ) with
1 misprediction for every destination partition (p0 ) switch
in algorithm 3. The derivations are similar to random access model and for the sake of brevity, we do not provide
a detailed deduction.

Random Memory Accesses

We define a random access as a non-sequential jump in
the address of memory location being read from or written to DRAM. Random accesses can incur latency penalties and negatively impact the sustained memory bandwidth. In this subsection, we model the amount of random accesses performed by different methodologies in a
single PageRank iteration.
8

5
5.1

Experimental Evaluation

per thread is statically balanced in terms of the number of edges processed. We also give each thread distinct memory spaces corresponding to all bins to avoid
atomicity concerns in scatter phase. We use the Intel
AVX non-temporal store instructions [1] to bypass the
cache while writing updates and use 128 Bytes cache line
aligned buffers to accumulate the updates for streaming
stores [5]. BVGAS gather phase is parallelized over bins
with load balanced using OpenMP dynamic scheduling.
The optimal bin width is empirically determined and set
to 256 KB (64K nodes). As bin width is a power of 2,
we use bit shift instructions instead of integer division to
compute the destination bin from node ID.
The PCPM scatter and gather phases are parallelized
over partitions and load balancing in both the phases is
done dynamically using OpenMP. Partition size is empirically determined and set to 256 KB. A detailed design
space exploration of PCPM is discussed in section 5.3.2.
All the implementations mentioned in this section execute 20 PageRank iterations on 16 cores. For accuracy
of the collected information, we repeat these algorithms
5 times and report the average values.

Experimental Setup and Datasets

We conduct experiments on a dual-socket Ivy Bridge
server equipped with two 8-core Intel Xeon E5-2650
v2 processors@2.6 GHz running Ubuntu 14.04 OS. Table 3 lists important characteristics of our machine.
Memory bandwidth is measured using STREAM benchmark [21]. All codes are written in C++ and compiled
using G++ 4.7.1 with the highest optimization -O3 flag.
The memory statistics are collected using Intel Performance Counter Monitor [36]. All data types used for
indices and PageRank values are 4 Bytes.
Table 3: System Characteristics
Socket
Core
Memory

no. of cores
shared L3 cache
L1d cache
L2 cache
size
Read BW
Write BW

8
25MB
32 KB
256 KB
128 GB
59.6 GB/s
32.9 GB/s

We use 6 large real world and synthetic graph datasets
coming from different applications, for performance
evaluation. Table 4 summarizes the size and sparsity
characteristics of these graphs. Gplus and twitter are follower graphs on social networks; pld, web and sd1 are
hyperlink graphs obtained by web crawlers; and kron is
a scale 25 graph generated using Graph500 Kronecker
generator. The web is a very sparse graph but has high
locality obtained by a very expensive pre-processing of
node labels [6]. The kron graph has higher edge density
as compared to other datasets.

5.2

Description
Google Plus
Pay-Level-Domain
Webbase-2001
Synthetic graph
Follower network
Subdomain graph

# Nodes (M)
28.94
42.89
118.14
33.5
61.58
94.95

# Edges (M)
462.99
623.06
992.84
1047.93
1468.36
1937.49

Results

5.3.1

Comparison with Baselines

Execution Time: Fig. 7 gives a comparison of the
GTEPS (computed as the ratio of giga edges in the graph
to the runtime of single PageRank iteration) achieved by
different implementations. We observe that PCPM is
2.1 − 3.8× faster than the state-of-the-art BVGAS implementation and upto 4.1× faster than PDPR. BVGAS
achieves constant throughput irrespective of the graph
structure and is able to accelerate computation on low
locality graphs. However, it is worse than PDPR for high
locality (web) and dense (kron) graphs. PCPM is able to
outperform PDPR and BVGAS on all datasets, though
the speedup on web graph is minute because of high performance of PDPR. Detailed results for execution time of
BVGAS and PCPM during different phases of computation are given in table 5. PCPM scatter phase benefits
from a multitude of optimizations to achieve a dramatic
5× speedup over BVGAS scatter phase.

Table 4: Graph Datasets
Dataset
gplus [11]
pld [23]
web [6]
kron [24]
twitter [18]
sd1 [23]

5.3

Degree
16
14.53
8.4
31.28
23.84
20.4

Implementation Details

Table 5: Execution time per iteration of PageRank for
PDPR, BVGAS and PCPM

We use a simple hand coded implementation of algorithm 1 for PDPR and parallelize it over vertices with
static load balancing on the number of edges traversed.
Our baseline does not incur overheads associated with
similar implementations in frameworks [31, 26, 33] and
hence, is faster than framework based programs [5].
To parallelize BVGAS scatter phase (algorithm 5), we
give each thread a fixed range of nodes to scatter. Work

Dataset
gplus
pld
web
kron
twitter
sd1

9

PDPR
Total
Time(s)
0.44
0.68
0.21
0.65
1.83
1.97

Scatter
Time(s)
0.26
0.33
0.58
0.5
0.79
1.07

BVGAS
Gather
Time(s)
0.12
0.15
0.23
0.22
0.32
0.42

Total
Time(s)
0.38
0.48
0.81
0.72
1.11
1.49

Scatter
Time(s)
0.06
0.09
0.04
0.07
0.18
0.24

PCPM
Gather
Time(s)
0.1
0.13
0.17
0.18
0.27
0.35

Total
Time(s)
0.16
0.22
0.21
0.25
0.45
0.59

50

4

40

Memory Bandwidth (GB/s)

5

GTEPS

3

PDPR
BVGAS
PCPM

2

1

0

30

PDPR
BVGAS
PCPM

20

10

0
gplus

pld

web

kron

twitter

sd1

gplus

pld

Datasets

web

kron

twitter

sd1

Datasets

Figure 7: Performance in GTEPS. PCPM provides substantial speedup over BVGAS and PDPR.

Figure 9: Sustained Memory Bandwidth for different
methods. PCPM achieves highest bandwidth utilization.
Table 6: Locality vs compression ratio r. GOrder improves locality in neighbors and increases compression

Communication and Bandwidth: Fig. 8 shows the
amount of data communicated with main memory normalized by the number of edges in the graph. Average
communication in PCPM is 1.7× and 2.2× less than
BVGAS and PDPR, respectively. Further, PCPM memory traffic per edge for web and kron is lower than other
graphs because of their high compression ratio (table 6).
The normalized communication for BVGAS is almost
constant and therefore, its utility depends on the efficiency of pull direction baseline.

Dataset
gplus
pld
web
kron
twitter
sd1

#Edges in
Graph (M)
463
623.1
992.8
104.8
1468.4
1937.5

Original Labeling
#Edges in
r
PNG (M)
243.8
1.9
347.7
1.79
118.1
8.4
342.7
3.06
722.4
2.03
976.9
1.98

GOrder Labeling
#Edges in
r
PNG (M)
157.4
2.94
166.7
3.73
126.8
7.83
169.7
6.17
386.2
3.8
366.2
5.29

60

terns in PCPM also enhance its energy efficiency resulting in lower µJ/edge consumption as compared to BVGAS and PDPR, as shown in fig. 10. Energy efficiency
is important from an eco-friendly computing perspective
as highlighted by the Green Graph500 benchmark [15].
Effect of Locality: To assess the impact of locality
on different methodologies, we relabel the nodes in our
graph datasets using the GOrder [35] algorithm. We refer
to the original node labeling in graph as Orig and GOrder
labeling as simply GOrder. GOrder increases spatial locality by placing nodes with common in-neighbors closer

Bytes accessed per Edge

50
40

PDPR
BVGAS
PCPM

30
20
10

0
gplus

pld

web

kron

twitter

sd1

Datasets

Figure 8: Main memory traffic per edge. PCPM communicates the least for all datasets except the web graph.

1.2

Note that the speedup obtained by PCPM is larger
than the reduction in communication volume. This is because by avoiding random DRAM accesses and unpredictable branches, PCPM is able to efficiently utilize the
available DRAM bandwidth. As shown in fig. 9, PCPM
can sustain an average 42.4 GB/s bandwidth compared
to 33.1 GB/s and 26 GB/s of PDPR and BVGAS, respectively. For large graphs like sd1, PCPM achieves
≈ 77% of the peak read bandwidth (table 3) of our system. Although both PDPR and BVGAS suffer from random memory accesses, the former executes very few instructions and therefore, has better bandwidth utilization.

1

Energy (μJ)

0.8

PDPR
BVGAS
PCPM

0.6
0.4
0.2

0
gplus

pld

web

kron

twitter

sd1

Datasets

Figure 10: DRAM energy consumption per edge. PCPM
benefits from reduced communication and random memory accesses.

The reduced communication and streaming access pat10

Table 7: DRAM data transfer per iteration (in GB).
PDPR and PCPM benefit from optimized node labeling
Dataset
gplus
pld
web
kron
twitter
sd1

PDPR
Orig GOrder
13.1
7.4
24.5
10.7
7.5
7.6
18.1
10.8
68.2
31.6
65.1
23.8

BVGAS
Orig GOrder
9.3
9.3
12.6
12.5
21.6
21.3
19.9
19.5
28.8
28.2
37.8
37.8

tion sizes. The kron dataset exhibits larger compression
than other graphs because of high edge density.
A direct consequence of increase in r is observed in
the amount of DRAM communication which reduces as
we increase the partition size (fig. 12). However, if the
partition becomes more than the cache capacity, cache is
unable to accommodate all the nodes of a partition resulting in cache misses. This drastically increases the
main memory traffic as for each cache miss, one complete cache line is transferred from DRAM.

PCPM
Orig GOrder
6.6
5.1
9.4
6.1
8.5
8.4
10.4
7.5
19.4
13.4
26.9
15.6

64

DRAM communication per edge (Bytes)

in the memory. As a result, outgoing edges of the nodes
tend to be concentrated in few partitions which increases
the compression ratio r as shown in table 6. However, the
web graph exhibits near optimal compression (r = 8.4)
with Orig and does not show improvement with GOrder.
Table 7 shows the impact of GOrder on DRAM communication. As expected, BVGAS communicates a constant amount of data for a given graph irrespective of the
labeling scheme used. On the contrary, memory traffic generated by PDPR and PCPM decreases because
of reduced cmr and increased r, respectively. These observations are in complete accordance with the performance models discussed in section ??. The effect on
PCPM is not as drastic as PDPR because after r becomes greater than a threshold, PCPM communication
decreases slowly as shown in fig. 6. Nevertheless, for almost all of the datasets, the net data transferred in PCPM
is remarkably lesser than both PDPR and BVGAS for
either of the vertex labelings.

Compression ratio r

16

32K

64K

128K

256K

512K

1M

2M

4M

8M

Partition Size (in Bytes)

Figure 12: Impact of partition size on communication
volume. Very large partitions result in cache misses and
increased DRAM traffic.
The execution time (fig. 13) also benefits from communication reduction and is penalized by cache misses
for large partitions. Note that for partition sizes >
256 KB and <= 1 MB, communication volume decreases but execution time increases. This is because
in this range, many requests are served from the larger
shared L3 cache which is slower than the private L1 and
L2 caches. This phenomenon decelerates the computation but does not add to DRAM traffic.

8

gplus
pld
web
kron
twitter
sd1

2

gplus
pld
web
kron
twitter
sd1

8

16

4

32

1.2
1

Normaized Time

0.8

1
32K

64K

128K

256K

512K

1M

2M

4M

8M

Partition Size (in Bytes)

Figure 11: Compression ratio increases with partition
size

gplus
pld
web
kron
twitter
sd1

0.6
0.4
0.2

0
32K

5.3.2

64K

128K

256K

512K

1M

2M

4M

8M

Partition Size (in Bytes)

PCPM Design Space Exploration

Figure 13: Impact of partition size on execution time.

As we increase the size of partition, the neighbors of each
node are forced to fit in fewer partitions resulting in better compression as shown in fig. 11. The web graph is an
exception for which the r value remains almost constant
because its node labeling provides high spatial locality
and close to optimal compression even for small parti-

Partition size represents an important trade off in
PCPM. Large partitions result in better compression but
poor locality for random accesses to nodes within the
partition. Fig. 14 shows the effect of altering partition
11

Time (in seconds)

40

6

30

In this paper, we formulated a Partition-Centric Processing Methodology (PCPM) that perceives a graph as a set
of links between nodes and partitions instead of nodes
and their individual neighbors. We presented several features of this abstraction and developed system level optimizations to exploit them.
We develop a novel PNG data layout for efficient processing using PCPM. The idea for this layout originated
when we were trying to relax the Vertex-centric programming constraint that all outgoing edges of a node should
be traversed consecutively. The additional freedom arising from treating edges individually allowed us to group
edges in a way that eliminates random memory accesses
to sustain > 75% of peak memory bandwidth. We merge
several pre-processing steps to reduce cost of computing PNG and show that its benefits far exceed the preprocessing overhead.
We conducted extensive analytical and experimental
evaluation of our approach and observed an average 2.7×
speedup in execution time and 1.7× reduction in DRAM
communication volume over state-of-the-art. We show
that irrespective of the graph locality and density, PCPM
remains the preferred choice of PageRank implementation as it communicates the least amount of data at higher
bandwidth compared to other methodologies.
Although we demonstrate the advantages of PCPM
on PageRank, we show that it can be easily extended
to generic SpMV computation. We believe that PCPM
can be an efficient programming model for other graph
algorithms or graph analytics frameworks. In this context, there are many promising directions for further exploration. For instance, the streaming memory access
patterns of PNG enabled PCPM are highly suitable for
High Bandwidth Memory (HBM) and disk-based systems. Exploring PCPM as a programming model for heterogenous memory or processor architectures is an interesting avenue for future work.
The Vertex-centric and Edge-centric GAS based implementations are oblivious to graph locality and in turn,
node labeling. However, the unique abstraction of PCPM
allows it to take advantage of locality optimized node ordering. We use GOrder [35] to show the effect of locality on PCPM. However, GOrder optimizes labeling for
Vertex-centric push or pull implementations and has very
high pre-processing cost (O(∑u∈V |No (u)|2 ). Developing
low-cost reordering algorithms tailored for PCPM is an
important thread of research that we are working on.
PCPM accesses nodes from only one graph partition
at a time. Hence, G-Store’s smallest number of bits representation [17] can be used to reduce the memory footprint and DRAM communication even further. Devising
novel methods for enhanced compression can also make

20

Gather
Scatter

10

0
32K

64K

128K

256K

512K

1M

2M

4M

8M

Partition Size (in Bytes)

Figure 14: Time consumption of scatter and gather
phases for sd1 graph. Both the phases execute fastest
for partition size= 256 KB

size separately on scatter and gather phases for PageRank computation on sd1 dataset. Both scatter and gather
phases benefit from higher compression as partition size
increases. However, gather phase performance saturates
early because its memory accesses are proportional to
1 + 1/r, as compared to scatter phase where accesses are
proportional to 1/r. However, in both the phases, nodes
within a partition are randomly accessed and hence, the
performance declines if partition size grows beyond what
fits in cache. Based on our observations, we chose the
256 KB as the optimal partition size for our platform.

5.3.3

Pre-processing Time

We assume that adjacency matrix in CSR and CSC format is available and hence, PDPR does not need any preprocessing. Both BVGAS and PCPM however, require a
beforehand computation of bin size and write offsets incurring non-zero pre-processing time as shown in table 8.
In addition, PCPM also constructs the PNG layout. Fortunately, the computation of write offsets is merged with
PNG construction (section 3.3) to reduce the overhead.
The pre-processing time is lesser than execution time of
even a single iteration (table 5) and gets easily amortized
over multiple iterations of PageRank.
Table 8: Pre-processing time of different methodologies.
PNG construction increases the overhead of PCPM
Dataset
gplus
pld
web
kron
twitter
sd1

PCPM
0.25s
0.32s
0.26s
0.43s
0.7s
0.95s

BVGAS
0.1s
0.15s
0.18s
0.22s
0.27s
0.32s

PDPR
0s
0s
0s
0s
0s
0s

12

Conclusion and Future Work

PCPM amenable to be used for large-scale graph processing on commodity PCs.

Optimizing sparse matrix-vector multiplication for
large-scale data analytics. In Proceedings of the
2016 International Conference on Supercomputing
(2016), ACM, p. 37.

References

[11] G ONG , N. Z., X U , W., H UANG , L., M ITTAL , P.,
S TEFANOV, E., S EKAR , V., AND S ONG , D. Evolution of social-attribute networks: measurements,
modeling, and implications using google+. In Proceedings of the 2012 Internet Measurement Conference (2012), ACM, pp. 131–144.

[1] Intel
c++
compiler
17.0
developer
guide and reference, 2016.
Available
at
https://software.intel.com/
en-us/intel-cplusplus-compiler-17.
0-user-and-reference-guide.
[2] A BOU -R JEILI , A., AND K ARYPIS , G. Multilevel
algorithms for partitioning power-law graphs. In
Proceedings of the 20th International Conference
on Parallel and Distributed Processing (2006),
IPDPS’06, IEEE Computer Society, pp. 124–124.

[12] G ONZALEZ , J. E., L OW, Y., G U , H., B ICKSON ,
D., AND G UESTRIN , C. Powergraph: Distributed
graph-parallel computation on natural graphs. In
Presented as part of the 10th USENIX Symposium
on Operating Systems Design and Implementation
(OSDI 12) (2012), USENIX, pp. 17–30.

[3] A LBERT, R., J EONG , H., AND BARAB ÁSI , A.-L.
Internet: Diameter of the world-wide web. nature
401, 6749 (1999), 130.

[13] G REEN , O., D UKHAN , M., AND V UDUC , R.
Branch-avoiding graph algorithms. In Proceedings
of the 27th ACM symposium on Parallelism in Algorithms and Architectures (2015), ACM, pp. 212–
223.

[4] A LDOUS , J. M., AND W ILSON , R. J. Graphs
and applications: an introductory approach, vol. 1.
Springer Science & Business Media, 2003.

[14] H AKLAY, M., AND W EBER , P. Openstreetmap:
User-generated street maps. IEEE Pervasive Computing 7, 4 (2008), 12–18.

[5] B EAMER , S., A SANOVI Ć , K., AND PATTERSON ,
D. Reducing pagerank communication via propagation blocking. In Parallel and Distributed Processing Symposium (IPDPS), 2017 IEEE International (2017), IEEE, pp. 820–831.

[15] H OEFLER , T. Green graph500. Available at http:
//green.graph500.org/.
[16] H UBER , W., C AREY, V. J., L ONG , L., FALCON ,
S., AND G ENTLEMAN , R. Graphs in molecular
biology. BMC bioinformatics 8, 6 (2007), S8.

[6] B OLDI , P., ROSA , M., S ANTINI , M., AND V I GNA , S. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th international conference on World wide web (2011), ACM,
pp. 587–596.

[17] K UMAR , P., AND H UANG , H. H. G-store: highperformance graph store for trillion-edge processing. In High Performance Computing, Networking,
Storage and Analysis, SC16: International Conference for (2016), IEEE, pp. 830–841.

[7] B OLDI , P., S ANTINI , M., AND V IGNA , S. Permuting web and social graphs. Internet Mathematics 6,
3 (2009), 257–283.

[18] K WAK , H., L EE , C., PARK , H., AND M OON , S.
What is twitter, a social network or a news media?
In Proceedings of the 19th international conference
on World wide web (2010), ACM, pp. 591–600.

[8] B RODER , A., K UMAR , R., M AGHOUL , F.,
R AGHAVAN , P., R AJAGOPALAN , S., S TATA , R.,
T OMKINS , A., AND W IENER , J. Graph structure
in the web. Computer networks 33, 1-6 (2000),
309–320.

[19] L IU , W.-H., AND S HERMAN , A. H. Comparative analysis of the cuthill–mckee and the reverse
cuthill–mckee ordering algorithms for sparse matrices. SIAM Journal on Numerical Analysis 13, 2
(1976), 198–213.

[9] B RONSON , N., A MSDEN , Z., C ABRERA , G.,
C HAKKA , P., D IMOV, P., D ING , H., F ERRIS ,
J., G IARDULLO , A., K ULKARNI , S., L I , H. C.,
ET AL . Tao: Facebook’s distributed data store for
the social graph. In USENIX Annual Technical
Conference (2013), pp. 49–60.

[20] M ALEWICZ , G., AUSTERN , M. H., B IK , A. J.,
D EHNERT, J. C., H ORN , I., L EISER , N., AND
C ZAJKOWSKI , G. Pregel: a system for largescale graph processing. In Proceedings of the 2010
ACM SIGMOD International Conference on Management of data (2010), ACM, pp. 135–146.

[10] B UONO , D., P ETRINI , F., C HECCONI , F., L IU ,
X., Q UE , X., L ONG , C., AND T UAN , T.-C.
13

[21] M C C ALPIN , J. D. Stream benchmark. Link: www.
cs. virginia. edu/stream/ref. html# what 22 (1995).

[32] S IEK , J. G., L EE , L.-Q., AND L UMSDAINE , A.
The Boost Graph Library: User Guide and Reference Manual, Portable Documents. Pearson Education, 2001.

[22] M C S HERRY, F., I SARD , M., AND M URRAY, D. G.
Scalability! but at what cost? In Proceedings of the
15th USENIX Conference on Hot Topics in Operating Systems (2015), HOTOS’15, USENIX Association, pp. 14–14.

[33] S UNDARAM , N., S ATISH , N., PATWARY, M.
M. A., D ULLOOR , S. R., A NDERSON , M. J.,
VADLAMUDI , S. G., DAS , D., AND D UBEY, P.
Graphmat: High performance graph analytics made
productive. Proceedings of the VLDB Endowment
8, 11 (2015), 1214–1225.

[23] M EUSEL , R., V IGNA , S., L EHMBERG , O., AND
B IZER , C. The graph structure in the web: Analyzed on different aggregation levels. The Journal
of Web Science 1, 1 (2015), 33–47.

[34] WANG , Y., DAVIDSON , A., PAN , Y., W U , Y.,
R IFFEL , A., AND OWENS , J. D. Gunrock: A highperformance graph processing library on the gpu.
In ACM SIGPLAN Notices (2016), vol. 51, ACM,
p. 11.

[24] M URPHY, R. C., W HEELER , K. B., BARRETT,
B. W., AND A NG , J. A. Introducing the graph 500.
Cray Users Group (CUG) 19 (2010), 45–74.
[25] N EWMAN , M. E., WATTS , D. J., AND S TRO GATZ , S. H. Random graph models of social networks. Proceedings of the National Academy of
Sciences 99, suppl 1 (2002), 2566–2572.

[35] W EI , H., Y U , J. X., L U , C., AND L IN , X.
Speedup graph processing by graph ordering. In
Proceedings of the 2016 International Conference
on Management of Data (2016), ACM, pp. 1813–
1828.

[26] N GUYEN , D., L ENHARTH , A., AND P INGALI ,
K. A lightweight infrastructure for graph analytics.
In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (2013),
ACM, pp. 456–471.

[36] W ILLHALM , T., D EMENTIEV, R., AND FAY,
P. Intel performance counter monitor-a better
way to measure cpu utilization. 2012. URL:
http://software.intel.com/en-us/articles/intelperformance-counter-monitor-a-better-way-tomeasure-cpuutilization (2016).

[27] N ISHTALA , R., V UDUC , R. W., D EMMEL , J. W.,
AND Y ELICK , K. A. When cache blocking of
sparse matrix vector multiply works and why. Applicable Algebra in Engineering, Communication
and Computing 18, 3 (2007), 297–311.

[37] W ILLIAMS , S., O LIKER , L., V UDUC , R., S HALF,
J., Y ELICK , K., AND D EMMEL , J. Optimization
of sparse matrix–vector multiplication on emerging multicore platforms. Parallel Computing 35,
3 (2009), 178–194.

[28] P ENNER , M., AND P RASANNA , V. K. Cachefriendly implementations of transitive closure.
Journal of Experimental Algorithmics (JEA) 11
(2007), 1–3.

[38] W ULF, W. A., AND M C K EE , S. A. Hitting
the memory wall: implications of the obvious.
ACM SIGARCH computer architecture news 23, 1
(1995), 20–24.

[29] P RABHAKARAN , V., W U , M., W ENG , X., M C S HERRY, F., Z HOU , L., AND H ARADASAN , M.
Managing large graphs on multi-cores with graph
awareness. 41–52.

[39] Z HOU , S., C HELMIS , C., AND P RASANNA , V. K.
Optimizing memory performance for fpga implementation of pagerank. In ReConFigurable Computing and FPGAs (ReConFig), 2015 International
Conference on (2015), IEEE, pp. 1–6.

[30] ROY, A., M IHAILOVIC , I., AND Z WAENEPOEL ,
W. X-stream: Edge-centric graph processing using streaming partitions. In Proceedings of the
Twenty-Fourth ACM Symposium on Operating Systems Principles (2013), ACM, pp. 472–488.

[40] Z HOU , S., L AKHOTIA , K., S INGAPURA , S. G.,
Z ENG , H., K ANNAN , R., P RASANNA , V. K.,
F OX , J., K IM , E., G REEN , O., AND BADER ,
D. A. Design and implementation of parallel
pagerank on multicore platforms. In High Performance Extreme Computing Conference (HPEC),
2017 IEEE (2017), IEEE, pp. 1–6.

[31] S HUN , J., AND B LELLOCH , G. E. Ligra: a
lightweight graph processing framework for shared
memory. In ACM Sigplan Notices (2013), vol. 48,
ACM, pp. 135–146.
14

[41] Z HU , X., H AN , W., AND C HEN , W. Gridgraph:
Large-scale graph processing on a single machine
using 2-level hierarchical partitioning. In 2015
USENIX Annual Technical Conference (USENIX
ATC 15) (2015), USENIX Association, pp. 375–
386.

15

