Multistage Switching Network in multiprocessors system

 

Different schemes of interconnection structure are:

Operation of 2 x 2 Interchange switch

The basic component of a multistage network is a two-input, two-output interchange switch. As shown in figure below the 2 x 2 switch has two inputs, labelled A and B, and two outputs, labelled 0 and 1.

 

Figure : Operation of 2x2 interchange switch

The switch has the capability of connecting input A to either of the outputs. Terminal B of the switch behaves in a similar fashion. If inputs A and B both request the same output terminal, only one of them will be connected; the other will be blocked.

Binary Tree Switches

Using the 2 x 2 switch as a building block, it is possible to build a multistage network to control the communication between a number of sources and destinations. To see how this is done, consider the binary tree shown in figure below. The two processors P1 and P2 are connected through switches to eight memory modules marked in binary from 000 through 111. The path from a source to a destination is determined from the binary bits of the destination number.

 

Figure : Binary Tree Switches strcuture

For example, to connect P1 to memory 101, it is necessary to form a path from P1 to output 1 in the first-level switch, output 0 in the second-level switch, and output 1 in the third-level switch. The first bit of the destination number determines the switch output in the first level. The second bit specifies the output of the switch in the second level, and the third bit specifies the output of the switch in the third level. It is clear that either P1 or P2 can be connected to any one of the eight memories. Certain request patterns, however, cannot be satisfied simultaneously. For example, if P1 is connected to one of the destinations 000 through 011, it means P2 can be connected to only one of the destinations 100 through 111.

Omega Switching Network

Many different topologies have been proposed for multistage switching networks to control processor-memory communication in a tightly coupled or to in a loosely coupled system. One such topology is the omega-switching network shown in figure below. In this configuration, there is exactly one path from each source to any particular destination. Some request patterns, however, cannot be connected simultaneously.

 

Figure : Omega Switching Network

For example, any two sources cannot be connected simultaneously to destinations 000 and 001. A particular request is initiated in the switching network by the source, which sends a 3-bit pattern representing the destination number. As the binary pattern moves through the network, each level examines a different bit to determine the 2 x 2 switch setting. Level 1 inspects the most significant bit, level 2 inspects the middle bit, and level 3 inspects the least significant bit. When the request arrives on either input of the 2 x 2 switch, it is routed to the upper output if the specified bit is 0 or to the lower output if the bit is 1.

Tightly Coupled System

In this system, the source is a processor and the destination is a memory module. The first pass through the network sets up the path. After path setup, transfer the address into memory and then transfer the data in either direction based on read or write request.

Loosely Coupled System

In this system, both the source and destination are processing elements. After the path is estab­lished, the source processor transfers a message to the destination processor.

If you want to know about how to consturcut Omega Switchign Network & How to work Omega Switching Network. You can watch second video of this post.

To learn more about Multistage Switching Network, watch below video

Video : Multistage Switching Network

Video : Working of Omega Switching Network

Watch more videos click here.