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 ^{k}n$ critical path lengths.

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

Background

Prefix Sum

Hillis-Steele Prefix Sum

Hillis and Steele Algorithm

Data parallel algorithms

(Extra Credit) Work-efficient

Exclusive (Blelloch)

Blelloch Algorithm

Scan Primitives for Vector Computers

Prefix Sums and Their Applications

Inclusive

Lecture

slides

Code To Use

class PhasableIntArrays extends AbstractPhasable

getSrcForPhase(phaseIndex)

getSrcForPhase(phaseIndex)

PowersOf2Iterable

PhasableIntArrays

One of the downsides to parallel scan requires memory. For our scans we add the additional requirement that we will not mutate the incoming array parameter. We could create log(n) arrays, one for each level but that would be wasteful. If we create two array buffers and switch which is the source to read from and which is the destination to write to at each power-of-two level of the scan, we should be good to go. This is what PhasableIntArrays helps us with. By using its getDstForPhase(int phaseIndex) and getSrcForPhase(int phaseIndex), we can get the source and destination array corresponding to the phase.

The table below shows which of the two buffer arrays, a or b, will be passed back for each phase index as the source or the destination array.

phase	0	1	2	3	4
src	data	a	b	a	b
dst	a	b	a	b	a
bonus info: power of 2	1	2	4	8	16

NOTE: think about which array is the correct one to return from your scan method given how you write your code.

PowersOf2Iterable

This studio should come in handy here. Recall that we implemented a PowersOfTwoLessThan class in this studio.

Example usage:

for(int v : new PowersOfTwoLessThan(71)) {
    System.out.println(v);
}

Code To Implement

Sequential Sum Scanner

class:	SequentialSumScanner.java
methods:	sumScan
package:	scan.exerise
source folder:	student/src/main/java

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

Warning:Do NOT mutate the data parameter. Return a new array which contains the sum scan of data.

Implement the simple sequential scan algorithm with the dependencies depicted below:

Work: N

CPL: N

Hillis and Steele Parallel Sum Scanner

class:	StepEfficientParallelSumScanner.java
methods:	sumScan
package:	scan.exercise
source folder:	student/src/main/java

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

(Extra Credit) Work Efficient Scan

Choose one path.

Inclusive (Blelloch)

class:	WorkEfficientParallelScan.java
methods:	sumScanExclusiveInPlace
package:	scan.challenge
source folder:	student/src/main/java

method: public static void sumScanExclusiveInPlace(int[] data) (parallel implementation required)

Exclusive

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

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

Visualization

class:	ScanApp.java	VIZ
package:	scan.viz
source folder:	student/src/main/java

Testing Your Solution

Correctness

Required

class:	__ScanTestSuite.java
package:	scan.exercise
source folder:	testing/src/test/java

Optional Work Efficient

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