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 the adjacency matrix A has row i = 0 and column i = 0. What does that say about task i?
8.2. Assume an ASA with W = 5 nodes or tasks and its depth is the maximum possible value.
(1) What is the maximum value of depth D?
(2) What is the structure of the adjacency matrix under this condition?
(3) What type of matrix is this adjacency matrix?
(4) What kind of matrix results if you raise the adjacency matrix to higher powers?
(5) Comment on the structure of Ak.
(6) What is the maximum power of the adjacency matrix at which the matrix is zero?
8.3. Assume a cyclic sequential algorithm with W = 5 nodes or tasks and it has a maximum-length cycle.
(1) What is the maximum value of depth D?
(2) What is the structure of the adjacency matrix under this condition?
(3) What kind of matrix results if you raise the adjacency matrix to higher powers?
(4) What is the maximum power of the adjacency matrix at which the matrix is zero?
8.4. An NSPA algorithm consists of nine tasks that depend on each other as follows:
| Task | Depends on tasks |
| 1 | NA |
| 2 | NA |
| 3 | NA |
| 4 | NA |
| 5 | NA |
| 6 | 1, 2, 3, 4 |
| 7 | 5 |
| 8 | 1, 4 |
| 6, 7, 8 |
(1) Draw the DAG for this algorithm.
(2) Assign tasks to the sequences.
(3) Identify the algorithm parameters D, P, and W.