**Definitions:** *List ranking* finds the distance of
each vertex from the head of a linked list. *List scan*
(parallel prefix) is similar. It compute for each vertex the "sum" of
the weights of prior vertices in the linked list, where "sum" is a
binary associative operator.

**Performance:** We implemented and compared four
parallel list ranking algorithms, and also compared them with a serial
version. The serial algorithm is trivial. Simply traverse each link
in the linked list counting the links. Wyllie's algorithm is the
simplest parallel algorithm. But it is not work efficient, and so its
performance degrades for longer linked lists. The Miller/Reif
algorithm is the simplest randomized algorithm but requires load
balancing. The Anderson/Miller algorithm is also randomized but does
not require any load balancing. We did not spend much time optimizing
the code for the above algorithms. But we expect their performance to
be within a factor of 2 or 3 of optimized code. Finally, the
Blelloch/Reid-Miller algorithm is the algorithm we developed. The
figure below shows the results of the five algorithms on one processor
of the Cray Y-MP/C90. The parallel algorithms are vectorized and
scale almost linearly on multiple processors. On eight processors our
algorithm can process one link of a linked list every 4.6 nsec.

**Papers:**Margaret Reid-Miller and Guy Blelloch wrote an
article List
Ranking and List Scan on the Cray C-90 that describes the
five list ranking algorithms, the vector multiprocessor implementation
and performance of the algorithms on the Cray C-90, and the
performance analysis of their algorithm. Margaret Reid-Miller gave a
presentation
of the work at SPAA'94.

Up to the Irregular Algorithms page.

mrmiller@cs.cmu.edu Last updated 16 June 1998