|
|
|
|
|
|
|
Figure 8.52
Baseline dynamic network topology. |
|
|
|
|
|
|
|
|
Figure 8.53
Network blocking. |
|
|
|
|
|
|
|
|
multistage network, frequently referred to as a MINmultistage interconnection network [312]. There are many types of such networks, including baseline, Benes, Clos, Omega [178], and Banyan. The baseline network is among the simplest, and is shown in Figure 8.52. The header causes successive stages of the switch to be set so that the proper connection path is established between two nodes. For example, consider a deterministic "obvious" routing algorithm for these M,N networks. Suppose node 010 sends a message to destination 110. The switch outputs labeled 1, 1, 0 cause the message to be routed to the 110 destination node by setting the control (c) so that either the upper output ("O") or the lower output ("1") of each switch is selected. Similarly, the return path is simply 010. The number of stages between two nodes is: |
|
|
|
|
|
|
|
|
where k is the number of inputs to the crossbar element (k ´ k), and therefore the total number of (k ´ k) switches required for a one-bit wide path is: |
|
|
|
|
|
|
|
|
The baseline network, such as shown in Figure 8.52, is subject to blocking. Blocking occurs between two messages at an intermediate point in the network, where the two messages share a common node output even though they do not share a common destination. |
|
|
|
|
|
