Communication locality oriented high-radix interconnection network and adaptive routing algorithm design

摘要

This invention proposes a new communication locality oriented high-radix (CLHR) network. In this hierarchical architecture, the lowest level includes routers or servers, called level-0; the upper level is composed by groups of routers or servers, called level-1; for the highest level, a number of level-(l−1) groups establish level-1 group. A new deadlock-free adaptive routing algorithm is proposed for the CLHR network. On the one hand, the proposed minus-first routing (MFR) algorithm or plus-first routing algorithm, that implements deadlock-free partially-adaptive routing without any virtual channel, can guarantee the number of communication hops between two nodes is no more than five. On the other hand, this invention presents the fully adaptive routing algorithm that uses MFR algorithm as the baseline routing using a new flow control scheme. The CLHR network and the new routing algorithm effectively improve the performance, save energy, improve the ability for separation, and resist disturbance.