SIMULATING ENHANCED MESHES, WITH APPLICATIONS

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.