CO-Pipelining-Q8

+1 vote

In a pipelined architecture Static branch prediction is used with branch taken assumption. Assume that 30% of the instructions executed for a program are branch instructions. Each stage has 2 nsec delay. Average Execution time(in nsec) if 80 % of the instructions are taken?

asked Jun 12 in Computer Organization by gbmentor (7,990 points)
reshown Jun 13 by gbmentor

4 Answers

+1 vote
 
Best answer

https://www.cse.iitk.ac.in/users/biswap/CS422/L9-BP.pdf

When pipeline predicts that branch is taken and the prediction is wrong then 2 additional stall cycles or 2 stage delays are introduced. 
If prediction is correct then pipeline works normally with out any penalty. 

 

Answer is 2.24 nsec 

answered 6 days ago by getgatebook (22,170 points)
edited 6 days ago by getgatebook
Sir in first line why 2 stage delay
branch address will be known after execution stage so it introduces 2 stalls.
Sir here 80 % of the instructions are taken.
Mean 80% branch not taken ?
Sir please explain last line
If 80% of the instructions are taken.
but it is written every stage has 2nsec delay, it is nowhere given that normal instructions take 1nsec delay and branch instructions take 2nsec delay.
i think question is ambiguous
where 1nsec delay is taken @tsabhineetsingh in first line every 1 is 1 stage delay not 1nsec delay
oh ok. but how is there 2 stage delay for the branch instruction?
after the execution stage, branch address will be known so 2nd instruction's IF stage will start after the execution stage(Mem stage) of the 1st stage without branch it will start from 1st instruction's decode stage so:

stall cycles = (decode,execute) so 2 stall cycles
When the number of stages in a pipeline aren't given, why do we assume it to be 5?

Suppose if there are only 4 stages(Fetch, Decode, Execte and Write), then the answer will be different.
I think the answer should not different if there are 4 stages then if prediction correction - 1 stage delay if not then EX stage computes again and old cycles will be flushed out

suppose I5's prediction is wrong in that case EXE compute new branch target address and I6 and I7 flushed out

Reference: https://www.cse.iitk.ac.in/users/biswap/CS422/L9-BP.pdf see slide-2
0 votes
AET  3.92 n sec
answered 6 days ago by tsnikhilsharmagate2018 (7,480 points)
how can u explain
Here we consider 100 instruction and 5 stage
Because here ask average and %is given than 100 is best number if branch than CPI 5 if not branch than CPI 1.

100 divided into 30 and 70
And 30 again 24 and 6
Because only 80% of 30% is branch

Now total branch 24 and not branch 76

So avg memory access time
(76*1*2+24*5*2)/100
392/100=3.92 nsec.
0 votes
Here we consider 100 instruction and 5 stage
Because here ask average and %is given than 100 is best number if branch than CPI 5 if not branch than CPI 1.

100 divided into 30 and 70
And 30 again 24 and 6
Because only 80% of 30% is branch

Now total branch 24 and not branch 76

So avg memory access time
(76*1*2+24*5*2)/100
392/100=3.92 nsec.
answered 6 days ago by tsnikhilsharmagate2018 (7,480 points)
0 votes

Let's assume there are 50 instructions 

30% of that are branch instructions so, # of branch instructions = \frac{30 \times 50}{100} = 15

# of non branch instructions = 50 - 15 = 35

80% of the branch instructions is taken so # of taken branch instructions \frac{15 \times 80}{100} = 12 

# of non-taken branch instructions = 15-12 = 3

it means 12 times of prediction is right (12 times it will fetch right address from Branch Target Buffer so no stalls) and 3 times of prediction is wrong (3 times it will flush and find new branch address after EXE stage so 2 stalls)

 

so

Average Execution time = (35(1 stage delay) + (12*(1 stage delay)+3*(1+2 stage delay)))/50

 = (35 + (12+9))/50 stage delays

= (56X2)/50 nsec = 112/50 = 2.24 nsec 

answered 6 days ago by 23rishiyadavpro20 (4,120 points)
should not the stalls be included when branch is taken instead where branch taken is false am i correct
this is a static branch prediction it always predict that a conditional jump will not be taken it always fetches the next sequential instruction. therefore delay slots are inserted as when the branch or jump is evaluated and found to be taken then only instruction pointer gets pointed to non sequential acess till then instruction in delay slot executes even if branch is taken so stall concept is only when branch is taken please tell where i am wrong
okay here in question it is stated that static branch prediction assumes that branch is taken always so stalls concept is associated when branch prediction comes out to be false otherwise it would have been vice versa am i correct
Yes when prediction false then change the prediction, flush the pipeline and penalty is the same as there is no branch prediction
should not branch penalty be = stage at which branch prediction is taken -1
I think you have not understood, please see above diagram Branch Target buffer is a type of cache which contains target address when not present then flush

check this pdf too - https://www.cse.iitk.ac.in/users/biswap/CS422/L9-BP.pdf
please can u elaborate your statement penalty is the same as there is no branch prediction . I have seen above pdf . here stalls will be two in case prediction comes out to be false as we have to flush the pipeline .so in this case when branch address is not found in branch target buffer then prediction is false am i right
Answer:
...