Designing parallel algorithms
In Chapter 1 we discussed what parallelism is and used a cooking analogy to present some ideas for executing multiple steps simultaneously, and to show how some steps would not benefit from changing the executor. We are now going to use a similar analogy as we explore in more detail the design of parallel algorithms.
A good starting point is the idea that a parallel algorithm is not simply a sped-up version of a sequential one. It involves a fundamental restructuring, such that tasks can occur simultaneously to take advantage of multiple computing units.
In Chapter 1 we imagined a group of friends preparing a meal together – a small setup that gave us a glimpse of parallelism. They could cut and chop in parallel, but there was not massive parallelism. However, let’s suppose that they had tremendous success in their endeavor and must now prepare not a few but some thousands of meals. Every step must now be carefully thought about...
