AN EFFICIENT HEURISTIC FOR PERMUTATION PACKET ROUTING ON MESHES WITH LOW BUFFER REQUIREMENTS

Even though exact algorithms exist for permutation routing of n2 messa ges on a n x n mesh of processors which require constant size queues, the constants are very large and the algorithms very complicated to im plement. In this paper, we present a novel, simple heuristic for the a bove problem. It uses constant and very small size queues (size = 2). For all the simulations we ran on randomly generated data, the number of routing steps that is required by our algorithm is almost equal to the maximum distance a packet has to travel. We demonstrate a patholog ical case where the routing takes more than the optimal, and we prove that the upper bound on the number of required steps is O(n2). Further more, we show that our heuristic routes in optimal time inversion, tra nsposition, and rotations, three special routing problems that appear very often in the design of parallel algorithms.