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 pipeline search operation are easity seen to be Ω(log n-log N) and Ω(D+log n-log N), respectively. Since for n=N1+Ω(1) the worst-case period is Ω(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 queuing theory techniques that a constant expected period can be achieved provided that n=O(N2N).

Additional Metadata
Keywords Average-case analysis, coarse grained processor network, parallel algorithms, pipelining, searching
Persistent URL dx.doi.org/10.1007/BF01379185
Journal International Journal of Parallel Programming
Citation
Akl, S.G. (Selim G.), & Dehne, F. (1989). Pipelined search on coarse grained networks. International Journal of Parallel Programming, 18(5), 359–364. doi:10.1007/BF01379185