Computer organization and architecture 10th edition #Problems 14.11

Question

The book says that a total time required for a pipeline with $k$ stages to execute $n$ instructions is as follows.

$T  _{k,n} =[pqnk+(1-pq)(k+n-1)] \tau$

$p$ is the probability of encountering a branch instruction.

$q$ is the probability that execution of a branch instruction I causes a jump to a nonconsecutive address.

(Each jump requires the pipeline to be cleared)

 

And this is my solution.

There are $p*q*n$ instructions which are a branch instruction that is taken.

Because they make k stalls, the number of stages of them is $p*q*n*k$

And the number of the rest of the instructions are $(1-p*q)*n$

They can be executed with pipelined, the number of stages of them is $(k+(1-p*q)*n-1)$

Therefore, the total time required is

$T  _{k,n} =[pqnk+(k+(1-pq)n-1)] \tau$

 

I can't understand why $1-pq$ is multiplied to $(k+n-1)$

Shouldn't it be $k+(1-pq)n-1$ because there are $(1-pq)n$ pipelined instructions?

Comments

Even if an instruction decides whether to take the branch or not only after it finishes all of its ‘k’ phases even then it will at max cause (k-1) stalls. And in that formula(book one), they have considered it to be (k+1).How? In ‘pqn’ part they have taken k additional cycles, and in (1-pq) part, again they have taken 1 cycle.

As far as i can comprehend things, it looks wrong to me.

$pqn(k-2) + (1-pq)(n+k-1)$ makes more sense.

Answer 1

consider it like to two cases 1 case for a branch taken p*q

one case for non branch instruction and branch not taken instruction which probability are 1 - pq

in second case forget about branch and think like you normally do for a pipeline question