Parallel Algorithm Design

Lecture and Exercises (LSF, Moodle)

  • Prof. Dr. Robert Strzodka
  • Thursday, 14:15 - 16:00, 16:15 - 18:00
  • 4 SWS and 6 ECTS
  • INF 350 / OMZ R U014
  • Start 2022-11-03


  • Multiple levels of parallelism
  • Parallel data access
  • Communication vs. computation
  • Latency vs. throughput
  • Work efficiency vs. step efficiency
  • Locality vs. parallelism
  • Parallel design patterns


The lecture and exercises are based on the book Structured Parallel Programming by Michael McCool, Arch Robison and James Reinders. The book can be purchased from many retailers as ebook or on paper. The book is also available online at the Heidelberg University Library (direct link to book). Specifically for TBB a highly related open-access book is ProTBB by Michael Voss, Rafael Asenjo and James Reinders. We will discuss SIMD in more detail than in these two books but also on a high level, as reference for SIMD details there is the book "Modern parallel programming with C++ and Assembly language" by Daniel Kusswurm (direct link to book)


The lecture covers fundamental patterns of parallel algorithms, which every programmer should know. It may be attended by beginners in parallel algorithms and parallel programming to gain a thorough overview of parallel patterns. For full participation in the exercises some experience with multi-threaded programming is recommended. As all book examples are based on C++ the participants should have a working knowledge of this programming language.


Each week there will be a reading assignment, in this way we will study the first part of the book (chapters 1-9) and the appendix. The lectures will not be used for presenting the chapters but rather discussing them. 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 CPUs supporting parallel execution with many threads. The second part of the book (chapters 10-15) contains different examples and is a good reference when working on a project with a related computing strategy.



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


There is no advance registration, simply attend the first lecture.