Algorithms and Parallel Computing

8.8 PERFORMANCE OF SERIAL AND PARALLEL ALGORITHMS ON PARALLEL COMPUTERS

The construction of Fig. 8.4 helps us identify all the algorithm parameters: W, D, and P.

The work parameter W is of course determined by counting all the nodes or tasks comprising the algorithm. From Fig. 8.4, we conclude that W = 10.

The parallelism of the algorithm is found by estimating the number of nodes assigned to each execution sequence.

(8.15)

From Fig. 8.1, we find that the parallelism of the algorithm is P = 4. Dedicating more than four processors will not result in any speedup of executing the algorithm.

From Fig. 8.4, we find the depth (D) as equal to the number of sequences required to complete the algorithm. From Fig. 8.4, we conclude that D = 4.

Using P parallel processors, the minimum algorithm latency is defined as the minimum time to execute the algorithm on P processors as given by

(8.16)

where τ_p is the processor time required to execute one task or node in the dependence graph.

The time its takes a single processor (uniprocessor) to complete the algorithm would be

(8.17)

The maximum speedup due to using parallel processing is estimated as

(8.18)

8.9 PROBLEMS

8.1. Suppose that ...