Task Division in Parallel Processing

A common first instinct when speeding up a job with several processors is to cut it into pieces of the same size and hand one piece to each processor. The reasoning seems sound. If every piece is the same amount of work, every processor should finish at the same moment, and the total time should drop roughly in proportion to the number of processors. Many beginners never question this belief. This article examines why it fails and what a better strategy looks like.

The source identifies two separate reasons why equal-sized pieces can finish at different times. Keeping them apart makes the problem easier to reason about. Equal size is a property of the input to each subproblem. It says nothing about how long each subproblem will run once a processor starts on it.

The speedup from adding processors depends on how evenly the work finishes, not only on how many processors exist. The longest subproblem sets the finish time. Shortening the other pieces does not help once the longest one is still running, because the job is not complete until every piece is complete.

The timeline above uses illustrative numbers. Processor 4 holds the piece with the most work, or runs on the slowest or most heavily loaded resource. Its finish time of 9 units is the job's finish time, even though the other three processors completed their pieces much earlier. The idle time of those three processors is the cost of an unbalanced split.

The standard response to uneven work is not to find a perfect split, which is usually impossible to predict. Instead, the problem is divided into many more subproblems than there are processors. Each processor handles several subtasks. When a processor finishes one, it is assigned another, and this continues until every subtask has been given out.

The effect is that processors which finish quickly take on more work, and slow or busy processors take on less. Each processor effectively works at its own pace. The diagram below shows the flow of work rather than a fixed assignment. A processor that is slow on one subtask simply returns to the pool later, so it does not hold up the subtasks that remain.

Load balancing is easiest when subtasks are independent. Independent subtasks can run in any order and at the same time, so a free processor can take any waiting subtask without checking anything. The source's image program is a very easy case because each of its subproblems is completely independent. Any number of them can run at once, and no subtask must wait for another.

Making subproblems small is what makes the many-subtasks approach work, but there is a limit. The source's guidance is that subproblems should be small but not too small. Subproblems should be small enough that processors stay busy, but not so small that the overhead of creating and assigning them becomes significant.

Subtask size involves a trade-off between two costs. If subtasks are too large, there are too few of them for the pool to smooth out differences, so some processors finish early and sit idle while a large subtask runs elsewhere. If subtasks are too small, the creation and assignment of each one adds a computational overhead, and when pieces are very small that overhead can add significantly to the total work.

The source's image program shows how the trade-off is resolved in practice. A pixel-by-pixel split would produce subtasks that are probably too small, because each one would carry very little work relative to the cost of creating and assigning it. Instead, each subtask computes one row of pixels. Since the image has several hundred rows, there are many subtasks, and each one is still substantial.