8.3k views
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 _____.

edited | 8.3k views
+24

For 100 instructions,

first 40 instructions are taking 3 cycles in PO phase. So first instruction will compete after 7 clock cycles and second instruction will complete after 10 clock cycles and so on...It is like an AP

7,10,13,...... up to 40th terms

So last term = 7 + 39 *3 = 124

first 40 instructions will be complete after 124 clock cycles.

For next 35 Instructions

41st instruction will complete after 126th clock cycle and 42nd instruction will complete after 128th clock cycle and so on...

126,128,.....up to 35th terms

So last term = 126 + 34*2 = 194

Next 35 instructions will be complete after 194 clock cycles.

For the remaining 25 instructions,

76th instruction will be complete after 195th clock cycle and 77th instruction will be complete after 196th clock cycle and so on...

195,196, 197, .....up to 25 term

So last term = 195 + 24 *1 = 219

hence, overall 100th instruction will be complete after 219 clock cycles...

Another way:

There are 100 Instructions out of which first instruction will take complete time, I mean (1 cycle for IF, 1 cycle for ID,1 cycle for OF, 3 cycles for PO and 1 cycle for WB) , So first instruction will take 7 clock cycles and remaining instructions will depend upon how much each individual instruction spending time in PO stage. Hence time would be:

7 cycles(for First instruction) + (40-1) * 3 + 35 *2 + 25*1 = 219 clock cycles..

+4
They never said that first 40 take 3 cycles, next 35 take 2 cycles remaining, 25 take 1 cycle. Wont the answer change in that case. I mean if we jumble the 3cycle instructions with 2 cycle instructions and 1 cycle instructions will the result be still be valid?
+2
Q says there is no data or control hazards but there may be structural hazards. If we visualize the timeline, there will be stalls due to PO taking extra cycles as next instruction's PO stage will wait for previous instruction's PO stage to finish. Why are we not taking this into account?
+1
Clock cycles$: 1\times 5\times 1+ 99\times 1\times 1 =104$

Extra Clock cycles$: 40\times 2\times 1+35\times 1\times 1=115$

$104+115=219\ clock\ cycles$
0

@rfzahid we are taking this into account. If you look at @akash.dinkar12's second method of solving the question, and make a timeline diagram (first type I, see how type I instructions stall amongst each other, you will get a CPI of 3; then try type II and you will get a CPI of 2 and so on), the numbers you will get will match up with what he has posted.

Structural hazards correspond to PO stages (or other stages, due to hardware being occupied by a previous instruction during a stall) causing stalls.

0
why are,nt we calculating first CPI as 1+0.4*2+0.35*1=2.15 and then calculating t=(n+k-1)*tp

(100+5-1)2.15=224cycles

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$

edited
+2

25 instruction takes 3 cycles,  i.e. these instructions suffering from 0 stall cycle,

Sir, small typo. It should be 25 instructions take 1 cycle,  i.e. these instructions suffering from 0 stall cycle,

+2
Corrected :-)
0
Thanks sir @DigvijayPandey sir small type mistake  So extra cycle would be 40*2+35*1+25*0=80+35=115, just change sir 20 to 25 , absolutely best answer just removing already done 1 cycle used earlier in total pipeline calc
+1
sir in pipelining cycle time of slowest stage is taken as a common cycle time of all other stages of the instruction .

then why here you had applied structural hazard concept at perform operation stage and stalled for two cycle time instead of taking slowest stage cycle time as common cycle time .
0
nice approach digvijay sir
0

Why can't I do it with (k+(n-1))*tp

for PO stage: 0.4*3 + 0.35*2 + 0.25*1 = 2.15 cycles for PO stage. This is larger than all the 5 stages of the given pipeline.

So applying the above formula it gives (5+99)*2.15 =224 cycles.

0
Sir does if mean that If a stage take n cycles then stalls caused by that stage is n-1??
0
Q says there is no data or control hazards but there may be structural hazards. If we visualize the timeline, there will be stalls due to PO taking extra cycles as next instruction's PO stage will wait for previous instruction's PO stage to finish. Why are we not taking this into account?
0

@rfzahid, structural hazards occurs when instruction shares the common hardware resource but in question nothing is mentioned like that. regarding your second question we are considering stalls in the answer these stalls are nothing but extra cycles.

0

@Gupta731 whenever tp is multiplied to k+n-1 i.e (k+n-1)tp , we get "execution time" of pipelining but here in this question they've asked for "number of clock cycles" required. Hence for that, N+k-1 gives us the number of cycles required for completion of execution of the sequence of given instructions.

0
simple and good approach
0

Why structural hazards are not taken into consideration here? i;e why are we considering that many PO instructions can be executed in parallel? In the question it has been told that there are no data and control hazards. If we do not make such assumptions, we get number of clock cycles as 227.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 # of Cycles I1 IF ID OF PO PO PO WB 7 I2 IF ID OF PO PO PO WB 10 I3 IF ID OF PO PO PO WB 13 I4 IF ID OF PO PO PO WB 16 I5 IF ID OF PO PO PO WB 19 I6 IF ID OF PO PO PO WB 22 The number of cycles for 40 such instructions = 7 + (39)*3 = 124 cycles 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 # of Cycles I1 IF ID OF PO PO WB 6 I2 IF ID OF PO PO WB 8 I3 IF ID OF PO PO WB 10 I4 IF ID OF PO PO WB 12 I5 IF ID OF PO PO WB 14 I6 IF ID OF PO PO WB 16 The number of cycles for 35 such instructions = 6 + (34)*2 = 74 cycles 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 # of Cycles I1 IF ID OF PO WB 5 I2 IF ID OF PO WB 6 I3 IF ID OF PO WB 7 I4 IF ID OF PO WB 8 I5 IF ID OF PO WB 9 I6 IF ID OF PO WB 10 The number of cycles for 25 such instructions = 5 + (24)*1 = 29 cycles The total number of cycles for 100 such instructions = 124 + 74 + 29 = 227 cycles

Please let me know if anything is wrong here.

+3

I got the mistake I made in my previous comment.

See below image. Hopefully it helps someone. :) 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.
0
Why can't I do it with (k+(n-1))*tp

for PO stage: 0.4*3 + 0.35*2 + 0.25*1 = 2.15 cycles for PO stage. This is larger than all the 5 stages of the given pipeline.

So applying the above formula it gives (5+99)*2.15 =224 cycles.
0

yes same doubt @Gupta731

0
You are applying the formula wrong..

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

edited
0
it's perfect. Thank you sir.
0
very good answer .. Thank you sir...
0
Thanks. It really helps.
0
Thanks. Simple and easiest approach.
0
Nice approach
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.