Adaptive, low latency, deadlock-free packet routing for networks of processors

Abstract

In order to provide an arbitrary and fully dynamic connectivity in a network of processors, transport mechanisms must be implemented, which provide the propagation of data from processor to processor, based on addresses contained within a packet of data. Such data transport mechanisms must satisfy a number of requirements, namely deadlock and livelock freedom, good hot-spot performance, high throughput and low latency. The paper proposes a solution to these problems, which allows deadlock free, adaptive, high throughput packet routing to be implemented on networks of processors. Examples are given which illustrate the technique for two-dimensional (2D) array and toroidal networks. The implementation of this scheme on arrays of transputers is considered. The scheme also serves as a basis for very-low latency routing strategy introduced here as well.