Exact and Approximate Median Splitting on Distributed Memory Machines

Abstract : — We present in this paper a new fine grained me-dian split algorithm which places the median on the middle index of an input array of size N . Running on P processors, the randomized version converges in O N P × (log(N) + µ) average time where 0 < P < N 4 and µ is the time to swap a pair of elements between two nodes. At each iteration, the nodes process only its local elements and exchange part of them with another processor of the network. This makes it a decentralized parallel algorithm and offers the possibility to take advantage of massively parallel computing networks based on distributed memory systems.
Type de document :
Communication dans un congrès
PDPTA, 2012, Las Vegas, United States
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01118331
Contributeur : Matthieu Garrigues <>
Soumis le : mercredi 18 février 2015 - 17:39:47
Dernière modification le : vendredi 8 décembre 2017 - 14:42:15
Document(s) archivé(s) le : mardi 19 mai 2015 - 10:55:27

Fichier

parallel_median_pdpta.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01118331, version 1

Collections

Citation

Matthieu Garrigues, Antoine Manzanera. Exact and Approximate Median Splitting on Distributed Memory Machines. PDPTA, 2012, Las Vegas, United States. 〈hal-01118331〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

55