In
parallel algorithm
In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machin ...
s, the list ranking problem involves determining the position, or rank, of each item in a
linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.
History
The list ranking problem was posed by , who solved it with a parallel algorithm using logarithmic time and O(''n'' log ''n'') total steps (that is, O(''n'') processors). Over a sequence of many subsequent papers, this was eventually improved to linearly many steps (O(''n''/log ''n'') processors), on the most restrictive model of synchronous shared-memory parallel computation, the exclusive read exclusive write
PRAM (; ;). This number of steps matches the sequential algorithm.
Related problems
List ranking can equivalently be viewed as performing a
prefix sum In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers is a second sequence of numbers , the sums of prefixes ( running totals) of the input sequence:
:
:
:
:...
For instance, the prefix sums ...
operation on the given list, in which the values to be summed are all equal to one. The list ranking problem can be used to solve many problems on
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
via an
Euler tour
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
technique, in which one forms a linked list that includes two copies of each edge of the tree, one in each direction, places the nodes of this list into an ordered array using list ranking, and then performs prefix sum computations on the ordered array . For instance, the height of each node in the tree may be computed by an algorithm of this type in which the prefix sum adds 1 for each downward edge and subtracts 1 for each upward edge.
References
*.
*.
*.
*.
*{{citation
, last = Wyllie , first = J. C.
, title = The Complexity of Parallel Computation
, publisher = Ph.D. thesis, Department of Computer Science,
Cornell University
Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to tea ...
, year = 1979.
Parallel computing