One (Not So Good) Solution
•One
solution is to apply the summation tree to compute each yi in parallel …
•This
is a “reduce to previous solution” approach
–Time
would be maximum depth, I.e. log2 n
–Processor
requirements would be
1+1+2+2+3+3+
… +n/2+n/2
=
n(n/2+1) = O(n2)
x1
x3
x2
x4
x5
x6
s3,4
s1,2
s5,6
s1,4
s5,8
s1,8
P0
P1
P2
The k = 6 solution