MPI-INF D1 Publications: Proceedings Article: Ultimate Parallel List Ranking?

URL of the conference:
URL for downloading the paper:
Event Address*:	Calcutta	Language:	English
Event Date* (no longer used):	~~December 17-20, 1999~~	Organization:	IEEE
Event Start Date:	17 December 1999	Event End Date:	20 December 1999

Publisher

Name*:	Springer	URL:
Address*:	Berlin	Type:

Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:	1745	Number:
Month:	December	Pages:	197-201
Year*:	1999	VG Wort Pages:
ISBN/ISSN:	0302-9743	Sequence Number:
DOI:


(LaTeX) Abstract:	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 weakness is overcome by adding two new ideas, each of which reduces the number of communication rounds by a factor of two.
Keywords:	Algorithms, Parallel Computing, List-Ranking


Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	Expert
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:

@INPROCEEDINGS{F.Sibeyn-HiPC-1999,
AUTHOR = {Sibeyn, Jop F.},
EDITOR = {Banerjee, Prith and Prasanna, Viktor K. and Sinha, Bhabani F.},
TITLE = {Ultimate Parallel List Ranking?},
BOOKTITLE = {Proceedings of the 6th International Conference on High Performance Computing (HiPC-99)},
PUBLISHER = {Springer},
YEAR = {1999},
ORGANIZATION = {IEEE},
VOLUME = {1745},
PAGES = {197--201},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Calcutta},
MONTH = {December},
ISBN = {0302-9743},
}

Entry last modified by Uwe Brahm, 03/02/2010

Edit History (please click the blue arrow to see the details)

	Editor(s) Jop F. Sibeyn	Created 02/19/2000 03:29:15 PM
Revisions 3. 2. 1. 0.	Editor(s) Uwe Brahm Uwe Brahm Anja Becker Jop F. Sibeyn	Edit Dates 02/14/2005 08:07:25 PM 02/14/2005 08:06:31 PM 29.03.2000 14:25:36 19/02/2000 15:29:15

Attachment Section