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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101948
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:31 AM
Last modification on : Friday, May 17, 2019 - 1:39:19 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

5

Files downloads

14