2.1Optimize Port Assignment Rules(编号)
According to the discussion above, we can know that IRN map can work effectively in small-scale network. However, IRN map cannot always find optimal and minimal paths, because each packet guided by IRN map traverses the shortest possible paths that are deadlock-free instead of through the shortest physical paths that may lead to deadlocks. Links fail to balancing the load under all-to-all pattern when the size of network scales up. Theoretical computations on links load for a 12*12 torus network at different positions in one dimension have been listed in the Table 2. We use “->” and “<-” signs to represent for the directions of traffic between two adjacent nodes, respectively. Traffic between node 9 and 10 is at a low pressure because in node 9, all the positive movements more than one step are forbidden and in node 10, all the negative movements more than one step are not allowed as well. But this will aggravate traffic loads on nodes far from node 9 and node 10. So, IRN map will not able to make optimal decisions in this case. New assignment rules are necessary to guide the fast transmission of packets.
We should achieve three objectives when designing new port assignment rules:
i) Packets should reach their destinations in a limited period or no Ping-Pong phenomenon occurs inside network;
ii) No cyclic dependence forms in the channel dependence graph;
iii) Rules should balance the load of each links as much as possible.
These objectives are closely independent with each other. A channel dependence graph will generate according to the path between arbitrary pair of servers in the torus network. Some potential deadlock-free port assignments may generate in this process. We will choose the port assignment that can perform best in balancing load among links as the optimal choice. So, we will divide optimal port assignment searching processes into three sub-steps.
For example, we can apply well-designed routing and assignment mechanisms to this network. According to the dimension-order routing algorithm, packets will keep transferring in one dimension until it reaches the column where the destination node locates. Packets will select appropriate routing directions in each dimension to avoid deadlock. To attain this goal, we will simplify the selecting routing direction process by integrating the multi-dimension into a single dimension and shift it to another dimension. To raise a 4*4 torus network as an example, it is a torus structure consisting of 4 nodes in each dimension. So, data packets can be sent to those two adjacent nodes by one hop, but if packets will be sent to nodes that far away, they have multiple options. Table 3 lists all the available choices for the torus topology, but some of them may result in deadlock inside network.
 
Node
Node 0
Node 1
Node 2
Node 3
Node 0
0
1
-1
Node 1
-1
0
1
Node 2
-1
0
1
Node 3
1
-1
0
 
(a). Different node to other nodes in the routing direction within a ring structure consisting 4 nodes. “—” represents either positive or negative direction.
 
Port direction
              Network performance
Node0
Node1
Node2
Node3
Deadlock
-Free
Load
-Balanced
Average Hop
-1
-1
-1
-1
×
×
1.33
-1
-1
-1
1
×
1.33
-1
-1
1
-1
×
1.33
-1
-1
1
1
×
1.33
-1
1
-1
-1
×
1.33
-1
1
-1
1
1.33
-1
1
1
-1
×
1.33
-1
1
1
1
×
1.33
1
-1
-1
-1
×
1.33
1
-1
-1
1
×
1.33
1
-1
1
-1
1.33
1
-1
1
1
×
1.33
1
1
-1
-1
×
1.33
1
1
-1
1
×
1.33
1
1
1
-1
×
1.33
1
1
1
1
×
×
1.33
 
(b). Distribution of deadlock and load under different routing direction. “√” represents port assignments are deadlock-free and make the load balanced. “×” has the contrary meanings.
Table 3. The available selections for the ring
 
4.1 Theorem
Dimension-order routing algorithm is deadlock-free in Mesh-of-Torus networks.
4.2 Proof
Mesh-of-Torus network is the combination of mesh and torus network. To be more specific, the basic unit of this network is mesh network, but it borrows the idea of torus network to connect those basic units into a whole. It is meaningless for us to simplify the deadlock avoidance problem and employ dimension-order routing algorithm in Mesh-of-Torus network on a single dimension on the basis of following reasons:
1) When packets are transferring in the 4×4 torus network, our port assignment have already guaranteed the formation of cyclic-relationship in every dimension as well as the prevention of deadlock.
2) When packets are transferring in a 4*4 torus network and boundary nodes of adjacent torus network, such as the clockwise and anticlockwise channels in a single dimension illustrated in Figure 3, we can prevent deadlock by the employment of port assignment rules in each 4*4 torus network, even if we add some boundary nodes of other torus network in it.
3) When packets are transferring among multiple subnets, such as the clockwise and anticlockwise channels in a single dimension illustrated in Figure4, we can avoid deadlock by preventing the formation of cyclic relationship by the application of the port assignment rules for all the subnet.
In a word, when dimension-order routing algorithm is applied, a single-dimension Mesh-of-Torus network is deadlock-free spontaneously.