List ranking
Encyclopedia
In parallel algorithm
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 write, 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.
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.
List ranking can equivalently be viewed as performing a prefix sum
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
via an Euler tour 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.
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
s, the list ranking problem involves determining the position, or rank, of each item in a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
. 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 write, 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.
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
Parallel Random Access Machine
In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine...
. This number of steps matches the sequential algorithm.
List ranking can equivalently be viewed as performing a prefix sum
Prefix sum
In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....
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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
via an Euler tour 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.