Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Matthieu Garrigues Connect in order to contact the contributor
Submitted on : Wednesday, February 18, 2015 - 5:39:47 PM
Last modification on : Friday, December 3, 2021 - 11:34:10 AM
Long-term archiving on: : Tuesday, May 19, 2015 - 10:55:27 AM


Files produced by the author(s)


  • HAL Id : hal-01118331, version 1



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



Les métriques sont temporairement indisponibles