7.1.3 Partitioning Example Discussion

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