Space-efficient parallel merging
Jyrki Katajainen, Christos Levcopoulos, Ola Petersson · RAIRO - Theoretical Informatics and Applications · 1993
The problem of designing space-efficient parallel mer ging algorithms is examined.It is shown that two sorted séquences of lengths m and n, m^n, can be merged in O {n/p-\-log n) time on an EREW PRAM with p processors, using only a constant amount of extra storage per processor.After a slight modification, the algorithm runs on a DCM {Direct Connection Machine) within the same resource requirements.Moreover, using similar techniques, it is shown that merging can be accomplished in O (n/p + log log m) time on a CREW PRAM with p processors, and 0(1) extra space per processor.Our algorithms use a sequential algorithm for in~place merging as a subroutine; if this is stable, the parallel algorithms are stable as well.Résumé.-Le problème de la conception d'un algorithme de fusion parallèle performant en espace est étudié.Il est montré que deux suites triées de longueur m et n, m^n peuvent être fusionnée en temps O {n/p + log n) sur un modèle PRAM à lecture et écriture exclusives avec p processeurs, en utilisant une quantité de mémoire supplémentaire constante par processeur.Après de légères modifications, l'algorithme tourne sur une machine à connexion directe {DCM) avec les mêmes conditions sur les ressources.De plus, en utilisant des techniques similaires, il est montré que la fusion peut être réalisée en temps O {n/p + log log m) sur un modèle PRAM à lecture concurrente et écriture exclusive avec p processeurs, et une mémoire supplémentaire en (9(1) par processeur.Nos algorithmes utilisent comme sous-routine un algorithme séquentiel de fusion en place; si celui-ci est stable alors l'algorithme parallèle est aussi stable.