So Hillis and Steele scan is fairly efficient.
It's actually the first scan to be implemented on GPUs.
Guy Blelloch popularized another formulation of scan in 1990, however,
that is even better at work efficiency.
It's a little bit more complex in terms of the algorithm though, so let's take a look at another example.
This algorithm has 2 stages--first to reduce, then to downsweep.
And let's note that this is an exclusive scan.
So we're going to do a sum scan that is exclusive, on the input array 1 through 8.
And so it's going to, again, have 2 stages.
The first is going to be a reduction, and it looks similar to the reductions that we've seen already.
And then the second stage is going to be new.
It's going to be a downsweep, and so that's going to take a different operator than we've seen before.
Let's start with the reduction. The reduce step actually looks like a fairly standard reduction.
The first step adds neighbors 1 hop away.
The next step adds neighbors 2 hops away.
And the third step is going to add neighbors 4 hops away.
However, unlike in reduce, we're going to keep the intermediate results around.
By intermediate results I mean this 1, this 3, this 3, this 10, 5, 11 and 7
because we're going to use them during the downsweep step.
Now step 2, the downsweep.
We're going to start by resetting the rightmost piece of data to the identify operator.
For sum, that identify operator is 0 and now we're going to use a communication
pattern that is exactly the same as what we saw in the reduction step except in mirror image.
So we see that we have this triangle kind of structure here.
We're going to do the same thing upside down when we do downsweep.
But what's going to be different about downsweep are 2 things.
The first one is that we're going to use a different operator.
So each operator is going to take 2 inputs, just as we did in reduction,
a left input and a right input, but it's going to produce 2 outputs, not 1.
So the left-most output is simply the right output copied to the left.
The right output is equal to the sum because we're doing sum scan of the 2 inputs.
The second thing that's a little bit different is that we're going to be using these intermediate results.
As we need to do a downsweep between 2 elements, some of the downsweep operators might
be written down here because we've derived them during the down-sweep.
But if we're missing a piece of data, then we just simply drag down the piece of data
that we need from the intermediate results that we stored up here during the reduce.
So let's get started. We're going to being the downsweep by operating on this element and this element.
That's, again, the mirror image of the communication pattern that we had before.
So since we don't have an element written here,
we'll just copy it down from the element that we have, right?
So now we'll apply this down sweep operator to this pair of elements.
The first we're going to do is we're going to take this 0, copy it over here.
And then we'll take this 10, add it to this 0, and get 10.
Now, we're going to operate on elements 2 to our left.
So, the 10 is going to be paired with this 11 here, that we've dragged down.
The 0 is going to be paired with this 3. So 0 will be copied over to the left.
Three and 0 will be added to get a 3 here.
Ten will be copied to the left, and 11 plus 10 is 21.
Now for the final step, each of these elements will be paired with the item to its left.
So, again, we're going to have to drag down intermediate values we kept around.
We're going to drag down the 7, drag down this 5, drag down this 3, drag down this 1.
And then for the final time apply your downsweep operator--
0, 0 plus 1 is 1, copy the 3, 3 and 3 make 6.
Copy the 10, 10 and 5 makes 15. Copy the 21, 7 and 21 make 28.
So now our output sequence is 0, 1, 3, 6, 10, 15, 21, 28,
which is the exclusive sum scan of the input of the vector from 1 to 8.
What we see, for instance, is that every output such as this 21 here--
21 is the sum of all the elements that came before.
So 21 is the sum of 1 to 6, and so on.
As a quiz I'd like you to compute the max scan of this input sequence--
2 1 4 3, using this reduced downsweep method.
So you're going to fill in these values from reduction and then fill in each of these values from a downsweep.
And when you finish you should have the max scan,
the max exclusive scan of these elements given these inputs.
So give it a shot.