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]

A special-purpose computer system has been designed to accelerate scanning large databases of DNA and protein sequences (biosequences) for patterns of interest. The system consists of a custom-designed circuit board installed in a host workstation and associated software. The board features a variable number of identical full-custom ASICs. Each biological sequence comparative analysis node. (BioSCAN) ASIC, in turn, features a large one-dimensional systolic array of identical processing elements (PEs). The BioSCAN system scans approximately two million database elements per second. For typical problems this results in a 1000-fold speedup over current workstations.>