06. (6 P: 3 each, 20 minutes)

Consider the following array: (4 6 7 1 28 5 21.

a. Perform a parallel inclusive prefix scan on the array using the Kogge-Stone

algorithm. Report the intermediate states of the array after each step. How many

add operations?

Solution:

b. Repeat using the work-efficient algorithm (Brent-Kung).

Solution: