5.1k 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.

$$\begin{array}{lll} \text{ADD} & \text{R5,R0,R1} & \text{;R5} \leftarrow \text{R0 + R1} \\ \text{MUL}& \text{R6,R2,R5} & \text{;R6} \leftarrow \text{R2 * R5} \\ \text{SUB} & \text{R5,R3,R6} & \text{;R5} \leftarrow \text{R3 -R6} \\ \text{DIV} &\text{R6,R5,R4} & \text{;R6} \leftarrow \text{R5/R4} \\ \text{STORE} &\text{R6,X}& \text{;X} \leftarrow \text{R6} \\ \end{array}$$

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$

edited | 5.1k views
0
Please someone change the direction of arrows in the instructions shown in this question.
0
It's $4-$ stage pipeline.  Memory access phase of RISC architecture is implicitly included in $EX$ stage so split phase can be safely assumed.
0

$$\require{xcolor} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline &C_1&C_2&C_3&C_4&C_5&C_6&C_7&C_8&C_9&C_{10}&C_{11}&C_{12}\\\hline \textbf{ADD}&\text{IF}&\text{ID}&{\color{green}{\underset{\enclose{circle}{1}}{\text{EX}}}}&\text{WB}\\\hline \textbf{MUL}&&\text{IF}&{\color{green}{\underset{\enclose{circle}{1}}{\text{ID}}}}&\text{EX}&\text{EX}&{\color{green}{\underset{\enclose{circle}{1}}{\text{EX}}}}&\text{WB}\\\hline \textbf{SUB}&&&\text{IF}&\color{red}{-}&\color{red}{-}&{\color{green}{\underset{\enclose{circle}{1}}{\text{ID}}}}&{\color{green}{\underset{\enclose{circle}{1}}{\text{EX}}}}&\text{WB}\\\hline \textbf{DIV}&&&&&&\text{IF}&{\color{green}{\underset{\enclose{circle}{1}}{\text{ID}}}}&\text{EX}&\text{EX}&{\color{green}{\underset{\enclose{circle}{1}}{\text{EX}}}}&\text{WB}\\\hline \textbf{STORE}&&&&&& &\text{IF}&\color{red}{-}&\color{red}{-}&{\color{green}{\underset{\enclose{circle}{1}}{\text{ID}}}}&\text{EX}&\text{WB}\\\hline \end{array}$$

$\color{red}{-}\quad\text{Stalls}$
$\color{green}{\enclose{circle}{1}} \quad \text{Operand forwarding from EX-ID using split phase}$

Correct Answer: $B$

by Boss (43.3k points)
edited
0
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
0
But,I have one doubt here:

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

0

@Kapil @Bikram sir

here number of stall-cycles = 6 right ?

+4
@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
0

@Bikram sir

thanks sir

0
@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 ?
+4

@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.

0
@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?
+1

@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...

0
 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

+1

@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...

0

@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.

0
Why stall cycle for I5 is not counted?
0
Thanks Vicky good explanation
+1
@Ayush, Becuase I5 is executing after I4 without any stalls.
0
@vs mam same doubt here also
0

anyone help!

mul and div are storing in same register(WAW), and in solution when div "ID" phase is going "R6" is not written back by mul instruction then how can we perform "ID"  at C7 while the mul is writing back to "R6".

the question is not saying anything about register renaming (is register renaming is default?).

0

MUL operation completed at C7, then how it cause WAW hazard ? @sudharshan

0

@Shaik Masthan thanks for your response actually I got my doubt clear by Arjun sir video.

0

IF of I4 has happened at 6th clock cycle.

This is because there will be temporary register or stage buffer in between two stages(IF-ID). One stage is considered still engaged until next stage takes data or control from stage buffer in order to proceed further. When the next stage is working then only previous stage can work.

answer = option D = $16$ cycles are required

by Boss (30.6k points)
+1
Why EX and ID of next instruction go together in 1 cycle by performing EX in first half and ID in next half of a clock cycle? It is not explicitly mentioned in question but nowadays it is assumed to take best option.
0

Are people still working with RISC pipeline?

0
why not? There might be multiple units for each of these stages but base is still the same.
0
@Arjun sir it is operand fording from EX to ID stage, not EX to EX stage.

here we have done same like

https://gateoverflow.in/8218/gate2015-2_44?show=32409#a32409

right?
0

@srestha goel Its a good reference you have given here. It from the latest question paper.

Until we know what books they follow; How can we get sure that these are default scenarios?

Taking that as defaults is true from the context of NPTEL references also?

0
Operand forwarding we have to assume the best case unless mentioned otherwise in question..
0
here it is mentioned from EX stage to ID stage. So, why shall not take 16 cycles rather 12 cycles
0
It is EX to ID. But this can be done in 1 cycle itself. EX stage operates in first half of the cycle and ID stage in next half. So, ID stage gets the modified output from EX stage.
0

as per NPTEL, Split access phase is b/w WB & ID only.

0
We cannot do split-phase access between same unit - like from EX-EX. But does it say we cannot do between EX-ID?
+1

They are not telling us about EX-ID split-phase access but are telling us about WB-ID split-phase access. So, it should be ok to take WB-ID split-phase access as default only, but not EX-ID.

also, on a casual note : there is no single question encountered in any previous gate year paper which suggests to perform EX-ID split phase access.

+3

Sir, should I be wrong if I think it a bit otherwise?Split phase is possible for register read and write operation, when we are writing in first half and reading in 2nd half . So WB-ID split phase possible. But here in the question it is explicitly mentioned that forwarding taking place from EX to ID ,so here ALU operation will take itself one cycle, so at the end of the cycle the value will be available for the next instruction's ID . So I think that the answer is 16.Sir, may be I am wrong.

If ' Operand forwarding from the EX stage to the ID stage is used.' was not mentioned then the answer would have been 12 bcz of ALU to ALU forwarding .

0
Do decode of an instruction has anything to do with execution of previous instruction?I don't think ID depends on EX,therefore both can be in 1 cycle,which will result in the total of 12 cycles.
0

@Arjun  sir i think here operand forwrding is not used in solution by amar. EX(I1) and ID(I2) should be done at one cycle. Thats what operand forwarding.

One more doubt normaly in risc pipeline WB ( done in two parts) to ID(operand fetch) also possible here not mentioned so we take default or ignore that.

0

@Arjun sir.

0
Which would be the best possible case for operand forwarding here?
+1
Not 12 as given in below answers?
+4
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).
0

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 !

0
@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
0
Split phase access even for EX stage? Which IIT prof. said this?
0
okay, so what we should consider ?16 or that ex-ex forwarding to get 12? in GATE?
0
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.
0

@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

0
when to use EX to EX and EX to ED
someone reply fast. Just few hours are left for Gate 19

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

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 ?

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

by Active (3.8k points)
edited
0
Answer given to this question is 14