Implementing Fast Parallel Graph Algorithms

Almost all of today's computers, from smart phones to supercomputers, use multiple cores and thus parallel processing. This thesis looks at implementing challenging fundamental problems on today’s parallel computers.
Master

Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to applications in many fields such as bioinformatics, computer networks, or social media analysis. However, most of these algorithms are designed for single core processors.

Today, almost all computers are parallel, having multiple cores, multiple processors, or additional accelerators such as GPUs. Some problems can easily be solved in parallel, but graph algorithms such as breadth-first-searches, shortest paths, or matchings are difficult to implement in parallel and constitute a challenge to the world’s most powerful computers, as evidenced by the Graph500 benchmark (graph500.org/).

This thesis aims at tackling this challenge, using parallel computers present at SIMULA. Sequential codes will be provided. Depending on the interest of the candidate, there is some flexibility in which algorithms will be implemented. The work will run in parallel with master projects at the algorithms group from the University of Bergen.

Goal

The aim of the thesis is to implement new graph algorithms on parallel computers, including GPUs using MPI, OpenMP, or CUDA. The ultimate goal is to compete in performance and scalability with the best available implementations.

Learning outcome

During the course of this master thesis, the candidate will learn more about graph algorithms and parallel programming of multicore CPUs, supercomputers and GPUs.

Qualifications

This topic requires solid knowledge of algorithms and C/C++. Familiarity with parallel programming using MPI, OpenMP, or CUDA is helpful but not required.

Supervisors

  • Johannes Langguth
  • Fredrik Manne, UiB

Collaboration partners

University of Bergen (UiB)