# 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.

# Code To Use

class PhasableIntArrays extends AbstractPhasable

getSrcForPhase(phaseIndex)
getSrcForPhase(phaseIndex)

## 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 from at each power of two level of the scan, we should be good to go.

The table below shows which array will be passed back for each offset.

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

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.

Example usage:

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

# Code To Implement

## Sequential Scan

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

method: public static int[] sumScanInclusive(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 Scan

 class: StepEfficientParallelScan.java methods: sumScanInclusive package: scan.studio source folder: src/main/java

method: private static int[] sumScanInclusive(PhasableIntArrays phasable) (parallel implementation required)

## (Extra Credit) Blelloch Work Efficient Scan

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

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