The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
3.2k views

A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R0, R1, R2, R3 and R4 respectively, before the execution of the instruction sequence.

 ADD  R5, R0, R1  ; R5 → R0 + R1
 MUL  R6, R2, R5  ; R6 → R2 * R5
 SUB  R5, R3, R6  ; R5 → R3 - R6
 DIV  R6, R5, R4  ; R6 → R5/R4
 STORE  R6, X  ; X  ← R6

 

The IF, ID and WB stages take 1 clock cycle each. The EX stage takes 1 clock cycle each for the ADD, SUB and STORE operations, and 3 clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is

  1. 10
  2. 12
  3. 14
  4. 16
asked in CO & Architecture by Veteran (21.9k points)
retagged by | 3.2k views

3 Answers

+40 votes
Best answer


This is what i have solved. so answer is 12

answered by Veteran (38.4k points)
selected by
@vicky

for  3rd and 4th instruction - c4 and c5 . there are 4 stall cycle

ans for 5th instruction  - c8 and c9  , there are  2 stall cycle .

so total stall cycles = 6

@Bikram sir 

thanks sir 

@Bikram sir @Vicky rix

A . Why I3 goes in ID stage in 6th cycle and not in 4th cycle ?

B. I think : Stalls are the cycles without any new input in the pipeline.

So,total cycles=12

Inputs=5

Therefore , stall cycles=12-5=7 Why is it wrong ?

@VS

A) They have given operand forwarding should happen from EX stage to ID stage. Which means ID stage of I2 should happen after the EX stage of I1, which means

                                                       

Now can we make 6 th clock-cycle as a split cycle ???

                        (Which means can we make both EX of I2 and ID of I3 in the 6 th clock-cycle (by doing EX in first half of clock-cycle and ID in 2nd half of clock-cycle) ??? )

To answer this, you need to first think what is meant by EX stage and what is meant by ID stage...?

                             EX stage means computing value using ALU unit and ID stage means Decoding the instruction and read the source registers from register file. Now we can definitely make EX stage in the first half of 6 th clock-cycle and ID stage in the 2 nd half of 6-th clock-cycle because one instruction is computing other is reading. (we always do split phase if 1 instruction is writing/computing and other instruction is reading but we will never do split phase if one instruction is computing and other instruction is also computing because ALU for 2 instructions cannot be done in a single clock-cycle. Example: EXECUTE-EXECUTE. Also we don't do split phase if one of the instructions is doing memory phase..the reason is generally memory phase alone needs atleast one clock-cycle).

Now coming back to your question, "Why I3 goes in ID stage in 6th cycle and not in 4th cycle ?"

                                         Because EX means computing and ID means reading so we can definitely make both in the same clock-cycle.



B) Number of stall-cycles means number of clock-cycles where you are supposed to do some stage (fetch or decode or ..anything) but you are not doing because of

             1) hardware needed for 1 stage is used by someother stage (structural hazard),

             2) there is a data dependency (RAW hazard, WAR hazard , WAW hazard),

             3) there is a control hazard (caused by BRANCH or JUMP instructions). 

Now coming back to your question "number of stall-cycles here"

Here number of clock-cycles, where we are supposed to do some stage work but not doing any work because of hazards = 6

For  3rd instruction  - c4 and c5 are 2 stall cycles                                                                                           For 4 th instruction - c4 and c5 are 2 stall cycles 
For 5th instruction  - c8 and c9  are  2 stall cycle . So totally 2+2+2 = 6 stall-cycles.

@Vicky

First of all thanks a lot for such a detailed explanation.

Actually for point A ..my doubt is not split phase access,I am saying I3 can go in ID stage in 4th cycle and remain there till 6th.Why is this wrong?

@VS

ur doubt is,

why

 

and not 

The reason is -- only in the 3 rd Execute stage of I2 data will be ready which I3 is trying to get from I2... If I3 is able to get the data at first Execute itself, then there is no need of 2 nd execute and 3 rd execute for I2. I2 needs 3 clock-cycles for execute(ALU) means the result of that ALU operation will be available only in the    3 rd execute stage...  

i2 E E E
i3 ID ID

ID

Now, I am saying why can't I3 remain in ID stage till 6th cycle and access reg file in 6th cycle itself.

I mean to say I get your point but whats wrong in the way I am thinking.

@Vicky rix

@VS  I3 only needs 1 ID stage .. then why are you extending it to 3 clock-cycles ??? 

Let us assume it is given in question that I3 needs 3 ID stages, still we cant do as you have drawn because we always start ID only after EX finishes.. And here we finish EX in the 1 st half of 6 th clock-cycle ..so only after that ID can start ... Also note that our computer doesnot know whether ID will need 1 clock-cycles or 2 clock-cycles or 3 clock-cycles... So we always start our "data getting stage of an instruction" only after "data giving stage of an instruction" finishes...

@Vicky

I3 needs only one ID stage thats right.But an instruction can surely wait in a state until the next stage is available.So,I3 can be in ID stage for 3 clock cycles.

(PS: This waiting thing you can also check in other gate previous year questions and also there have been extensive discussions on this topic here in GO.Now,I don't exactly remember the question but i have read it somewhere,specially something Multiple buffers concept.)

Can you provide some reference for your comment  :

ID start only after EX finishes.

Why stall cycle for I5 is not counted?
+15 votes

answer = option D = $16$ cycles are required

answered by Veteran (30.5k points)

@Arjun sir.

Which would be the best possible case for operand forwarding here?
Not 12 as given in below answers?
Yes, as per the wording of the question "16" should be the answer. But when a similar question (with EX-ID forwarding) was asked in GATE 2015, answer was taking the same as EX-EX forwarding (12 here).

https://gateoverflow.in/8218/gate2015-2_44 .

This one . And I was asking  the reason for the same .  How do we generalise  split phase occurs or not !

@arjun

I got this reviewed from a professor at IIT. He says assume split phase in case of operator forwarding if nothing is mentioned explicitly. He says it will be mentioned if the operator forwarding does not happens in the same cycle (which actually should be from the definition of operator forwarding ) otherwise you can challenge the question
Split phase access even for EX stage? Which IIT prof. said this?
okay, so what we should consider ?16 or that ex-ex forwarding to get 12? in GATE?
I could have chosen 16 in hurry. But after reading comments i can see there is nothing clear. However, i think ID should come in the same cycle as EX because EX stage is also including Data Memory phase. May be this is some kind of hint to choose 12 as answer.

@Arjun sir i think that question given in 2015 is a typo and they might have overlooked it split phase has got nothing to do with forwarding  we cannot assume things suppose if only one clock cycle is given for execute phase we are generally supposed to make writes at the rising edge then from where will it perform the actual execution of the operation if it writes the result directly in the rising edge so the answer here is 12  using operand forwarding, by default i only say WB AND RD PHASE CAN OCCUR IN THE SAME CLOCK CYCLE ONE IN THE RISING EDGE(WB) AND THE OTHER IN FALLING EDGE (RD) IN EVERY NPTEL LECTURE ON COA they r using the same example

+3 votes

Hi  , I have a very silly doubt here. 

 

Can we do the IF stage as I did ? because in other answers I could see , IF is also done after EX

amarVashishth 

srestha goel 

I have the confusion here that , IF stage of I4 instruction , can I start it in clock 4 ? because anyhow , ID should be started at  clock 7. or does IF also needs to start at clock 6 ?

Please clarify this doubt.

 

 

(N.B : please bear with my poor , illegible hand-writing )

 

answered by Boss (5.8k points)
edited by
Answer given to this question is 14


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,732 questions
39,309 answers
110,280 comments
36,733 users