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.

Further, the dependencies in scan:

$y_{i}=y_{i-1}+x_{i}$

make it seem to have little hope for parallelism. However, simple yet clever approaches can achieve $\log n$ critical path lengths.

While we will simply implement prefix sum, scan can be used for other associative operations.

Background

Prefix Sum

Required

Hillis and Steele Algorithm

Optional

Blelloch Algorithm

Code To Investigate

class ArraysHolder

getSrc()

getDst()

nextSrcAndDst()

class PowersOfTwoLessThan implements Iterable<Integer>

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