Scan

Motivation

Scan, also known as parallel prefix, is a fundamental and useful operation in parallel programming. We will gain experience in building Hillis & Steele scan with an optional work efficient Blellock scan.

Background

Prefix Sum

Hillis and Steele Algorithm

Algorithm

Code To Implement

Sequential Scan

class:	SequentialScan.java
methods:	sumScan
package:	scan.studio
source folder:	student/src/main/java

method: public int[] sumScan(int[] data) (sequential implementation only)

Hillis and Steele Parallel Scan

class:	ParallelScan.java
methods:	sumScan
package:	scan.studio
source folder:	student/src/main/java

method: public int[] sumScan(int[] data) (sequential implementation only)

(Optional) Blelloch Work Efficient Scan

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

method: public int[] sumScan(int[] data) (sequential implementation only)

Testing Your Solution

Correctness

Required

class:	ScanTestSuite.java
package:	scan.studio
source folder:	testing/src/test/java

Optional Work Efficient

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