So let's try a slightly harder algorithm called list ranking.
In list ranking, each node has the index of its successor in the list,
and we know the first element in the output.
What we want to be able to do is put the nodes in order.
This has a number of uses, and in our lab, we've used it to decompress data
that's been compressed with B sub 2, so let's take a look at an example.
As an example we've got 10 nodes here.
We know that the output is going to begin with node 0
and the successor to node 0, so one farther in the chain is node 5.
The successor to node 5 is node 2.
The successor to node 2 is node 7 and so on.
So this is our input--this array of 5, 6, 7, 9, 2, 3, 0, 1.
What's our output going to be?
It's going to be the chain 0, 5, 2, 7, 4, 9, 1, 6, 3, 8.
So here's our input, and here's the output.
Now, you can note that the array is actually circular,
so it's necessary to actually designate the starting point,
and in this case we're saying that node number 0 is the starting point.
Of course, a serial processor could do this N steps.
The question is, how can we make it work with parallel hardware
with a smaller number of steps?
我们尝试一个稍难的算法,叫做列表排名。
在列表排名中,每个节点都有它在列表中
的后继节点的索引,
我们知道输出中的第一个元素。
我们希望做的是把节点排序。
这有很多用途,在我们实验室,我们用它来解压
被B sub2压缩的数据。那么让我们来看个例子。
例如,这里我们有10个节点。
我们知道输出将开始于节点0
及其后继节点,即链中前进一位是节点5。
节点5的后继节点是节点2。
节点2的后继节点是节点7,等等。
所以这是我们的输入—数组5、6、7、9、2、3、0、1。
我们的输出是什么?
输出会是0、5、2、7、4、9、1、6、3、8。
所以这是我们的输入,这是输出。
现在,你注意到数组实际上是圆形的,
所以有必要实际指定起点,
在这个例子中,我们说节点0是起点。
当然,一个串行处理器可以用N步完成这个。
问题是,我们如何让它在并行硬件上进行,
用更少的步骤完成?