Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-1999-1-005

Ultimate parallel list ranking?

Sibeyn, Jop F.

MPI-I-1999-1-005. September 1999, 20 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-1999-1-005.ps199 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1999-1-005
Hide details for BibTeXBibTeX
@TECHREPORT{Sibeyn1999,
  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},
}