Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

Parallel Merge Sort for Distributed Memory Architectures

Abstract : Cole presented a parallel merge sort for the PRAM model that performs in log n parallel steps using n processors. He gave an algorithm for the CREW PRAM model for which the constant in the running time is small. He also gave a more complex version of the algorithm for the EREW PRAM; the constant factor in the running time is still moderate but not as small. In this paper we give an approach to implement Cole's parallel merge sort on a distributed memory architecture. Both, the CREW and the EREW algorithms have been considered. A data placement algorithm is presented as well as the associated data movements. Our proposition sorts n items using exactly n processors in log n parallel time. The constant in the running time is only one greater than the one obtained for the PRAM model.
Document type :
Reports
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101948
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:31 AM
Last modification on : Saturday, September 11, 2021 - 3:18:55 AM

File

RR1994-05.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101948, version 1

Collections

Citation

Jean-Marc Adamo, Luis Trejo. Parallel Merge Sort for Distributed Memory Architectures. [Research Report] LIP RR-1994-05, Laboratoire de l'informatique du parallélisme. 1994, 2+35p. ⟨hal-02101948⟩

Share

Metrics

Record views

16

Files downloads

46