pipelining

Question

A CPU has five-stage pipeline where each stage takes 1ns, 2ns, 1.5ns, 3ns, 2.5ns. Instruction fetch happens in the first stage of the pipeline. Branch instructions are not overlapped. i.e., the instruction after the branch is not fetched till the branch instruction is completed. 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 ________

Comments

6120 ns?

---

I think, there is something missing in the question

when we will find out target instruction, I mean after which stage we are going to find an address of target instruction??

---

Answer 7920 ns??

---

I don't have answer with me

Answer 1

Number of instructions = $1200$
Each clock cycle takes $max(1ns, 2ns, 1.5ns, 3ns, 2.5ns) = 3ns$
Execution time of $1200$ instructions = $(5 + 1199)*3$ = 3612 ns
Number of branch instructions = $\frac{30}{100}*1200 = 360$

The instruction after the branch is not fetched till the branch instruction is completed.

So each branch instruction will stall pipeline for 4 clock cycles  = $360*4*3$ = 4320 ns
The average execution time of the program for 1200 instructions  = 3612 + 4320 = 7932 ns. 

Comments

I donot think this solution correct

because u took all 1200 instruction taking 3 clock cycle

which isnot correct

only 1200-360 instruction can take 3 clock cycle

Moreover branch instruction are not overlapped

---

I think, answer is correct.

${\color{Blue}{Another\, way\, to \, solve \, this \, question :-} } \displaystyle$

Since , We have total 1200 instructions. Now divide these 1200 instructions into 2 separate

units of Branch and Non-Branch  instructions.

So,

$\bullet$ Number of Branch Instructions = $\frac{1200*30}{100}$ = 360

$\bullet$ Number of Non-Branch Instructions = 1200-360 = 840

Since , we have 5 stages and maximum delay = 3 ns

So, For Non-Branch Instructions , Execution Time = (1*5 + 839*1) * 3 =  2532 ns

Since , Branch Instructions are not overlapped . So, each branch instruction will be executed one by one (similar to non-pipelined processor).

So, for 360 Branch Instructions , Execution Time will be :- 360 * 5 * 3 = 5400 ns

So, Total Average Execution Time = 2532 + 5400 = ${\color{Blue} {7932\, ns}}$

Soumya did the same thing in different way. she has taken 1200 instructions as non-branch instructions on the pipelined processor. So, total time = 3612 ns

Now , since branch instructions are not overlapped. So, for each branch instruction we have to take 4*3 = 12 ns extra time. Since , total branch instructions = 360. So , total extra time = 360*12 = 4320 ns

So, Total Time = 3612 + 4320 = 7932 ns

---

@ankit Perfect Explanation.. :)
@srestha .. I did exactly what Ankit has said in above comment.

Answer 2

For non branch instruction, it will take max(among all pipeline stages)=3ns

For branch it is non overlapping instruction, which will take 10 ns

Now there are 30% of 1200 instruction(360 instructions) are branch instruction and 70% of instruction are non branch(840 instructions)

$=360\times 10+840\times 3=6120ns$

Comments

For non branch how it is 10 ns

Total clock cycles for non branch inst is 5*1+(840-1)*1=844 ??

---

@srestha ma'am, since branch instruction are not overlapping due to which stalls be created ,thats why avg. Instruction execution time will be increase .I think answer will be 7920 ns.