MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Ultimate parallel list ranking?

Sibeyn, Jop F.

September 1999, 20 pages.

Status: available - back from printing

Two improved list-ranking algorithms are presented. The ``peeling-off'' algorithm leads to an optimal PRAM algorithm, but was designed with application on a real parallel machine in mind. It is simpler than earlier algorithms, and in a range of problem sizes, where previously several algorithms where required for the best performance, now this single algorithm suffices. If the problem size is much larger than the number of available processors, then the ``sparse-ruling-sets'' algorithm is even better. In previous versions this algorithm had very restricted practical application because of the large number of communication rounds it was performing. This main weakness of this algorithm is overcome by adding two new ideas, each of which reduces the number of communication rounds by a factor of two.

  • Attachement: (199 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Sibeyn, Jop F.},
  TITLE = {Ultimate parallel list ranking?},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-1999-1-005},
  MONTH = {September},
  YEAR = {1999},
  ISSN = {0946-011X},