|
|
|
|
|
|
|
8.16.2 Network Dimensionality and Link-Limited Network |
|
|
|
|
|
|
|
|
Networks usually are analyzed under the assumption of constant channel bandwidth. The assumption frequently is made that the link bandwidth is fixed at w = n bits, or each channel is n bits wide with unit delay. Under these assumptions, higher-dimensional networks have some significant advantages. They offer more node-to-node connections than lowerdimensional networks, and have a shorter delay or diameter across the network. The number of hops, both average and maximum, is significantly reduced with higher-dimensional networks. |
|
|
|
|
|
|
|
|
Dally [64] points out the inadequacy of the preceding analysis, as it ignores the complexity of the links connecting the nodes. Higher-dimensional networks must necessarily be mapped onto two or three dimensions to be realized. This mapping increases wire delays and also provides a somewhat unfair analysis advantage to the higher-dimension networks in not recognizing the costs inherent in the extra connections. As processors become smaller (the nodes), the importance of the linksthe channels that connect the processorsis increased. Rather than comparing networks on distance or bandwidth, Dally proposes to compare networks based upon equal bisection width. We assume in this study, as in study 8.3, that l = 200. The bisection width is the minimum number of wires cut when the network is divided into two equal halves. Thus, rather than comparing networks with a constant number of nodes and node size, he compares networks with constant bisection width. In his analysis, wire density is held constant. For his analysis, the bisection width B of a k-ary n-cube with w-bit wide communications channels is: |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
For a binaryn-cube, B(2,n) = wN. The dynamic baseline network using 2 ´ 2 crossbars (k = 2) has the same bisection width as B(2,n). If we use the binary n-cube as a base, then networks with lower dimensionality and the same bisection width have greater channel width. In fact, they have channel width: |
|
|
|
 |
|
|
|
|
w(k, n) = k/2 |
|
|
|
|
|
|
|
|
Compute the bisection width of a grid (32,2). A (32,2) network has bisection width (w = 1) of |
|
|
|
|
|
|
|
|
That is, there are 64 wires (w = 1) required to partition the network. Recall that the (32,2) is actually a torus, and thus the bisection of 64, not 32. |
|
|
|
|
|
