Interconnection Networks
CSE Sem-4
Static Networks
❖ Interconnection networks can transfer data between processors
and memory. These are made of switches and links (wires,
fiber).
❖ Classification of network topology: Static Networks, Dynamic
Networks and Crossbar Networks
❖ Static Networks: These networks are formed by point-to-point
direct connections, which will not change during program
execution.
❖ Types of Static Networks:
1. 1-D : Linear array (used for pipeline architecture, N nodes are
connected with N-1 links)
2. 2-D : Ring (Two terminal nodes of a linear array connected
with one extra link), star, tree, mesh and systolic array
3. 3-D : Completely connected ring, 3 cube (degree of each node
is 3), 3-cube-connected-cycle (CCC)
Dynamic Networks
❖ Dynamic networks: These are implemented with switches, which are dynamically configured to match the
communication demand in user programs.
❖ Types of Dynamic Networks: Single stage network, multistage network, crossbar network
❖ Single stage network:
• A single stage of switching elements (SEs) exists between the i/ps and the o/ps of the network.
• The simplest SE that can be used is the 2*2 SE (which is 2*2 switch).
• This switch has 2 i/ps and 2 o/ps. Messages arriving on either i/p line can be switched to either o/p line.
The connection in a 2×2 switch can be of four types:
• In the straight setting, the upper i/p is transferred to the upper o/p and the lower i/p is transferred to the lower o/p.
• In the exchange setting, the upper i/p is transferred to the lower o/p and the lower i/p is transferred to the upper o/p.
• In the upper-broadcast setting the upper i/p is broadcasted to both the upper and the lower outputs.
• In the lower-broadcast setting the lower i/p is broadcasted to both the upper and the lower outputs
Multistage Interconnection Network ( MIN )
Multistage Interconnection Networks (MINs) are a class of high-speed computer networks where the first stage
of links is connected to the sources (usually processors) and the last stage is connected to the destinations
(memory modules).
MINs have been classified into two classes depending on the availability of paths to establish new connections:
1. Blocking: A connection between input/output pair is not always possible because of conflicts with
existing connections. Typically, there is a unique path between every input/output pair. A uni-path network is also
called a Banyan Network.
A Banyan network is defined as a class of multistage interconnection networks in which there is one and
only one path from any input node to any output node.
Delta Networks, are a subset of Banyan networks. The routing property of Delta Network is called a Self
routing Property or Delta Property.
Types of Delta Networks: Omega Network, Butterfly Network
2. Non Blocking: Any input can be connected to any free output port without affecting the existing
connections. They require extra stages and have multiple paths between every input and output. A popular example of
Non-blocking networks is a Clos network.
Omega Network
Omega Network:
• Omega networks are considered to be the most popular of Delta networks.
• The interconnections between stages are
defined by the logical rotate left of the bits
used in the port ids.
000 000 000 000
001 010 100 001
010 100 001 010
011 110 101 011
100 001 010 100
101 011 110 101
110 101 011 110
111 111 111 111
Omega Network
For (NxN) omega network,
• No of stages: log2N
• No of switches in each stage: N/2
• Each bit in the destination address can be
used to route the message through one
stage.
• The destination address bits are scanned
from left to right and the stages are
traversed from left to right.
• The first MSB is used to control the
routing in the first stage; the next bit is
used to control the routing in the next
stage, and so on.
• If the bit in the destination address is 0,
the message is routed to the upper output
of the switch. If the bit is 1, the message is
routed to the lower output of the switch.
Crossbar Switch Networks
Crossbar Switch system contains of a number of cross
points that are kept at intersections among memory
module and processor buses paths.
In each cross point, the small square represents a switch
Each switch point has control logic to set up the transfer
path among a memory and processor.
It calculates the address which is placed in the bus to
obtain whether its specific module is being addressed.
In addition, it eliminates multiple requests for access to
the same memory module on a predetermined priority
basis.
