Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Background)
(Background)
Line 5: Line 5:
 
[https://en.wikipedia.org/wiki/Prefix_sum Prefix Sum]
 
[https://en.wikipedia.org/wiki/Prefix_sum Prefix Sum]
  
 +
==Required==
 
[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]
+
[[File:Hillis-Steele_Prefix_Sum.svg]]
 +
 
 +
==Optional==
 +
[https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_2:_Work-efficient Blelloch Algorithm]
  
 
<youtube>mmYv3Haj6uc</youtube>
 
<youtube>mmYv3Haj6uc</youtube>
 +
 +
[[File:Prefix sum 16.svg]]
  
 
=Code To Implement=
 
=Code To Implement=

Revision as of 23:30, 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

Required

Hillis and Steele Algorithm

Hillis-Steele Prefix Sum.svg

Optional

Blelloch Algorithm

Prefix sum 16.svg

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