GATE CSE 2018 | Question: 50

Question

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch $(IF)$, Instruction Decode $(ID)$, Operand Fetch $(OF)$, Perform Operation $(PO)$ and Writeback $(WB)$, The $IF$, $ID$, $OF$ and $WB$ stages take $1$ clock cycle each for every instruction. Consider a sequence of $100$ instructions. In the $PO$ stage, $40$ instructions take $3$ clock cycles each, $35$ instructions take $2$ clock cycles each, and the remaining $25$ instructions take $1$ clock cycle each. Assume that there are no data hazards and no control hazards.

The number of clock cycles required for completion of execution of the sequence of instruction is _____.

Comments

Po takes 215 cycles + remaining instructions takes 4 cycles=219

---

Important point related to this Question

==> In a standard 5-stage pipeline, if a stage like PO requires more than 1 clock cycle for an instruction, it creates a structural bottleneck.

==> A structural hazard occurs when the hardware cannot support all possible combinations of instructions that we want to execute in the same clock cycle. When a functional unit or execution stage takes multiple clock cycles to complete, an instruction behind it that needs that same unit must be stalled until the unit becomes free.

Trick to solve this Question might not work for other ..

$\text{Total Clock Cycles} = (\text{Pre-}PO\text{ cycles})+ (\text{Total } PO\text{ cycles})+ (\text{Post-}PO\text{ cycles})$

 

---

Shortcut approach:

1st normal execution i.e, 

(5+100-1)1+extra=104+extra

2nd count extras i.e,40*2+35*1+25*0=115

(In previous step already 1 cycle is added so now only add remaining)

Finally Total =219

Answer 1

Total Instruction $= 100$
Number of stages $= 5$
In normal case total cycles $= 100 +5 -1 = 104$ cycles

Now, For PO stage $40$ instructions take $3$ cycles, $35$ take $2$ cycles and rest of the $25$ take $1$ cycle.
That means all other stages are perfectly fine and working with $CPI$ (Clock Cycle Per Instruction)$ = 1$

PO stage:
$40$ instructions take $3$ cycles i.e. these instructions are suffering from $2$ stall cycle,
$35$ instructions take $2$ cycles i.e. these instructions are suffering from $1$ stall cycle,
$25$ instructions take $1$ cycles i.e. these instructions are suffering from $0$ stall cycle,

So, extra cycle would be $40*2 + 35*1 + 25*0 = 80+35 = 115$ cycle.

Total cycles = $104 + 115 = 219$

Comments

@SparshSheth Structural hazards (resource confilct)

---

In question if there given no data hazard then we can use split case am i right ?!

 

---

@rohith1001 So as per the diagram we are assuming that first the 40 instructions will execute, then 35 instructions and finally 25 instructions, but what if a different order of execution is followed? For example first an instruction which takes 3 clock cycles for PO, followed by an instruction with 2 clock cycles for PO, and then the instruction which takes 1 clock cycle for PO, and this sequence is followed. In such questions is it correct to assume a certain order of execution?

Answer 2

Total Instruction =100
Instruction Fetch (IF). Instruction Decode (ID). Operand Fetch (OF), and Write back (WB) performed in 1 cycle.
PO stage:
40 instructions takes 3 cycle
35 instructions take 2 cycles
25 instructions take 1 cycle
Average number of cycles required is = (40 x 3+35 x 2+25 x 1)/100 = 2.15 cycles.
On an average first instruction completed in 1+1+1+1+2.15 cycles = 6.15;
Remaining 99 instruction will takes 99 × 2.15 = 212.85 cycles
Total number of cycles is 6.15+212.85 = 219 cycles.

Comments

You are applying the formula wrong..

So according to your solution

First stage will execute in 6.15 cycles

The next 99 instructions will execute in 2.15 cycles..

Therefore time=6.15+99*2.15

                           =219

---

good answer.. I like it.

---

@sourav_123 best solution......

Answer 3

We have 100 instructions.We only focus on PO stages.Becoz of pipeline,instructions execute like this...

1st instruction takes (1+1+1+3+1)=7 Clock cycles.

2nd to 40th instructions PO stages takes=39*3 clock cycles.

41th to 75th instructions PO stages takes=35*2 clock cycles.

76th to 100th instruction PO stages takes=25*1 clock cycles.

So, total=7+(39*3)+(35*2)+(25*1).

219 clock cycles required.

Comments

please tell how 1st instruction takes 7 clock cycles ?????

 

---

@sahil_gupta Because 1st instruction will go thought all fetch,decode,operand loading, perform operation and write back where perform op take 3 clock cycles and all other take 1 clock cycles each..

---

But why it takes 3 clock cycles?

Answer 4

7 + 39×3 + 35×2 +25×1 = 219 clock cycle

Comments

Another way could be 100 + Extra cycles  = $100 + 40*2 + 35 + 4$ (for initial filling of pipeline) = 219

---

 

7 + (39×3) + (35×2) +(25×1) = 219 clock cycle.SIMPLE & CLEAN

Answer 5

Consider it like a counting problem :

There are total (40*3 + 35*2 + 25*1 ) 'individual' PO stages and each 'individual' PO stage will take one clock cycle. Also, the initial filling of the pipeline will require 3 'extra' clock cycles of IF, ID and OF and the last clock cycle of the pipeline will always be a WB stage.

Also, since there is NO data hazard or control hazard, the IF, ID, OF and WB stages will fit in the pipeline without causing any stalls. So, the only hazard possible is due to PO stage - so, one clock cycle for each PO stage.

So, total clock cycles required = No. of clock cycles for PO stage + Initial filling of Pipeline + one last cycle for WB stage = 215 + 3 + 1 = 219 clock cycles.

Answer 6

the number of clock cycles required = Total number of cycles required in general case + Extra cycles required
= (5 + 99) + Extra cycles
= (104) + 40*(3-1)+35*(2-1)+20*(1-1)
= 104+ 40*2+35*1
= 104 + 115
= 219 cycles