Single step undirected reconfigurable networks

The reconfigurable mesh (RN-MESH) can solve a large class of problems in co nstant time, including problems that require logarithmic time by other, eve n shared memory, models such as the PRAM with a similar number of processor s [3]. In this work we show that for the RN-MESH these constants can always be reduced to one, still using a polynomial number of processors. Given a reconfigurable mesh that computes a set of values in constant time, we show that ir can be simulated by a single step reconfigurable mesh with maximum size that is polynomial in the size of the original mesh. The proof is con structive, where the construction of the single step RN-MESH holds for the relatively weak undirected RN-MESH model. In this model broadcasts made on buses arrive at all nodes that belong to the undirected connected component of the transmitting processor. A result similar to the one that is obtaine d in this work was previously obtained for the directed reconfigurable mesh model (DRN) [5]. However, the construction for the DRN-MESH relies on the fact that the buses are directed, and thus cannot be applied to the undirec ted case. In addition, the construction presented here is simpler and uses significantly fewer processors than the one obtained for the DRN-MESH.