Pipelining formulas

$t_i$ is the delay of stage $i$ and $t_{\text{latch}}$ is the inter-stage register (latch) delay, taken as 0 only if the question says so. The slowest stage sets the clock for every stage.

The first instruction needs $k$ cycles to pass through all the stages (pipeline fill). After that, one instruction completes every cycle. Valid for an ideal pipeline with no stalls.

$t_{\text{np}}$ is the time one instruction takes on the non-pipelined machine, as the question defines it: usually the sum of the stage delays. As $n\to \infty$, $S\to t_{\text{np}}/T_p$.

Only when $t_{\text{np}}=k{T}_p$, i.e. all stages have equal delay and latch delay is ignored (or the non-pipelined machine is defined as taking $k$ pipelined cycles per instruction). Then $S\to k$ as $n\to \infty$: the ideal maximum speed-up equals the number of stages.

Instructions completed per unit time with no stalls. It approaches $1/T_p$ as $n\to \infty$.

Efficiency is the fraction of stage-cycles that do useful work: $nk$ busy stage-cycles out of $k(k+n-1)$. It is below 1 for any finite $n$ because of fill and drain, and it tends to 1 as $n\to \infty$. It equals $S/k$ only in the balanced-stage case, where $t_{\text{np}}=k{T}_p$.

For a scalar in-order pipeline, ${\text{CPI}}_{\text{ideal}}=1$. Here $p_i$ is the fraction of all instructions that suffer hazard type $i$, and ${\text{penalty}}_i$ is the number of stall cycles it costs. The sum is the average number of stall cycles per instruction. This is the steady-state figure: pipeline fill cycles are ignored.

The standard performance equation. On the pipelined machine, $T_{\text{clk}}=T_p$.

$t_{\text{np}}$ is the non-pipelined time per instruction. The second line holds only for balanced stages with no latch overhead. Both lines ignore fill cycles, so they describe a long program.

$d$ is the distance in program order: $d=1$ for the very next instruction. This assumes the register file is written in the first half of WB and read in the second half of ID, so a read in the same cycle as the write sees the new value. The consumer's ID must then fall no earlier than the producer's WB, so $d\ge 3$ needs no stall. If the register file is not split-cycle (the read must come in a cycle after the write), the result becomes $\max (0,4-d)$.

$s_{\text{resolve}}$ is the number of the stage at whose end both the outcome and the target are known. The correct instruction is fetched in the next cycle. No delay slot or prediction is assumed. For example, resolving at the end of EX (stage 3) squashes the 2 instructions in IF and ID, a penalty of 2 cycles; resolving at the end of ID gives 1.

$p_{\text{branch}}$ is the fraction of all instructions that are branches. $p_{\text{penalised}}$ is the fraction of those branches that pay the penalty: under predict-not-taken, the taken fraction; under a predictor, the mispredicted fraction. If the pipeline stalls on every branch regardless of outcome, $p_{\text{penalised}}=1$.