# List Ranking on PC Clusters

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.
Keywords :
Type de document :
Rapport
[Research Report] RR-3869, INRIA. 2000, pp.14
Domaine :

Littérature citée [11 références]

https://hal.inria.fr/inria-00072785
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

### Identifiants

• HAL Id : inria-00072785, version 1

### Citation

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

### Métriques

Consultations de la notice

## 198

Téléchargements de fichiers