ISI2012-PCB-CS-2a

Question

A machine $\mathcal{M}$ has the following five pipeline stages; their respective time requirements in nanoseconds (ns) are given within parentheses:

• $F$-stage — instruction fetch ($9$ ns),
• $D$-stage — instruction decode and register fetch ($3$ ns),
• $X$-stage — execute/address calculation ($7$ ns),
• $M$-stage — memory access ($9$ ns),
• $W$-stage — write back to a register ($2$ ns).

Assume that for each stage, the pipeline overhead is $1$ ns. A program $P$ having $100$ machine instructions runs on $\mathcal{M}$, where every $3$rd instruction needs a $1$ – cycle stall before the $X$-stage. Calculate the CPU time in seconds for completing $P$.

Comments

@dhruvkc123

every 3rd instruction needs a 1-cycle

Means  3rd, 6th, 9th,.....,99th instruction needs one more extra cycle. So total count is 33 not 34.

I hope this helps.

---

99= 3+(n-1)3= 33 (finding nth term .. ) this will sure  help you

---

Answer : 1370

---

Nice Question !!

Answer 1

As there are $5$ stages so $1$ instruction will take $5$ clock cycles, now all subsequent
instructions will take $1\text{-}1$ cycle each So,
Now without any stall cycle total cycles are $ 5+(100-1) =104$

Now each $3^{rd}$ instruction is taking one stall cycle So,
Total stall cycles in $100$ instructions are $\dfrac{100}{3}=33$

Total cycle to complete the $100$ instructions are $104+33=137$ cycles.

Max time taken from all the stages are $9\text{ ns}$ and $1\text{ ns}$ is overhead
then $10\text{ ns}$ can be given as clock cycle time
So, total time taken is: $137\times 10=1370 \text{ ns}$   ...:)

Comments

i am getting stall also in 4,5,6..........cycle and so on,

pls see this;

consider there are only 6 instructions

F	D	X	M	W
	F	D	X	M	W
		F	D	---	X	M	W
			F	D	---	X	M	W
				F	---	D	X	M	W
					---	F	D	---	X	M	W

 

YELLOW COLOR CELL SHOWS THE STALL THAT IS PRESENT IN EVERY THIRD INSTRUCTION,

ORANGE COLOR CELL SHOWS THE STALL THAT WILL COME BCOZ THE UNIT IS NOT EMPTY, IT IS CONTAINING THE DATA OF PREVIOUS INSTRUCTION,

pls check this, am i wrong or right; bcoz if this is correct then i guess answer will change;

however am not able to generalize the approach!!

 

 

---

@Gate Fever, but these orange colors stall are not affecting the pipeline because after every third instruction next instruction is coming in next clock cycle.

now check the approach which is mentioned in answer-

1*5+(6-1)*1 = 10

now each 3rd instruction is taking 1 stall, = 2

so total clock cycle- 12

---

@Gate Fever @Shubhgupta @Bikram @jothee @shayal chhabra @HeadShot @Digvijay Pandey @srestha @akash.dinkar12

Please, justify this!

Edit:- Got it. Thanks.

Answer 2

Tc=Max(among all delay of stages)+Toverhead

Tc=10ns

Time required for one instruction=(1+SF*SP)Tc

Here, SF=0.33 bcz every third out of 100 and SP=1(Stall)

T1st=(1+.033*1)Tc=13.3ns

Therefore for 100 instruction=13.3*100ns=1330ns

Comments

1330 is average instruction time and 1370 is exact time for this question,so what will be the correct answer among these?

@Bikram sir see this.

---

@reena_kandari

i think 1370 is the correct answer .

---

@reena_kandari  $1330$ when there are large number of instructions.

Answer 3

Clock cycle for pipe line is 10 ns,  we take Max time

there is 100 instruction

33 instruction are branch instruction which take CPI=2     , 2 clock cycle to execute

67 instruction are non branching instruction which take CPI=1 ,   1 clock cycle to execute

so ,Total time taken is == 67*1 + 33*2 = 133 clock cycle

and 1 clock cycle is of 10ns

Total time taken as = 1330ns

Comments

dont u think 1st instruction will not finish in just 1 cycle as u r doing 67*1.. it should be 5+66*1 cycles

Answer 4

"Every 3rd instruction needs a 1– cycle stall before the X-stage"

therefore for 100 instructions , clock cycles will be = 100/3 = 33 clock cycles stalls

And the time taken for each cycle is = max( 9,3,7,9,2) + 1ns of overhead = 9+1 = 10ns

therefore for 33 clock cycles it take =  33 * 10 = 330 ns

 

And the time taken by CPU to execute 100 instructions is

= 1(1st instruction) * 5(CPI) * 10(each clock cycle time)  +  99(remaining 99 instruction) * 1 ( CPI ) * 10(each clock cycle time) 

= 1040 ns

 

Total time taken by CPU = 330 + 1040 = 1370 ns Ans.

 

 

Answer 5

No.of cycles required is (stages+no.of instructions-1)*stage delay

Here max delay is 9ns which will be our stage delay.

5 stages, 100 instructions requires (5+100-1)*9ns = 104*9ns = 936ns

It is also mentioned that every 3rd instruction needs a 1-cycle stall before the X-stage. For 100 instructions extra 100 ns will be added.

So, the required CPU time will be 936+100 = 1036ns.

Please correct me. If it is wrong.

Comments

Every third instruction need a stall cycle means out of 100 instruction 3rd,6th,9th......  instructions have stall cycle.