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?
