PageRank is a fundamental link analysis algorithm and a key representative of the performance of other graph algorithms and Sparse Matrix Vector (SpMV) multiplication. Calculating PageRank on sparse graphs generates large amount of random memory accesses resulting in low cache line utilization and poor use of memory bandwidth . In this paper, we present a novel Partition-Centric Processing Methodology (PCPM)  that drastically reduces the amount of communication with DRAM and achieves high memory bandwidth. Similar to the state of the art Binning with Vertex-centric Gather-Apply-Scatter ( BVGAS) method, PCPM performs partition wise scatter and gather of updates with both phases enjoying full cache line utilization. However, BVGAS suffers from random memory accesses and redundant read/write of update values from nodes to their neighbors. In contrast, PCPM propagates single update from source node to all destinations in a partition, thus decreasing redundancy effectively. We make use of this characteristic to develop a novel bipartite Partition-Node Graph (PNG) data layout for PCPM, that enables streaming memory accesses, with very little generation overhead . We perform detailed analysis of PCPM and provide theoretical bounds on the amount of communication and random DRAM accesses. We experimentally evaluate our approach using 6 large graph datasets and demonstrate an average 2.7x speedup in execution time and 1.7x reduction in communication  , compared to the state of the art . We also show that unlike the BVGAS implementation , PCPM is able to take advantage of intelligent node labeling that enhances locality in graphs, by further reducing the amount of communication with DRAM . Although we use PageRank as the target application in this paper, our approach can be applied to generic SpMV computation.
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.7x speedup in execution time and 1.7x 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.
R
and
that also functions as
R
other graph algorithms and Sparse Matrix Vector
Sparse Matrix-Vector
R
Calculating PageRank on sparse graphs generates large amount of
The traditional PageRank implementation generates fine granularity
R
low cache line utilization and poor use of memory bandwidth
large amount of wasteful DRAM traffic and poor bandwidth utilization
A
to compute PageRank,
R
communication with DRAM and achieves high
DRAM communication while achieving high sustained
R
Similar to the state of the art Binning with Vertex-centric
PCPM uses a Partition-centric abstraction coupled with the
R
BVGAS) method, PCPM performs partition wise scatter and gather of updates with both phases enjoying full cache line utilization. However, BVGAS suffers from random memory accesses and redundant read/write of update values from nodes to their neighbors. In contrast, PCPM propagates single update from source node to all destinations in a partition, thus decreasing redundancy effectively. We make use of this characteristic to develop a novel bipartite Partition-Node Graph (PNG) data layout for PCPM, that enables streaming memory accesses, with very little generation overhead
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
R
analysis of PCPM and provide theoretical bounds on the amount of communication and random DRAM accesses. We experimentally evaluate
analytical and experimental evaluation of
R
graph datasets
graphs
A
volume
R
state of the art
state-of-the-art
R
the BVGAS implementation
other GAS based implementations
R
take
further reduce main memory traffic by taking
D
in graphs, by further reducing the amount of communication with DRAM