Dynamic Routing Reconfiguration for Low-Latency and Deadlock-Free Interconnection Networks

For interconnection networks of large-scale super-computers, it is reported that low-diameter randomized networks are effective in reducing network latency. Since these networks with irregular structures have many cyclic connections, deadlocks in packet routing lead to the deterioration of communication performance. This research proposes a dynamic routing reconfiguration method that can alter multiple spanning trees based on different root nodes to support both deadlock freedom and low latency. Using our proposed method, the average number of hops was improved by 5.41 % at maximum under random permutation traffic. Moreover, it is found that for communication traces of parallel applications, the average packet latency can be reduced by up to 3.61 % by using our proposed dynamic routing reconfiguration.