Pipelined search on coarse grained networks

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).

• View at Publisher
• View at Scopus