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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.