Algorithms and Parallel Computing

7.7 PROBLEM PARTITIONING

Problem partitioning breaks up the computation task into smaller parts or subtasks that take less time to compute. Partitioning strives to generate subtasks that have the same size. Partitioning works best, of course, for trivially parallel algorithms. Otherwise, the subtasks will not execute in parallel. The challenge now shifts to how to combine the results of the subtasks to obtain the final result.

Take the simple example of adding K numbers using N processors:

(7.10)

Since addition is associative and distributive, we can break up the problem into N tasks where each task requires adding s = |K/N| numbers on each processor:

(7.11)

(7.12)

Figure 7.1 shows a schematic representation of the partitioning technique. The original task or problem is partitioned into small equal portions that should execute faster. The number of partitions would typically equal the number of available processors.

Figure 7.1 Problem partitioning divides the problem into N equal-sized subtasks. In this case, N = 8.

After these additions are complete, we are faced with ...