next up previous

3.4 Topology     continued...

The first example of a multistage network is the crossbar switch Figure 14. In a typical application there will be a column of processors on the left edge and a row of memories on the bottom edge. The switch configures itself dynamically to connect a processor to a memory module. As long as each processor wants to communicate with a different memory there will be no contention. If two or more processors need to access the same memory, however, one will be blocked until the switch reconfigures itself. A crossbar has a short diameter --- information needs to pass through only one switching element on a path from one edge to another --- but poor scalability. If there are n processors and a like number of memories there are interior switches. Adding another processor and memory means adding another 2n - 1 interior nodes.

A banyan network is a multistage switching network that has the same number of inputs as outputs and interior nodes that are switches. Examples of banyan networks are butterfly networks and omega networks, which are both built from switches. The diameter of a butterfly is , where n is the number of inputs and outputs, and there are switches, so these networks scale more efficiently than a crossbar (Figure 15). The switch in a butterfly can be configured in one of two states (Figure 15). One configuration connects input 0 to output 0 and input 1 to output 1. The other configuration flips the outputs, so input 0 connects to output 1 and input 1 connects to output 0. The switching network uses the binary representation of the destination address in order to construct a path from input to output. The switch at stage i in the network uses bit i to determine how to configure itself: if the bit is 0, the request should go through the top output, and if it is 1 it should go through the bottom output. For example, suppose a processor needs to fetch information from memory M. The binary representation of 5 is 101. The first switch will pass the request out its bottom output, the second switch will pass the request out its top output, and the last switch will pass the request out its bottom output. Note that this pattern of connections (top-bottom-top) works no matter which processor generates the request. Whether a switch configures itself in the straight-through or flipped configuration depends on which input the request comes from. For example, if the request comes from the top input and should be routed out the top output, then the switch will go into the straight-through configuration, but if the request comes from the top input and should go out the bottom the switch will use the flipped configuration.

Figure 15: Butterfly Network.