The adaptive routing has been expected as one of the best approaches to improve the network performance overcoming the message contention problem by utilizing available network bandwidth. Many adaptive routing algorithms for networks that adopt the wormhole routing have been developed. Most of these algorithms have been applied to the network with the additional virtual channels. The use of virtual channels is required to prevent deadlock and increases network throughput and the degree of adaptiveness.
The turn model involves analyzing the directions in which packets can turn in a network and the cycles that the turns can form. Restricting just enough turns to break all of the cycles produces routing algorithms. Previous adaptive routing algorithms based on the turn model have proposed. These routing algorithms could be applied to the network with only two virtual channels, because it is difficult that the turn model is applied to the network with many virtual channels. In this thesis, we generalize the turn model to apply it to the network with many virtual channels. The generalized turn model can be easily applied to the network with arbitrary numbers of virtual channels.
We also propose a minimal fully adaptive routing algorithm based on the generalized turn model for two-dimensional meshes. The proposed routing algorithm maximizes the degree of adaptiveness by minimizing the routing restriction and is proved to be deadlock-free. Finally, the performance of the proposed adaptive routing algorithm is evaluated by simulation under various traffic patterns by varing the number of virtual channels.
