GATE Computer Organization formula sheet

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

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

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

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

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