Scan

From CSE231 Wiki
Revision as of 23:27, 4 April 2018 by Cosgroved (talk | contribs) (Background)
Jump to: navigation, 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.

Background

Wikipedia Prefix Sum

and Steele Algorithm

Algorithm

Code To Implement

Sequential Scan

class: SequentialScan.java Java.png
methods: sumScan
package: scan.studio
source folder: 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: 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: 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: src/test/java

Optional Work Efficient

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