Assignment 4
CS525: Parallel Computing
Due Dec 12, 2014.

• You are required to write a parallel PageRank program in MPI. Web graphs of various sizes are available from the Stanford Network Repository.
  
  Your program must take one of these files as input. For the purposes of this assignment, one processor reads the file and communicates equal number of nodes to all other processes. The processes initialize their pagerank values to the identity vector (normalized) and compute page rank through iterative multiplication with the matrix (power iterations). The process continues until the pageranks do not change significantly (the two-norm of the pagerank vector changes by less than 10^{-5}, say.
  
  The key challenge in this assignment is to write a highly optimized matrix-vector product. As indicated in the class, you do not want to broadcast the entire intermediate pagerank vector to all processors. This is unlikely to give you good performance on larger number of processors. For this reason, you only want to communicate the necessary elements of the vector to processors that need them.
  
  To get started on the mc cluster, here are some instructions.
  
  
  
  Grading: Your solutions will be graded by running the program on the test inputs. You will be graded on two counts -- first, your serial runtime should not be very high (i.e., you must have a meaningfully efficient serial sparse matrix-vector product). Second, you should get reasonable parallel speedup. The grading scale is as follows: 30% points for programs that execute correctly. 70% of the points for performance. All programs will be run on the mc (mc01-18) cluster in the department (this is the cluster you should use to benchmark your programs as well) on up to 16 cores. If you get a speedup of more than 12, you will get all 70%. If you get a speedup of between 8 and 12, you get 50%, 4 and 8, you get 30%, 1 - 4, you get 15%. No points for speedup of under 1 (!). These speedups are for the largest problem instance in the Stanford web respository that your program can execute on.
  
  
• Repeat the previous problem using pthreads.
  
  Grading: Your solutions will be graded by running the program on the test inputs. You will be graded on two counts -- first, your serial runtime should not be very high (i.e., you must have a meaningfully efficient serial implementation). Second, you should get reasonable parallel speedup. The grading scale is as follows: 30% points for programs that execute correctly. 70% of the points for performance. All programs will be run on the mc machines in the Department (this is the cluster you should use to benchmark your programs as well) on up to 16 cores. If you get a speedup of more than 12, you will get all 70%. If you get a speedup of between 8 and 12, you get 50%, 4 and 8, you get 30%, 1 - 4, you get 15%. No points for speedup of under 1 (!). These speedups are for the largest problem instance in the Stanford web respository that your program can execute on.