Scan

From CSE231 Wiki
Revision as of 05:45, 5 April 2018 by Cosgroved (talk | contribs)
Jump to navigation Jump to search

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:

make it seem to have little hope for parallelism. However, simple yet clever approaches can achieve 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

Hillis-Steele Prefix Sum.svg

Optional

Blelloch Algorithm

Prefix sum 16.svg

Code To Investigate

ArraysHolder

getSrc()
getDst()
nextSrcAndDst()

class PowersOfTwoLessThan

Code To Implement

Sequential Scan

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

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

Hillis and Steele Parallel Scan

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

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

(Optional) Blelloch Work Efficient Scan

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

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

Testing Your Solution

Correctness

Required

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

Optional Work Efficient

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