Leveraging Novel Hardware to Accelerate Combinatorial Algorithms

The Graphcore IPU is a novel AI processor that is radically different from traditional CPUs and GPUs. It offers very high memory performance, but using it requires a redesign of existing algorithms, which is topic of this thesis.
Master

Nowadays, GPUs are not the only available accelerators at a developer's disposal. Hardware accelerators for AI/ML problems have entered the market and they offer exciting new possibilities. We want to repurpose these novel hardware architectures to solve general-purpose algorithms which until now only run on CPUs. This thesis focuses on widely used backtracking algorithms. Implementing backtracking will lead to fast core routines for knapsack and other combinatorial optimization problems.

Goal

The goal is to implement a backtracking algorithm for Graphcore's IPU hardware. This requires finding ways to distribute work and schedule communication for an efficient implementation.

Learning outcome

  • Be able to program parallel C++ on the IPU.
  • Formulate algorithms in a Bulk Synchronous Parallel model.
  • Understand and evaluate algorithmic performance tradeoffs.

Qualifications

  • C/C++ or Golang
  • Understanding of parallel algorithms
  • Knowledge of assembly is a plus

Supervisors

  • Luk Burchard
  • Johannes Langguth
  • Xing Cai

Contact person