View source for Work Efficient Parallel Scan Assignment

=Background=
A [https://en.wikipedia.org/wiki/Prefix_sum#Algorithm_2:_Work-efficient work-efficient parallel scan] was developed by [http://www.cs.cmu.edu/~guyb/ Guy Blelloch] and outlined in: [https://www.cs.cmu.edu/~guyb/papers/sc90.pdf Scan Primitives for Vector Computers] and [https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf Prefix Sums and Their Applications].

{{CollapsibleYouTube|Blelloch Scan|<youtube>mmYv3Haj6uc</youtube>}}

=Comparison=
In the two circuit diagrams, you can see that there is less work to do in Blelloch scan, although there are more steps (but not asymptotically more, both scans provide lg(N) spans/critical path lengths).

{| class="wikitable"
|+ Comparison of Parallel Scans
|-
! Blelloch (Work Efficient) !! <== ==> !! Hillis and Steele (Step Efficient)
|-
| [[File:Prefix sum 16.svg]] || || [[File:Hillis-Steele Prefix Sum.svg]]
|}

=Code To Implement=
You may choose to implement either Inclusive or Exclusive Blelloch Scan. This is an in-place mutating scan algorithm, which means you can mutate the original data array.

===Inclusive Scan or Blelloch Exclusive Scan===
{{CodeToImplement|WorkEfficientParallelMutatingSumScanner|IsInclusive|scan.challenge}}

{{Sequential|public boolean isInclusive()}}
: Here you can indicate whether you will implement inclusive or exclusive scan.

{{CodeToImplement|WorkEfficientParallelMutatingSumScanner|sumScan|scan.challenge}}

{{Parallel|void sumScan(int[] data)}}

=Testing Your Solution=
{{TestSuite|_WorkEfficientScanTestSuite|scan.challenge}}