III. ROUTING AND DEADLOCK AVOIDANCE
We choose dimension-order routing to guide packets’ transmission in consideration of its simplicity and fast routing characteristics. Dimension-order routing algorithm is the higher level decision that it will guide packets to firstly transit forwarded in one dimension, x dimension for example, until it reaches its target columns. Then it continues to route in the other dimension and arrives at its destination.
Dimension-order routing algorithm is deadlock-free in full-duplex meshes and binary hypercube [19][20][21]. However, according to what we have discussed in previous chapter, we have developed traditional torus network to avoid deadlock in the network. So we need to propose a corresponding routing mechanism to adapt to this the new topology we have proposed.
A map-based systematic approach called IRN has been introduced to design algorithms for interconnection networks. IRN will determine routing direction for each node to another node inside network. In a 4*4 torus network with the radix of n(n>=5). IRN map will be generated when adding a row above IRN map of radix n-1 and adding a column on the left side of the IRN map of radix n-1. The two leftmost boxes in the IRN map will be filled with “-1” signs and others with “1” signs to complete the new column. As for the new column added to the IRN map, the two lowest boxes in the IRN map will be filled with “1” signs and others will be filled with “-1” signs. The “1” , “-1”, “0” signs represent for positive, negative and current position, respectively.
In this IRN with radix of n, we can find a node that moves towards positive direction no more than one step, and it moves towards negative direction no more than one step as well. So in this way, it can avoid deadlock inside the network even if it does not introduce a virtual channel in the network. The IRN map is shown in Table 1.