Leveraging Novel Hardware to Accelerate Combinatorial Algorithms
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.
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.
- Be able to program parallel C++ on the IPU.
- Formulate algorithms in a Bulk Synchronous Parallel model.
- Understand and evaluate algorithmic performance tradeoffs.
- C/C++ or Golang
- Understanding of parallel algorithms
- Knowledge of assembly is a plus
- Luk Burchard
- Johannes Langguth
- Xing Cai