situations, a single parallelization strategy might be all that is required to
produce a parallel solution for a problem. However, in other situations, there
is no single strategy sufficient to solve the problem effectively, and it is
necessary to select a combina-tion of approaches.
pipeline strategy represents a good starting point for a combination of
approaches. The various stages in the pipeline can be further parallelized. For
example, one stage might use multiple threads to perform a calculation on one item
of data. A dif-ferent stage might have multiple threads working on separate
items of data.
mapping a process to an implementation, it is important to consider all the
ways that it is possible to exploit parallelism and to avoid limiting yourself to
the first approach that comes to mind. Consider a situation where a task takes
100 seconds to complete. Suppose that it‚Äôs possible to take 80 of those seconds
and use four threads to complete the work. Now the runtime for the task is 20
serial seconds, plus 20 seconds when four threads are active, for a total of 40
seconds. Suppose that it is possible to use a different strategy to spread the
serial 20 seconds over two threads, leading to a perform-ance gain of 10
seconds, so the total runtime is now 30 seconds: 10 seconds with two threads
and 20 seconds with four threads. The first parallelization made the
application two and a half times faster. The second parallelization made it
1.3x faster, which is not nearly as great but is still a significant gain.
However, if the second optimization had been the only one performed, it would
have resulted in only a 1.1x performance gain, not nearly as dramatic a pay-off
as the 1.3x gain that it obtained when other parts of the code had already been