Interconnection Structures Video Lecture - Computer Science Engineering (CSE)

smell oh man Raheem so guys we are
dealing with the multi process
organization and we said we have
basically two ways to improve our
performance either we use multiple
independent jobs and just operate them
concurrently on a multiple processors in
parallel or we have a single job and we
break them into the partitions and then
execute them in parallel right so if you
can you can you can decompose a program
to parallel execute tasks and then just
you have to see whether they have there
are dependents a lot so we have the
intelligent compilers the Chuck's the
data independence about between the
chunks and then see which can be
executed power which part can be egg is
going to puddle and then start executing
then we have a multi process so if we
have a multi process systems and
basically they are organizing in two
ways either they are tightly coupled or
loosely coupled in tightly coupled
basically we have there they have a
sheared memory
what if you have a shared memory we call
them a tightly coupled processor and but
that doesn't preclude them from having
the local memory we have a local memory
as of the shared memory that means if
you have multi processors then you can
have a shared memory and no matter what
process you are and they want to
interconnect with each other you can use
the shared memory right and that scores
calls it tightly coupled and then we
have a loosely coupled there's an
alternative model of micro processor
basically in the distributed memory we
have or loosely coupled system we call
them what happens in this is we have
private local memory to the every
processor and how we then how the
question is how this processor will
communicate with the with with this
processor or another processor okay so
what happens is we have a switching
scheme in between which will route
information from one processor and the
processor because we do not have a
shared memory so what we have is a
switching scheme in between so basically
this is sometimes also called the what's
called as the message passing
so we send the we sound basically what
we send a packet which comes of address
contents and some adult detection so
that packs addressed to a specific
processor or taken by first available
process you can it can be taken to the
first whole process a broadcast we can
broadcast them or we can send it to a
particular processor so this scheme is
called as loosely coupled systems and
they have at the higher degree of
interaction between each other or we can
have a tactical system where we have a
shared memory now the companies that are
you know in in a multiprocessor system
we can have a cpus like this this is my
cpu but i we do not have the only cpus
okay we say it's a cpus but we can have
also the input/output processors and we
need to have some interconnection
structure now by which they can they can
they can you know they can sure what
their data or whatever they want to
share between each other so in a loosely
coupled system we have interconnection
structures basically so that we can
connect one cpu with the another say p
or like that or with the memory so they
believe that we have the interconnection
structures and we have the time she'll
come to us on multi board memory or
cross legislature Melissa T switching
Network or hypercube systems so the
first thing is time shared common bus so
what is the time share common bus we
have a memory unit this is a memory unit
and we have the CPU this is the CPU one
okay we can have the CPU - and CPU 3
similarly CPU 4 and so much on CPUs then
they connected with a one single common
bus and they are tied together with it
so anybody want to share anybody want to
send data ok they have to use they have
grab the bus and and one guy at a time
can grab the bus that's important also
okay so this really put it very puts up
a lot of limit on it
you know the only one system can sure
can have a transfer on a bus the other
guys are either doing the local tasks at
that moment of time or they are they are
waiting they are waiting it's not
because there's a lot of conflict it
could be the conflicts they could be
accident so we need some arbitration so
this the the limitation is that here is
that only one system or only one
processor can send at a time at a one
time that means only one process of
communicating with the memory so other
processor waiting are doing some local
tasks so this is this is limited so that
the oral speed is limited the single
path so that that's not going to be the
good thing are we can have then what
works cause a dual bus system okay we
have a time check on bus and we have
single bus then what we have an
improvement over this we said that what
we do is we have a local bus and a
system bus concept okay so if if we have
a CPU for examples in my CPU and with it
we can have also the input out
processors right and what caused input
channels and we could have also the
local memory let us connect them with a
local bus is connecting to them and we
have a another CPU see for example here
the same structure right and they are
connected here we have another guy here
maybe we have we have on this side also
the same structure CPU with input/output
processors and the local memory input
out processors and the local memory and
so on and now we have one bus what is
called as a system bus now we have a
system bus you can connect with local
our core processor using this bus the
local bus this is the local bus or you
want it a communicate with all of these
guys you need to have a system bus so
besides these users you need to have a
one more thing what is called as bus
arbitration unit or system bus
controller system bus controller so you
have to tie with this and this gal too
will have a system bus controller right
on one side combined with this and on
the other side it acts with this
similarly this guy also has a system bus
controller right system bus controller
and this is my system bus and there
could be a one big common shared memory
and connect with the system bus so if
you want it want to run a complicated
with the with the this memory
combination memory you have your system
bus if you are using local memory you
can use it so but one now one thing is
that we have here only single bus and
here we have a two other system okay but
still they are limited because system
bus will be taken up by only one system
so we cannot have we can't have access
to the common shared memory at the same
time if the processor from this guy this
processor one it communicates the
processor CPU to this is CP one for
example if you see V 2 is communicating
with the common shared bus and cp1 also
want to share the common bus same time
it can't happen because system bus can
be occupied by only one guy data so this
has a limitation so yeah it has improve
it or the single bus okay time shared
common bus with a single single bus
structure then we have a developer
structure which has a an added features
but it doesn't remove all the
deficiencies so we have moved on to the
next step what is called as the multi
port memory what's idea in a multi pod
memory is that you are trying let me say
what is the limitation here
remove the evolution that we want that
process one is accessing the commercial
bus the processor 2 also should be
access the same commercial bus so what I
do here is we break this common shared
bus into the chunks Boston commercial
memory sorry we break this common memory
into the modules okay say for me this is
the memory module 1 this is memory
module 2 this is memory module 3 mm
Belgium 4 so we don't have the one
single memory rather we have the memory
modules right this is my memory but we
have I broken them into the memory
module 1 2 3 & 4 whatever then say first
I have a 4 CPUs or whatever structure
they have ok they may have the local
buses and all that no problem but we
have s CPU 1 CPU 2 3 & 4 this is my CPU
1 now what happens is we connect the CPU
1 for example with every memory module
it's connecting with this it's
connecting with this it's connecting
with this module also it's connecting
with this module also right I should
erase this year so we should say like
this ok
getting me now this processor is also
connecting with everybody let me let me
draw it first so what we are having here
is that you have a different memory
modules and every CPU is connected with
every module right so you have every CPU
you connect with every module so that
means if this CPU is one connector with
the with the memory module one and CPU
two or what would like to have something
in a memory module two they can go
directly and three can the CPU three can
go here and see beforehand so that means
in memory will be access about all the
CPUs at the same time because this time
memory is not in a single unit rather it
has a different modules okay but it has
it does increase the efficiency but one
thing is there but what else if here all
the four want to access memory module
one then it will have the priority
concept so if someone is like CP 1 we
have given high priority then 2 and then
3 then 4 them if all of these guys are
out of them few want to access the
memory module one Symington see no
memory module one will be accessing one
at a time so it will get priority if
this guy enough CP 1 and CP u 3 for
example access CP 1 will be given
priority than CP 3 they in the term of
order of the CPUs here okay so the
conflicts will be resolved easily but if
you are accessing Lisa V 1 xx Sigma u 1
and these guy out of these guys they can
access these module without any conflict
because if other guy is not using that
module you can use that very easily but
it was a conflict then the priority will
suggest who should access that memory
module very simple but the problem is
that it requires expensive control logic
we need a very expensive control
to control all this chaos here and
leaves a large number of cabling as you
could see the large number of cables we
are seen only for modular 4 CPUs if that
increases these wires will increase
you know cables and connectors and
control logic peel is a shrub that the
big drawbacks of is is number one we
have a very expensive control logic and
then we have basically this thing that
we have the large number of cables and
connectors so to mitigate this we have
the third thing what is called as a
crossbar switch okay so we more the
third thing what is called as cross bar
switch rather than the multi coat memory
the idea multiple memory will be there
we have memory modules okay but we want
to remove that those you know wiring
that clutter right so what we have in a
crossbar switch is like this diagram as
you see this is the idea is same as the
cross in the image not so this is the
what we have is the multi port memory
right the idea is same as in a multi
port memory what we have now in multi
port memory right we have the number of
we divided the memory into different
modules now it is the same here in the
crossbar switch but we have the crossbar
switch like these and this has helped us
to reduce that wiring we had so we see
we saw the lot of lot of wiring that
wiring is gone
okay we have another nice and easy
structure as you can see here but we
have a cross spawn points at every
interconnection now cross point it is a
switch it is an artificial Abdullah deck
it knows how to connect from CPU one to
the memory one or from other guys other
guys are coming in what are the
priorities who should connect who should
not connect and this is all that in
switch this is what's called a cross bar
switch and a particular cross bar switch
you want to see how that works that
cross bar how this cross bar switch is
working basically is like this that the
cosmos will be basically the multiplex
now it has an arbitration logic as well
so on one side gets things from the
direct control and data address and
control from the CPU 1 similarly data
control address 1 CP 2 all the four can
connect with it no problem but all of
them who has the priority who should go
and only one out of the four will be
accessing the memory at a time so that
conflicts will be resolved much easier
easily by the cross point crossbar
switch right so memory module this may
be not known in memory the memory module
and whose data and whose address will be
and who will read a ride the memory
module will be done by the multiplexer
so this crossbar here right so it can
every CPU can it can take things from
all the cpus including its own cpu CP 1
and decides who should go to the memory
one so it has a switching facility so it
is basically a multiplexer and an
arbitration logic right so this is our
crossbar switch now the next thing what
we have is what else we go into the
multi stage now the multi-staged
switching so after this crossbar switch
we basically has the what is called as
the multistage switching Network in meld
I stay switching now what what we do is
we have the heart of it is the to cross
to interchange switch this thing this to
cross to in your sense which is
basically what is the highlighter ok
this thing I'm blocking off this is the
heart of the heart of the thing that we
have two inputs and two outputs and in
between is a switching element which can
take a a from the one in output or from
the zero output similarly B
from the zero or from the one right and
we can build out of this to cross to
hundreds which a multi-stage switch like
we have the Omega switch here we got 8
cross 8 Omega switch where we have Aryan
puts right we have 8 inputs on this side
okay and we have 8 outputs so where will
be connect which will be connected where
is done by this tab but here we have
special type of wiring that this 0 I
think I will go to hand ok here we go
here we go 0 this 0 connected here the 1
is connected to the second interchange
switch ii then 2 to this 3 to this 4 to
this 5 to this ok and 6 to this sam do
this and here we connect these output to
these 2 then this guy with these 2
within this guy with these 2 then this
guy with last 2 and this thing will
repeat in between so how many levels we
have in between we repeat that and if we
have a go for example to this 1 1 1 so
what will be the path this 1 1 1 itself
is suggesting me the path
ok what I'm saying is this 1 1 1 is
itself suggesting a path because it has
three ones the first one means first
stage second one is second stage third
one is third stage okay
the first stage one that means because
the output this is 0 this is 1 say for
example this guy the one this one wants
to go to this to the last one and one so
what should you do in a first stage that
is from this way it will connect to the
one that means 1 then with this guy ok
because this is 0 this is 1 in a second
stage it is also the 1 right
it will connect to the 1 okay so I have
one here
in the first stage it goes here connects
with the one here right and comes here
throw this one and again connects to one
that means to collect to the one that's
this thing and it will go here so for
example I have to go 1 0 0 from anywhere
say for a sound for from for I'm going
to go to the 1 0 0 what is it what is
the first mole MSB here that is 1
because I have the for the first level I
have 1 second level I have 0 third
letter has 0 1 0 0 so starting from this
it cut it goes here the first I had to
go 1 that is 1 connect with this right
and come here and here I have zero that
means connect with this zero right from
here I will go here and now here connect
with again with zero go third loud we
have 0 as you see here so 0 and you are
connected so from anywhere to anywhere
you can do no problem whatsoever but
there is a one big difference between
these two guys if you could see here
right if I have to go to the yes hmm
ok no no no it's not like that
you just just waited let me blast the
question ok you just concentrate here
these questions usual answer right you
just wait wait and watch ok moodle's
telling is about this thing so so you
can go from anywhere to anywhere no
problem whatsoever only thing is if for
example you want to go to this 1 0 0 say
first I'm saying I want to go to 1 0 0
the 4 and the 5 both want to go to this
1 0 0 so that is a problem because this
switch can handle only one connection at
a time right otherwise all the conflicts
will are getting
you know mitigated very easily and no
problem sir so it's it goes eight you
can bolt your sixteen cross sixteen
within the same fashion
okay you start from the zero that goes
to the first if you hear like here you
start from zero that goes here then one
goes to the next two goes to the the
next and next and next and so on right
then we go to 16 but I'm having a
sixteen across 16 Omega Network you will
then you will have here some eight we
would not have if we extend this to the
sixteen we will have here eight these
interchange switches okay and so on now
one goes here to go 0 1 goes here 2 goes
here 3 goes here
okay then four will go here five will go
here six and seven eight then after that
they will start repeating like this like
we did with this up to three we were
here up to four we start repeating right
add in a second we got first with these
two okay this with the next to this with
next to this will next to okay then we
come back later on we come back after
the fourth when you're done afford the
fifth one will come back like it come
back from here right and then it will
repeat listen at the next levels will
repeat and here we have only three
levels one two three and in that case we
will have some four levels okay 16 plus
6 because if we have eight across eight
so what how would you mind what are the
levels so that is equivalent to if we
have an input Omega if we have say for
example here we have the eight input
Omega so you presume it was eight input
Omega so n is equal to eight here so
it's a and so how many states it will
have is log to base two n much of stages
or that much of switches I will use
so it is having eight and is eight so
there will be three stages 2 to the
power 3 is 8 right because log to the
base 2 n is equal to whatever I are
calculated that and and I know is 8 here
so log to the base 2 8 is equal to 3 so
I need three states so if we have 16
cross 16 basically this is n inputs and
and outputs okay 16 cross 16 so how many
levels will be having here log to the
base 2 16 that's definitely 4 because 2
to the power 4 is 16 it getting me so
that much of levels will be having so we
are having four levels and how much of
if you want to say in one level how much
switches switching at the elements will
be there okay that will be n over 2
these are the number of those switch
these switch like this how many switches
we have in a particular level I mean say
if we have this M talking of this level
right
how many switching elements are
interchanged switch we have that is
equal to n over 2 if we our inputs are n
is equal to 8 what is n inputs so the
switching elements in a 1 level will be
4 how many levels log to the base 2 and
that is 3 right if you are 16 cross 16
then how many how many switching elbers
in a one-level that will be 8 and how
many levels will be having log to the
base 2 n that's log to the base 2 16
that is equal to how much for right
similarly no matter what now let 32
cross 32 like that and you will
calculate how many switching elements
you will have in a particular level okay
except for surfers once at 32 so it will
be how much 16 and how much of levels 5
right so you can do any
damn whatever the network right so the
next thing in it is the last thing in it
is what that is my hair done multi-stage
we have done multi stage now right what
we did just just quick about it we did
the time sheer common bus which has then
we have two types one is the single gown
sheer and then with a double sheer
common bus a local bus our system was
then we have multi port memory which
which broke the memory into the modules
then we but we had a lot of wiring there
so to reduce that we have crossbar
switch we put a cross points you know
and to reduce those wiring wiring a lot
of wiring of multi port memory
organization and then we said we have
the multi stage switching Network which
is the most beautiful thing and the last
thing we have in the interconnection
structures is hypercube interconnection
hyper cube inter connection so hyper
cube into one more thing to tell before
would happen and cube interconnection is
that in tightly coupled multiprocessor
right where we have the where we have
the memory shared memory the connection
will be between the processor and the
memory module so first pass and say
first pass okay for the network sets up
the pot sets of the path and succeeding
passes are used to transfer the address
into the memory and then transfer the
data in either direction know from this
way or that way
and depending on you have to read or
write similarly in loose legal
multiprocessor both source and
destination are processes processing
elements source as a destination of both
processing elements right when you have
aspect of the path then the source plus
transfer message to the destination
processor that's a message passing in a
loosely coupled why we do not have a
sheer memory now we go to the hypercube
error
connections