Interconnection Networks

Multiprocessors interconnection networks (INs) can be classified based on a number of criteria.

1. Mode of Operation. According to the mode of operation, INs are classified as synchronous versus asynchronous.
   • In synchronous mode of operation, a single global clock is used by all components in the system such that the whole system is operating in a lock-step manner.
   • Asynchronous mode of operation, on the other hand, does not require a global clock. Handshaking signals are used instead in order to coordinate the operation of asynchronous systems.
   • While synchronous systems tend to be slower compared to asynchronous systems, they are race and hazard-free.
2. Control Strategy. According to the control strategy, INs can be classified as centralized versus decentralized.
   • In centralized control systems, a single central control unit is used to oversee and control the operation of the components of the system. The function and reliability of the central control unit can become the bottleneck.
   • In decentralized control, the control function is distributed among different components in the system.
   • While the crossbar is a centralized system, the multistage interconnection networks are decentralized.
3. Switching Techniques. Interconnection networks can be classified according to the switching mechanism as circuit versus packet switching networks.
   • In the circuit switching mechanism, a complete path has to be established prior to the start of communication between a source and a destination. The established path will remain in existence during the whole communication period.
   • In a packet switching mechanism, communication between a source and destination takes place via messages that are divided into smaller entities, called packets. On their way to the destination, packets can be sent from a node to another in a store-and-forward manner until they reach their destination.
   • While packet switching tends to use the network resources more efficiently compared to circuit switching, it suffers from variable packet delays.
4. Topology.An interconnection network topology is a mapping function from the set of processors and memories onto the same set of processors and memories.

   • A fully connected topology, for example, is a mapping in which each processor is connected to all other processors in the computer.
   • A ring topology is a mapping that connects processor $k$ to its neighbors, processors $(k-1)$ and $(k+1)$.
   • In general, interconnection networks can be classified as static versus dynamic networks.
   • In static networks, direct fixed links are established among nodes to form a fixed network, while in dynamic networks, connections are established as needed.
   • Shared memory systems can be designed using bus-based or switch-based INs (see Fig. 1.7).
     • The simplest IN for shared memory systems is the bus. However, the bus may get saturated if multiple processors are trying to access the shared memory (via the bus) simultaneously.
     • A typical bus-based design uses caches to solve the bus contention problem.
     • Other shared memory designs rely on switches for interconnection. For example, a crossbar switch can be used to connect multiple processors to multiple memory modules.

     Figure 1.7: Bus Based and Switch Based Shared Memory INs, Single Bus Based and Multiple Bus Based Shared Memory INs.
   • Message passing INs can be divided into static and dynamic.
     • Static networks form all connections when the system is designed rather than when the connection is needed.
     • Dynamic INs establish a connection between two or more nodes on the fly as messages are routed along the links.
     • The number of hops in a path from source to destination node is equal to the number of point-to-point links a message must traverse to reach its destination.
     • The ultimate performance of an interconnection network is greatly influenced by the number of hops taken to traverse the network.
     • Figure 1.8 shows a number of popular static topologies.

       Figure 1.8: Examples of Static Topologies.

       
     • Figure 1.9 shows examples of dynamic networks. The single-stage interconnection network of Fig. 1.9a is a simple dynamic network that connects each

       Figure 1.9: Single-Stage, Multi-Stage and Crossbar Switch Dynamics INs.
       of the inputs on the left side to some, but not all, outputs on the right side through a single layer of binary switches represented by the rectangles.
     • The binary switches can direct the message on the left-side input to one of two possible outputs on the right side.
     • If we cascade enough single-stage networks together, they form a completely connected multistage interconnection network (MIN), as shown in Fig. 1.9b.
     • These are dynamic INs because the connection is made on the fly, as needed.
     • For example, to connect source 111 to destination 001 in the network, the switches in the first and second stage must be set to connect to the upper output port, while the switch at the third stage must be set to connect to the lower output port (001).
     • Similarly, the crossbar switch of Figure 1.9c provides a path from any input or source to any other output or destination by simply selecting a direction on the fly.
     • To connect row 111 to column 001 requires only one binary switch at the intersection of the 111 input line and 011 output line to be set.
     • The crossbar switch clearly uses more binary switching components; for example, $N^2$ components are needed to connect $N \times N$ source/destination pairs. The MIN, on the other hand, connects $N \times N$ pairs with $N/(2*(log N))$ components.
     • The major advantage of the crossbar switch is its potential for speed. In one clock, a connection can be made between source and destination. The diameter of the crossbar is one. (Diameter, D, of a network having N nodes is defined as the maximum shortest paths between any two nodes in the network.)
     • The MIN, on the other hand requires $log N$ clocks to make a connection. The diameter of the MIN is therefore $log N$.
     • If two pairs attempt to communicate at the same time along a shared path, one pair must wait for the other. This is called blocking, and such MINs are called blocking networks.

       Figure 1.10: Performance Comparisons of Some Dynamics INs and Performance Characteristics of Static INs.
     • Figure 1.10a shows a performance comparison among a number of different dynamic INs. Figure 1.10b shows a performance comparison among a number of static INs.