Advanced Parallel Algorithms

Lecture and Exercises (LSF)

  • Prof. Dr. Robert Strzodka
  • Thursday, 14:15 - 16:00, 16:15 - 18:00
  • 4 SWS and 6 ECTS
  • Heidelberg, INF 350 / OMZ R U012
  • Start 18.10.2018


The lectures Parallel Algorithm Design and Advanced Parallel Algorithms can be attended in the same semester in parallel. Parallel Algorithm Design has fewer prerequisits and looks at more topics in breadth, while Advanced Parallel Algorithms requires familiarity with CUDA programming and looks at fewer topics in depth.


  • Most recent developments in GPUs
  • On-the-fly data transformations
  • Data locality optimizations
  • Hierarchical algorithms
  • SIMD utilization
  • Precision, accuracy and numerical schemes
  • Numerical efficiency vs. parallel efficiency
  • Data representation


The lecture is partly based on the book Programming Massively Parallel Processors by David B. Kirk and Wen-mei W. Hwu. Both the 2nd edition from 2013 and the 3rd edition from 2017 can be accessed online at the Heidelberg University Library.

We assume the audience are already familiar with CUDA programming and thus with the contents of the first 6 chapters of that book. This knowledge can be obtained in the lecture GPU Computing or from the book itself. We will use the following chapters on Parallel Patterns for the lectures, however, we will dig deeper than in the book. In further lectures, we will also cover more advanced topics with respect to parallelism and numerical computations, often discussing parallelization strategies in view of seemingly sequential dependencies.

The lecture presents the most up-to-date developments in parallel computing on GPUs and is the starting ground for research and thesis work in this area. While GPUs will be the device of choice for implementations and exercises, most of the algorithmic reasoning applies also to other many-core processors like the Xeon Phi.

In the first weeks there will be regular exercises and mid-term each group will choose a larger scientific project. The results will be presented by the students in the last lecture. For the exercises and the projects we will provide access to high performance GPUs with the newest functionality.