DE Oracle @ UMUC

Every problem contains an upper bound on the number of agents which can be meaningfully employed in its solution.

Additional agents beyond this number will not improve solution time, and can indeed be detrimental. This upper bound provides an idea as to how suitable a problem is for parallel implementation: a measure of scalability.

A given problem may only be divided into a finite number of sub-problems, corresponding to the smaller task. The availability of more agents than there are tasks will not improve solution time. The problem of clearing a room of N chairs (see animation) may be divided into N tasks consisting of removing a single chair. A maximum of N workers can be allocated one of these tasks and hence perform useful work.

The optimum solution time for clearing a room may not in fact occur when employing N workers due to certain aspects of the problem limiting effective worker utilization.

This phenomenon can be illustrated by adding a constraint to the problem, in the form of a doorway providing egress from the room. A BOTTLENECK will occur as large numbers of workers attempt to move their chairs through the door simultaneously, as shown in this animation.

The delays caused by this bottleneck may be so great that the time taken to empty the room of chairs by this large number of workers may in fact be longer than the original time taken by the single worker. In this case, reducing the number of workers can alleviate the bottleneck and thus reduce solution time.