7.1.1 — Master Rule Sheet (all rule cards merged)

Every Rule Card from the 54 lessons, grouped by phase, in course order. Use it for revision in the last weeks: read one phase per sitting, and for any line you cannot explain in your own words, open its lesson (the lesson ID links to it).

📝

How to revise with this sheet

• Cover the rules of a lesson with your hand; say them from its title alone.
• Check, and mark the lesson's ID on paper if you missed anything.
• Next day, re-test only the marked IDs (spaced recall).

🧭 Phase 0 · Foundations

0.1.1 What a computer is: CPU, memory, I/O, buses; the stored-program idea; fetch–decode–execute

• Five units: input, output, memory, ALU, control. CPU = ALU + control + registers.
• Stored program: instructions and data in one memory; PC = address of the next instruction.
• Von Neumann: one memory path (bottleneck). Harvard: separate instruction and data memories.
• Address bus one-way (CPU → memory); data bus two-way; control bus carries commands and status.
• Instruction cycle: fetch → PC advance → decode → operand fetch → execute → store.

0.1.2 Performance: clock, cycle time, CPI, execution time, MIPS, speedup, Amdahl's law

• T = 1/f. CPU time = IC × CPI × T = IC × CPI / f.
• CPI of a mix = Σ fraction × cycles.
• MIPS = f / (CPI × 10⁶); compare machines by CPU time, not MIPS.
• Speedup = old time / new time. Amdahl: 1 / ((1−F) + F/S); upper limit 1/(1−F).

0.2.1 Binary and hex, powers of two, size units, log₂: n bits name 2ⁿ things

• One hex digit = 4 bits. 1 K = 2¹⁰, 1 M = 2²⁰, 1 G = 2³⁰.
• 2ⁿ locations ↔ n address bits. N items need ⌈log₂ N⌉ bits.
• 2ᵃ / 2ᵇ = 2ᵃ⁻ᵇ: convert sizes to exponents before dividing.
• B = byte (8 bits), b = bit.

0.2.2 Signed integers: 2's complement, ranges, sign extension, overflow; bit fields and shifts

• Unsigned: 0 … 2ⁿ−1. Two's complement: −2ⁿ⁻¹ … 2ⁿ⁻¹−1; MSB weight −2ⁿ⁻¹.
• Negate: invert and add 1. Sign-extend by copying the MSB.
• Signed overflow: same-sign operands, other-sign result. Carry out = unsigned overflow.
• Left shift ×2ᵏ; logical right shift for unsigned; arithmetic right shift keeps the sign.
• Field bits i..j: (word >> j) AND (2^(i−j+1) − 1).

0.2.3 Digital building blocks: gates, MUX, decoder, adder, flip-flops, registers, clock, tri-state bus

• 2ᵏ-to-1 MUX: k select lines. k-to-2ᵏ decoder: one active output.
• Full adder: sum = a⊕b⊕c, carry = ab + c(a⊕b). Ripple adder: carries pass stage to stage.
• Register = n flip-flops + load; changes only at the clock edge. Counter adds 1 per edge.
• Tri-state: 0, 1 or Z; exactly one driver per bus per cycle.
• Clock cycle ≥ slowest register-to-register path.

0.2.4 Memory as an array: address, word, byte vs word addressing, endianness, alignment

• Capacity = 2^(address bits) × addressable unit.
• Byte-addressable: word number = ⌊address / word size⌋.
• Big-endian: MSB at lowest address. Little-endian: LSB at lowest address.
• k-byte object aligned ⇔ address multiple of k; misaligned word = 2 accesses.
• Data bus width = bytes per transfer.

🧾 Phase 1 · Instructions & Addressing Modes

1.1.1 Instruction = opcode + operands; instruction formats; the instruction cycle

• Instruction = opcode + operand fields (+ mode bits). Opcode bits = ⌈log₂ #ops⌉; register field = ⌈log₂ #regs⌉.
• Immediate = leftover bits: unsigned max 2ⁿ−1; signed −2ⁿ⁻¹ … 2ⁿ⁻¹−1.
• Instruction k (from 0) of fixed length L at start S: S + k·L.
• Cycle: IF → ID → OA → OF → EX → WB/SR → interrupt check. IF always references memory.
• Notation: destination first; M[X] = contents of location X; #c = constant.

1.1.2 3-, 2-, 1- and 0-address machines: register, accumulator and stack code

• 3-address: dest ← src1 OP src2. 2-address: dest ← dest OP src. 1-address: AC ← AC OP M. 0-address: stack.
• Stack op: pop b, pop a, push a OP b. Translate via postfix.
• Load/store: only LOAD/STORE touch memory; arithmetic on registers.
• Fewer addresses → shorter instructions, more of them.

1.1.3 Instruction types: data movement, ALU, shifts, compare and flags, branches and jumps

• Types: data movement, arithmetic, logical, shift/rotate, compare/test, control transfer, I/O, NOP/HALT.
• Flags: Z (zero), N (MSB), C (carry out), V (signed overflow). CMP = subtract and keep only flags.
• BEQ: Z = 1; BNE: Z = 0; signed a < b after CMP a, b: N ⊕ V = 1.
• Rotate wraps bits; shift loses them.
• IC counts executed instructions: setup + iterations × body + exit.

1.1.4 Instruction encoding: opcode space, register fields, expanding opcodes

• Fixed k-bit opcode: ≤ 2ᵏ instructions.
• Expanding: total encodings 2ʷ; a class with f operand bits uses count × 2ᶠ.
• Next class max = (2ʷ − Σ count·2ᶠ) ÷ 2^(f_next). Carve from most operand bits to fewest.
• Classic 16-bit / 4-bit fields: 15 + 15 + 15 + 16 = 61 instructions.

1.2.1 Immediate, register, direct, indirect and register-indirect modes

• EA = where the operand finally is.
• Immediate #c: operand c (0 accesses). Register R: operand in R (0).
• Direct A: EA = A (1). Indirect @A: EA = M[A] (2). Register indirect (R): EA = R (1).
• Total references = fetch words + operand accesses + 1 if the result goes to memory.

1.2.2 Displacement modes: indexed, base, PC-relative; auto-increment and auto-decrement

• Displacement d(R): EA = d + R. Indexed: big address in instruction, index in register. Base: address in register, small displacement.
• PC-relative: EA = (address of next instruction) + offset; offset = T − (X + L).
• (R)+: use M[R], then R += d. −(R): R −= d, then use M[R]. d = operand size.
• Position-independent code: PC-relative branches.

1.2.3 Choosing modes: arrays, pointers, constants, relocatable code; memory references per mode

• Constant → immediate; fixed global → direct; pointer in register → register indirect; pointer in memory → indirect.
• A[i] → indexed; record field / locals → base + displacement; *p++ → auto-increment; push → auto-decrement.
• Relocatable code → PC-relative (and base register).
• Data accesses: immediate/register 0; indirect 2; all others 1.
• Element address = base + i × size.

1.3.1 Tracing programs: registers, memory and flags; counting memory references and cycles

• Trace values in a table: one row per iteration.
• IC = setup + iterations × body + end (the final not-taken branch counts).
• Memory references = Σ instruction words fetched + data accesses.
• Cycles = Σ (executions × cycles of that instruction).
• Instruction addresses: running sum of sizes.

1.3.2 Stack, subroutine call and return; RISC vs CISC

• Downward stack, SP at top: PUSH = SP −= w, M[SP] ← X; POP = X ← M[SP], SP += w.
• CALL: push return address (next instruction), PC ← target. RET: PC ← pop.
• Recursion depth = active calls × frame size; count calls carefully (f(10)…f(0) = 11).
• RISC: fixed length, load/store, few modes, many registers, CPI ≈ 1. CISC: the opposite.

⚙️ Phase 2 · ALU & Datapath

2.1.1 Building an ALU: 1-bit slice, n-bit ALU, subtraction, flags Z N C V

• ALU slice: AND, OR, sum computed together; MUX (operation select) picks one; slices chained by carries.
• a − b = a + NOT b + 1 (B-invert XORs + carry-in₀ = 1).
• Control bits = ⌈log₂ #operations⌉.
• Z = NOR(result); N = MSB; C = cₙ; V = cₙ₋₁ ⊕ cₙ.

2.1.2 Adder speed: ripple-carry delay, carry-lookahead (generate, propagate), gate-delay counting

• Ripple: last carry n·t_c; last sum (n−1)·t_c + t_s; ≈ 2 gate delays per bit for carries; Θ(n).
• gᵢ = aᵢbᵢ, pᵢ = aᵢ ⊕ bᵢ; cᵢ₊₁ = gᵢ + pᵢcᵢ; sᵢ = pᵢ ⊕ cᵢ.
• CLA (unlimited fan-in): 1 (g,p) + 2 (carries) + 1 (sum) = 4 gate delays.
• Bounded fan-in CLA: Θ(log n). Rippled CLA blocks: 2 per block after g/p.

2.1.3 Multiplication: shift-and-add, Booth's algorithm; restoring division

• Shift-and-add (unsigned): one addition per 1 bit; product 2n bits.
• Booth: (Q₀,Q₋₁) 10 → A − M; 01 → A + M; 00/11 → nothing; then arithmetic shift right A,Q,Q₋₁; n steps.
• Recode with a 0 appended: pairs (bit, right neighbour): 10 = −1, 01 = +1.
• Booth operations = transitions; worst case alternating bits (n ops); best case long runs.
• Restoring division: shift, subtract, restore if negative; n steps.

2.2.1 CPU registers and register transfer notation: PC, IR, MAR, MDR, GPRs, flags, SP

• PC: next instruction address. IR: current instruction. MAR: address bus. MDR: data bus.
• Memory read: MAR ← addr; MDR ← M[MAR] (Read, wait MFC). Write: MAR, MDR set; M[MAR] ← MDR.
• RTL: ← transfer; commas = same step; IR(address) = address field.
• Fetch: MAR ← PC; MDR ← M[MAR], PC ← PC + 4; IR ← MDR.

2.2.2 Single-bus datapath: control signals and micro-operation steps for fetch and execute

• Single bus: one out per step; MAR in-only; ALU A ← MUX(Y, 4), B ← bus; result → Z.
• Fetch: PCout, MARin, Read, Select4, Add, Zin | Zout, PCin, Yin, WMFC | MDRout, IRin (3 steps).
• Register ALU op execute: 3 steps (Y ← src1; Z ← Y op src2; dest ← Z).
• Memory operand: + MAR load / Read step; overlap work with WMFC.
• Branch: offset + Y (PC) → Z → PC: 2 steps.

2.2.3 Two- and three-bus datapaths; counting cycles per instruction

• Three-bus: R1 ← R2 + R3 in 1 step; two-bus: 2 steps; single bus: 3 steps.
• Counting: one value per bus per step; one ALU op per step; written values readable next step.
• Memory reads need an address step and a data step (or WMFC).
• The question's datapath description always wins.

🎛️ Phase 3 · Control Unit

3.1.1 Control signals, control steps and the step counter: what a control unit must produce

• Control unit inputs: IR opcode, step counter (T1…Tn), flags, MFC/interrupts. Output: all control signals per step.
• Step counter: ⌈log₂ max steps⌉ bits, decoded one-hot; End resets; WMFC freezes.
• Instruction time = (steps + waits) × clock period.
• Control signals ≈ 2 per register (in/out) + memory + ALU + MUX + sequencing.

3.1.2 Hardwired control: decoder, step counter and signal equations

• Hardwired = instruction decoder + step decoder + AND–OR network (+ flags).
• Signal = Σ (Tⱼ · INSᵢ [· flag]); fetch steps carry no instruction factor.
• Counter enable = NOT(WMFC) + MFC.
• Fast, inflexible, RISC-style.

3.2.1 Microprogrammed control: control memory, control words, microroutines, µPC

• Control word = all signals of one step; microinstruction = stored control word (+ sequencing).
• Microroutine per instruction; fetch routine shared; µPC + starting-address generator; End → fetch.
• CM words = fetch + Σ execute steps; CM bits = words × width.
• Microprogrammed: flexible, slower, CISC-friendly.

3.2.2 Microinstruction formats: horizontal vs vertical, field encoding, control-memory size

• Horizontal: width = number of signals; fast; parallel; big CM.
• Vertical: field of k mutually exclusive signals = ⌈log₂(k+1)⌉ bits (⌈log₂ k⌉ if one is always active).
• Width = Σ fields (+ independent signals) (+ condition select + next address).
• CM bits = words × width.

3.2.3 Microprogram sequencing: next-address field, conditional branches; hardwired vs microprogrammed

• Next microinstruction: µPC + 1; branch to next-address field if condition true; opcode mapping; End → fetch.
• Width = control bits + ⌈log₂ #conditions⌉ + ⌈log₂ CM words⌉; CM words = 2^(next-address bits).
• Nanoprogramming: N·⌈log₂ D⌉ + D·W vs N·W.
• Hardwired: fast, rigid, RISC. Microprogrammed: flexible, slower, CISC.

🗃️ Phase 4 · Memory Hierarchy & Cache

4.1.1 Why a hierarchy: speed, cost, size; locality; hit, miss, hit ratio

• Down the hierarchy: slower, larger, cheaper per bit. Avg cost = Σ cᵢSᵢ / Σ Sᵢ.
• Temporal locality: reuse soon; spatial locality: neighbours soon.
• Hit ratio h = hits / accesses; miss ratio = 1 − h.
• Misses move whole blocks; a cache slot is a line.

4.1.2 Average memory access time: hierarchical vs simultaneous access; multi-level formulas

• Given hit and miss times directly: T = h·t_hit + (1−h)·t_miss.
• Hierarchical: T = t_c + (1−h)t_m. Simultaneous: T = h·t_c + (1−h)t_m.
• 3 levels hierarchical: t₁ + (1−h₁)[t₂ + (1−h₂)t₃]; simultaneous: h₁t₁ + (1−h₁)h₂t₂ + (1−h₁)(1−h₂)t₃.
• Default to hierarchical unless the question says parallel/simultaneous.
• Speedup = t_m / T.

4.1.3 Memory chips: SRAM vs DRAM, ROM types, DRAM refresh; chip organisation 2ᵏ × n

• SRAM: flip-flop, fast, no refresh, caches. DRAM: capacitor, dense, cheap, refresh, main memory.
• ROM, PROM (once), EPROM (UV), EEPROM (byte, electrical), Flash (block, electrical).
• 2ᵏ × n chip: k address lines, n data lines, CS.
• DRAM refresh overhead = rows × row time / refresh period; multiplexed address pins = half the bits (square array).

4.1.4 Memory interfacing: building larger memories from chips, address decoding, chip counts

• Chips = (W/w)(B/b). Address lines = log₂ W; common = log₂ w; decoder log₂(W/w) → W/w.
• Width expansion: shared address and CS; depth expansion: decoder on high bits drives CS.
• Address range: fixed high bits, all combinations of the low bits.
• Partial decoding → aliasing.

4.1.5 Secondary storage and bandwidth: disk access time, transfer rate, interleaved memory

• Capacity = surfaces × tracks × sectors × bytes. Cylinder = same track on all surfaces.
• Access = seek + ½ rotation + transfer; rotation = 60/rpm s; transfer rate = bytes per track × rps.
• Low-order interleaving: block of k words in t_a + k·t_b vs k(t_a + t_b).

4.2.1 Cache lines and blocks; direct mapping: tag, line, offset

• Offset = log₂ B; lines L = C/B; line bits = log₂ L; tag = address bits − line − offset.
• Block j → line j mod L, tag ⌊j/L⌋.
• Line stores valid + tag + data. One comparator; no replacement policy.
• Blocks per line = 2^(tag bits).

4.2.2 Fully associative and set-associative mapping; comparators and multiplexers

• k-way: sets S = L/k; set bits log₂ S; tag = address − set − offset; block j → set j mod S.
• Fully associative: tag = address − offset; L comparators.
• Comparators = k; data MUXes = output width × (k-to-1).
• Doubling ways: index −1 bit, tag +1 bit. Hit latency adds MUX delay for k > 1.

4.2.3 Tag directory size and cache hardware: valid, dirty and replacement bits

• Directory = L × (tag + V [+ D] [+ replacement bits]).
• Total storage = L·B·8 + directory.
• Index never stored. Comparators: 1, k or L, each tag-bits wide.

4.2.4 Tracing references: hits and misses; compulsory, capacity and conflict misses

• Trace: byte address → block → set (j mod S) → hit/miss → update (LRU unless stated).
• Direct: S = L; fully associative: S = 1.
• Compulsory (first use), capacity (fully associative of same size also misses), conflict (the rest).
• Associativity cuts conflict misses; size cuts capacity misses; neither guarantees fewer misses on every sequence.

4.2.5 Replacement policies: LRU, FIFO, random, optimal; tracing sets

• LRU: evict least recently used (hits reorder). FIFO: evict earliest loaded (hits don't). Random. OPT: evict farthest next use (benchmark). LFU: least used.
• Belady's anomaly: FIFO only.
• LRU state: log₂ k bits per line (counter scheme); ≥ ⌈log₂ k!⌉ per set exact.

4.3.1 Write policies: write-through vs write-back, dirty bit, write-allocate

• Write hit: write-through (cache + memory) vs write-back (cache only, dirty bit, write block on eviction).
• Write miss: write-allocate vs no-write-allocate. Pairs: WB + WA; WT + NWA.
• Write-back: T = t_c + (1−h)(1 + d)·t_block.
• Write-through (writes take t_m): T = f_r[t_c + (1−h)t_m] + f_w·t_m.

4.3.2 Miss penalty and block transfer; memory-stall cycles; CPI with cache misses

• Miss penalty = latency + (B / bus width) × transfer time (or interleaving formulas).
• Stall cycles = accesses × miss rate × penalty.
• CPI = CPI_base + m_I·P + f_mem·m_D·P.
• Perfect-cache speedup = CPI_eff / CPI_base.

4.3.3 Multilevel caches: L1 and L2, local vs global miss rate, inclusion

• Local miss rate = misses ÷ accesses reaching that level; global = misses ÷ all references = m₁·m₂.
• AMAT = t₁ + m₁(t₂ + m₂·t_mem) (m₂ local).
• Stalls/instr = accesses/instr × m₁ × (t₂ + m₂·t_mem).
• Inclusive vs exclusive.

4.3.4 Programs and caches: array layout, loop order, counting misses

• Row-major: addr = base + (i·M + j)·s. Column-major: base + (j·N + i)·s.
• Row-wise misses = bytes ÷ B; miss ratio = s ÷ B.
• Column-wise: stride M·s; reuse needs all N blocks to survive (size and mapping).
• Fix: loop interchange; blocking (tiling).

🏭 Phase 5 · Pipelining

5.1.1 The pipeline idea: stages, latches, cycle time, k + n − 1 cycles

• Pipeline: k stages, pipeline registers between them; all move each cycle.
• τ = max stage delay + latch delay.
• Pipelined time = (k + n − 1)τ; non-pipelined = n × Σ stage delays.
• Space–time diagram: instructions × cycles.

5.1.2 Speedup, efficiency, throughput; unequal stages, latch delay, splitting stages

• Speedup = T_nonpipe / T_pipe; balanced: nk/(k+n−1) → k.
• Unequal: large-n speedup = Σtᵢ / (max tᵢ + d).
• Efficiency = speedup/k = n/(k+n−1) (balanced). Throughput → 1/τ.
• Splitting the bottleneck: new τ = new max + d, k + 1 stages.

5.1.3 The 5-stage RISC pipeline IF ID EX MEM WB; space–time diagrams

• IF: fetch, PC + 4. ID: decode, read registers. EX: ALU / address / branch. MEM: load/store. WB: write register.
• Separate I- and D-caches; register file write first half, read second half.
• Instruction i (no stalls) is in stage s at cycle i + s − 1.
• Ideal CPI = 1.

5.2.1 Structural hazards and stalls; CPI and speedup with stalls

• Hazards: structural (hardware), data (values), control (branches).
• Stall = bubble; CPI = 1 + average stalls.
• Speedup (balanced, no overhead) = k / (1 + stalls); in general (CPI·T)_np / (CPI·T)_p.
• Total cycles = k + n − 1 + stalls.

5.2.2 Data dependences: RAW, WAR, WAW; finding them in code

• RAW: later reads what earlier writes (true). WAR: later writes what earlier reads (anti). WAW: both write (output).
• Count only nearest pairs (no intervening write).
• In-order 5-stage: only RAW stalls. Renaming removes WAR/WAW.

5.2.3 Handling data hazards: stalling, operand forwarding, the load-use hazard

• No forwarding, split RF: stalls 2/1/0 for distance 1/2/3 (no split: 3/2/1).
• Forwarding: ALU→ALU 0 stalls; load→next use 1 stall; distance 2 after a load: 0.
• Cycles = k + n − 1 + stalls; draw the diagram when dependences overlap.
• Scheduling independent instructions after loads hides the load-use stall.

5.2.4 Control hazards: branch penalty, flushing, prediction, delayed branch

• Penalty = r − 1 (resolution at the end of stage r): EX → 2, ID → 1.
• Stall: CPI = 1 + f_b·penalty. Predict-not-taken: 1 + f_b·p_taken·penalty.
• Delay slots always execute; filled slots hide penalty.
• Count only executed instructions; next fetch after resolution.

5.3.1 Full cycle counting: mixed hazards and multi-cycle stages

• start(i,s) = max(end(i,s−1)+1, end(i−1,s)+1, operand ready, branch resolved+1); end = start + cycles − 1.
• Multi-cycle EX blocks later EX; forward at its end.
• Answer = end of last stage of the last instruction.
• Out-of-order completion creates WAR/WAW hazards.

5.3.2 Pipeline performance from an instruction mix: effective CPI, comparing designs

• CPI = 1 + Σ fraction × (probability) × stall cycles (+ memory stalls).
• Time per instruction = CPI × τ; MIPS = f / CPI.
• Speedup = (CPI·τ)_old / (CPI·τ)_new.
• Deeper pipeline: faster clock, bigger penalties.

🔌 Phase 6 · I/O: Interrupts & DMA

6.1.1 I/O devices, interfaces and ports; memory-mapped vs I/O-mapped I/O; buses

• Interface registers (ports): data, status, control.
• Memory-mapped: ports in memory space, LOAD/STORE, memory space reduced.
• Isolated: separate space, IN/OUT, extra select line.
• Synchronous bus: clock. Asynchronous: handshake. Arbitration: daisy chain or central.

6.1.2 Programmed I/O: polling, busy-waiting and its CPU cost

• Programmed I/O: CPU checks status, moves each word; busy-waits.
• Polling fraction = r × p / f; minimum r = data rate ÷ bytes per poll.
• Busy-waiting occupies the CPU for the whole transfer.
• I/O rates: decimal unless stated.

6.2.1 Interrupts: the interrupt cycle, ISR, context saving, vectored interrupts, priority and daisy chain

• Interrupt: finish current instruction → (if enabled) save PC (next instruction) and PSW → disable → ISR → RTI.
• Vectored: ISR address at table base + vector × entry size. Non-vectored: ISR polls devices.
• Daisy chain: priority by position. Mask register; NMI unmaskable; nesting by priority.

6.2.2 Interrupt-driven I/O: overhead per transfer; interrupts vs polling

• Interrupt CPU fraction = units/s × overhead per unit (cycles/f).
• Gain over busy-wait = time between units ÷ overhead.
• Scale by the device's active fraction for overall cost.
• Very fast block devices → DMA.

6.2.3 DMA: the controller, burst mode, cycle stealing, transparent mode; CPU time lost

• DMA: CPU programs address, count, direction; controller requests bus (HOLD), gets grant (HLDA), transfers, interrupts at the end.
• Burst (block), cycle stealing (word at a time), transparent (idle cycles only).
• Overhead fraction = CPU time per block ÷ block delivery time. Cycle stealing = stolen cycles/s ÷ bus cycles/s. Burst blocking = Y/(X + Y).
• k-bit count → ⌈S / 2ᵏ⌉ DMA operations.