Assignment 3

Implement parallel PageRank in CUDA. PageRank of a node pi in a graph is given by the following formula.

Here p1, p2, ..., pN are the nodes, M(pi) is the set of nodes that link to pi, L(pj) is the outdegree of node pj, and N is the total number of nodes in the graph. d = 0.85 and initialization of PR(pi) = 1/N.
PR(pj) should be the old value of pagerank of node pj. Number of iterations of your pagerank implementation must be exactly 10 (i.e., the pagerank kernel should get invoked 10 times).

Follow these steps.

  1. Download lonestargpu benchmark suite(cd; bunzip2 lonestargpu-2.0.tar.bz2; tar xf lonestargpu-2.0.tar), compile SSSP (cd lonestargpu-2.0/apps/sssp/; make) and execute sssp in it (../../bin/sssp /home/workspace/inputs/lonestargpu/rmat20.gr).
  2. Input files (extension .gr) are available in rngpu:/home/workspace/inputs/lonestargpu/.
  3. Create a parallel directory pagerank using SSSP (cp -r sssp pagerank) and modify the code to perform PageRank computation. You can use the graph library supported by lonestargpu. Pagerank value must be of type float. Compiling your code must result in binary file pagerank in bin/ directory of lonestargpu.
  4. Input to your program would be a single argument mentioning path to the input graph in .gr format as supported by lonestargpu.
  5. Output of your pagerank program should be N lines (N is the number of graph nodes) where ith line contains the pagerank value computed for the ith node. Print each pagerank value with six decimal digits.
The directory structure should be ~/lonestargpu-2.0/apps/pagerank/main.cu
Output for rmat20, output for USA-road-d.FLA