Worksheet 5
CS599 Parallel Programming and Algorithms
Reduction and Scan Operations

1. Find the product of the following array (i.e. perform a multiplication reduction) using the parallel reduction strategy shown in class.

+---+---+---+---+---+---+---+---+---+
| 2 | -1| 4 | 6 | 2 | 3 | 8 | 7 | -3|
+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8

2. How much work (multiplication operations) is required to find this product? How many steps are required?

3. Using the Hillis and Steele method, perform an inclusive scan on the following array.

+---+---+---+---+---+---+---+---+
| 3 | 7 | 2 | 4 | 1 | 6 | 9 | 7 |
+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7

4. How much work (addition operations) is required to find this cumulative sum? How many steps are required?

5. Using the Blelloch method, perform an exclusive scan on the following array.

+---+---+---+---+---+---+---+---+
| 8 | 1 | 6 | 4 | 2 | 3 | 4 | 7 |
+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7

6. How much work (addition operations) is required to find this cumulative sum? How many steps are required?