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

# 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 :
Document type :
Reports
Domain :

Cited literature [11 references]

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

### Identifiers

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

Record views