Lecture - 15 Dynamic Interconnection Networks

Dynamic Interconnection Networks
Dynamic networks provide

reconfigurable connections
between nodes.
A simple switch with two
inputs (x and y) and two
outputs (z0 and z1). A
control line, s, determines
whether the input lines
should be connected to the
output lines in straight state
or exchange state.
Using this switch we can
design a network that can
connect a source x to one
of eight possible
destinations 0 to 7.
The destination address is
denoted bit-wise d2d1d0
A simple 1-to-8 interconnection network.

A permutation refers to the connection of a set of sources to a set

of destinations such that each source is connected to a single
destination. A permutation [(s0,d0),(s1,d1), ......,(s7,d7)] means that
source s0 is connected to d0, s1 to d1, and so on.
Switching the position of the connections of inputs 1 and 4 to the
switches 0 and 2 of stage 2. This new network is able to connect 0
to 0 and 1 to 1, simultaneously, and establish the permutation.
Classification of dynamic networks
In a Crossbar switch network every
input node can be connected to
any output node. The crossbar
switch provides all possible
permutations, as well as support
for high system performance.
The connection between each pair
of nodes is established by a
crosspoint switch.
There are N2 crosspoint switches
for providing complete
connections between all the
nodes. The crossbar switch is an
ideal network to use for small N.
However, for large N, the
implementation of the crosspoint
switches makes this design
complex and expensive
A Crossbar switch
Single-stage networks, also called
recirculating networks, require
routing algorithms to direct the
flow of data several times through
the network so that various
connections and permutations can
be constructed.
In Multistage networks, due to
more switches, the number of
possible permutations on a single
pass increases; however, there is a
higher investment in hardware.
A single-stage network based on the
shuffle-exchange connection
A Concentrator interconnects
a specific idle input to an
arbitrary idle output.
A Connector establishes a
path from a specific input to a
A concentrator with six
specific output. inputs and four outputs
In a Nonblocking network, it is always possible to connect an idle
pair of terminals (input/output nodes) without disturbing
connections already in progress. Such a network has no blocking
states whatsoever. These type of networks are said to be universal
networks since they can provide all possible permutations.
The Rearrangeable networks are also universal networks; however,

in this type of network it may not always be possible to connect an
idle pair of terminals without disturbing established connections.
In a Rearrangeable network, given any set of connections in
progress and any pair of idle terminals, the existing connections can
be reassigned new routes (if necessary) so as to make it possible to
connect the idle pair at any time.
In contrast, in a Blocking network, depending on what state the

network may be in, it may not be possible to connect an idle pair of
terminals in any way.
Blocking Interconnection networks
Omega is a well-known multistage Blocking network. It
provides necessary permutations for many applications.
Originally proposed by Lawrie, as an interconnection
network between processors and memories.
The network allows conflict-free access to rows, columns,
diagonals, and square blocks of matrices.
This is important for matrix computation. The omega
network provides the necessary permutations (for certain
applications) at a substantially lower cost, since the omega
requires fewer switches.
The omega network consists of n = log2 N stages, where N is
the number of inputs /outputs. Each stage in the network
consists of a column of N/2 switches as a shuffle pattern of
links, exchanged with the next stage.
Omega Interconnection network
Figure represents an omega network when
N=8. Each switch has two inputs, two outputs,
and four possible connection states.
The four possible states

of the switch
An eight-input omega network
There is an efficient routing algorithm for setting the states of the switches
in the omega network.
A source S (with address sn-1 sn-2 . . . s0 ) has to be connected to a certain
destination D (with address dn-1 dn-2 . . . d0 ).
Starting at input S, connect the input of the first switch [in the (n-1)th
stage] that is connected to S to the upper output of the switch when dn-1=
0; otherwise, to the lower output.
This process continues until a path is established between S and D.
Figure represents a path between source 2 (i.e., S = 010) and destination 6
(i.e., D =110).
The omega network is a blocking network; that is, some permutations
cannot be established by the network. For example, a permutation that
requires sources 3 and 7 to be connected to destinations 1 and 0,
respectively, cannot be established. However, such permutations can be
established in several passes through the network.
In general, for a single-stage shuffle-exchange network with N nodes,
every arbitrary permutation can be realized by passing through this
network at most 3(log2N)-1 times.
In addition to one-to-one connections, the omega network also
supports broadcasting.
The omega network can be used to broadcast data from one source
to many destinations by setting some of the switches to the upper
broadcast or lower broadcast state.
Broadcasting 2
to 4, 5, 6 & 7
Switching functions- Interconnection
network
Every permutation can be represented in terms of a set of
switching functions. The switching representation of omega
network is derived from representations of basic functions,
such as shuffle and exchange.
Shuffle ( ): The shuffle function is defined as
(xn-1 xn-2 . . . x0 ) = xn-2 xn-3 ... x0 xn-1
This function can also be represented as a set of switching
functions, such as:
Exchange (E): The exchange function E is defined as

E = (xn-1 xxn-20 x0) = xn-1 xn-2
This function can also be represented as a set of switching
functions, such as:
Switching function- Omega network
Omega Network ( ). Recall that the omega network with n stages is a sequence of
n shuffle-exchange functions. That is, = E( (E (E( ())))). Thus, to determine
to which destination a given source X=xn-1xn-2....x1x0 is connected, we must first
apply function , then E, next again , and so on. As shown below, after applying
and E n times to the source X, the switching functions can be obtained.
First we apply :
(X ) xn-2x0 xn-1.
Next, we apply E to xn-2x0 xn-1.
E( (X )) xn-2x0 xn-1 cn-1 ,
where the bit cn-1 represents the control signal to the switches of the (n-1)th stage,
and denotes the Boolean XOR function. One control signal ci goes to all the
switches of the stage i, and each switch can have two states, straight (ci=0) and
exchange (ci=1). Note that the bit xn-1 is exclusive-ored with cn-1, rather than
complemented. This is because the bit cn-1 determines whether a switch is in the
straight state or the exchange state, if a switch is in exchange state then the
exchange function should be applied.
Now we apply and then E to xn-2x0 xn-1cn-1

E( (E( (X )))) xn-3xn-1cn-1 xn-2cn-2 ,
where the bit cn-2 represents the control signal to the switches of the (n-2)th stage.
Therefore Omega function is (X ) xn-1cn-1x1c1 x0c0.
And its switching function is fi = xi ci for 0 i n-1

Lecture - 15 Dynamic Interconnection Networks

Uploaded by

Copyright:

Available Formats

Lecture - 15 Dynamic Interconnection Networks

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture - 15 Dynamic Interconnection Networks

Uploaded by

Copyright:

Available Formats

Dynamic Interconnection Networks

Dynamic networks provide

A simple 1-to-8 interconnection network.

A permutation refers to the connection of a set of sources to a set

The Rearrangeable networks are also universal networks; however,

In contrast, in a Blocking network, depending on what state the

The four possible states

Exchange (E): The exchange function E is defined as

Now we apply and then E to xn-2x0 xn-1cn-1

You might also like