made easy

Question

A hypothetical 5 stage pipeline processor is designed in which branch is predicted at 3rd stage and each stage takes 1 cycle to compute its tasks. If f is the probability of an instruction being branch instruction then the value of f such that speedup is atleast 3 is____

Comments

@Somoshree Datta 5 yes but how

---

@Harshit Bajpai as the branch is predicted at $3rd$ stage so the stalls due to branch instruction should be $2$

---

Let total number of instructions to execute be n.

Time taken in non pipelined processor= 5*n

time taken in pipelined processor= n+2*f*n (since number of stalls for f*n number of branch instructions is 2)

So 5n/[n(1+2f)] = 3

Solving this equation, we get f= 1/3

Answer 1

suppose there is only 1 instruction.

time to execute that instruction without pipeline = 5 clock cycles  (since there are 5 stages and each stage takes 1 cc)

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

for pipeline format

3rd stage is capable of knowing Branch Address (given)

=> number of stall cycles = 2

f % instructions are branch instructions

=> stall frequency = f

CPI of pipeline =  (1 + stall Freq * stall cycles) clocks

                         = (1 + f * 2) clocks

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

speed up = time to execute in non pipeline/ time to execute in pipeline

=> 3 = 5/ (1+2f)

=> 1+2f = 5/3

=> 2f = 2/3

=> f = 1/3.

Answer 2

The approach is pretty simple. Ideally 5 stage pipeline should have a speedup of 5, but here the speedup is 3. Therefore there are some stalls in the pipeline.

speedup = non pipeline time / pipeline time. Nothing is mentioned about the frequency of the processor, so assume it to be same for both processors.

so,    3 = 5 / x   here x is the CPI for pipelined, and 5 is the CPI for non pipelined. So we get x = 5/3.

Now CPI = 1 + stall frequency* stall cycles     here stall cycle is 2 as we predict the bracnh at 3rd stage.

so,    5/3 = 1 + f*2

         f = 1/3