Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save wolfram77/12e5a19ff081b2e3280d04331a9976ca to your computer and use it in GitHub Desktop.
Save wolfram77/12e5a19ff081b2e3280d04331a9976ca to your computer and use it in GitHub Desktop.
STIC-D based Algorithmic Optimizations for Monolithic PageRank : REPORT

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
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment