The total time require for a pipeline to execute

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)

However, I can not understand why this makes sense. The formula indicates that

"If there is a branch instruction and is taken, the number of stages is nk. And in the remaining cases, it is (1-pq)(k+n-1)

I can understand the second case, but why is the number of stages nk in the first case? I think that the result of nk stages never occurs unless every instruction is a branch instruction so that the pipeline is cleared every time each instruction is executed. Instructions after a branch instruction which is taken can be executed in the pipeline, so it must be less than nk. What do I miss?

Answer 1

The exact time could be obtained as $\tau\sum p_i\,c_i$ where $p_i$ is the probability of taking $c_i$ cycles. Let's admit that by virtue of linearity, it ends up to be equivalent to $\tau\sum p_i\,C_i$ with two terms, $p_0=pq$, thus $p_1=(1-pq)$. The two terms $C_0$ and $C_1$ must make the formula correct for the extreme cases $pq=1$ and $pq=0$.

The $C_0=nk$ term (the question's first case) is the number of cycles it would take to execute the $n$ instructions with each requiring $k$ cycles (because each jumps to a non-consecutive location and requires refilling the $k$ stages).

The $C_1=k+n−1$ term is the number of cycles it would take for linear code (either because there is no branch instruction, or none jumps to a non-consecutive address). The $n$ term is such that each additional instruction adds one cycle, and the other terms are such that for $n=1$, the outcome is the $k$ cycles necessary to fill the $k$ stages of pipeline.