Complexity of Sub-Bus Mesh Computations
Anne Condon, Richard E. Ladner, Jordan Lampe, Rakesh Kumar Sinha · SIAM Journal on Computing · 1996
The time complexity of several fundamental problems on the sub-bus mesh parallel computer with p processors is investigated. The problems include computing the PARITY and MAJORITY of p bits, the SUM of p numbers of length $O(\log p)$, and the MINIMUM of p numbers. It is shown that in one dimension the time to compute any of these problems is $\Theta (\log p)$. In two dimensions the time to compute any of PARITY, MAJORITY, and SUM is $\Theta (\tfrac{{\log p}} {{\log \log p}})$. It was previously shown that the time to compute MINIMUM in two dimensions is $\Theta (\log \log p)$ [R. Miller et al., IEEE Trans. Comput., 42 (1993), pp. 678–692; L. Valiant, SIAM J. Comput., 4 (1975), pp. 348–355]