CONSTANT QUEUE ROUTING ON A MESH

Packet routing is an important problem in parallel computation since a single step of interprocessor communication can be thought of as a packet routing task. In this paper we present an optimal algorithm for packet routing on a mesh-connected computer. Two important criteria for judging a routing algorithm are (1) its run time, i.e., the number of parallel steps it takes for the last packet to reach its destination, and (2) its queue size, i.e., the maximum number of packets that any node will have to store at any time during routing. We present a 2n - 2 step routing algorithm for an n × n MIMD mesh that requires a queue size of only 112. The previous best known result is a routing algorithm with the same time bound but with a queue size of 1008. The time bound of 2n - 2 is optimal. A queue size of 1008 is rather large for practical use. We believe that the queue size of our algorithm is practical. The improvement in the queue size is possible due to (among other things) a new sorting algorithm for the MIMD mesh. © 1992.