STIC-D based Algorithmic Optimizations for Monolithic PageRank : REPORT

report-sticd-based-algorithmic-optimizations-for-monolithic-pagerank.md

STIC-D based Algorithmic Optimizations for Monolithic PageRank

While doing research work with Prof. Kishore Kothapalli, and Prof. Dip Sankar Banerjee.

Abstract — The performance benefits of five different algorithmic optimizations for PageRank were studied here. The first two include splitting vertices by components, and sorting components by topological order in block-graph. The remaining three optimizations include skipping computation on in-identical, chain, and converged vertices. This was done on both a CPU, as well as a GPU. Results indicated that splitting vertices by components provided a small performance improvement on average on both the devices. However, sorting components provided little additional benefit. The other three optimizations were beneficial only on certain graphs, but were detrimental on others due to their associated cost. Therefore, skip in-identical and chain optimizations should be applied only on graphs with a large number of in-identical and chain vertices respectively. In contrast, as the applicability of skip converged optimization cannot be predicted beforehand, it can be ignored. Moreover, in all cases the impact on performance was lower for GPU, compared to CPU. This is possibly because of the warp divergence introduced by the three skip optimizations due to irregular skipping of rank computation of vertices. (🎞️ slides)

Index terms — PageRank algorithm, STIC-D based algorithmic optimizations, Split components, Sort components, Skip in-identicals, Skip chains, Skip converged.

Experiments

CPU	GPU
Split components	Split componnets
Skip in-identicals	Skip in-identicals
Skip chains	Skip chains
Skip converged	Skip converged

1. Performance benefit of PageRank with vertices split by components.
2. Performance benefit of skipping in-identical vertices for PageRank.
3. Performance benefit of skipping chain vertices for PageRank.
4. Performance benefit of skipping converged vertices for PageRank.
5. Performance benefit of CUDA based PageRank with vertices split by components
6. Performance benefit of skipping in-identical vertices for CUDA based PageRank
7. Performance benefit of skipping chain vertices for CUDA based PageRank
8. Performance benefit of skipping converged vertices for CUDA based PageRank

report-sticd-based-algorithmic-optimizations-for-monolithic-pagerank.pdf

slides-sticd-based-algorithmic-optimizations-for-monolithic-pagerank.pdf