Scattering and multi-scattering in trees and meshes, with local routing and without buffering

In interconnection networks, messages must go through a sequence of interme diate nodes before reaching their final destinations. In general, these int ermediate nodes have the possibility to store a message during several roun ds. This allows the node to wait for a link that gets the message closer to its destination to be free. This is the store-and-forward model. However, intermediate storage is often difficult to realize. In this paper, we consi der a communication model in which intermediate nodes do not need store the in-transit messages. The messages must leave the router immediately. Under this model, we study communication operations that involve many messages, such as scattering and multi-scattering. This allows us to give optimal or near-optimal scattering and algorithms. In addition, we use shortest-paths local routing functions in the networks under consideration. This is a real istic hypothesis when dealing with parallel systems. These features are sig nificant of what we do: provide general powerful and efficient algorithms t hat can be adapted in real machines. (C) 1999 Published by Elsevier Science B.V. All rights reserved.