loading...
Optimal Parallel Merging Algorithms on BSR
Dallas/Richardson, Texas, USA December 07-December 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.100012000 International Symposium on Paral ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
"Optimal Parallel Merging Algorithms on BSR," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 12, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2000.10001,
author = {},
title = {Optimal Parallel Merging Algorithms on BSR},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2000},
issn = {1087-4089},
pages = {12},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.10001},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - Optimal Parallel Merging Algorithms on BSR
SN - 1087-4089
SP
EP
PY - 2000
KW - null
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
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.