Parallel Processing

The divide-and-conquer paradigm may be used to perform parallel prefix computation on the PRAM. The problem is composed of two subproblems: computing the odd-indexed results 1, 3, 5, ... and computing the even-indexed results 0, 2, 4, ...

The first subproblem is solved as follows. Pairs of consecutive elements in the input list (0 and 1, 2 and 3, 4 and 5, and so on) are combined to obtain a list of half the size. Performing parallel prefix computation on this list yields correct values for all odd-indexed results. The even-indexed results are then found in a single PRAM step by combining each even-indexed input with the immediately preceding odd- indexed result. Complete the code below to perform the above algorithm for the sum computation.

forall even numbered processors j, copy X[j] + X[j+1] into S[j/2] m := last index of si S := 1 while (s