Comparision of OpenMP and CUDA-based, Monolithic and Levelwise Dynamic PageRank algorithms.

With CUDA implementation on Fixed graphs

This experiment (cuda-on-fixed) was for comparing performance between:

1. Find static pagerank of updated graph using nvGraph.
2. Find dynamic pagerank of updated graph using nvGraph.
3. Find static monolithic CUDA based pagerank of updated graph.
4. Find dynamic monolithic CUDA based pagerank of updated graph.
5. Find static levelwise CUDA based pagerank of updated graph.
6. Find dynamic levelwise CUDA based pagerank of updated graph.

Each approach was attempted on a number of graphs, running each with multiple batch sizes (1, 5, 10, 50, ...). Each batch size was run with 5 different updates to graph, and each specific update was run 5 times for each approach to get a good time measure. Levelwise pagerank is the [STIC-D algorithm], without ICD optimizations. Indeed, dynamic levelwise pagerank is faster than the static approach for many batch sizes. In order to measure error, nvGraph pagerank is taken as a reference.

Comparing with Monolithic approach

This experiment (compare-monolithic) was for comparing performance between:

1. Find dynamic pagerank of updated graph using Monolithic PageRank.
2. Find dynamic pagerank of updated graph using Levelwise PageRank.
3. Find dynamic pagerank of updated graph using pure CPU/GPU HyPR.
4. Find static pagerank of updated graph using plain STIC-D PageRank (CPU only).
5. Find incremental pagerank of updated using nvGraph PageRank (GPU only).

• Affected vertices are grouped together by SCC. report
• Small SCCs are combined together. report
• Details of CUDA implementation. report
• L2-norm converges slower that L∞-norm. report

This study was carried out to extend the Levelwise strategy of PageRank computation in the STIC-D paper to perform dynamic PageRank on the CPU as well as the GPU. This levelwise computation of PageRank is computationally more efficient because it processes SCCs in topological order, avoiding unnecessary recomputation of SCCs that are dependent upon ranks of vertices in other SCCs which have not yet converged. We have compared it to our monolithic CPU/GPU implementations, along with other state-of-the art implementations, such as nvGraph and HyPR in batch sizes of 500, 1000, 2000, 5000, and 10000 edges. We also contrasted the performance of a batched update to a series of single edge updates (cumulative).

Results indicate that Levelwise approach is in general faster than Monolithic PageRank on the CPU, and the opposite is true on the GPU. This likely has to do with the fact that processing a large number of small levels is inefficient. Hence with Levelwise PageRank, smaller levels/components should be combined and processed at a time in order to help improve GPU usage efficiency.

Other experiments

• approach-combine-levels
• adjust-batch-size
• kitchen-sink

References

• STIC-D: algorithmic techniques for efficient parallel pagerank computation on real-world graphs
• PageRank Algorithm, Mining massive Datasets (CS246), Stanford University
• SuiteSparse Matrix Collection