On Parallel Searching
Marc Snir · SIAM Journal on Computing · 1985
We investigate the complexity of searching a sorted table of n elements on a synchronous, shared memory parallel computer with p processors. We show that $\Omega (\lg n - \lg p)$ steps are required if concurrent accesses to the same memory cell are not allowed, whereas $O(\lg n/\lg p)$ steps are sufficient if simultaneous reads are allowed. The lower bound is valid even if only communication steps are counted, and the computational power of each processor is not restricted. In this model, $\Theta \sqrt {\lg n} $ steps are required for searching when the number of processors is unbounded. If the amount of information that a memory cell may store is restricted, then the time complexity for searching with an unbounded number of processors is $\Theta (\lg n/\lg \lg n)$. If the amount of information a processor may hold is also restricted, then an $\Omega (\lg n)$ lower bound holds. These lower bounds are first proven for comparison-based algorithms; it is next shown that comparison-based algorithms are as powerful as more general ones in solving problems defined in terms of the relative order of the inputs.
Cited by 110 works. doi:10.1137/0214051
Authors
References
- On a Problem of Formal Logic
- Ultracomputers
- Should Tables Be Sorted?
- Routing, merging, and sorting on parallel models of computation
- A fast parallel algorithm for routing in permutation networks
- Finding the maximum, merging and sorting in a parallel computation model
- Bounds on the time for parallel RAM's to compute simple functions
- Mesh-Connected Computers with Broadcasting
- Trade-Offs between Depth and Width in Parallel Computation
- Binary Search in a Multiprocessing Environment