指针跳转

指针跳转或路径加倍是一种设计技术，用于操作指针结构的并行算法，如链接列表和有向图。指针跳转允许算法以相对于最长路径长度的对数时间复杂度来跟踪路径。它通过跳转到由邻居计算的路径的末端来实现这一点。指针跳转的基本操作是将指针结构中的每个邻居替换为其邻居的邻居。在算法的每一步中，这种替换是针对数据结构中的所有节点进行的，这可以独立地并行进行。在下一步中，当邻居的邻居被跟踪时，在上一步中已经被跟踪的邻居的路径被添加到节点被跟踪的路径中，这是一个单一的步骤。因此，每一步都有效地将探索的路径所穿越的距离加倍。指针跳转xxx通过观察简单的例子来理解，如列表排名和寻根。

可以用指针跳转算法解决的较简单的任务之一是列表排名问题。这个问题定义如下：给定一个有N个节点的链接列表，找出每个节点到列表末端的距离（用节点数衡量）。距离d(n)定义如下，对于节点n来说，它通过一个叫做next的指针指向其后继者。如果n.next是nil，那么d(n)=0。对于任何其他节点，d(n)=d(n.next)+1。这个问题在顺序机器上很容易用线性时间解决，但是并行算法可以做得更好：给定n个处理器，这个问题可以用对数时间解决，O(logN)，通过以下指针跳跃算法。分配一个N个整数的数组。初始化：对于每个处理器/列表节点n，并行：如果n.next=nil，设置d[n]←0。否则，设置d[n]←1。在算法的最后一行发生指针跳转，每个节点的下一个指针被重置以跳过节点的直接继承者。正如PRAM计算模型中常见的那样，假设内存访问是以锁步方式进行的，因此每个n.next.next内存的获取都是在每个n.next内存的存储之前进行的；否则，处理器可能会破坏彼此的数据，产生不一致的情况。下图是并行列表排名算法如何对一个有11个元素的链接列表使用指针跳转。正如该算法所描述的，xxx次迭xxx始时，所有的等级都被设置为1，除了那些有空指针的下一个。xxx次迭代看的是近邻。之后的每一次迭代都是前一次迭代的两倍。分析该算法可以得到一个对数的运行时间。初始化循环需要恒定的时间，因为N个处理器中的每一个都执行恒定数量的工作，而且都是并行的。主循环的内循环也需要恒定的时间，就像（假设）循环的终止检查一样，所以运行时间是由这个内循环的执行频率决定的。由于每次迭代中的指针跳跃将列表分成两部分，一部分由奇数元素组成，另一部分由偶数元素组成，因此每个处理器的n所指向的列表的长度在每次迭代中减半，在每个列表的长度最多为1之前，最多可以用O（logN）时间完成。

找根追踪图中的路径本来就是一个串行操作，但指针跳转通过同时追踪所有路径并在依赖性操作中分享结果来减少总的工作量。指针跳转每次都会迭代并找到一个继任者–一个更接近树根的顶点。通过跟踪为其他顶点计算的继任者，每一次迭代都可以将每个路径的遍历翻倍，这意味着可以在对数时间内找到树根。指针翻倍是在一个数组succeror上进行的，数组中的每一个顶点都有一个条目。每个successor[i]被初始化为顶点i的父索引，如果该顶点不是根，则初始化为i本身，如果该顶点是根。