Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Background)
(Background)
Line 6: Line 6:
  
 
[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>
  
 
[https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_2:_Work-efficient|Blelloch Algorithm]
 
[https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_2:_Work-efficient|Blelloch Algorithm]
 +
 
<youtube>mmYv3Haj6uc</youtube>
 
<youtube>mmYv3Haj6uc</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

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