de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Practical Parallel List Ranking

MPG-Autoren

Sibeyn,  Jop F.
Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44543

Guillaume,  Frank
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45450

Seidel,  Tillmann
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Sibeyn, J. F., Guillaume, F., & Seidel, T. (1997). Practical Parallel List Ranking. In G. Bilardi, A. Ferreira, R. Lüling, & J. Rolim (Eds.), Proceedings of the 4th Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR-97) (pp. 25-36). Berlin: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3972-0
Zusammenfassung
Parallel list ranking is a hard problem due to its extreme degree of irregularity. Also because of its linear sequential complexity, it requires considerable effort to just reach speed-up one (break even). In this paper, we address the question of how to solve the list-ranking problem for lists of length up to $2 \cdot 10^8$ in practice: we consider implementations on the Intel Paragon, whose PUs are laid-out as a grid. It turns out that pointer jumping, independent-set removal and sparse ruling sets, all have practical importance for current systems. For the sparse-ruling-set algorithm the speed-up strongly increases with the number $k$ of nodes per PU, to finally reach $27$ with 100 PUs, for $k = 2 \cdot 10^6$.