Work Efficient Parallel Scan Assignment

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)

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
methods:	IsInclusive
package:	scan.challenge
source folder:	student/src/main/java

method: public boolean isInclusive() (sequential implementation only)

Here you can indicate whether you will implement inclusive or exclusive scan.

class:	WorkEfficientParallelMutatingSumScanner.java
methods:	sumScan
package:	scan.challenge
source folder:	student/src/main/java

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

Testing Your Solution

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