| Space-efficient parallel merging | |
| Authors: | Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson |
| Published in: | Proceedings of the 4th International PARLE Conference (Parallel Architectures and Languages Europe), Lecture Notes in Computer Science 605, Springer-Verlag (1992), 37–49 |
| DOI: | 10.1007/3-540-55599-4_79 |
| Copyright: | © Springer-Verlag |
| Abstract: | The problem of designing space-efficient parallel merging algorithms is examined. It is shown that two sorted sequences 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. This construction avoids the Θ(log n) slowdown when EREW PRAMs are simulated by DCMs. Moreover, using similar techniques, it is shown that merging can be accomplished in O(n / p + loglog m) time on a CREW PRAM with p processors, and O(1) extra space per processor. Our algorithms use a sequential algorithm for in-place merging as a subroutine, and if this is stable, also the parallel algorithms are stable. |
| Related: |  HTML (Technical report) HTML (Journal article) |
| BibLATEX: | @inproceedings{KLP1992bC,
author = {Jyrki Katajainen and Christos Levcopoulos and Ola Petersson},
title = {Space-efficient parallel merging},
booktitle = {Proceedings of the 4th International PARLE Conference (Parallel
Architectures and Languages Europe)},
series = {Lecture Notes in Computer Science},
volume = {605},
publisher = {Springer-Verlag},
year = {1992},
pages = {37--49},
}
|