Download Programming on Parallel Machines - matloff

134
CHAPTER 7. THE PARALLEL PREFIX PROBLEM
and
fn = fn−1 + fn−2 , n > 1
(7.3)
The point is that (7.3) can be couched in matrix terms as
fn+1
fn
=A
fn
(7.4)
fn−1
where
A=
1 1
1 0
(7.5)
Given the initial conditions (7.2) and (7.4), we have
fn+1
fn
=A
n−1
1
1
(7.6)
In other words, our problem reduces to one of finding the scan of the set A, A2 , ..., An−1 , with matrix
multiplication as our associative operator.
Note that among other things, this example shows that in finding a scan,
• the elements might be nonscalars, in this case matrices
• the associative operator need not be commutative
On the other hand, this is not a very good example in the sense that all the xi are identical past i = 0, each
being equal to A, with x0 being I. The problem with this is that in the parallel implementation presented
below, lots of duplicate work would be done.
A better example would be permutations. Say we have the vector (12,5,13,8,88). Applying the permutation
(2,1,0,3,4) would say the old element 0 becomes element 2, the old element 2 becomes element 0, and all
the rest stay the same. The result would be (13,5,12,8,88).
This too can be cast in matrix terms, by representing any permutation as a matrix multiplication. We just