Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Code To Investigate)
Line 28: Line 28:
  
 
=Code To Investigate=
 
=Code To Investigate=
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html ArraysHolder]
+
class [https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html ArraysHolder]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html#getSrc-- getSrc()]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html#getSrc-- getSrc()]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html#getDst-- getDst()]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html#getDst-- getDst()]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html#nextSrcAndDst-- nextSrcAndDst()]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/ArraysHolder.html#nextSrcAndDst-- nextSrcAndDst()]
  
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/PowersOfTwoLessThan.html class PowersOfTwoLessThan]
+
class [https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/scan/core/PowersOfTwoLessThan.html PowersOfTwoLessThan]
  
 
=Code To Implement=
 
=Code To Implement=

Revision as of 00:45, 5 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:

y_i = y_{i-1} + x_i

make it seem to have little hope for parallelism. However, simple yet clever approaches can achieve \log n critical path lengths.

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 Investigate

class ArraysHolder

getSrc()
getDst()
nextSrcAndDst()

class PowersOfTwoLessThan

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