Scattering and multi-scattering in trees and meshes, with local routing and without buffering
In interconnection networks, messages must go through a sequence of intermediate nodes before reaching their final destinations. In general, these intermediate nodes have the possibility to store a message during several rounds. 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 consider 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 realistic hypothesis when dealing with parallel systems. These features are significant of what we do: provide general powerful and efficient algorithms that can be adapted in real machines.
scattering multi-scattering local routing 0-buffering