On the Power of the 2 X n Reconfigurable Mesh

The reconfigurable mesh (rmesh) consists of an array of processors connected by a fast interconnection network, which enables to dynamically obtain various communication patterns determined by local selections of switching nodes. It is well known that a 3Xn rmesh can compute the parity of n bits in constant time while in contrast, a PRAM with poly(n) processors cannot solve the problem faster than OMEGA (lg n over lg lgn). It was not known, however, to what extent the power of reconfiguration can be utilized on a 2Xn rmesh. In this paper we resolve this question by showing that a 2 X n rmesh can be optimally simulated on a CRCW PRAM in THETA(alpha (n)) time, where alpha (.) is the inverse Ackerman function; it can also be simulated in constant time with a slight inefficiency.