HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

List Ranking on PC Clusters

Isabelle Guérin Lassous Jens Gustedt 1
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present two algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM for short): if $p$ is the number of processors and $n$ the size of the list, then we give a deterministic one that achieves $O(\log p \log^* p)$ communication rounds and $O(n \log^* p)$ for the required communication cost and total computation time; and a randomized one that requires $O(\log p)$ communication rounds and $O(n)$ for the required communication cost and total computation time. We report on experimental studies of these algorithms on a PC cluster interconnected by a Myrinet network. As far as we know, it is the first portable code on this problem that runs on a cluster. With these experimental studies, we study the validity of the chosen CGM-model, and also show the possible gains and limits of such algorithms for PC clusters.
Document type :
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:53:31 AM
Last modification on : Friday, February 4, 2022 - 3:22:13 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:22:21 PM


  • HAL Id : inria-00072785, version 1



Isabelle Guérin Lassous, Jens Gustedt. List Ranking on PC Clusters. [Research Report] RR-3869, INRIA. 2000, pp.14. ⟨inria-00072785⟩



Record views


Files downloads