Parallel Merge Sort for Distributed Memory Architectures

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.Cole a présenté un algorithme de tri de fusion parallèle pour le modèle de calcul PRAM, qui s’exécute en O(log n) étapes parallèles en utilisant n processeurs. Dans son article il donne un algorithme pour le modèle CREW PRAM dans lequel la constante du temps d'exécution est modérée, ainsi qu'une version plus complexe pour le modèle CREW PRAM; la constante du temps d'exécution est toujours modérée mais moins que dans la version CREW PRAM Dans ce rapport nous donnons une approche pour l'implémentation du tri de Cole sur une architecture à mémoire distribuée. Les deux versions, CREW et EREW, de l’algorithme de Cole ont été considérés. Un algorithme de placement de données est présenté ainsi que que les mouvements de données associés. Notre approche permet le tri de n éléments en utilisant n processeurs en temps O(log n). La constante multiplicative du temps d’exécution n'est que très légèrement supérieure à celle obtenu sur le modèle PRAM