Parallel Algorithm Design

Note

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.

Contents

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

Description

The lecture and exercises are based on the book Structured Parallel Programming by Michael McCool, Arch Robison, 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.

 

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 knowlege 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. 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.