Fast parallel communication on mesh connected machines with low buffer requirements

Even though exact algorithms exist for permutation routing of n² on a n×n mesh of processors which require constant size queues, the constants are very large, and the algorithms very complicated to implement. A novel, simple heuristic is presented for this problem. The main contribution of the parallel algorithm is that it uses constant and very small queues (queue size for exactly two packets is needed). The algorithm has several attractive features: it is very simple and does not require complex operations for the maintenance of the queues. Experimental results on random-generated data show that the number of steps required to complete the routing is almost equal to the maximum distance a packet has to travel