- All Implemented Interfaces:
- java.io.Serializable, java.util.concurrent.Future<java.lang.Void>
- Direct Known Subclasses:
- PAS.FJDScan, PAS.FJLScan, PAS.FJOScan
- Enclosing class:
- PAS
abstract static class PAS.FJScan
extends jsr166y.ForkJoinTask<java.lang.Void>
Cumulative scan
A basic version of scan is straightforward.
Keep dividing by two to threshold segment size, and then:
Pass 1: Create tree of partial sums for each segment
Pass 2: For each segment, cumulate with offset of left sibling
See G. Blelloch's http://www.cs.cmu.edu/~scandal/alg/scan.html
This version improves performance within FJ framework mainly by
allowing second pass of ready left-hand sides to proceed even
if some right-hand side first passes are still executing. It
also combines first and second pass for leftmost segment, and
for cumulate (not precumulate) also skips first pass for
rightmost segment (whose result is not needed for second pass).
To manage this, it relies on "phase" phase/state control field
maintaining bits CUMULATE, SUMMED, and FINISHED. CUMULATE is
main phase bit. When false, segments compute only their sum.
When true, they cumulate array elements. CUMULATE is set at
root at beginning of second pass and then propagated down. But
it may also be set earlier for subtrees with lo==origin (the
left spine of tree). SUMMED is a one bit join count. For leafs,
set when summed. For internal nodes, becomes true when one
child is summed. When second child finishes summing, it then
moves up tree to trigger cumulate phase. FINISHED is also a one
bit join count. For leafs, it is set when cumulated. For
internal nodes, it becomes true when one child is cumulated.
When second child finishes cumulating, it then moves up tree,
executing complete() at the root.
This class maintains only the basic control logic. Subclasses
maintain the "in" and "out" fields, and *Ops classes perform
computations.