Performance modeling of PageRank in large-scale systems

Performance modeling of PageRank in large-scale systems: A case study

Doekemeijer, Niels (TU Delft Electrical Engineering, Mathematics and Computer Science)

Varbanescu, A. L. (mentor)
Sips, H.J. (graduation committee)
Pawełczak, Przemysław (graduation committee)
Hidders, J. (graduation committee)

Delft University of Technology

Computer Science

2020-08-26

Graphs are a ubiquitous concept used for modeling entities and their relationships. Large graphs, present in a variety of domains, are often fundamentally difficult to process because of sheer size and irregular computation structure. In recent years, both academia and industry have committed to designing scalable solutions to efficiently process these graphs.

Next to processing large datasets in a distributed environment, a relatively new trend is to accelerate single node computation performance using heterogeneous platforms (for example, by leveraging the GPU as well as the CPU). However, the structure of the input graph can markedly influence the processing speed on a certain platform and it is unclear what would be the most efficient platform for execution given an input dataset.

In this thesis, we will analyze the performance of multiple PageRank implementations for diverse platforms. Using implementations for CPU (using OMP), GPU (using OpenCL and CUDA), and heterogeneous environments (using StarPU and MPI), we will characterize platform performance in relation to the structure of the input dataset. Finally, we will propose and evaluate a performance model for PageRank that takes into account traits of the input graph.

Graph Analysis
Performance Analysis
Heterogeneous Computing
Benchmark
Pagerank

http://resolver.tudelft.nl/uuid:19b8ab1c-82d2-48d0-98de-21cc72dc58d9

Student theses

master thesis

© 2020 Niels Doekemeijer