Difference between revisions of "Scan"

From CSE231 Wiki
Jump to: navigation, search
(Code To Implement)
Line 44: Line 44:
 
=Code To Implement=
 
=Code To Implement=
 
==Sequential Scan==
 
==Sequential Scan==
{{CodeToImplement|SequentialScan|sumScan|scan.studio}}
+
{{CodeToImplement|SequentialScan|sumScanInclusive|scan.studio}}
  
{{Sequential|public int[] sumScan(int[] data)}}
+
{{Sequential|public static int[] sumScanInclusive(SwappableIntArrays swappable)}}
  
==Default Arrays Holder==
+
==SwappableIntArrays==
 
One of the downsides to parallel scan requires memory.  For our scans we add the additional requirement that we will not mutate the incoming array parameter.  We could create log(n) arrays, one for each level but that would be wasteful.  If we create two array buffers and switch which is the source to read from and which is the destination to write from at each power of two level of the scan, we should be good to go.
 
One of the downsides to parallel scan requires memory.  For our scans we add the additional requirement that we will not mutate the incoming array parameter.  We could create log(n) arrays, one for each level but that would be wasteful.  If we create two array buffers and switch which is the source to read from and which is the destination to write from at each power of two level of the scan, we should be good to go.
  
The table below shows which array will be passed back for each offset if <code>nextSrcAndDst</code> used appropriately from a parallel scan.
+
The table below shows which array will be passed back for each offset if <code>swap</code> used appropriately from a parallel scan.
 
{|class="wikitable"
 
{|class="wikitable"
 
! ||1|||2||4||8||16
 
! ||1|||2||4||8||16
Line 66: Line 66:
 
==Hillis and Steele Parallel Scan==
 
==Hillis and Steele Parallel Scan==
  
{{CodeToImplement|ParallelScan|sumScan|scan.studio}}
+
{{CodeToImplement|StepEfficientParallelScan|sumScanInclusive|scan.studio}}
  
 
{{Parallel|public int[] sumScan(int[] data)}}
 
{{Parallel|public int[] sumScan(int[] data)}}
  
 
==(Optional) Blelloch Work Efficient Scan==
 
==(Optional) Blelloch Work Efficient Scan==
{{CodeToImplement|WorkEfficientScan|sumScan|scan.challenge}}
+
{{CodeToImplement|WorkEfficientParallelScan|sumScanExclusiveInPlace|scan.challenge}}
  
{{Parallel|public int[] sumScan(int[] data)}}
+
{{Parallel|public static void sumScanExclusiveInPlace(int[] data)}}
  
 
=Testing Your Solution=
 
=Testing Your Solution=

Revision as of 05:43, 12 March 2019

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

Hillis-Steele Prefix Sum

Hillis and Steele Algorithm

Hillis-Steele Prefix Sum.svg


(Optional) Work-efficient Blelloch Scan

Blelloch Algorithm

Prefix sum 16.svg

Code To Investigate

class ArraysHolder

getSrc()
getDst()
nextSrcAndDst()

class PowersOfTwoLessThan implements Iterable<Integer>

The Core Questions

  • What are the tasks?
  • What is the data?
  • Is the data mutable?
  • If so, how is it shared?

Code To Implement

Sequential Scan

class: SequentialScan.java Java.png
methods: sumScanInclusive
package: scan.studio
source folder: src/main/java

method: public static int[] sumScanInclusive(SwappableIntArrays swappable) Sequential.svg (sequential implementation only)

SwappableIntArrays

One of the downsides to parallel scan requires memory. For our scans we add the additional requirement that we will not mutate the incoming array parameter. We could create log(n) arrays, one for each level but that would be wasteful. If we create two array buffers and switch which is the source to read from and which is the destination to write from at each power of two level of the scan, we should be good to go.

The table below shows which array will be passed back for each offset if swap used appropriately from a parallel scan.

1 2 4 8 16
src: data a b a b
dst: a b a b a

NOTE: think about which array is the correct one to return from your scan method given how you write your code.

class: DefaultArraysHolder.java Java.png
methods: getSrc
getDst
nextSrcAndDst
size
package: scan.studio
source folder: src/main/java

Hillis and Steele Parallel Scan

class: StepEfficientParallelScan.java Java.png
methods: sumScanInclusive
package: scan.studio
source folder: src/main/java

method: public int[] sumScan(int[] data) Parallel.svg (parallel implementation required)

(Optional) Blelloch Work Efficient Scan

class: WorkEfficientParallelScan.java Java.png
methods: sumScanExclusiveInPlace
package: scan.challenge
source folder: src/main/java

method: public static void sumScanExclusiveInPlace(int[] data) Parallel.svg (parallel implementation required)

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