  These lecture notes are designed to accompany an imaginary, virtual,
undergraduate, one or two semester course on fundamentals of Parallel Computing
as well as to serve as background and reference for graduate courses on
High-Performance Computing, parallel algorithms and shared-memory
multiprocessor programming. They introduce theoretical concepts and tools for
expressing, analyzing and judging parallel algorithms and, in detail, cover the
two most widely used concrete frameworks OpenMP and MPI as well as the
threading interface pthreads for writing parallel programs for either shared or
distributed memory parallel computers with emphasis on general concepts and
principles. Code examples are given in a C-like style and many are actual,
correct C code. The lecture notes deliberately do not cover GPU architectures
and GPU programming, but the general concerns, guidelines and principles (time,
work, cost, efficiency, scalability, memory structure and bandwidth) will be
just as relevant for efficiently utilizing various GPU architectures. Likewise,
the lecture notes focus on deterministic algorithms only and do not use
randomization. The student of this material will find it instructive to take
the time to understand concepts and algorithms visually. The exercises can be
used for self-study and as inspiration for small implementation projects in
OpenMP and MPI that can and should accompany any serious course on Parallel
Computing. The student will benefit from actually implementing and carefully
benchmarking the suggested algorithms on the parallel computing system that may
or should be made available as part of such a Parallel Computing course. In
class, the exercises can be used as basis for hand-ins and small programming
projects for which sufficient, additional detail and precision should be
provided by the instructor.
