Analysis of Algorithms : An Active Learning Approach

202 PARALLEL ALGORITHMS

P 11 P 12 P 13 P 14

54

76 66 4 53 1107

52

83

142

96

35 71

47 23522

4

P 21 P 22 P 23 P 24

■FIGURE 7.6G
P 13 and P 22 are
now done, and P 14 ,
P 23 , and P 24 work
on their next values

P 11 P 12 P 13 P 14

54

76 66 53 42617

52

4

147

962

35 83

1

47 22 23 5

P 21 P 22 P 23 P 24

■FIGURE 7.6H

P 14 and P 23 finish,

andP 24 works on

its last two values

P 11 P 12 P 13 P 14

54

76 66 53 26 4 1 7

52

147

9621

35 84

3

47 22 23 5

■FIGURE 7.6I P^21 P^22 P^23 P^24

The multiplication is

done and the

processors hold

the result of

54 52 47 22

76 66 53 26