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.
Type de document :
[Research Report] RR-3869, INRIA. 2000, pp.14
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:53:31
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:22:21



  • 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〉



Consultations de la notice


Téléchargements de fichiers