Pipelined search on coarse grained networks

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¹⁺⁽¹⁾ 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 research was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A3336 and A9173.