Lecture 3.2.

3 (Various interconnection networks) CO5

INTERCONNECTION NETWORKS

 In parallel computing, Interconnection networks are very crucial for efficient

communication among all processors within a similar system.
 There are two main approaches for interconnecting these processors:
static interconnection network and Dynamic interconnection network.
 High-speed represents a single processor or memory module or even a group of
processors.
 High-speed computer Networks aim to provide fast and efficient
performance(communication) among the nodes.
 The infrastructure supports high bandwidth and low latency.

There are two types of Interconnection Network

1. Static Interconnection Network

2. Dynamic Interconnection Network

Static Interconnection Network

 Static interconnection networks are fixed.

 In a unidirectional static interconnection network, connections between nodes allow
communication to occur in only one direction. So, the data can be transmitted from
one node to another node but not in the reverse direction. However, in a bidirectional
static interconnection network, the connection between nodes allows communication
to occur in both directions.
 The choice between both connections depends on the specific requirements of the
parallel computing system.

There are also two types of Static Interconnection Network

a) Completely/Fully Connected Network

 Connectivity: Here each node connected to every other node in the system, means
that there is direct connection between any pair of nodes.

 Bandwidth and Latency: So here is the highest degree of connectivity. Advantages

of fully connected network are low latency and high bandwidth.
  Cost and Complexity: As the number of wires require more here so the it is
expensive and it is much complex also

 Data Transmission: Since there are direct connections between processors, data
can be transmitted quickly and efficiently.

 Number of Links: Number of links are required here is n(n-1)/2. Here n = 6, so

total links will be 15 and each node link with (n-1) = (6-1) = 5 another nodes.

b) Limited Connection Network

It is also known as partial network, each node is connected by a subset of other nodes.
It offers advantages such as reduced cost and complexity, optimized communication
pattern and improved scalability. But they might introduce limitations in terms of
bandwidth and fault tolerance compared to Completely or Fully connected network.

Examples: Ring Network, Tree Network, Linear array Network, Mesh Network,
Hypercube Network

Linear Network: In a liner network every system is connected linearly or in single

row fashion where if one system fails every system afterwards will stops working.

Ring Network: There is no major difference between linear and ring network only
the difference between linear and ring is that the last node is connected to first node
in Ring Network.

Three cube Network: A “Three Cube Network” typically refers to a network

topology used in computer networking and data center design. This topology involves
three switches (or cubes) interconnected in a specific way to provide redundancy and
fault tolerance.
 Two-Dimensional Network: A two-dimensional network, in the context of computer
networking and parallel computing, typically refers to a network topology where
devices or nodes are arranged in a grid-like fashion. This type of network structure is
commonly used in various distributed computing environments for efficient
communication between nodes.

Here are some key points regarding Limited connection network,

 Connectivity: Here we notice lower number of connections per node compared

to Completely or Fully connected network.

 Communication Paths: Communication between some nodes may be routed

through other node in this network.

 Scalability: It offers good scalability as the number of connections per node

typically grows.

 Cost and Complexity: Limited Connection Networks have lower cost and
complexity.

 Bandwidth and Latency: Limited Bandwidth compared to

completely connected networks as there are limited number of connections.

Dynamic Interconnection Network

Unlike Static Interconnection Network, where connections are fixed between node, it enables
the dynamic reconfiguration of connection to adapt to changing communication
requirements.

Some key points about Dynamic Interconnection Network:

1. Reconfiguration:

 The network can dynamically change its configuration to adapt to different

communication patterns or workloads. This allows the network to connect any
two components as needed.
 Optimizes communication paths.
 Adapts to changes in workloads.
 Supports fault recovery by rerouting around failed components.
 Example: A multistage interconnection network (e.g., Clos network) can
reconfigure to provide direct paths between active components.

2. Switching Mechanisms:

 Refers to the methods used to transfer data through the network. Common
mechanisms include:
o Circuit Switching: Establishes a dedicated path for the entire
communication.
o Packet Switching: Divides messages into packets that are routed
independently.
o Wormhole Switching: Sends data in small "flits" (flow control digits)
that are transmitted in a pipeline fashion.
 Determines latency and throughput.
 Impacts network performance and efficiency.
 Example: Packet switching is commonly used in dynamic networks to support
parallel communications.

3. Flexibility:

 The ability to support various communication patterns and configurations

without major hardware changes. Dynamic networks can handle:
o Point-to-point communication.
o Broadcast or multicast.
o Data aggregation or reduction.
 Makes the network suitable for a wide range of applications.
 Reduces the need for application-specific hardware.
 Example: A crossbar switch provides maximum flexibility by allowing any
input to connect to any output.

4. Scalability:

 The network can grow to support additional components (e.g., processors or

memory modules) without significant performance degradation.
 Supports future expansion of systems.
 Ensures consistent performance as the system size increases.
  Example: Fat-tree networks are scalable and often used in data centers to
connect a large number of servers.

5. Fault Tolerance:

 The network can detect and recover from failures in components (e.g.,
switches, links) by rerouting traffic or reconfiguring connections.
 Increases system reliability.
 Ensures continuous operation despite hardware failures.
 Example: Dynamic networks use redundant paths to reroute data in case of
link or node failures.

6. Communication Efficiency:

 Refers to the network's ability to minimize delays and maximize bandwidth

utilization for data transfer.
 Reduces latency and improves overall system performance.
 Prevents congestion and bottlenecks.
 Example: Networks with low-diameter topologies, such as hypercube or
torus, reduce the average number of hops for data transfer, enhancing
efficiency.

Organizational Structure
Interconnection networks are composed of following three basic components −

 Links − A link is a cable of one or more optical fibers or electrical wires with a
connector at each end attached to a switch or network interface port. Through this, an
analog signal is transmitted from one end, received at the other to obtain the original
digital information stream.
 Switches − A switch is composed of a set of input and output ports, an internal
“cross-bar” connecting all input to all output, internal buffering, and control logic to
effect the input-output connection at each point in time. Generally, the number of
input ports is equal to the number of output ports.
 Network Interfaces − The network interface behaves quite differently than switch
nodes and may be connected via special links. The network interface formats the
packets and constructs the routing and control information. It may have input and
output buffering, compared to a switch. It may perform end-to-end error checking and
flow control. Hence, its cost is influenced by its processing complexity, storage
capacity, and number of ports.

Interconnection Network
Interconnection networks are composed of switching elements. Topology is the pattern to
connect the individual switches to other elements, like processors, memories and other
switches. A network allows exchange of data between processors in the parallel system.

 Direct connection networks − Direct networks have point-to-point connections

between neighboring nodes. These networks are static, which means that the point-to-
point connections are fixed. Some examples of direct networks are rings, meshes and
cubes.
  Indirect connection networks − Indirect networks have no fixed neighbors. The
communication topology can be changed dynamically based on the application
demands. Indirect networks can be subdivided into three parts: bus networks,
multistage networks and crossbar switches.

o Bus networks − A bus network is composed of a number of bit lines onto

which a number of resources are attached. When busses use the same physical
lines for data and addresses, the data and the address lines are time
multiplexed. When there are multiple bus-masters attached to the bus, an
arbiter is required.

o Multistage networks − A multistage network consists of multiple stages of

switches. It is composed of ‘axb’ switches which are connected using a
particular interstage connection pattern (ISC). Small 2x2 switch elements are a
common choice for many multistage networks. The number of stages
determine the delay of the network. By choosing different interstage
connection patterns, various types of multistage network can be created.

o Crossbar switches − A crossbar switch contains a matrix of simple switch

elements that can switch on and off to create or break a connection. Turning
on a switch element in the matrix, a connection between a processor and a
memory can be made. Crossbar switches are non-blocking, that is all
communication permutations can be performed without blocking.

References

Reference Books:
● J.P. Hayes, “Computer Architecture and Organization”, Third Edition.
● Mano, M., “Computer System Architecture”, Third Edition, Prentice Hall.
● Stallings, W., “Computer Organization and Architecture”, Eighth Edition, Pearson
Education.
Text Books:
● Carpinelli J.D,” Computer systems organization &Architecture”, Fourth Edition,
Addison Wesley.
● Patterson and Hennessy, “Computer Architecture”, Fifth Edition Morgaon Kauffman.

Other References:
 [Link]
 [Link]
parallel_computer_architecture_interconnection_network_design.htm

Video Links:
 [Link]
 [Link]