The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+33 votes

An instruction pipeline has five stages where each stage take 2 nanoseconds and all instruction use all five stages. Branch instructions are not overlapped. i.e., the instruction after the branch is not fetched till the branch instruction is completed. Under ideal conditions,

- Calculate the average instruction execution time assuming that 20% of all instructions executed are branch instruction. Ignore the fact that some branch instructions may be conditional.
- If a branch instruction is a conditional branch instruction, the branch need not be taken. If the branch is not taken, the following instructions can be overlapped. When 80% of all branch instructions are conditional branch instructions, and 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.

+37 votes

Best answer

Each stage is $2$ns. So, after $5$ time units each of $2$ns, the first instruction finishes (i.e., after $10$ns), in every $2$ns after that a new instruction gets finished. This is assuming no branch instructions. Now, once the pipeline is full, we can assume that the initial fill time doesn't matter our calculations and average execution time for each instruction is $2$ns assuming no branch instructions.

- Now, we are given that $20\%$ of instructions are branch (like JMP) and when a branch instruction is executed, no further instruction enters the pipeline. So, we can assume every $5$th instruction is a branch instruction. So, with this assumption, total time to finish $5$ instruction will be $5 * 2 + 8 = 18$ ns (as when a branch instruction enters the pipeline and before it finishes, $4$ pipeline stages will be empty totaling $4 * 2 = 8$ ns, as it is mentioned in question that the next instruction fetch starts only when branch instruction completes). And this is the same for every set of 5 instructions, and hence the average instruction execution time $= 18/5 = 3.6$ ns

- This is just a complex statement. But what we need is to identify the $\%$ of branch instructions which cause a branch to be taken as others will have no effect on the pipeline flow.

$20\%$ of instructions are branch instructions. $80\%$ of branch instructions are conditional.

That means .$2*.8 = 16\%$ of instructions are conditional branch instructions and it is given that $50\%$ of those result in a branch being taken.

So, $8\%$ of instructions are conditional branches being taken and we also have $20\%$ of $20\% = 4\%$ of unconditional branch instructions which are always taken.

So, percentage of instructions where a branch is taken is $8+4 = 12\%$ instead of $20\%$ in (A) part.

So, in $100$ instructions there will be $12$ branch instructions. We can do a different calculation here as compared to (A) as $12$ is not a divisor of $100$. Each branch instruction causes a pipeline delay of $4*2 = 8$ ns. So, $12$ instructions will cause a delay of $12 * 8 = 96$ ns. For $100$ instructions, we need $100 * 2 = 200 $ ns without any delay and with delay we require $200 + 96 = 296$ ns for $100$ instructions.

So, average instruction execution time $= 296/100 = 2.96$ ns

(We can also use this method for part (A) which will give $100 * 2 + 20*8 = 360$ ns for $100$ instructions)

0

Thank You Arjun Sir for an elaborate and understandable explanation.

Could you help me with a link for such kind of pipeline problems with delays .?

Could you help me with a link for such kind of pipeline problems with delays .?

+16

part b)

if branch not taken following instructions can be overlapped , implies stall=0

if branch taken, it would be simply after k-1 stall = 4 stalls.

20% are branch

80% of branch are conditional ,implies 80% of 20% are conditional

which means 20% are unconditional(always takes), implies 20% of 20% are unconditional which are taken

50% of branch conditional are taken, implies 50% of 80% of 20% are taken

considering for all cases where there is stall :

therefore, Tavg=(1+stall cyle*stall freq) clocks

= (1+ ( 0.50*0.80*0.20*4 ) + (0.20*0.20*4) ) clocks

= 1.48 clocks= 1.48 * max{stage dealy}= 1.48*2ns= 2.96 ns

if branch not taken following instructions can be overlapped , implies stall=0

if branch taken, it would be simply after k-1 stall = 4 stalls.

20% are branch

80% of branch are conditional ,implies 80% of 20% are conditional

which means 20% are unconditional(always takes), implies 20% of 20% are unconditional which are taken

50% of branch conditional are taken, implies 50% of 80% of 20% are taken

considering for all cases where there is stall :

therefore, Tavg=(1+stall cyle*stall freq) clocks

= (1+ ( 0.50*0.80*0.20*4 ) + (0.20*0.20*4) ) clocks

= 1.48 clocks= 1.48 * max{stage dealy}= 1.48*2ns= 2.96 ns

0

It isn't the branch instruction but the instruction following it which incurs the overhead of 10 units, am I correct?

0

**if branch taken, it would be simply after k-1 stall**

can someone please elaborate this statement ? thanks

0

"as when a branch instruction enters the pipeline and before it finishes, 4 pipeline stages will be empty totaling 4 * 2 = 8 ns, as it is mentioned in question that the next instruction fetch starts only when branch instruction completes)."

This 8 ns delay will be in 6 th instruction? As 5 th instruction is branch instruction the delay will happen in 6th instruction. I am confused which instruction will have delay of 8 ns and will face stalls if 5th instruction is branch then next instruction should be fetched only once 5 th instruction is fiinhsed with its execution.

To execute 5 instruction it will take 18 ns but to execute 6th it will include 8 ns delay plus 2 ns to execute total 10 ns. I don't know if my understanding is correct please help.

This 8 ns delay will be in 6 th instruction? As 5 th instruction is branch instruction the delay will happen in 6th instruction. I am confused which instruction will have delay of 8 ns and will face stalls if 5th instruction is branch then next instruction should be fetched only once 5 th instruction is fiinhsed with its execution.

To execute 5 instruction it will take 18 ns but to execute 6th it will include 8 ns delay plus 2 ns to execute total 10 ns. I don't know if my understanding is correct please help.

+44 votes

if an instruction branches then it takes $2ns \times 5 = 10ns$, coz if branch is taken then the instruction after that branch instruction is not fetched until entire current branch instruction is completed, this means it will go through all stages.

if an instruction is non-branch or branching does not happen then, it takes $2ns$ to get completed.

**a)** $\text{average time taken} = 0.8 \times 2ns + 0.2 \times 10ns = 3.6ns$

**b) **

$\text{Average time taken,}$

$ = 0.8 \times 2ns + 0.2 \Big( 0.2 \times 10ns + 0.8 \big( 0.5\times 10ns + 0.5 \times 2ns\big)\Big)$

$ =2.96ns$

+2 votes

**A))**

**Let total number of instruction is n**

**Tavg=n x 20% x 5 x 2ns + n x 80% x 1 x 2ns/n**

**Tavg=3.6ns**

**B))**

**Let us suppose we have 100 instruction**

**20% are branch instruction and 80% Not branch instruction**

**out of 20% ,80% of 20% are cnditional branch and 20% of 20% are unconditional**

**Now 50% of 80% of 20% are branch instruction where branch is taken and 50% of 80% of 20% branch not taken.**

**Clock average=148/100=1.48**

**Tavg=1.48 x 2ns=2.96ns**

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,870 questions

47,531 answers

146,027 comments

62,297 users