Deterministic Permutation Routing on Meshes

New deterministic algorithms for routing permutations on two-dimensional meshes are developed. On an n \Theta n array, one of them runs in the optimal 2 \Delta n \Gamma 2 steps. It has maximum queue length 32. Another algorithm runs in near-optimal time, 2 \Delta n +O(1) steps, with a maximum queue length of only 12. Keywords: parallel computation, meshes, permutation routing. 1 Introduction The exchange of information between processing units, PUs, is one of the most important problems on parallel computers in which the PUs communicate through an interconnection network. Transferring packets, pieces of information generated by PUs, is a basic communication step. Usually, a PU is connected to a small number of other PUs, and the packets sent by it need to travel through a sequence of intermediate PUs to their final destination. Handling all the packets moving through a network is called packet routing. The efficiency of a packet routing protocol is measured by two parameters: the ti..