Deadlock-Free Fully-Adaptive Minimal Routing Algorithms: Limitations and Solutions
P. López ; J. Duato
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
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.
Publié le : 2012-01-26
Classification: 
@article{cai223,
     author = {P. L\'opez and J. Duato},
     title = {Deadlock-Free Fully-Adaptive Minimal Routing Algorithms: Limitations and Solutions},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai223}
}
P. López; J. Duato. Deadlock-Free Fully-Adaptive Minimal Routing Algorithms: Limitations and Solutions. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai223/