Exact and Approximate Median Splitting on Distributed Memory Machines - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Exact and Approximate Median Splitting on Distributed Memory Machines

Matthieu Garrigues
Antoine Manzanera

Résumé

— 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.
Fichier principal
Vignette du fichier
parallel_median_pdpta.pdf (275.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01118331 , version 1 (18-02-2015)

Identifiants

  • HAL Id : hal-01118331 , version 1

Citer

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

Collections

ENSTA ENSTA_U2IS
70 Consultations
57 Téléchargements

Partager

Gmail Facebook X LinkedIn More