What is an interconnection network?
An interconnection network in a parallel machine transfers information
from any source node to any desired destination node. This task should be
completed with as small latency as possible. It should allow a large
number of such transfers to take place concurrently. Moreover, it should
be inexpensive as compared to the cost of the rest of the machine.
The network is composed of links and switches, which helps to send the
information from the source node to the destination node. A network is
specified by its topology, routing algorithm, switching strategy, and flow
control mechanism.
Difference between static and dynamic interconnection network
https://www.youtube.com/watch?v=uFab0OOcAfI
explain different types of static interconnection network:
Static (fixed) interconnection networks are characterized by having fixed
paths, unidirectional or bidirectional, between processors.
Static interconnection networks for elements of parallel systems (ex.
processors, memories) are based on fixed connections that can not be
modified without a physical re-designing of a system.
Static interconnection networks can have many structures such as a linear
structure (pipeline), a matrix, a ring, a torus, a complete
connection structure, a tree, a star, a hyper-cube.
In linear and matrix structures, processors are interconnected with their
neighbors in a regular structure on a plane.
Two types of Static Interconnection network identified:-
1. Completely Connected Networks (CCNs)
2. Limited Connection Networks (LCNs).
1- Completely Connected Networks
In a completely connected network each node is connected to all other
nodes in the network.
CCN guarantee fast delivery of messages from any source node to any
destination node (only one link has to be traversed).
Every node is connected to every other node in the network, therefore
routing of messages between nodes becomes a straightforward task.
CCN guarantee fast delivery of messages from any source node to any
destination node. Only one link has to be traversed.
CCNs are expensive in terms of the number of links needed for their
construction. This disadvantage becomes more and more apparent for
higher values of N.
2-Limited Connection Networks
Limited connection networks (LCN) do not provide a direct link from every
node to every other node in the network. Instead, communications
between some nodes have to be routed through other nodes in the
network.
The length of the path between nodes, measured in terms of the number
of links that have to be traversed, is expected to be longer compared to
the case of CCN.
A number of regular interconnection patterns for LCNs include:
1. linear arrays
2. ring (loop) networks
3. two-dimensional arrays (nearest-neighbor mesh)
4. tree networks and cube networks.
Write short note on multistage network:
Multistage connection networks are designed with the use of small
elementary crossbar switches (usually they have two inputs) connected in
multiple layers.
It is an interconnection system consisting of multiple layers of interlinked
switching elements arranged in a predefined topology allowing processor
and memory modules to communicate with each other.
The network like this is an alternative for crossbar switches if we have to
switch a large number of connections, over 100. The extension cost for
such a network is relatively low.
In such networks, there is no full freedom in implementing arbitrary
connections when some connections have already been set in the switch.
Because of this property, these networks belong to the category of so
called blocking networks.
A multistage connection network for parallel systems be like as shown
below in Fig-5
Fig-4 MultiStage Connection Network(Benes Network)
However, if we increase the number of levels of elementary crossbar
switches above the number necessary to implement connections for all
pairs of inputs and outputs, it is possible to implement all requested
connections at the same time but statically, before any communication is
started in the switch.
Write short note on crossbar network:
Crossbar Switches
A crossbar switch is a circuit that enables many interconnections between
elements of a parallel system at a time.
A crossbar switch has input data pins, output data pins and control pins.
It has multiple input and output lines that form a crossed pattern of
interconnecting lines between which a connection may be established by
closing a switch located at each intersection, the elements of the matrix.
A crossbar switch is an assembly of individual switches between a set of
inputs and a set of outputs. The switches are arranged in a matrix.
If the crossbar switch has M inputs and N outputs, then a crossbar has a
matrix with M × N cross-points or places where the connections cross. At
each cross-point is a switch, when closed, it connects one of the inputs to
one of the outputs, and below is the diagram of Cross-bar switch:-
Fig-3 Cross-Bar Switch
Control instructions can request reading the state of specified input and
output pins which is their current connections in a crossbar switch, as
shown in above.
Write short note on 3D hypercube connection:
Hypercube (or Binary n-cube multiprocessor) structure represents a
loosely coupled system made up of N=2n processors interconnected in an n-
dimensional binary cube. Each processor makes a node of the cube.
Therefore, it is customary to refer to each node as containing a processor, in
effect it has not only a CPU but also local memory and I/O interface. Each
processor has direct communication paths to n other neighbor processors.
These paths correspond to the cube edges.
There are 2 distinct n-bit binary addresses which can be assigned to the
processors. Each processor address differs from that of each of its n
neighbors by exactly one bit position.
Hypercube structure for n= 1, 2 and 3.
A one cube structure contains n = 1 and 2n = 2.
It has two processors interconnected by a single path.
A two-cube structure contains n=2 and 2n=4.
It has four nodes interconnected as a cube.
An n-cube structure contains 2n nodes with a processor residing in
each node.
Each node is assigned a binary address in such a manner, that the
addresses of two neighbors differ in exactly one bit position. For example,
the three neighbors of the node with address 100 are 000, 110, and 101 in a
three-cube structure. Each of these binary numbers differs from address 100
by one bit value.
