Let's recap what you've done.
You've replaced the conventional linked list representation with one based on
arrays.
With that you're now ready to go parallel.
To help you do that, I'm going to give you a handy primitive called a jump.
Here's a picture of a jump.
Oh wait, sorry, wrong picture.
Let's try again.
Suppose you're looking at a specific linked list node.
In a jump, you move the next pointer so
that it points to the neighbor's neighbor.
So take this next pointer, for example, and
let's replace it with a pointer to the neighbor's neighbor.
Now, think about this for a second.
What the!
Bad billy goat!
What would happen, if at every node in the list,
you did a jump at exactly the same time?
Let's try it and see.
So here's the list.
At every node, do a jump.
Notice what you've just done.
You've effectively split the list into two sub lists.
As you can imagine, that's exactly what you need to do divide and conquer.
Now if you keep doing this, these sub lists will get shorter and shorter and
you'll get more and more of them.
Jump.
Given a set of next pointers as input,
you can perform a jump in parallel using this algorithm.
And notice that the new algorithm puts the jump pointers in a new output array
called N sub out.
So for each node i, we check to see if the next pointer is nil and
if it's not, we do a jump.
By placing the output in a separate output array, we avoid collisions and
that's what makes it safe to use parallel for.
Okay, you're almost ready for the parallel list ranking algorithm.
So far you've seen three ideas.
The first is to store the list as an array pool.
The second is to recognize the list ranking is roughly an add scan.
Of course you need to set the right initial values.
And finally if we have a jump operation, we can do divide and conquer.
Go ahead and put these ideas together.
You've established that a linked list has an equivalent array pool
representation.
So when I sketch the algorithm, I'll draw a linked list in the old
fashioned way, but you always know that there's an array pool equivalent.
What about treating the list ranking as an add scan?
Remember that the key idea here was to choose the right set of initial values
at each node.
So we put a 0 at the head and 1's everywhere else.
So now we can apply the third idea which is to use jumps to get sublists.
If you jump repeatedly, you know the sub list will get shorter and shorter.
At the same time, you'll be transforming this list, so
you're going to have to do something with these initial values.
How about this, let's maintain an invariant.
The invariant will be, if we take any node i, and
we start at the head of its sub list, and
then let's say we traverse the sub list, and we add up all the values.
Then we'll get exactly the rank of i.
So for the initial values, you can easily check that this holds.
Now suppose I've done a bunch of jumps and I'm looking at a particular sublist.
So here I'm just in the middle of some sublist.
And let's further suppose that the invariant holds.
Now let's jump everywhere simultaneously.
You'll get a list that looks like this.
Now notice what happened.
For this node here, we effectively cut 4 out of its sublist, but
we need to maintain this invariant.
So we can't just drop the value 4, we've got to incorporate it somehow.
An easy way to do that would just be to absorb 4's value.
So 12 would become 16.
The way this can work is before we do a jump from 4, we take the value of 4 and
push it to its successor.
Okay. Let's give this a try.
Let's do one step of the update and jump.
For the update every node pushes its value to its successor.
Then we do the jump to create two sublists.
And let's just repeat this process.
Push, jump,
push, jump.
Once every node is a stand alone node you are done.
Now I already gave you a subroutine to perform the jumps.
What about the updates?
Here's an algorithm for just the update step, which is parallel.
So for each node i, we take its value and we push it to the successor..
We'll do all the rights to a separate array of ranks.
This way we can do all these updates in parallel.
Okay. You're now almost ready to see
the final algorithm.