Networking Reference
In-Depth Information
n
a
2 -dimension torus with radix 4 ( k =4). Router pin bandwidth is limited, thus building a 10-ported
router for a hypercube instead of a 7-ported torus router may not be feasible without making each
port narrower .
3.3.1 NODE IDENTIFIERS
The nodes in a k -ary n -cube are identified with an n -digit, radix k number. It is common to refer to
a node identifier as an endpoint's “network address.” A packet makes a finite number of hops in each
of the n dimensions. A packet may traverse an intermediate router, c i , en route to its destination.
When it reaches the correct ordinate of the destination, that is c i = d i , we have resolved the i th
dimension of the destination address.
3.3.2 k -ARY n -CUBE TRADEOFFS
The worst-case distance (measured in hops) that a packet must traverse between any source and any
destination is called the diameter of the network. The network diameter is an important metric as it
bounds the worst-case latency in the network. Since each hop entails an arbitration stage to choose
the appropriate output port, reducing the network diameter will, in general, reduce the variance in
observed packet latency. The network diameter is independent of traffic pattern, and is entirely a
function of the topology, as shown in Table 3.1
Table 3.1: Network diameter and average latency.
Diameter
Average
Network
(hops)
(hops)
mesh
k 1
(k + 1 )/ 3
torus
k/ 2
k/ 4
hypercube
n
n/ 2
flattened butterfly
n
+
1
n
+
1
(n
1 )/k
from/to
0
1
2
3
4
5
6
7
8
from/to
0
1
2
3
4
5
6
7
8
0
0
1
2
3
4
5
6
7
8
0
0
1
2
3
4
4
3
2
1
1
1
0
1
2
3
4
5
6
7
1
1
0
1
2
3
4
4
3
2
2
2
1
0
1
2
3
4
5
6
2
2
1
0
1
2
3
4
4
3
3
3
2
1
0
1
2
3
4
5
3
3
2
1
0
1
2
3
4
4
4
4
3
2
1
0
1
2
3
4
4
4
3
2
1
0
1
2
3
4
5
5
4
3
2
1
0
1
2
3
5
4
4
3
2
1
0
1
2
3
6
6
5
4
3
2
1
0
1
2
6
3
4
4
3
2
1
0
1
2
7
7
6
5
4
3
2
1
0
1
7
2
3
4
4
3
2
1
0
1
8
8
7
6
5
4
3
2
1
0
8
1
2
3
4
4
3
2
1
0
(a) radix-9 mesh
(b) radix-9 torus
Figure 3.3: Hops between every source, destination pair in a mesh (a) and torus (b).
In a mesh (Figure 3.3 ), the destination node is, at most, k -1 hops away. To compute the
average, we compute the distance from all sources to all destinations, thus a packet from node 1 to
Search MirCeyron ::




Custom Search