The development of efficient packet routing algorithms is a very important task in the construction of parallel computers. In a parallel architecture, different computing elements must be able to communicate with each other fast while the size of the message (packet) queues created during the routing must be bounded, ideally, to a small constant. Through packet routing, real machines are able to simulate idealized machines and theoretical models can be tested and tuned. Up to now, the best existing permutation packet routing algorithm on the mesh architecture is by Leighton, Makedon and Tollis which routes the packets to their destination in optimal time and with constant size queues. However, drastically new methodologies are needed to make these results practical. Two types of parallel communication algorithms will be considered, online and off-line on multidimensional meshes and tori. Off-line packet routing is used in cases where the communication pattern is known in advance, before the execution, or for computations in which the data dependencies are fixed before run-time. Universal approximation algorithms for packet routing on meshes and tori will also be examined for completing the routing in the cases of actual problems. A universal approach is also needed in the case of off-line routing, that can be applied to any pattern, such as many to one routing.
