| 词条 | Pointer jumping |
| 释义 |
List rankingOne of the simpler tasks that can be solved by a pointer jumping algorithm is the list ranking problem. This problem is defined as follows: given a linked list of {{mvar|N}} nodes, find the distance (measured in the number of nodes) of each node to the end of the list. The distance {{mono|d(n)}} is defined as follows, for nodes {{mono|n}} that point to their successor by a pointer called {{mono|next}}:
This problem can easily be solved in linear time on a sequential machine, but a parallel algorithm can do better: given {{mvar|n}} processors, the problem can be solved in logarithmic time, {{math|O(log N)}}, by the following pointer jumping algorithm:[2]{{rp|693}} {{framebox|blue}}
The pointer jumping occurs in the last line of the algorithm, where each node's {{mono|next}} pointer is reset to skip the node's direct successor. It is assumed, as in common in the PRAM model of computation, that memory access are performed in lock-step, so that each {{mono|n.next.next}} memory fetch is performed before each {{mono|n.next}} memory store; otherwise, processors may clobber each other's data, producing inconsistencies.{{r|clrs}}{{rp|694}} Analyzing the algorithm yields a logarithmic running time. The initialization loop takes constant time, because each of the {{mvar|N}} processors performs a constant amount of work, all in parallel. The inner loop of the main loop also takes constant time, as does (by assumption) the termination check for the loop, so the running time is determined by how often this inner loop is executed. Since the pointer jumping in each iteration splits the list into two parts, one consisting of the "odd" elements and one of the "even" elements, the length of the list pointed to by each processor's {{mono|n}} is halved in each iteration, which can be done at most {{math|O(log N)}} time before each list has a length of at most one.{{r|clrs}}{{rp|694–695}} Root findingFollowing a path in a graph is an inherently serial operation, but pointer jumping reduces the total amount of work by following all paths simultaneously and sharing results among dependent operations. Pointer jumping iterates and finds a successor — a vertex closer to the tree root — each time. By following successors computed for other vertices, the traversal down each path can be doubled every iteration, which means that the tree roots can be found in logarithmic time. Pointer doubling operates on an array successor with an entry for every vertex in the graph. Each successor[i] is initialized with the parent index of vertex i if that vertex is not a root or to i itself if that vertex is a root. At each iteration, each successor is updated to its successor's successor. The root is found when the successor's successor points to itself. The following pseudocode demonstrates the algorithm. '''Input:''' An array parent representing a forest of trees. parent[i] is the parent of vertex i or itself for a root '''Output:''' An array containing the root ancestor for every vertex '''for''' ''i'' ← 1 '''to''' length(parent) '''do in parallel''' successor[''i''] ← parent[''i''] '''while''' true '''for''' ''i'' ← 1 '''to''' length(successor) '''do in parallel''' successor_next[''i''] ← successor[successor[''i'']] '''if''' successor_next = successor '''then''' break '''for''' ''i'' ← 1 '''to''' length(successor) '''do in parallel''' successor[''i''] ← successor_next[''i''] '''return''' successor The following image provides an example of using pointer jumping on a small forest. On each iteration the successor points to the vertex following one more successor. After two iterations, every vertex points to its root node. References1. ^{{cite books |first=Joseph |last=JáJá |title=An Introduction to Parallel Algorithms |publisher=Addison Wesley |year=1992 |isbn=0-201-54856-9}} {{Parallel computing}}2. ^{{Introduction to Algorithms|edition=2}} 2 : Algorithms|Parallel computing |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。