  PageRank is a graph centrality metric that gives the importance of each node
in a given graph. The PageRank algorithm provides important insights to
understand the behavior of nodes through the connections they form with other
nodes. It is an iterative algorithm that ranks the nodes in each iteration
until all the node values converge. The PageRank algorithm is implemented using
sparse storage format, which results in irregular memory accesses in the code.
This key feature inhibits optimizations to improve its performance, and makes
optimizing the PageRank algorithm a non-trivial problem. In this work we
improve the performance of PageRank algorithm by reducing its irregular memory
accesses. In this paper, we propose FUSED-PAGERANK algorithm, a compiler
optimization oriented approximate technique that reduces the number of
irregular memory accesses in the PageRank algorithm, improving its locality
while making the convergence of the algorithm faster with better accuracy in
results. In particular, we propose an approximate PageRank algorithm using
Loop-Fusion. We believe that ours is the first work that formally applies
traditional compiler optimization techniques for irregular memory access in the
PageRank algorithm. We have verified our method by performing experiments on a
variety of datasets: LAW graphs, SNAP datasets and synthesized datasets. On
these benchmarks, we have achieved a maximum speedup (vs. -O3 optimization) of
2.05X, 2.23X, 1.74X with sequential version, and ~4.4X, ~2.61X, ~4.22X with
parallel version of FUSED-PAGERANK algorithm in comparison with Edge-centric
version of PageRank algorithm.
