Pipeline CPU-III Video Lecture - Electronics and Communication Engineering (ECE)

so we're we are discussing about the
MIPS processor architecture we have
developed one data path for a single
cycle implementation of instructions and
the data path as we have seen is like
this and in this one we have said that
there are a number of data units which
are duplicated so when you go for single
cycle implementation of the MIPS
processor there are duplicated data
units and we have seen later that the
other design printers of having single
cycle implementation that is on an
average the CPU performance will become
poor so an improvement over this that we
have tried is instead of trying for a
single cycle implementation we can go
for multi cycle implementation and in
multi cycle implementation what we have
done is we have broken this data path
into a number of steps so there are five
different steps and in addition to that
we can reduce the duplication of data
units so for example earlier we had one
Lu and a number of other units and all
the add operations are now being termed
done by only this ALU and of course
because we are going for multi cycle
implementation so we had to had we had
to have a number of intermediate
registers for storing the intermediate
values then we just mentioned that after
discussing this that will go for a
pipeline to data path that means how
this can be converted to a pipelined
architecture now as we have said in case
of pipelining that more than one
instructions will be in the pipeline
simultaneously some instruction will be
fetched previous instruction will be
decoded the instruction which was first
before that will be executed instruction
which was hist before that that will
finally put the result either in memory
or in one of the registers so these are
different operations that will be
performed by different instructions
maybe during the same clock period so
because we'll have more than one
instructions in the pipeline
simultaneously so it is quite obvious
that for pipeline architecture it is
better that not to go for optimization
of the hardware that means instead of
trying to replace all the adders with a
single ALU we will make use of the same
single cycle implementation architecture
as this and try to see how this can be
converted to a biplane to happen did
about it okay but will have duplicated
during its so I have just redrawn this
single cycle implementation of the
architecture here okay so you find that
all the units which you are there in the
single cycle cycle architecture all of
them are played are present here at this
stairs when an instruction is to be
fetch the data units which are involved
is obviously the program counter the
program counter has it has to give the
address of the instruction that has to
be pasted we have this instruction
memory then we have this adder which
increments the program counter after an
instruction is fetched okay then we have
this multiplexer a selector which
selects one among this incremented
program counter or the branch address
which has to be generated during the
execution phase so one of this will be
selected by this multiplexer
and the next program counter value will
be loaded into the program counter
higher from the next instruction will be
fetched once an instruction is first we
have said in multi cycle implementation
that during the next phase what you have
to do is we have to decode the
instruction and at the same time you
have also said that we can read the
registers which are specified by the
instruction the values of the registers
which are required because we don't know
that what is the instruction that is to
be executed until and unless the
instruction is decoded so this treat the
reading of registers is done in advance
before knowing what is the instruction
and we have also mentioned that this
read operation does not
Honda operation because even if the
register values which are read they are
not needed they'll be overwritten by
subsequently by the appropriate values
okay so here also during the next phase
the registers will be read it will be
read simultaneously the instruction will
be decoded okay these phase onwards
whatever operation that has to be
performed that depends upon the decoder
output okay so this whole thing as you
see that this is nothing but in the
single cycle implementation of the
processor that you have done only thing
that we have done here only changes now
these operations are more organized that
is the all the operations which have to
be performed is broken into five
pipeline stages the first stage is
responsible for fetching an instruction
from the memory and this stage we call
as ia for instruction is instruction
fetch stage okay the next stage is
instruction decode or ID which we are
specifying as instruction decode at the
same time registered it third stage in
the pipeline which is the execute stage
we are calling it as a XOR execute and
at the same time if there is any memory
of reference operation to be performed
the address of the memory is also
calculated so during this phase it will
be execution of the instructions for our
type instructions as well as address
calculation for memory if it is an
intake instruction okay fourth stage is
actually the memory access stage I mean
this is the stairs well when either you
write into the memory or you read from
the memory so we have to write into the
memory if the operation to be performed
is a stored or SW type of operation the
data will be read from the memory it
will be if it is load word or LW type of
instruction and the final stage that is
the fifth stage in the pipeline we call
it a WP or right back
right bat means whatever is the output
the data will be written back into one
of the registers
depending upon which ever is the
destination register that is specified
within the instructions okay when I
discussed about up about the pipeline
you have said that whenever I have so
many pipeline stages in between every
stairs I have to have pipeline latches
ok so here again between every stairs
I'll have a number of pipeline stages
pipeline latches so I will have a
pipeline latch here I'll have a pipeline
latch here I will have a pipeline latch
here I will also have a pipeline last
year ok now coming to this architecture
you find that as long as the data flows
in the forward direction that is from
left to right so this direction flow of
direction from left to right when all
the instructions need to the data flow
from left to right the pipeline gives
maximum efficiency okay but there are
two instances when the pipeline will
suffer that is when that information has
to move in the backward direction that
is from right to left okay so we have
two such situation one is the right back
stairs when the data has to be written
from the fifth stairs has to move from
the fifth stage to the second step okay
so this is one situation when the data
will move from right to left and the
second is this one that is in case of
any branch instruction you are
calculating the branch address here in
the execution phase and the branch
address that is calculated has to be
loaded into the program counter in the
first stage that is instruction fetch
stage okay so these are the two
situations when the data has to move or
the information has to move backwards in
the pipeline okay and whenever such
situation arises the pipeline
performance is bound to degrade but we
have to see that how we can reduce that
degradation
okay now one way that this can be
handled is by means of the reservation
table and you find that this kind of
architecture is nothing but a special
case of generalized pipeline that we
have discussed so if you remember this
figure a generalized pipeline
architecture where the data can move
from in the forward direction data can
also move in the backward direction okay
now for any operation how this different
pipeline stages are to be used for
execution for completion of a particular
function that has to be specified with
the help of a reservation table okay and
we had given two such instances of
reservation tables one for computation
of function a otherwise for computation
function B and this reservation table is
nothing but specifying that during which
time staff which of the pipeline stages
will be used for performing which
operation okay so if I go by this type
of reservation table type of concept and
that case you'll find that all the
instructions which has to pass through
this pipeline will have its own
reservation table okay say for example
if I go for if the instruction which is
to be executed is simply add R 1 R 2 R 3
if this is the instruction that is pre
executed the operation of this is our
three gets the value of R 1 plus R 2
okay so what is the first operation
first we have to face with this
instruction for fetching the instruction
the instruction fetch stage will be used
the second operation that is to be
performed is decoding the instruction as
well as reading the register values r1
and r2 which is to be performed during
the idea stage okay the next operation
will be you have to add r1 and r2 which
is to be performed by the execute stills
okay next is the result has to go to r3
okay
so output of r1 plus r2 is available at
the ALU output which will pass through
this multiplexer and in the fifth stage
the data will be written back into
register r3 okay so this is how you find
that all these pipeline stages will be
used sorry here the operation will not
be our three gates are one or two but it
is our one gets r2 plus r3 because the
first register which is specified in the
instruction that is the distinction
register how about the sequence of
operations remain the same so if I want
to design the reservation table for this
instruction what I will do is I'll have
pipeline stages I t then sorry first
pipeline stages I F then ID then execute
next is memory the next is right back
let us see how the reservation table of
this will look like during time step T
zero this instruction will make use of
the I've steps during t1 the next time
period the instruction we make use of I
T steps during t2
it will make use of the execute stress
okay during t3 what is the stage that is
used right back cannot be done during t3
because now the data is available here
memory operation is not needed so during
t3 this instruction does not make use of
any of the stages okay during t4 it will
make use of this tight back stairs and
the data has to be written into register
so the unit that will be used is ideally
okay so during t4 again ID will be used
okay
ID and write back together because you
have to select the multiplexer properly
but because all the stages of pipeline
information has to flow all the stages
flow through all the stages and that is
controlled by the latches at every stage
we have a latch so even if I am not
making use of this data unit for
transferring the data from this latch to
this latch I need one clock cycle and
that is what is t3 during t3 I am not
performing any operation simply moving
the data the result from one latch to
another night okay so this will be the
reservation table for this add
instruction similarly I can
so this will be during t4 okay so
similarly I can decide that what will be
the reservation table for every
instruction okay now once you know this
reservation table for different
instructions then I can go for pipeline
scheduling that is once an instruction
enters the pipeline I can decide when
the next instruction can enter okay that
is following the pipeline state diagram
that we have already discussed that is
one way this can be done but however
this can be improved let us say how this
improvement can be made when I talk
about this pipeline then what are the
problems that we can face in the
pipeline the problems that you face in
the pipeline are sometimes called
pipeline hazards
okay one kind of pipeline hazard is
called a structural hazard
so this statue a structural hazard
arises if the harder head does not
permit combination of the instructions
that we wanted to execute simultaneously
say for example when we had converted
the single cycle architecture to a multi
cycle architecture you find that in a
single cycle architecture which is
nothing but a variation of this without
the latches here I have used an
instruction memory and data memory the
instruction memory and data memory are
different in multi cycle implementation
what you have done we have combined the
instruction memory and data memory into
a single memory unit okay now if I use a
single memory unit for storing both the
instruction and the data then what
problem will face here you find that in
this particular case I can have a
situation that one instruction can be
faced simultaneously during the same
clock period some other instruction can
access the data in memory either for
reading the data or for writing the data
okay if I combine these two in a single
memory unit that is have both the
instruction and the data into the same
memory in that case such a type of
operation will not be possible either
you can fetch the instruction from the
memory or you can read data or write it
data into the memory one of the two
operations you can do you cannot do both
that means fetching the instruction and
accessing the memory data memory
simultaneously is not possible okay
whereas that is possible if I have this
instruction memory and data memory
separately so if I combine these two
then obviously that gives leads to some
bottleneck in the pipeline that is
simultaneous instruction read and data
rate is not possible and this is a kind
of Hazard which is given by the pipeline
and that is because of the harder'
limitation okay and this kind of Hazard
is known as structural hazard so one
such structural hazard in this pipeline
architecture is
avoided by having separate memories for
instruction and data the second kind of
hazard that we can have in a pipeline is
called a control hazard
control hazard comes due to the fact
that some decision has to be taken based
on the insta output of some instruction
while other instructions are already in
the pipeline
say for example a branch instruction we
have said we have taken an instruction
like this branch on equal or 1 or 2 then
offset this is an example instruction
that you have taken now here it says
that whenever R 1 and R 2 are same then
you have to take the branch and the
branch address will be opposite value
away from the current program counter
oil ok now find that whether this branch
has to be taken or branch is not to be
taken that depends upon the output of
this instruction that means whether R 1
and R 2 they're equal or not that you
will come to know only in the execute
phase so if we have to decide that what
will be the next program counter value
only after execute phase that means at
least for two clock periods the pipeline
will not be able to take new
instructions ok this is a problem which
is called pipeline stalling stalling the
pipeline that means you are not allowing
new instructions to enter the pipeline
okay and that problem will always be
there because I can never know without
executing the instruction whether the
branch is to be taken or branch is not
to be taken but we have to find out some
organization ok so what is the
optimization that can be made one
optimization is branch prediction that
means to predict whether the branch is
to be taken or branches not to be taken
in the simplest case we can assume that
branches not to be taken
so whenever this branch on equal r1r2
upset that enters this pipeline that
goes to all the stages in case of
stalling what we have to do is until and
unless these stages come take that means
until and unless we know that r1 is
equal to r2 or r1 is not equal to r2 we
do not allow giving instructions
instructions to enter the pipeline okay
in case of this prediction when I'm
predicting that branch is not-taken I
will not stop instructions from entering
the pipeline when the first instruction
that is branch on equal that moves from
I f2 decode stairs the next instruction
from the sequence will enter the IPS
here our my prediction is branch will
not be taken so the next instruction
already enters the i p-- stairs when the
branch on equal comes to this execute
stairs the next instruction which was
the knife comes to ID and the third
instruction will come to I upstairs only
after this I will come to know whether
the branch will be successful or branch
will not be successful in case the
branch is not successful then all these
instructions will pass to the pipeline
as it is okay
in case the branch is successful in that
case the time taken by these two
instructions in this pipeline stages
will be a state because in that case the
next instruction that will be fetched
into this IH stairs that will come from
the branch address not from the same
sequence in which the instructions are
already taken okay and in this
particular case possibly it will not
lead to any problem because the
operation that you are doing in ID is
only registered rate and we have already
said that way even if you read the
registers you are not executing on them
you are not doing any performance on
them okay so possibly the operation that
you do even in this idea stage that is
not harmful but there can be situations
in case of other pipelines that whatever
operation you do in these two stages
that may already modify some of the data
which is harmful
okay so that has to be carefully looked
into whenever you design a pipeline if
you have any such a data modification
during these stages okay either fault or
example that is not helpful only will
only the time taken by the instructions
in these two stages are wasted no they
have come from higher i f2 ID yes okay I
have to I agree then the instruction
which has come to ID that has to go to
execute states so I can have the control
unit if the control unit decides that
the branch is to be taken that means my
prediction was strong what I will do is
I'd not load the days to this latch so
that it does not enter the execution
stage because the moment it enters the
execution stairs it is going to modify
that data so that I will not commit that
is to be taken by the controller
okay so this is one approach when you
predict that the branch is not-taken the
other approach can be branches taken
that is also another prediction okay and
this can be further defined based on the
history what happens is whenever and
some instructions are executed you
maintain the history of the instructions
which are executed the situation's
become more complicated but more
sophisticated okay so in the history
whenever such a branch instruction is
encountered you go back to the history
to check our linear execution of the
same branch instruction what happened
whether the branch was taken or punch
was not taken if you find that in
earlier case branch was taken you assume
that branch will be taken if in the
earlier kists you find that the branch
was not taken again you assume that the
branch will not be taken so accordingly
you select that which instruction next
has to come to the side stairs okay how
about these are all finally find my son
obviously in this case you need extra
amount of memory additional memory to
maintain the history so obviously there
are some advantages and disadvantages in
every approach okay so that is about the
control hazard the third kind of hazard
that we have in case of pipeline is
called data hazard
now what is this data hazard suppose I
have a sequence of instructions like
this add r1 r2 r3 and we have said that
this operation performs addition of r2
and r3 and the result goes to r1 okay
suppose the next instruction is subtract
or 5 or 1 or 4 this is the next
instruction and this will perform the
operation
r5 gets the data which is R 1 minus r4
what will be the performance of this
pipeline in this case because you'll
find that the second instruction cannot
be executed until and unless r1 is
written in 2 because only then the right
data is available for the subtract
instruction
okay now coming to this pipeline what
happens the first instruction subtract
will come here instruction fetch then we
will come to exec ID then it will come
to execute then it will pass to memory
and only in the right back stairs
or one will be written back into the
stage devices okay coming to the second
instruction you find when the add
instruction is in this stage that is
memory stays the second instruction is
in the execute stage ok so when the addi
instruction is in the memory stairs the
second sub tacit subtract instruction
which is the immediate next that is in
the execute stage and in the execute
stairs it expects the correct value of
r1 isn't it but the correct value of r1
has not been set yet that will be set
only after write back that isn't
so if we don't take any extra precaution
then this subject stairs will use delay
is the previous value of r1 because the
correct value of r1 has not yet been
restored but in r1 you have some value
so this subtract operation will make use
of the previous value of r1 which is a
wrong one to give you a wrong result
into our faith isn't it so naturally
this is again another kind of hazard and
no compiler will give you this error
this error will come only at the output
okay so we have to take extra precaution
to take care of such problem so how this
can be done what can be done is you find
that when the subject instruction is in
the execute stairs at that time value of
r1 is available at the output of value
that means at the output of this latch
okay so here what we can do is I can
bypass these two stages for our one
value what I can have is I can have a
feedback from this to this ALU input
okay that means here I have to have a
multiplexer one more multiplexer one of
the inputs to the multiplexer will come
from the register file the other input
to the multiplexer will come from the
ALU output itself now the controller has
to decide that which one to select okay
so whenever such a type of destra hazard
situation comes now the controller has
to select the ALU output to be fed to
the ALU input and the subject operation
can continue as needed so while doing
this what I am doing is effectively I am
bypassing this memory access stairs
I am also bypassing the write back
stairs getting the data directly in
the input from the Ailee world put
itself okay so this is a mechanism which
is called a bypass mechanism sometimes
it is also called forwarding mechanism
okay so solution to this data hazard can
be by bypassing or forward
okay so we can have these three kinds of
hazards in pipeline architecture the
structural hazard as we have said that
this can be avoided by duplication of
resources however it is not possible to
avoid it always there will be some
situation in which structural hazards
will come and in that case pipeline will
suffer but by duplication of resources
we can ensure that the performance
degradation will be as minimum as
possible similarly we can have control
hazards and these situations are bound
to come we cannot avoid it but what can
be done is in such cases I can move this
adder which is used for computation of
branch address from this stage to this
stage right now this adder is in the
execute stairs if I move this from the
execute stage to idea stairs because
even in ideaa stairs all of them are
available whatever is this offset that
is available whatever is the next
program counter value that is also
available so if I move this ladder from
the execute stage to idea stairs I can
even save one clock period for taking
the battery okay so when this control
hazard can be removed but it cannot be
totally avoided the third one is data
hazard for avoiding that data hazard we
can make use of the bypassing or
forwarding mechanism and in this case
what is needed is in this register to
ALU circuit a registered to ALU data
path had to make some more modification
that means I have to put one more
multiplexer here control circuit has to
be designed accordingly so that control
circuit will identify can locate such
data hazards and generate the control
signals accordingly so that the data to
the ALU is available at that point
so with this I'll stop this pipeline
architecture and the processor
architecture as such so next class
onwards we'll talk about the other
components of a computer system