The whole Computer Organization and Architecture formula sheet, to print

Smallest $k$ with $2^k\ge n$. Applies to an opcode field ($n$ instructions), a register field ($n$ registers) or an address field ($n$ addressable locations).

$N_2$, $N_1$, $N_0$ are the numbers of two-, one- and zero-address instructions. The two-address format has a $(W-2A)$-bit opcode; each unused two-address code gives $2^A$ one-address codes, and each unused one-address code gives $2^A$ zero-address codes. Assumes every instruction is exactly $W$ bits, every address field is $A$ bits, and $W>2A$.

$R$ is the index register (indexed), the base register (base) or the PC (PC-relative); $D$ is the displacement field. For PC-relative, $D$ is signed.

$P{C}_{\text{after fetch}}$ is the address of the instruction AFTER the branch (branch address + branch length), unless a question says the branch's own address is used. $D$ is the signed displacement in bytes, unless the ISA scales it.

Range in displacement units relative to the base PC. If the displacement counts instructions of $s$ bytes, multiply by $s$ to get the byte range.

One bit-slice of any adder. Both outputs need all three inputs to be stable.

An adder/subtractor passes each $B_i$ through an XOR gate with a mode line $M$ and sets $C_0=M$: $M=0$ adds and $M=1$ subtracts. $V=1$ signals signed (2's complement) overflow. For unsigned numbers, $C_n=1$ after an addition means the result does not fit in $n$ bits. After a subtraction done as $A+\overline{B}+1$, $C_n=1$ means $A\ge B$ (no borrow).

$t_c$ is one FA's carry delay and $t_s$ is its sum delay, measured from when its carry-in is stable (its $A_i$, $B_i$ are already stable). If one figure $t_{FA}$ is given for both outputs, both times equal $n{t}_{FA}$. The delay grows linearly with $n$.

$G_i=1$: bit $i$ produces a carry whatever $C_i$ is. $P_i=1$: bit $i$ passes an incoming carry on to $C_{i+1}$. Some texts use $P_i=A_i+B_i$. The carry equations below still hold with that choice, but the sum can then no longer be formed as $P_i\oplus C_i$.

Each expanded carry is a two-level AND-OR expression in the $G$'s, $P$'s and $C_0$, so every carry is ready 2 gate delays after the $P$, $G$ signals, whatever its position. The cost is fan-in: $C_i$ has $i+1$ product terms and its largest AND gate has $i+1$ inputs.

This is independent of $n$ only because fan-in is assumed unlimited. If a question counts an XOR as more than one gate delay, substitute its figure in the first and last terms.

Fan-in limits force wide adders to be built from $k$-bit CLA blocks. Each block's $G^{\ast }$, $P^{\ast }$ take 2 gate delays after the bit-level $P_i$, $G_i$. A second-level look-ahead unit applies the same carry equations to the block signals, giving the carry into every block at once instead of rippling between blocks. With a fixed block size $k$, the number of look-ahead levels grows as ${\log }_{k}n$, so the delay grows as $O(\log n)$.

$W$ is the number of words (microinstructions) and $w$ is the width of one microinstruction. When a question gives the number of address bits $a$ of the CAR instead, $W=2^a$. Convert to bytes by dividing by 8, and to KB with K = $2^{10}$.

$W$ is the number of control-memory words that must be addressable. $c$ is the number of branch choices the field must select among, counting 'unconditional' (or 'no branch') as a choice when the question includes it.

Group $j$ holds $k_j$ mutually exclusive signals. The $+1$ is the code for 'none of this group active'. Drop it (use $\lceil {\log }_2{k}_j\rceil$) only if the question says exactly one signal of the group is always active, or says no-operation need not be encoded.

The fraction of memory references satisfied directly by the cache. Miss ratio $=1-h$.

Use this when main memory is accessed only after the cache lookup has missed, so a miss costs $T_c+T_m$. $T_m$ is the time to get the needed data from main memory. If the question says a whole block is transferred into the cache on a miss and gives the block-transfer time, use that time as the miss cost in place of a single-word $T_m$.

Use this when the cache and main memory are looked up in parallel. On a miss, the cache-check time is hidden inside the longer memory access and is not added again.

The miss penalty is the EXTRA time a miss costs on top of the hit time. With hierarchical access and $T_{penalty}=T_m$, this is the same as the hierarchical formula above.

Number of lines $=$ cache size $÷$ block size, whatever the associativity. The extra bits per line are whatever the question specifies. Typically that is a valid bit, a dirty bit for a write-back cache, and any replacement bits.

Model: L2 is accessed only on an L1 miss, and main memory only on an L2 miss, with each lower-level time added on top (hierarchical). $M{R}_{L2}$ here is the LOCAL miss rate of L2: misses in L2 $÷$ accesses that reach L2 (the L1 misses). It is not the global miss rate.

The fraction of ALL CPU accesses that miss in both L1 and L2 and go to main memory. If a question gives a global L2 miss rate, divide it by $M{R}_{L1}$ to get the local rate before using the AMAT formula.

Here $M$ and $m$ are numbers of words, and $w$ and $b$ are bits per word. Each row places $w/b$ chips side by side to form the full word width. $M/m$ rows are stacked to supply all the words. The memory needs ${\log }_{2}M$ address lines. Each chip takes the low ${\log }_{2}m$ of them, and the remaining ${\log }_2(M/m)$ high-order bits drive a decoder that selects one row.

Model: all $n$ banks start their access together. The first word is on the bus after $T_{access}$ (the bank access time, including placing the word on the bus). Each further word, already read in its own bank, needs only one bus transfer time $T_{transfer}$. Questions may define the timing differently, for example with a separate address-send cycle. Use the question's model when it gives one.

Same model with a single bank: each word is a full, separate access. This is the baseline against which the speedup from interleaving is measured.

Seek: moving the head to the correct track. Rotational latency: waiting for the target sector to rotate under the head. Transfer: reading or writing the data once positioned. Add a controller overhead only if the question gives one. Unless stated otherwise, a given seek time is taken as the average seek time.

Half the time of one revolution, in seconds (RPM = revolutions per minute). This is the AVERAGE. The worst case is a full revolution and the best case is zero.

One track passes under the head per revolution, so the transfer rate is the track capacity times the revolutions per second. Equivalently, reading one sector takes (revolution time) $÷$ (sectors per track).

$n$ = number of interrupts serviced in the period analysed; $t_{cs}$ = context-save time; $t_{svc}$ = the ISR's own execution time, excluding save and restore; $t_{cr}$ = context-restore time. Divide by the total elapsed time to get the fraction of CPU time spent.

$t_{\text{int}}$ = total CPU time per interrupt (save + service + restore); $T_{\text{int}}$ = average time between interrupts; $r=1/T_{\text{int}}$ = interrupts per second. If there is one interrupt per word, $r$ is the device's word rate. This holds only while $t_{\text{int}}<T_{\text{int}}$. Otherwise the CPU cannot keep up and data is lost.

$N$ = number of words in the block; $t_{\text{mem}}$ = one memory (bus) cycle time. This holds when:

• each word needs exactly one memory cycle;
• the words are available back to back (for example from the device's buffer);
• the DMAC holds the bus for the whole block;
• bus request/grant overhead is ignored.

During this time the CPU cannot use the bus. It can still carry on with internal operations that need no bus.

One bus cycle is stolen per word, assuming each word needs exactly one memory access. The two sides are equal in the standard model, where the CPU would have used the bus in every stolen cycle and arbitration overhead is ignored. This is the same product as burst mode, but it means something different. In cycle stealing, the loss is spread as $N$ separate one-cycle delays, and the total elapsed time is set by the device's word rate. In burst mode, the CPU is locked out for one continuous stretch.

$t_c$ = time of the one bus cycle stolen per word; $T_w$ = time between successive word transfers, i.e. the device's word period. This assumes the CPU would otherwise use the bus in every cycle, and $t_c\le T_w$.

Some questions give a time $x$ to prepare a word and a time $y$ to transfer it ($y=t_c$). If the device cannot prepare the next word during the transfer, $T_w=x+y$. If preparation overlaps the transfer, $T_w=x$ (assuming $x\ge y$). State which reading you use.

$t_{\text{setup}}$ = CPU time to program the DMAC for one block; $t_{\text{done}}$ = CPU time for the completion interrupt. This assumes the device transfers continuously, one block after another, and ignores the bus cycles DMA steals. Add the stolen-cycle fraction separately if the question asks for it.

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