pipelining

Question

A CPU has five-stage pipeline where each stage takes $1\hspace{0.1cm}ns$, $2\hspace{0.1cm}ns$, $1.5\hspace{0.1cm} ns$, $3\hspace{0.1cm}ns$, $2.5\hspace{0.1cm} ns$. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. Assume that each stage requires one clock cycle. $30\%$ of the instructions are conditional branches. Find the average execution time of the program for $1200$ instructions is ________.

Answer 1

total instructions =1200

Time period of clk=max{1,2,1.5,3,2.5}=3ns

30% of the instructions are conditional branches.So total clk cycles required to execute (1200*$\frac{30}{100}$)=360 instructions=(3*360)=1080.Because a conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline(leads to take 3 clk cycles for completing single instruction).

For remaining 70%,i.e (1200-360)=840 non branch instructions one required 5 clk cycle and others 839 required 1 clk cycle each.so total (5+839*1)=844 clks required.

so total (844+1080)=1924 clk cycles needed

Therefore average execution time of the program for 1200 instructions is =(1924*3)ns=5772ns

Comments

see my attempt

There were 2 stall cycles for pipelining for 30 % of the instructions

For pipelined processor, Here, t=max(1,1.5,2,2.5,3)=3, t_p=3

Average execution time= (1+ stall frequency × Stall cycle) x t_p

                                     = (1+ 0.30 × 2) x 3 =4.8 x 1200 = 5760 ns

plz verify why i am wrong

---

@Amit ,Sambit has calculated Total clock cycles for 840 non-branch instructions as 1*5 + (840-1)*1 = 5 + 839*1 = 844..So , he got answer 5772 ns...

But in case of ideal pipeline , Total clock cycles = 840*1 = 840 ..So , then execution time will be (840+1080)*3 = 5760.. which is correct in case of ideal pipeline...But sambit's answer is correct practically..

---

From what I have noticed, it is better to follow Sambit's method when all information is given. Using the formula, it gives more of an approximation. If it is an MCQ or if number of instructions aren't given, we may use the formula.

---

https://gateoverflow.in/1818/gate2006-42

check this one here also ideal case is used and number of instruction are also given

---

  Amit puri  for this question if we calculate exact answer,the ans will not differ so much because number of instructions are huge.But see this question https://gateoverflow.in/204125/gate2018-50.Here they wanted the exact clk cycles.

---

@Amit That's exactly my point. It's an MCQ. You can judge by the options. But if it is a NAT then you need an exact answer.

Answer 2

........

Comments

 ankitgupta.1729 

i think by default we use ideal pipeline.(in  made easy note book)

---

@abhishek , thanks!

---

I have a confusion over here, wont be 4.8 multiplied by 1204 according to the formula (k+n-1)*maxDelay

k+n-1= 5+1200-1 = 1204