Question 10: Finding the sum of 16 numbers can be represented by the binary-tree computation graph of Figure 2 mentioned bellow with T(1) = W(1) = 15. Assume unit-time addition

Suppose, we have total number of processors, p=8. And essentially, the 8 processors perform all of the additions at the same tree level in each time unit, beginning with the leaf nodes and ending at the root. The relatively low efficiency is the result of limited parallelism near the root of the tree.

Now redraw the Figure 2 for the following conditions:

Assuming that addition operations that are vertically aligned in Figure 2 are to be performed by the same processor and that each inter-processor transfer, represented by an oblique arrow, also requires one unit of work (time), the number of processors are same as p = 8.

Applying the formulas or rules of the effectiveness of parallel processing, algorithm, and architecture define the following, where, p=Number of processors.

W(p) Work performed by p processors

T(p) Execution time with p processors, where T(1) = W(1); T(p) W(p)

S(p) Speedup

E(p) Efficiency

R(p) Redundancy

U(p) Utilization, and

Q(p) Quality