Abstract
The time complexity of searching a sorted list ofn elements in parallel on a coarse grained network of diameterD and consisting ofN processors (wheren may be much larger thanN) is studied. The worst case period and latency of a sequence of pipeline search operation are easity seen to be Ω(logn−logN) and Ω(D+logn−logN), respectively. Since forn=N 1+Ω(1) the worst-case period is Ω(logn) (which can be achieved by a single processor), coarse-grained networks appear to be unsuitable for the search problem. By contrast, it is demonstrated using standard queuing theory techniques that a constant expected period can be achieved provided thatn=O(N2 N).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Snir, On Parallel Searching,SIAM J. Comput. 14:3:688–708 (1985).
S. G. Akl,The Design and Analysis of Parallel Algorithms, Prentice-Hall (1989).
A. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley (1976).
F. Dehne and N. Santoro, Optimal VLSI Dictionary Machines on Meshes, inProc. Int. Conference on Parallel Processing, pp. 832–840, St. Charles, Ill. (1987).
F. Dehne and N. Santoro, An Optimal VLSI Dictionary Machine For Hypercube Architectures, to appear inProc. Workshop on Parallel and Distributed Computing, Bonas (France) (1988).
A. Papoulis,Probability Theory, Random Variables, and Stochastic Processes, McGraw-Hill (1984).
Author information
Authors and Affiliations
Additional information
This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A3336 and A9173.
Rights and permissions
About this article
Cite this article
Akl, S.G., Dehne, F. Pipelined search on coarse grained networks. Int J Parallel Prog 18, 359–364 (1989). https://doi.org/10.1007/BF01379185
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF01379185