Parallel Page Rank

Team Members

Aditya Bhawkar, Swarali Patil

Checkpoint

Click for our checkpoint report

checkpoint

Final

Click for our final report

href="https://github.com/adb1997/pcaproject/blob/main/15618%20Final%20Project%20-%20Parallel%20PageRank.pdf">final

Link for github repository

href="https://github.com/Swarali20/PCA-Final-Project"

Summary

We aim to implement the page rank algorithm using the graph data structure in parallel with the help of concepts taught in class like data parallel, shared memory and message passing models, specifically MPI. The performance will be compared against existing serial implementations.

Background

The PageRank algorithm was developed by Google in 1999 which provides an insight into how the internet can be thought of as a graph. The algorithm envisages the internet as a directed graph with unweighted edges. Each node of the graph represents a webpage and links between two webpages are denoted by a link. Each node receives a score based on its ‘importance’. Pages with high-quality content should receive higher scores than pages with low-quality content. With the ever growing size of the internet, the number of pages is growing at an exponential rate. Such an application will greatly benefit from parallel processing

Challenge

Google themselves have moved way beyond PageRank and use very powerful hardware. However, this project will be a good opportunity to utilize various data parallel techniques learned in this class.

When we do partitioning for data parallelism, we need to distribute data evenly to the tasks in order to maximize the performance of the parallel execution. A significant challenge would be in figuring out how to partition the data well, as there are several techniques to partition a graph in the page rank algorithm. There are usually many more edges compared to vertices.

Depending on the workload, the majority of the time is spent in accessing the neighbours of the vertices of the graph which can be anywhere in memory. This leads to poor spatial locality of data accesses. So we will have to figure out a way to efficiently access memory such that we have better cache locality.

Resources

GHC machines to develop and implement the code PSC machines for testing message passing version

Goals and Deliverables

Plan to achieve

The initial plan is to develop the algorithm and test it for sequential correctness using the GHC cluster. Once that is achieved, we aim to parallelize PageRank using MPI, and eventually scale the speedup using the PSC machines.

Hope to achieve

We do hope to achieve a significant improvement in terms of computation time which improves as we add more cores. It would be hard to reasonably quantify the speedup so soon in the project but we do hope to update that eventually as we progress. Current simple implementations in research show at least 10x-20x speedup which we would hope to hit. At the poster presentation, if all goes well, we would like to have a demo that would showcase our comparative analysis through speedup graphs.

Through this project we intend to achieve a deeper understanding of graph algorithms through one of their most popular implementations in industry as well as academia in that of PageRank. This would allow us to apply several skills that we have learned in theory as well as through assignments. Additionally, the project would also give us a greater grasp on memory hierarchies in computer architecture, along with their application in parallel systems.

Extra goal : Time permitting, we compare our implementation against a standard parallel graph computation library called Boost which will be run on CPU.

Timeline

Week 1 (11/2 - 11/7)	(Project proposal due) Research on ideas to parallelise algorithm
Week 2 (11/8 - 11/14)	Baseline implementation of PageRank, profile code to figure out bottlenecks
Week 3 (11/15 - 11/21)	Implement parallelized version of baseline code
Week 4 (11/22 - 11/28)	(Milestone Report due) Implement message passing version
Week 5 (11/29 - 12/5)	Explore GPU implementation, Collect readings and compare with standard parallel graph computation libraries
Week 6 (12/6 - 12/10)	Final report & demo