2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00)
Optimal Parallel Merging Algorithms on BSR
Dallas/Richardson, Texas, USA
December 07-December 07
ISBN: 0-7695-0936-3
Merging is one of the most fundamental problems in computer science. It is well lcnown that \Omega( N \over p + log log N) time is required to merge two sorted sequences each of length N on CRCW PRAM with p processors, where p \leq N log\alpha,N for any constant a. In this paper, we describe two optimal O(1) time solutions to the problem for p = N on BSR (Broadcasting with Selective Reduction). They are the first constant time solutions to the problem on any model of computation. We also give an optimal solution to the problem for p < N on BSR with O(N /over p) time, which is the first improvement with non-constant time but still better than the lower bound for PRAM.