An Introduction to Parallel Programming

Citation

Pacheco, P. S., & Malensek, M. (2021). An Introduction to Parallel Programming (2nd ed.). Morgan Kaufmann (Elsevier).

Chapter Summary

The second edition, about 496 pages, has eight chapters. Three programming interfaces from the first edition (MPI for distributed memory, Pthreads and OpenMP for shared memory) are joined by a new chapter on GPU programming with CUDA. The authors describe the book as an elementary introduction for students and professionals who can program a conventional single-processor system but have little or no experience with multiprocessor systems. The publisher stresses a tutorial approach that starts from small programs and builds towards harder examples, with exercises that ask students to compile, run and modify the example programs. The authors' downloadable source code comes with an index that ties every program to the section that discusses it, and it shows how each chapter is organised around a few problems that recur across the book.

Chapter 1: Why Parallel Computing

The opening chapter sets out, as its title says, why parallel computing is needed, before the book turns to hardware, software and the individual programming interfaces.

Chapter 2: Parallel Hardware and Parallel Software

Background on parallel hardware and software. The errata shows that the hardware material includes cache coherence (Section 2.3.5), and adds the authors' note that snooping coherence is now rarely used because busses do not scale. The code index places a serial histogram program in Section 2.7.1, the chapter's example for developing a parallel program.

Chapter 3: Distributed Memory Programming with MPI

Starts from a program that prints a greeting from every process, then parallelises the trapezoidal rule in several versions, moving from point-to-point messages to collective operations such as reduction and broadcast. Later sections cover distributing vectors with scatter and gather, matrix-vector multiplication, derived datatypes, timing and evaluating performance, and a parallel odd-even transposition sort.

Chapter 4: Shared-Memory Programming with Pthreads

Introduces threads with a greeting program and matrix-vector multiplication, then uses an estimate of pi to expose race conditions and compare ways of protecting a critical section: busy-waiting, mutexes and semaphores. Further topics are barriers built three ways, read-write locks applied to a shared linked list, and thread safety, shown by tokenising text with a library function that is not thread-safe.

Chapter 5: Shared-Memory Programming with OpenMP

Revisits the trapezoidal rule with critical sections, reduction clauses and parallel for loops; shows a loop that cannot be parallelised naively (the Fibonacci numbers); and covers variable scope, odd-even sort, loop scheduling, message passing among threads with critical, atomic and lock constructs, matrix-vector multiplication, OpenMP tasks and thread safety.

Chapter 6: GPU Programming with CUDA

New in this edition. Begins with a kernel launched as a block of threads, then vector addition, returning results from the device, and three increasingly refined CUDA versions of the trapezoidal rule (the errata places warp shuffle functions in Section 6.11), ending with bitonic sort implemented first within one thread block and then across several.

Chapter 7: Parallel Program Development

Two larger case studies, each solved in every interface of the book. An n-body solver, in a basic and a reduced version, is parallelised with OpenMP, Pthreads, MPI and CUDA; sample sort is then developed serially and with OpenMP, Pthreads, MPI and CUDA, the MPI versions using different communication patterns.

Chapter 8: Where to Go from Here

The final chapter points to further study, as its title indicates.

Key Concepts

Chapters 1–2: Foundations

• Shared and distributed memory: the two broad classes of parallel systems, which determine whether processes communicate through memory or messages.
• Cache coherence: keeping copies of shared data consistent across the caches of different cores.
• Parallel software: programs written to run as several cooperating processes or threads.

Chapter 3: MPI

• Point-to-point and collective communication: sending messages between pairs of processes, or among all processes at once (reduce, broadcast, scatter, gather).
• Data distribution: splitting vectors and matrices among processes in blocks.
• Derived datatypes: describing non-contiguous data so that it can be sent in one message.
• Performance evaluation: timing parallel programs and judging how well they scale, the subject of Section 3.6.

Chapters 4–5: Pthreads and OpenMP

• Race condition and critical section: errors that arise when threads update shared data at the same time, and the code regions that must be protected.
• Mutexes, semaphores, barriers, condition variables and read-write locks: the synchronisation tools of Pthreads.
• Directives and clauses: OpenMP's way of parallelising loops and regions, including reductions and scheduling.
• Thread safety: whether a function behaves correctly when called by several threads at once.

Chapters 6–7: GPUs and Larger Programs

• Kernels, threads and blocks: the CUDA model of running many lightweight threads organised into blocks on a GPU.
• Warp-level operations: functions such as warp shuffles that let threads in a warp exchange values efficiently.
• N-body simulation and sample sort: the case studies used to compare all four interfaces on realistic problems.

Critical Analysis

Strengths

• The same problems across every interface. The trapezoidal rule appears in MPI, OpenMP and CUDA; matrix-vector multiplication and odd-even transposition sort recur; and Chapter 7 solves the n-body problem and sample sort in all four interfaces. Students can compare the programming models directly rather than learning each against unrelated examples.
• Learning from broken programs. The code index shows a deliberate pattern of showing a buggy or naive version first (a race-prone estimate of pi, an incorrect Fibonacci loop, text tokenising that is not thread-safe) and then repairing it, which teaches why the synchronisation tools exist.
• Practical and runnable. The authors provide all source code, keep an errata list on their website, and the publisher lists lecture slides, a solutions manual and an image bank for instructors. Exercises ask students to compile, run and modify the programs.
• Up to date with GPUs. The new CUDA chapter and the CUDA versions in Chapter 7 bring accelerators into a text that previously covered only CPUs and clusters.

Limitations

• C-centred and API-centred. All programs are in C, and the book teaches four specific interfaces. It does not treat higher-level frameworks or the theory of parallel algorithms beyond what the examples need.
• GPU coverage is CUDA only. Readers working with other accelerators or portable GPU frameworks will need other sources. The publisher also mentions heterogeneous programming, but the table of contents has no separate chapter on it, so readers should not expect extended coverage of that topic.
• Not a distributed-systems text. The book is about making one computation run faster on many processors; fault tolerance, consistency and replication, central to the rest of this course, are outside its scope.
• Some hardware material dates quickly. The authors' own errata notes that the snooping-coherence description in Chapter 2 reflects a technique that is now rarely used.

Where It Fits in the Course

In a distributed systems course, this book covers the parallel-computing side: how to write programs that use many cores, many nodes or a GPU to run one computation faster. The other books address a different question, how to build services that keep working across unreliable machines and networks. Roberto Vitillo's Understanding Distributed Systems is a concise introduction for developers to communication, coordination, scaling and resilience in networked services; Coulouris and colleagues' Distributed Systems: Concepts and Design and van Steen and Tanenbaum's Distributed Systems are the principles-first textbooks on architectures, naming, coordination, consistency, replication and fault tolerance.

Kleppmann and Riccomini's Designing Data-Intensive Applications addresses replication, partitioning and stream processing for production data systems, and Cachin, Guerraoui and Rodrigues's Introduction to Reliable and Secure Distributed Programming is a graduate text on fault-tolerant abstractions and consensus. Pacheco and Malensek's Chapter 3 on MPI is the closest bridge: message passing between processes is the common ground, but here the aim is speed, not tolerance of failure. Read this book when the course includes parallel programming, or as the practical complement to the distributed-systems texts.

How to Use This Book

The book suits undergraduates in a first parallel or high-performance computing course, science and engineering students who need to speed up their own codes, and programmers with no parallel experience. Readers should be comfortable programming in C, including pointers and arrays, since all examples are in C.

• Core: Chapters 1–2 for vocabulary and design method, then at least one interface in depth. Many courses take Chapter 3 (MPI) and Chapter 5 (OpenMP); Chapter 4 (Pthreads) gives the clearest view of synchronisation at a low level.
• GPU option: Chapter 6, which can follow Chapter 2 directly if a course concentrates on GPUs.
• Synthesis: Chapter 7, read after the interfaces you studied; follow the n-body and sample-sort solutions in those interfaces and compare their performance.
• Close: Chapter 8 for directions to further study.

Download the source code from the authors' site and run every example as you read, timing it with different numbers of processes or threads; this is where performance evaluation becomes concrete. Check the errata list before relying on the GPU code listings. If possible, use a real multicore machine and a small cluster or a GPU, since performance behaviour cannot be learned from a single core.