Formula sheet

Every formula from every topic. Type to filter.

🧩 Instruction Formats & Addressing Modes

Memory refs per mode
Immediate 0 · Register 0 · Direct 1 · Reg-indirect 1 · Indirect 2 (to get the operand)
Instruction length
L = opcode + (#operands × field width) [+ mode bits]
Expanding opcode (2-addr → 1-addr → 0-addr)
1-addr max = (2^opbits − x)·2^a · 0-addr max = ((2^opbits − x)·2^a − y)·2^a (x = #2-addr, y = #1-addr, a = address-field bits, opbits = L − 2a)
Registers addressable
k register-field bits → 2^k registers
Address bits
Memory of 2^n words → n address bits; addressable range = 2^n × word size

🚰 Instruction Pipelining & Hazards

Time without pipeline
T = n · k · t (k stages of equal delay t)
Time with pipeline (no stalls)
T = (k + n − 1) · t_p where t_p = max(stage delay) + latch
Speedup
S = n·k / (k + n − 1) → k as n → ∞
Efficiency / Throughput
η = S / k Throughput = n / ((k+n−1)·t_p) → 1 / t_p
With stalls
CPI = 1 + (stalls per instruction) S ≈ k / (1 + stalls per instr)
Branch penalty
CPI = 1 + (branch freq) × (fraction taken or mispredicted) × (penalty cycles)
Non-pipelined cycle (for comparison)
t_unpipe = sum of all stage delays (no latch)

⚡ Cache Memory

Number of lines
#lines = cache size / block size
Number of sets
#sets = #lines / k (k = 1 → direct, k = #lines → fully assoc.)
Tag bits
tag = address bits − log₂(#sets) − log₂(block size)
Tag directory size
#lines × (tag + valid [+ dirty] [+ replacement bits])
AMAT
AMAT = hit time + miss rate × miss penalty
Two-level (hierarchical access)
AMAT = t₁ + m₁·(t₂ + m₂·t_mem)
Two-level (simultaneous access)
AMAT = h₁t₁ + (1−h₁)h₂t₂ + (1−h₁)(1−h₂)t_mem
CPI with memory stalls
CPI = CPI_base + (mem refs / instr) × miss rate × miss penalty
Miss penalty for block fetch
= first-word latency + (words/block − 1) × per-word time (or burst time)
Hit ratio
H = hits / total accesses miss rate = 1 − H

🔢 Number Representation & Computer Arithmetic

2's complement range (n bits)
−2^(n−1) … +2^(n−1) − 1
Sign-magnitude / 1's complement range
−(2^(n−1) − 1) … +(2^(n−1) − 1)
Unsigned range
0 … 2^n − 1
IEEE-754 single value
(−1)^s × (1 + f/2^23) × 2^(e − 127)
Single: exponent range / largest
e = 1…254 → 2^−126 … 2^127 · max ≈ (2 − 2^−23)·2^127 ≈ 3.4×10^38
Double value
(−1)^s × (1 + f/2^52) × 2^(e − 1023)
Booth steps
n steps for n-bit multiplier; product needs 2n bits
Overflow detect
V = C_in(MSB) ⊕ C_out(MSB)
Decimal digits
n bits ≈ n × 0.301 decimal digits

🧠 ALU, Datapath & Control Unit

Horizontal width
= #control signals (+ next-address / condition bits)
Vertical field width
bits per field = ⌈log₂(#mutually exclusive signals + 1)⌉ (+1 for 'no signal')
Control store size
= #microinstructions × microinstruction width
Single-cycle clock
T = max over instructions of total path delay
Multi-cycle clock
T = max stage delay (+ register overhead)
Execution time
Time = Σ (cycles of each instr) × T

📈 Performance: CPI, MIPS, Amdahl

CPU time
T = IC × CPI / f_clock = IC × CPI × t_clk
Average CPI
CPI = Σ (fraction_i × CPI_i)
MIPS
MIPS = f_clock / (CPI × 10⁶) = IC / (T × 10⁶)
Amdahl
Speedup = 1 / ((1 − f) + f / s)
Max possible speedup
S_max = 1 / (1 − f)
Speedup of A over B
S = T_B / T_A

🏛️ Memory Hierarchy & Main Memory

Memory size
2^(address bits) × (bits per word)
Chips needed
(total words / chip words) × (total width / chip width)
Decoder
extra address bits = log₂(#chips in the depth direction)
Pages / frames
#pages = virtual space / page size · #frames = physical memory / page size
Page table size
= #pages × PTE size
VA split
VA = page number (VPN) + offset (log₂ page size)
EAT with TLB (1-level PT)
EAT = h(t + m) + (1 − h)(t + 2m) [t = TLB time, m = memory time]
EAT with page faults
EAT = (1 − p)·EAT_mem + p·(fault service time)
Interleaved bandwidth
≈ M words per access time T for M banks (ideal, sequential access)

💽 Secondary Storage (Disk)

Capacity
= surfaces × tracks/surface × sectors/track × bytes/sector
Avg rotational latency
= ½ × (60 / RPM) s = 30000 / RPM ms
Transfer time for 1 sector
= (60 / RPM) / (sectors per track) s
Data rate
= (bytes per track) × (RPM / 60) bytes/s
Access time
= seek + rotational latency + transfer (+ controller)
Bits to address a sector
= log₂(surfaces) + log₂(tracks) + log₂(sectors)

🔌 I/O Interface, Interrupts & DMA

Polling overhead
CPU fraction = (polls/s × cycles per poll) / f_clock; polls/s ≥ data rate / bytes per transfer
Interrupt overhead
CPU fraction = (interrupts/s × cycles per ISR) / f_clock
DMA overhead
CPU time = (setup + completion ISR cycles) per block ÷ block time; plus bus cycles stolen
Cycle-stealing slowdown
fraction of bus cycles lost = (DMA transfer rate in words/s) / (bus cycles/s)
Async serial efficiency
= data bits / (start + data + parity + stop)
Block transfer time (DMA)
= block size / device data rate (device limited)