1989-10-01
Pipelined search on coarse grained networks
Publication
Publication
International Journal of Parallel Programming
,
Volume 18
-
Issue 5
p. 359-
364
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
|