|
What this book is not:- A programmer's cookbook- A programming manual- A math textThis is an engineering theory textbook: enough theory to teach you how to reason about practical problems on the problems' own terms. 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. Some call for programming, some for thinking. Learning to reason about these problems is hard and the books are hard. The examples are in Java. This book is no exception. If it were easy, such books would be unnecessary. 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.
That said, it is generally very clear, but it is not light reading or easy study. It demands serious study time. They indicate that the authors have a deep grasp not only of their subject matter but of how to teach it. (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).
It's very well paced and you never feel that familiar information overload so common in computer science texts. I took a class with Professor Herlihy at Brown in which he used perhaps an early version of this text. This is quite a feat for an advanced topic in computer science. It was a great class and a great textbook, likely one of the best, most understandable texts I've encountered in the world of advanced computer science. The chapters are relatively short and to the point, each requiring no more the 30 - 45 minutes of reading. It's also quite accessible, it seems someone with only cursory understanding of basic computer science could grasp much of what is conveyed, while at the same time it never feels "dumbed down" for the laymen. Highly recommended.
If you're working in a large enterprise, the major trends at the moment are SOA and SaaS - and this book does not deal with them in the context of multicore. The books is also too academic and there's too much theory and not enough practical advice for enterprise architects.
Chapter 14 explains skiplists, an intriguing way to implement a container that has logarithmic search time and that is inherently parallel. In particular, shared-memory multiprocessors have specific implementation details, such as cache coherence policies, that directly affect parallel software run on such architectures. Some programmers may argue that they should not need to know how hardware behaves. 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. Java programmers will be especially interested in understanding monitors, while all OO programmers should have an appreciation of synchronizing an entire class. Realizing the importance of CAS is vital for advanced parallel programmers who want to implement nonblocking algorithms.Chapter 6 - Universality of ConsensusThis chapter explains how to build universal consensus for your own concurrent objects. It is one of the most difficult chapter in the text. It explains how to implement shared memory that behaves "correctly" without using mutual exclusion.
Because of this, readers should pay particular attention to this chapter. Get through it and keep reading.Chapter 4 - Foundations of Shared MemoryThis chapter concentrates on understanding shared memory, the cornerstone of all multi-threaded applications. A high consensus number, say N, for a synchronization primitive means that synchronization primitive can "correctly" solve the consensus problem for N concurrently executing threads. First, the authors explain how to implement hash tables using coarse-grained locks, then with fine-grained locks, then with no locks at all. The authors demonstrate how to build priority queues with arrays, trees, heaps and skiplists.Chapter 16 - Futures, Schedules and Work DistributionThis chapter presents some important aspects in understanding parallelism.
While I would like to agree, the unfortunate state of multi-core programming currently requires a basic understanding of memory consistency models and cache behaviors. The different types of memory that are discussed are single-reader single-writer (SRSW), multiple-reader single-writer (MRSW) and multiple-reader multiple-writer (MRMW). Atomic registers have a consensus number of 1, they support only 1 thread's execution that is guaranteed to consistently and validly solve the consensus problem.The most important point of this chapter (in my opinion) is that compare-and-swap (CAS), or compare-and-set, has an infinite consensus number (section 5.8). The chapter also explains a neat cancellation problem called elimination.
Consensus numbers will undoubtedly confuse novice parallel programmers. Elimination is useful for avoiding overflows, underflows and other types of bounded problems.Chapter 12 - Counting, Sorting and Distributed CoordinationThis chapter explains how to take problems that seem to be inherently sequential and make them parallel. It explains how to implement locks using assembly level operations (test-and-set and test-and-test-and-set), how to reduce bus contention using backoff, how to reduce cache pressure by having threads spin on their local cache memory and how to manage an unknown number of threads using locks.After reading this chapter, most readers should have an appreciation for the hardware complexity of implementing something as simple as a lock. The introduction gives a brief overview of the direction of the text: principles and practice.----------------------------------------Part 1 - PrinciplesChapter 2 - Mutual ExclusionMutual exclusion is a key concept to multi-threaded programming, and this chapter is rightly placed at the beginning of the text.
For example, critical sections have an infinite consensus number (e.g. In short, the higher the consensus number the better. The chapter also explains important ideas about the overhead of threads, stealing work, and sharing work. The chapter also explains how to deal with open-addressed hash tables which are particularly challenging.Chapter 14 - Skiplists and Balanced SearchMost non-experts that make it this far in the text will be greatly rewarded by this chapter. Some readers may want to skim it.----------------------------------------Unofficially, Chapters 13 - 15 focus on achieving parallelism in algorithms that are inherently parallel.
This is an important chapter for non-experts to think about, as it explains how operation interleavings are not as discrete as we pretend they are and how shared memory should behave in all possible cases.Chapter 5 - The Relative Power of Primitive Synchronization OperationsThis chapter explains the varying strength of different wait-free synchronization primitives. The Art of Multiprocessor Programming is an outstanding text that will soon become a classic. Barriers are important in preventing threads from getting to far ahead or too far behind one another.Chapter 18 - Transactional MemoryThis chapter briefly describes a new parallel programming concept called transactional memory (TM). 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). 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. 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.
Unlike red-black trees or balanced binary trees that yield logarithmic search time complexity, skiplists do not need to be rebalanced. Readers will enjoy seeing how easy it is to extract parallelism in these naturally parallel algorithms.----------------------------------------Chapter 13 - Concurrent Hashing and Natural ParallelismThis chapter explains how to build parallel hash tables, with both open and closed addressing. Herlihy and Shavit are responsible for HTM and STM, respectively. The chapter also explains both combining and diffracting trees, both of which are very interesting ways to make sequential problems parallel. The following ideas are touched on: HTM + cache coherence, composition, contention managers and transactional serialization. support an infinite number of concurrent threads).
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 ObjectsThis chapter starts off simple, but gets complex fast. This chapter is one of the more complex chapters of the text. There is a directed effort to explain parallel programming concepts as they relate to multi-core (or many-core) architectures. The ABA problem is a subtle, but important problem.Chapter 11 - Concurrent Stacks and EliminationThis chapter starts where the last chapter left off; it explains how to implement concurrent stacks, containers with first-in-last-out behavior. This is why modern instruction set architectures (ISAs) all provide CAS: it is critical to supporting an unlimited number of concurrently executing threads.
This chapter may cause some confusion to non-experts, but readers should try to understand at least the basic principles conveyed here as they are important to most general parallel programming problems.Chapter 17 - BarriersThis chapter explains how to use barriers, a synchronization primitive that ensures threads move together through "gates" or "phases". The chapter also explains a classic parallel problem known as ABA, where thread1 observes x == A, thread2 does x=B and then x=A and thread1 then observes x == A. 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 - IntroductionWhy is this book called "The Art of Multiprocessor Programming" and not "The Art of Parallel Programming." It is not by accident. Skiplists do not need to be rebalanced due to their unique algorithmic layering, making them inherently parallel. As such, skiplists have a notable benefit over their inherently sequential logarithmic search time counterparts.This is a critically important chapter for practitioners hoping to exploit high parallelism while retaining logarithmic search time.Chapter 15 - Priority QueuesThis chapter explains how to implement priority queues, containers that are queues where each element has an identifiable level of importance. The chapter then explains the ways to implement pools as different types of queues, containers with first-in-first-out behavior. Moreover, the section on reentrant locks is simple but important to preventing deadlocks.----------------------------------------Unofficially, Chapters 9 - 11 focus on achieving parallelism in algorithms that have sequential bottlenecks and are therefore inherently sequential.----------------------------------------Chapter 9 - Linked Lists: The Role of LockingThe chapter explains how to implement ordered linked lists (e.g., IntSets or just sets) in a variety of different ways.
The chapter starts out with the most basic implementation and then begins to increase performance by relaxing the strictness of the required thread synchronization.Chapter 10 - Concurrent Queues and the ABA ProblemThe chapter explains how to implement pools, a collection of unordered or ordered items. 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. TM uses optimistic concurrency and greatly simplifies parallel programming. While it will be an interesting chapter for experts, novices may want to skip it.----------------------------------------Part II - Practice Chapter 7 - Spinlocks and ContentionThis chapter explains the important differences between different types of locking. Herlihy and Shavit note this and make an effort to address it in a "just what you need to know" fashion, as done in this chapter.Chapter 8 - Monitors and Blocking SynchronizationThis chapter explains monitors, conditions, the differences between readers and writers, and reentrant locks. In particular, the authors explain how to keep threads busy with work without causing the threads to become busy with "looking for work". TM is currently receiving a lot of research attention and many researchers believe TM will soon become the new way to do parallel programming.
-> is a total order on events, partial order on intervals. Throughout chapter 3 I was wanting more of both. An example of this the introduction of the precedence relation operator "->" (a right pointing arrow). This book is challenging. To get the most out of this book do yourself a favor visit the companion site to get the slides and errata. English description is good at communicating the broad sense while formal notation is needed to be rigorous.
That said the notation introduced in chapters 2 & 3 have me excited for what's to come (I've just completed ch 3).
Events are denoted with lower-case labels while intervals upper-case, unless of course the upper-case label is denoting a thread/memory location/some other entity.
If you're experiencing a WTF moment, review twice break review again, then hit the errata.
Several occasions I flipped between chapters reviewing earlier notational details I thought I understood only to come to the conclusion the book is inconsistent in usage.
Finally like another reviewer I've noticed discrepancies between code and text.
The problem is by the time it's important to recall upper-case really does mean interval, there's been numerous examples where it hasn't.
The material is challenging enough without this ambiguity.
I'm hopeful my submitted erratum will help others.
Then hit iTunes U and look up Maurice Herlihy.
|
