The optimal solution to the dining philosophers problem given in
the answer to the Quick Quiz in
Section
is an excellent example of ``horizontal parallelism'' or
``data parallelism''.
The synchronization overhead in this case is nearly (or even exactly)
zero.
In contrast, the double-ended
queue implementations are examples of ``vertical parallelism'' or
``pipelining'', given that data moves from one thread to another.
The tighter coordination required for pipelining in turn requires
larger units of work to obtain a given level of efficiency.
Quick Quiz 7.9: The tandem double-ended queue runs about twice as fast as the hashed double-ended queue, even when I increase the size of the hash table to an insanely large number. Why is that? End Quick Quiz
Quick Quiz 7.10: Is there a significantly better way of handling concurrency for double-ended queues? End Quick Quiz
These two examples show just how powerful partitioning can be in devising parallel algorithms. However, these example beg for more and better design criteria for parallel programs, a topic taken up in the next section.
Paul E. McKenney 2011-12-16