Narrow Results

The purpose of this paper is to present non-trivial lower bounds for two classes of enhanced meshes. To achieve this goal we present efficient simulations of these two classes of enhanced meshes on the CREW-PRAM and Common-CRCW. From this, known computational lower bounds for the PRAM are transferred to the enhanced meshes. Our approach of transferring lower bounds from the PRAM to enhanced meshes is novel. Specifically, we show that any computation that takes O(t(n)) steps on an n-processor mesh with multiple broadcasting can be performed in O(t(n)) steps on an n-processor CREW-PRAM with O(n) extra memory. Similarly, with α standing for the inverse Ackermann function, we show that any computation that takes O(t(n)) computational steps on an n-processor basic reconfigurable mesh can be performed in O(α(n)t(n)) computational steps on an n-processor Common-CRCW with O(n) extra memory. We also show that some of the lower bounds that we derive are tight by providing matching upper bounds; as an example, we show that n items stored in one row of a mesh with multiple broadcasting can be sorted in O(log n) time and that this is time optimal. The best previously-known algorithm for this problem takes O(log² n) time.

The literature abounds with enhanced mesh models and numerous results for them. These models employ buses connecting a large (usually a polynomial) number of processors resulting in high bus loading and a very low bus data rate. In this paper we propose an enhanced mesh model called the mesh with binary-tree (multiple bus) network (MBTN) with low bus loading. We measure the cost of the model in terms of its loading, degree (connections per processor), number of buses and layout area. We also devise an algorithm to perform prefix computations on the MBTN. The MBTN's parameters can be selected to provide a wide range of tradeoffs between its cost and performance. Most importantly, for every major existing enhanced mesh model, there is a choice of parameters that makes the MBTN superior to the existing model.

Key to the MBTN is a novel implementation of a binary-tree algorithm on a multiple bus network (MBN). We propose two constant loading MBNs that can run binary tree algorithms optimally. We also show that any network (such as the MBTN) that is capable of running binary tree algorithms efficiently can also solve linear recurrences efficiently. These results may be of independent interest.