We present a new deterministic algorithm for routing permutation, on a two-dimensional MIMD mesh. The algorithm runs in the optimal time 2n-2 on an n*n mesh, and the maximal number of packets stored in a processing unit is 81. A modification of the algorithm, running in time 2n+O(1), has the maximal queue length of only 31. The algorithm is simple, no conflict-resolution strategy is required. Keywords: mesh-connected computer, permutation routing, optimal algorithm, conflict freeness
Ulrike Peiker, Martin Griebl