| Space-efficient parallel merging | |
| Authors: | Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson |
| Publication: | Report 91/15, Department of Computer Science, University of Copenhagen (1991), 12 pp. |
| 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 (Conference paper) HTML (Journal article) |
| BibLATEX: | @report{KLP1991R,
author = {Jyrki Katajainen and Christos Levcopoulos and Ola Petersson},
title = {Space-efficient parallel merging},
type = {Report},
number = {91/15},
institution = {Department of Computer Science, University of Copenhagen},
year = {1991},
pagetotal = {12},
}
|