The Art of Multiprocessor Programming

What this book is not: - A programmer's cookbook - A programming manual - A math text This is an engineering theory textbook: enough theory to teach you how to reason about practical problems on the problems' own terms. If it were easy, such books would be unnecessary. Learning to reason about these problems is hard and the books are hard. This book is no exception. That said, it is generally very clear, but it is not light reading or easy study. It demands serious study time. Given the increasing importance of concurrency to real-world performance (and the economics of computing) the investment of time seems likely to be profitable. The book progresses from simple (but still difficult) foundation principles to a variety of established techniques. It is not concerned with other issues of software design and construction but it covers its own purview thoroughly. The exercises are non-trivial and sometimes geniunely hard. Some call for programming, some for thinking. They indicate that the authors have a deep grasp not only of their subject matter but of how to teach it. The examples are in Java. (A note on doing the exercises: due to the inherent limitations of threading on single-processor/single-core/single-thread machines, errors in code may not show up on such machines; if you don't have true multi-thread hardware, beware.)

The Art of Multiprocessor Programming is an outstanding text that will soon become a classic. I give a chapter by chapter review of it below. Practitioners that are already well versed in parallel programming can jump directly to Chapter 7, however, I would suggest at least skimming Chapters 2, 3 and 4. Even those programmers who understand shared memory and locking may be shocked at how relaxed memory models or compiler optimizations can reorder operations causing innocent looking code to break. ---------------------------------------- Chapter 1 - Introduction Why is this book called "The Art of Multiprocessor Programming" and not "The Art of Parallel Programming?" It is not by accident. There is a directed effort to explain parallel programming concepts as they relate to multi-core (or many-core) architectures. In particular, shared-memory multiprocessors have specific implementation details, such as cache coherence policies, that directly affect parallel software run on such architectures. The introduction gives a brief overview of the direction of the text: principles and practice. ---------------------------------------- Part 1 - Principles Chapter 2 - Mutual Exclusion Mutual exclusion is a key concept to multi-threaded programming, and this chapter is rightly placed at the beginning of the text. This chapter presents some of the foundational concepts in parallel computing, such as, understanding time related to operation interleavings, pessimistic critical sections, forward progress, deadlocks and fairness. In addition, some of the classic algorithms are presented here, such as Lamport's Ticket Locking and Peterson's 2-Threaded Lock. Chapter 3 - Concurrent Objects This chapter starts off simple, but gets complex fast. While experts will understand and acknowledge the importance of this chapter, less experienced programmers will find it very challenging to understand and may be turned off: don't give up! My suggestion to non-experts is to focus on understanding two concepts of this chapter: hardware sequential consistency (3.4) and software linearizibility (3.5). Once you understand both concepts, skim all other sections except section 3.8. Java programmers may want to pay special attention to the Java Memory Model section (3.8) and ill-formed unsynchronized code. General programmers will also be interested in this section as it is important to understand how the hardware's memory consistency model, the programming language's memory model and the compiler's operation reordering optimizations may interfere with what "looks like" correct code. Do not be discouraged by the difficult of this chapter. It is one of the most difficult chapter in the text. Get through it and keep reading. Chapter 4 - Foundations of Shared Memory This chapter concentrates on understanding shared memory, the cornerstone of all multi-threaded applications. It explains how to implement shared memory that behaves "correctly" without using mutual exclusion.

This book gives programmers the practical and theoretical tools they need to adapt to the proliferation of multi-core machines. It opens with six chapters on theoretical subjects. These chapters are fascinating in their own right as well as directly applicable to my daily work. I thought the most important subjects were wait-free synchronization (every method completes in a finite number of steps), lock-free synchronization (some method completes in a finite number of steps), and some computability proofs. The authors use computability to demonstrate the equivalence of several types of synchronization primitives. They also present some impossibility proofs that show you how to avoid trying to solve unsolvable problems. The computability results and synchronization guarantees combine to give you the tools to determine whether one concurrent algorithm is "better" than another. The remainder of the book is devoted to practical subjects. These chapters cover locks, a variety of data structures, work scheduling, and some miscellaneous topics. Java's java.util.concurrent package provides production-quality implementations of most of these data structures. The authors know this, and they use the data structures chapters to demonstrate generally applicable techniques while avoiding unnecessary implementation details. The work scheduling chapter is a sobering reminder of the difficulty inherent in fully exploiting highly parallel architectures. The authors show how to use recurrences to analyze the relative speedup an algorithm gains by running on P processors instead of a single processor. Combining this with the discussion of Ahmdal's Law earlier in the book we see that the essential math behind parallelism severely penalizes you for seemingly small sequential portions of your code. I also found the counting networks chapter fascinating, as I had never encountered that material before. The book also provides appendices aimed at bringing inexperienced readers up to speed. That said, I wouldn't recommend this book for inexperienced programmers. The material is challenging. If you are looking for a gentler introduction to this subject, consider Java Concurrency in Practice. Each chapter ends with a note describing the history of the material and providing pointers to the bibliography. These demonstrate that the authors have been significant contributors to this field. I do agree with the review from Vyacheslav Imameyev - some of the code samples are wrong. I think they missed "volatile" keywords in several places. I don't see this as a cookbook, so I'm still giving the book five stars. Highly parallel machines are here to stay. Programmers need to adapt to this or suffer competitive disadvantage. This is the book to read in order to meet that challenge.

Took the class from Herlihy that goes with this book. He's an extremely intelligent and knowledgeable man, and the book is invaluable. I will be using it many times in my future computer science career. Lots of valuable reference information, algorithms, proofs of correctness (critical for parallel systems!), and key core concepts that help you think about multiprocessor problems in new ways.

This is a great, lucid - and PRACTICAL book on concurrent programming in general. It's equally applicable if you're programming for a multi-core CPU ... or if you're simply programming threads ... or even if you're programming a cluster. Half the book is about "theory" (written in a thoroughly engaging, easy-to-follow style), the remaining half about "practice": various tips and tricks obviously learned from hard-earned experience. There's also a great discussion of "transactional memory", which I'm sure is going to become increasingly important - and increasingly mainstream. This book is a welcome addition to any practitioner's bookshelf!