Work Efficient Parallel Scan Assignment

From CSE231 Wiki
Jump to navigation Jump to search

Background

A work-efficient parallel scan was developed by Guy Blelloch and outlined in: Scan Primitives for Vector Computers and Prefix Sums and Their Applications.

Video: Blelloch Scan  

Comparison

In the two circuit diagrams, you can see that there is less work to do in Blelloch scan, although there are more steps (but not asymptotically more, both scans provide lg(N) spans/critical path lengths).

Comparison of Parallel Scans
Blelloch (Work Efficient) Hillis and Steele (Step Efficient)
Prefix sum 16.svg Hillis-Steele Prefix Sum.svg

Code To Implement

You may choose to implement either Inclusive or Exclusive Blelloch Scan. This is an in-place mutating scan algorithm, which means you can mutate the original data array.

Inclusive Scan or Blelloch Exclusive Scan

class: WorkEfficientParallelMutatingSumScanner.java Java.png
methods: IsInclusive
package: scan.challenge
source folder: student/src/main/java

method: public boolean isInclusive() Sequential.svg (sequential implementation only)

Here you can indicate whether you will implement inclusive or exclusive scan.
class: WorkEfficientParallelMutatingSumScanner.java Java.png
methods: sumScan
package: scan.challenge
source folder: student/src/main/java

method: void sumScan(int[] data) Parallel.svg (parallel implementation required)

Testing Your Solution

class: _WorkEfficientScanTestSuite.java Junit.png
package: scan.challenge
source folder: testing/src/test/java