How to Make Things Faster

Chapter 74. Parallelization

Parallelization is a form of latency hiding. It works like this:

The point of parallelizing a task is to reduce that task’s response time by exploiting unused capacity. However, the benefits of parallelization come at a cost. Parallel operations can reduce response times, but they don’t reduce load. Parallelizing in fact always increases system load, because parallel algorithms require extra instructions to partition the workload among the parallel processes and then harvest the work done by those processes (the extra C1 and C2 costs in my sequence diagram above).

Parallel algorithms can have false allure. For example, imagine a serial algorithm that returns its result in 10 seconds, using 10 seconds’ worth of resources. Now imagine a parallel algorithm that returns the same result in 5 seconds, but it consumes 50 seconds’ worth of resources. The parallel algorithm will be alluring to its user because it’s twice as fast, but it will put five times more load onto the system.

If just one person on the system uses the parallel algorithm, the resulting increase in traffic intensity, crammed into one little 5-second interval, might go unnoticed. But when everyone else gets wind that they can cut their response times in half by parallelizing their stuff, too, traffic intensities can grow quickly to the point where everyone is miserable, high and right on ...