Pipelined search on coarse grained networks. (English) Zbl 0701.68043
Summary: The time complexity of searching a sorted list of n elements in parallel on a coarse grained network of diameter D and consisting of N processors (where n may be much larger than N) is studied. The worst case period and latency of a sequence of pipelined search operations are easily seen to be \(\Omega\) (log n-log N) and \(\Omega (D+\log n-\log N)\), respectively. Since for \(n=N^{1+\Omega (1)}\) the worst-case period is \(\Omega\) (log n) (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 queueing theory techniques that a constant expected period can be achieved provided that \(n=0(N2^ N)\).
MSC:
68Q25 | Analysis of algorithms and problem complexity |
68W15 | Distributed algorithms |
68P10 | Searching and sorting |
68M10 | Network design and communication in computer systems |
References:
[1] | M. Snir, On Parallel Searching,SIAM J. Comput. 14:3:688-708 (1985). · Zbl 0607.68047 · doi:10.1137/0214051 |
[2] | S. G. Akl,The Design and Analysis of Parallel Algorithms, Prentice-Hall (1989). · Zbl 0754.68053 |
[3] | A. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley (1976). · Zbl 0326.68005 |
[4] | F. Dehne and N. Santoro, Optimal VLSI Dictionary Machines on Meshes, inProc. Int. Conference on Parallel Processing, pp. 832-840, St. Charles, Ill. (1987). |
[5] | 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). |
[6] | A. Papoulis,Probability Theory, Random Variables, and Stochastic Processes, McGraw-Hill (1984). · Zbl 0558.60001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.