Deadlock-Free Fully-Adaptive Minimal Routing Algorithms: Limitations and Solutions

Abstract

In previous papers, a theory for the design of deadlock-free adaptive routing algorithms as well as a design methodology have been proposed. In this paper, an adaptive routing algorithm, obtained from the application of this theory to the 3-D torus, is evaluated under different load conditions and compared with other algorithms. The results show that this algorithm is very fast, also increasing the network throughput considerably.  Nevertheless, this adaptive algorithm has cycles in its channel dependency graph. Consequently, when the network is heavily loaded messages may temporarily block cyclically, drastically reducing the performance of the algorithm. Two mechanisms are proposed to avoid this problem.