Scan

From CSE231 Wiki
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.

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: 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