Permutation Routing on Reconfigurable Meshes

In this paper we present efficient algorithms for packet routing on the reconfigurable linear array and the reconfigurable two-dimensional mesh. We introduce algorithms that are efficient in the worst case and algorithms that are better on average. The time bounds presented are better than those achievable on the conventional mesh and previously known algorithms. We present two variants of the reconfigurable mesh. In the first model, M _r , the processors are attached to a reconfigurable bus, the individual edge connections being bidirectional. In the second model, M _mr , the processors are attached to two unidirectional buses. In this paper we present lower bounds and nearly matching upper bounds for packet routing on these two models. As a consequence, we solve two of the open problems mentioned in [9]. Received August 17, 1998; revised November 3, 1999.