Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Motivation)
(Motivation)
Line 1: Line 1:
 
=Motivation=
 
=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.
+
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.
  
 
Further, the dependencies in scan make it seem to have little hope for parallelism.  However, simple yet clever approaches can achieve log n CPLs.
 
Further, the dependencies in scan make it seem to have little hope for parallelism.  However, simple yet clever approaches can achieve log n CPLs.
 +
 +
While we will simply implement prefix sum, scan can be used for other associative operations.
  
 
=Background=
 
=Background=

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

Further, the dependencies in scan make it seem to have little hope for parallelism. However, simple yet clever approaches can achieve log n CPLs.

While we will simply implement prefix sum, scan can be used for other associative operations.

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