- 1 Motivation
- 2 Background
- 3 Code To Investigate
- 4 Code To Implement
- 5 Testing Your Solution
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 critical path lengths.
While we will simply implement prefix sum, scan can be used for other associative operations.
Hillis-Steele Prefix Sum
One of the applications for scan is pack operation. Given an input array, the operation produces an output array containing only the elements that satisfy some specified predicate.
The problem with parallelizing pack is that although it is easy to determine whether an element should be filtered out into the output, we can't know where to put the element in the output array. It seems that placing an element into the output requires knowledge of the placement of the previous elements.
This is where prefix sum becomes very useful. For example, if you have an integer array input:
You want to filter out all elements that are less than five. You can first create a flag array in which all the positions i where input[i] is less than 5 is flagged as "1" and all other positions are marked as "0".
The prefix sum of this flag array is:
Notice how each position that that was flagged now has a distinct number assigned to it in the prefix sum array. We can use this to help us index the output array.
(Optional) Work-efficient Blelloch Scan
Code To Investigate
Code To Implement
Default Arrays Holder
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
nextSrcAndDst used appropriately from a parallel scan.
NOTE: think about which array is the correct one to return from your scan method given how you write your code.
Hillis and Steele Parallel Scan
(Optional) Blelloch Work Efficient Scan
Testing Your Solution
Optional Work Efficient