408 views
A system employs $10$ stage instruction pipeline in which $5$% instruction results in data dependency, $10$% instruction results in control dependency, $2$% instructions results in structural dependency. $10$% instructions are exposed to data and control dependencies. If the penalty for structural dependency is $1$ clock and the penalty for control dependency and data dependency are $3$ clocks and $2$ clocks respectively. The average instruction time is _______ [in cycles]

edited | 408 views
0
1.92 ??
0
+1
I got 1.99 clock cycles as below is that correct?

Assume 100 instructions

Data Dependency --> 5%----->2 clk cycles ===> 5*2 ==> 10

Control Dependency --> 10% --> 3 clk cycles ===> 10*3 ==> 30

Structural Dependency --> 2%---> 1 clk cycle ===> 2* 1==>2

Control +Data Dependency --> 10% --> 5 cycles (sum of (2,3))===> 10* 5==> 50

10+30+2+50 ==>92

Average time per instruction =(100+92)/100 ==>1.92
0
0

ME gave $1.92$ as the answer.

I can arrive at $1.92$ after doing some arithmetic, but I am looking for a more structured solution. My major source of confusion is: data and control dependency instructions are already given as $5$% and $10$% respectively. However, data and control dependency instructions are again given as $10$%.

5% instruction results in data dependency, 10% instruction results in control dependency, 10% instructions are exposed to data and control dependencies.

• Doesn't doing simple arithmetic make us over-count penalties for both data and control dependencies?

I fail to understand your solution. As per your solution, $5$ instructions have data dependency ($5$% as given in the question), and there is a penalty of $2$ clock cycles, then why are you doing $5*3$? And you are doing the same thing in all situations except Control + Data Dependency.

0

10% instructions are exposed to data and control dependencies

That means this 10 % of instructions are suffering from data as well as control dependencies ..

SO they might incur total penalty of =>.pentalty due to control dependency + pentalty due to structural depedency

can u post there solution...

0
control + data dependency =3 cycle????? how ??
0

Assume 100 instructions

Normal execution = 1 * 10 + 99 * 1 = 109 cycles

But in this some of instructions are creating stalls so we have to add that also

Data Dependency --> 5%-----> 2 Penalty / stall cycles ===> 5*2 ==> 10

Control Dependency --> 10% --> 3 Penatlty / stall cycles ===> 10*3 ==> 30

Structural Dependency --> 2%---> 1 Penatlty / stall cycle ===> 1* 2==>2

Control +Data Dependency --> 10% --> 3 stalls for control dep + 2 stalls for data dep===> 10* 5==> 50

Total stalls ==> 10 + 30 + 2 + 50 = 92 cycles

Total cycles for 100 instructions = 109 + 92 = 201 cycles

Average time per instruction = 201/100 ==>2.01 cycles

0
Sorry that was a calculation error, I edited my solution now.
0
Why you took max(3,2)

If lets say control dep is due to branch it calculates target address at Instruction deode phase and data dependency may be at operand fetch phase depending on execution completion of dependent instruction phase ..
0

Yes you are right @jatin khachane 1. Thanks for correcting me.

My assumption was for 100 instructions the CPI was 1 assuming there weren't any stalls and adding the overhead due to stalls.

0

I am not sure about answer given by them or discussed here. @Shaik Masthan @Mk Utkarsh @lakshman please verify.

0

@jatin khachane 1 what if we assume the number of instructions to be 1000 then,

Normal execution = (1000 + 10 - 1)*1 = 1009

Stalls = (0.05*2 + 0.1*3 + 0.02*1 + 0.1*5)*1000 = 920

average time per instruction = (1009 + 920)/1000 = 1.929

as we increase the number of instructions the avg CPI will be almost 1. So, 1.92 should be the correct answer

Correct me if i'm wrong

0
All the explanations were right, but the little error is because of taking number of instructions if n is large then the error tends to zero i.e. CPI will be 1 and we have to add extra time for stalls i.e. 0.92 -> 1.92
+1

@Utkarsh Joshi

can u please ur thought on this ques

+1

let there are n instructions, Normally Pipe line without hazards gives us CPI = 1,

but in this question, there are hazards ==> CPI > 1

Number of instructions which cause structural hazards = 2% = 0.02 * n

Given that it cause penalty of 1 clock cycle ===> this instruction cause 1 more clocks as penalty compare to normal instruction

ā“ CPI for this type of instructions = 1+1 = 2

Number of instructions which cause Data hazards = 5% = 0.05 * n

Given that it cause penalty of 2 clock cycle ===> this instruction cause 2 more clocks as penalty compare to normal instruction

ā“ CPI for this type of instructions = 1+2 = 3

Number of instructions which cause control hazards = 10% = 0.1 * n

Given that it cause penalty of 3 clock cycle ===> this instruction cause 3 more clocks as penalty compare to normal instruction

ā“ CPI for this type of instructions = 1+3 = 4

Number of instructions which cause control and data hazards = 10% = 0.1 * n

it means, which cause control hazard, after stalling then it also cause data hazard....

and my assumption is this instructions are not counted twice

Given that it cause penalty of (3+2) clock cycle ===> this instruction cause 5 more clocks as penalty compare to normal instruction

ā“ CPI for this type of instructions = 1+5 = 6

Number of instructions which cause none of the hazards = ( n - ( $\frac{(2+5+10+10)}{100}$*n ) ) = ( 1 - 0.27 ) * n = 0.73 * n

Normal instructions are having CPI = 1

Average CPI = $\frac{((0.02*n)*2)\;+\;((0.05*n)*3)\;+\;((0.1*n)*4)\;\;+\;((0.1*n)*6)\;+\;((0.73*n)*1)}{n}$

= $((0.02)*2)+((0.05)*3)+((0.1)*4)+((0.1)*6)+((0.73)*1)$

= 0.04 + 0.15 + 0.4 + 0.6 + 0.73 = 1.92

by Veteran (65.8k points)
edited
0

@jatin khachane 1 @Shaik Masthan sir only doubt here is whether we are overcounting or not. If you are sure that we are not overcounting then 1.92 is okay!

+1

" 5% instruction results in data dependency, 10% instruction results in control dependency, 2% instructions results in structural dependency. 10% instructions are exposed to data and control dependencies"

The reason why I felt we are not over counting is the percentage of having control and data dependencies is more when compared to percentage of data dependency only.

Correct me if I'm wrong.

+2
if they really means, it is over counting, then

10 % control and data means there should be atleast 10% data hazards, but given that 5% of data hazards.

i hope they didn't correctly frame the Question grammatically.

But anyway it is a test series question, don't bother much about it :)
0
Hmm!
0

total 100 % instructions

5% data

10% control

2% structural

10% data and control

73% normal

so i think we are not overcounting

@Shaik Masthan

For normal instruction we should not take CPI = 1 as ideal pipeline is not given it may give wrong result in finding exact clocks

https://gateoverflow.in/204125/gate2018-50

0

Yes @jatin khachane 1 but here number of instructions are not given so when we take n as very large value the average tends to 1, that's the reason behind assumption of CPI as 1

0
Ya right

Thanks š
0

@Shaik Masthan I think your answer makes complete sense. It, however, needs a small edit. You have forgotten decimals and instead, have used integers in your calculation as highlighted below.

Number of instructions which cause none of the hazards = ( n - ( (2+5+10+10)*n ) ) = ( 1 - 0.27 ) * n = 0.73 * nāāāāāāā

+1

@jatin khachane 1

if nothing given about no.of cycles for each stage, by default we assume CPI = 1

@zeeshanmohnavi

corrected !

0

@shaikh brother  I am not getting why you have taken penalty + normal instruction CPI
Please tell me why this is not correct approach see it ->

0
penalty means extra how many cycles we want
0
@shaikh bro means whenever it says about penalty then we will add normal instructions CPI

And if it would say that there are 4 stages and result will be obtain after second stage due to this hazard then i think in these case we will take CPI 2 right ?
0

normally, we will fetch another instruction after 1 stage, right ?

So, if you are saying, after second stage, the next instruction which have to fetched, will know  ==> you are introducing 1 stall which is penalty

So, in general terms, if  you are saying, after k$^{th}$ stage, the next instruction which have to fetched, will know  ==> you are introducing k-1 stalls are penalty for that instruction