Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Created page with "=Background= <youtube>RdfmxfZBHpo</youtube> <youtube>mmYv3Haj6uc</youtube>")
 
Line 1: Line 1:
 +
=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=
 
=Background=
 
<youtube>RdfmxfZBHpo</youtube>
 
<youtube>RdfmxfZBHpo</youtube>
  
 
<youtube>mmYv3Haj6uc</youtube>
 
<youtube>mmYv3Haj6uc</youtube>
 +
 +
=Code To Implement=
 +
==Sequential Scan==
 +
{{CodeToImplement|SequentialScan|sumScan|scan.studio}}
 +
 +
{{Sequential|public int[] sumScan(int[] data)}}
 +
 +
==Hillis and Steele Parallel Scan==
 +
{{CodeToImplement|ParallelScan|sumScan|scan.studio}}
 +
 +
{{Sequential|public int[] sumScan(int[] data)}}
 +
 +
==(Optional) Blelloch Work Efficient Scan==
 +
{{CodeToImplement|WorkEfficientScan|sumScan|scan.challenge}}
 +
 +
{{Sequential|public int[] sumScan(int[] data)}}
 +
 +
=Testing Your Solution=
 +
==Correctness==
 +
===Required===
 +
{{TestSuite|ScanTestSuite|scan.studio}}
 +
===Optional Work Efficient===
 +
{{TestSuite|WorkEfficientScanTestSuite|scan.challenge}}

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

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