Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Background)
(Background)
Line 3: Line 3:
  
 
=Background=
 
=Background=
[https://en.wikipedia.org/wiki/Prefix_sum Wikipedia Prefix Sum]
+
[https://en.wikipedia.org/wiki/Prefix_sum Prefix Sum]
  
[https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_1:_Shorter_span,_more_parallel|Hillis and Steele Algorithm]
+
[https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_1:_Shorter_span,_more_parallel Hillis and Steele Algorithm]
  
 
<youtube>RdfmxfZBHpo</youtube>
 
<youtube>RdfmxfZBHpo</youtube>

Revision as of 23:28, 4 April 2018

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

Prefix Sum

Hillis 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