loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.
Citation:
"Optimal Parallel Merging Algorithms on BSR," ispan, pp.12, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000
Usage of this product signifies your acceptance of the Terms of Use.