MadeEasy Test Series: CO & Architecture - Pipelining

Question

An instruction pipeline consists of following 5 stages:
IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MA = Memory Access and WB = Register Write Back.
Now consider the following code:

1. LOAD            R8, 0(R5);               R8 = memory [R5]
2. LOAD            R9, 4(R5);               R9 = memory [R5 + 4]
3. ADD              R7, R8, R9;             R7 = R8 + R9
4. SUB              R6, R7, R8;             R6 = R7 – R8

Assume that each stage takes 1 clock cycle for all the instructions. How many cycles are required to execute the code, without operand forwarding over a bypass network?

• A. 9
• B. 10
• C. 11
• D. 14

Comments

I got 12 cycles as answer.

---

I am also getting 12 but the ans given is 14

---

plz provide soln for this ques

---

Test series' are extensively flawed like the coaching centers . Not reliable.

Answer 1

	1	2	3	4	5	6	7	8	9	10	11	12
I1	IF	ID	EX	MA	WB
I2		IF	ID	EX	MA	WB
I3			IF	X	X	ID	EX	MA	WB
I4				X	X	IF	X	X	ID	EX	MA	WB

WB and ID can go together in 1 cycle- WB writes to register file in first half of a cycle and ID reads it from the second half. This is a common technique and need not be explicitly given in question. So, answer is 12 cycles without operand forwarding. (Suppose this answer is not there in choice for GATE, we can do WB and ID in separate cycles and get the answer in choice. But for previous GATE questions this was never the case). 

With operand forwarding:

	1	2	3	4	5	6	7	8	9
I1	IF	ID	EX	MA	WB
I2		IF	ID	EX	MA	WB
I3			IF	ID	X	EX	MA	WB
I4				IF	X	ID	EX	MA	WB

Comments

Nice Explanation Sir !! Thanks

---

error

IF below IF in cycle 4,5 in without operand forwarding.

ID below ID in cycle 5 with operand forwarding.

---

Thanks. Corrected..

---

Arjun Also  OR=Operand Read(fetch) and WB = Register Write Back can work in same cycle right?(General doubt ,Not related to this question).

---

@arjun sir ,

in ur without operand forwarding fig  ID of I3 could come in cycle 4, couldn't it ?
Similarly in With Operand Forwd Fig Couldn't ID of I4 come in cycle 5.

couldn't operand frw be done from MA of I2 to I3? Why there is a stall in I3 ?

---

For the first one- it won't affect the answer rt? Actually an instruction can enter a stage only when the previous one has entered the next stage there by freeing the output buffer of this stage. But we can avoid this restriction by using multiple buffers- unnecessary here as there is no change in result.

MA to MA forwarding? Not possible because I3 is an ADD instruction and it needs data in EX stage.

---

@arjun sir,
No Sir , MA of I2 to EX of I3 ...?
Q3] couldn't operand frw be done from MA of I2 to I3? Why there is a stall in I3 ?


Q1] in ur without operand forwarding fig  ID of I3 could come in cycle 4, couldn't it ?
{ ID is instruction decode before decoding all the operands must be in register
 ID of I3 could come in cycle 4  also ? I know it wont affect ans . i wann to check my understanding }

Q2] Similarly in With Operand Forwd Fig Couldn't ID of I4 come in cycle 5.
{ i think this is not possible since EX of i3 is not finised in cycle 5 }

---

1. MA of I2 to EX of I3- that is the operand forwarding I have shown.

2. Nopes. Not possible. Because of data dependency. I3 depends on I2. So, only after I2 produces output to register (WB), I3 can read the values from register. These two operations can go together in a single cycle due to split phase technique- WB happening in first half, and ID in second half of a clock cycle.

3. yes, same reason I told in previous comment. If we want we can do with extra buffer, but no use.

---

@Arjun Sir : What if question didn't specified with or without operand forwarding, then which one is better to follow. What if we follow both methods and find the answers and both answers is there in option ?

---

For any question, if in doubt chose the best implementation- here one with OF.

---

@Arjun Sir, as ADD and SUB instructions are using register addressing modes, MA stage would not be there for ADD and SUB because we need not access the memory for effective address calculation.

Hence, even without Operant Forwarding, this can be done in 10 cycles, right?

---

Then we need special technique to skip the pipeline stages based on instruction. AFAIK there is no such way. (each stage is being done at maximum speed possible. So, skipping is not easy)

---

@Arjun Sir,
1)  in with operand forwarding solution, can you please explain why EX of I3 is in cycle 6 and not in cycle 5 ? Can't we have split phase access here and put MA of I2 and EX of I3 in clock cycle 5 ? 

 

---

@swagnikd
Here , Operand is being forwarded from MA of I2 to EX of I3 . MA should complete before operand can be forwarded . This cannot happen in split phase  because only after the completion of MA it will be ready which takes at least a full clock cycle.

---

@pC
Are you saying that, Since memory access takes time, MA can never complete in half cycle? Is that the reason why it will always take a full clock cycle?

---

@swagnikd , What are the instrctions that can be completed in half cycle ?
Just see this GATE question : https://gateoverflow.in/1391/gate2005_68?show=77905#a77905

It should bring more clarity in Pipeline concepts :)

---

@pC Thank you. :) I read it all. I really understood the concepts. But nowhere it is explained why MA takes atleast 1 full clock cycle. Also I need to know what are the instructions that are completed in half cycle. Can u help me with these? 

---

Arjun Sir please have a look Similar question 

https://gateoverflow.in/85102/test-made-easy

---

@Arjun Sir

plz have a chk here

In operand forwarding case, why there need a stall ?

I think it is not required

Because , there we can do EX to EX forwarding and then the stall also be removed.

Data dependency is there in I₂ to I₃

that is fine

But this cannot be a problem , if we forward from EX to EX stage.

Moreover it will remove stall,

chk here http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/forward.html

The 1st example of this link in operand forwarding is forwarding from EX to EX stage

So, can we conclude if there is no possibility to forward from MA to EX stage (or it is causing a stall) , we can simply forward from EX to EX stage?

---

@Arjun sir here WB = Register Write Back.  is given we cannot assume it in two stages i.e. if simple WB is given then we can slpit otherwise there is no meaning of WB = Register Write Back. 

---

the IF of I4 is in cycle 4. Won't it cause a structural hazard with the MA of the first instruction?

---

Has anyone told that there is no separate Instruction and data cache or any other structural limitation?

---

Didn't get what does 

Actually an instruction can enter a stage only when the previous one has entered the next stage there by freeing the output buffer of this stage.

mean for ID of I₃ not being present in t_4.

Does it have anything to do with ID is also kind of OF as there's no such phase. So, it's waiting till the data is available and getting it using split phase with WB of the previous instruction?

---

@Arjun Sir, @pC

Is WB --> EX forwarding is also used here ??

So that I3 will have correct inputs in 6th clock i.e R8 from I1[WB-->EX] and R9 from I2 [MA-->EX] ?
 

---

@Arjun sir can we do forwarding from WB stage to EX or from WB to MEM stage??

---

Sometime next week we can have a discussion on pipelining.

---

Ok sir..just can you clear this small doubt now

Is WB-->EX forwarding used here sir...in one other question like this one only it is used..

---

this doubt is taking away my mental peace..

---

@sushmita...did u got tht doubt cleared if yes please comment abt that

---

@srestha mam, Did you find reason why we not used operand forwarding EX-EX.

why we are taking uncessary stall cycle.

 

---

@ arjun sir ,@sushmita mam, if I3 to I4 op forw can be done in EX-EX then why can't it be done the same way in I2 to I3(I3 EX stage at T5) ? What is actual work EX and MA do in instructions 1,2?

---

@pranavsettaluri9 I2 contain indirect memory access (this part is indirect memory access "4(R5)") of actual of I2 is calculate in MA stage not in EX stage so we do operand forwarding from MA-EX stage .

In I3 and I4 no indirect memory access is required so we do operand forwarding from EX-EX stage.

---

why EX of I4 is not there in stage 8 ?

---

can any one explain me about memory access stage under add or sub instruction.

---

@gatecse @Arjun sir,@Abhrajyoti00

Small doubt.

Why decode of I3 not started in 4^th clock.

my reason

   → decode include reading the value of register.

 

Please clarify 

---

@GateOverflow04 If you notice, $I3$ is ADD instruction : $R7 = R8+R9$. Now the value of registers R8 and R9 are depending upon $I1$ and $I2$. That is why until the value of $R9$ is written back $(WB)$ in $I2$, the $ID$ (instruction decoding) can’t start. And both $WB$ and $ID$ can happen in same cycle as @Arjun Sir has stated:-

$WB$ and $ID$ can go together in 1 cycle- $WB$ writes to register file in first half of a cycle and $ID$ reads it from the second half. 

Answer 2

I1

IF

ID

EX

MA

WB

I2

IF

ID

x

x

EX

MA

WB

I3

IF

ID

x

x

x

x

EX

MA

WB

I4

IF

ID

x

x

x

x

x

x

EX

MA

WB

Total required cycle is 14.