Short notes: Computer Organization & Architecture
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
Most predictable topic. Nearly every paper has an EA / operand-value or instruction-format question.
- Instruction = opcode + operand fields. Length = opcode bits + mode bits + register/address bits. Format decides how many distinct instructions are possible.→ Opcode says what, operands say on what; longer operand list squeezes the opcode.
- n-address machines. 3-addr:
ADD R1,R2,R3· 2-addr:ADD R1,R2(dest = src1) · 1-addr: uses accumulator · 0-addr: stack machine (PUSH/POP, ops on top-of-stack).→ Fewer addresses, shorter instructions, longer program. - Expanding opcode. Unused opcode patterns of a longer-address format are 'borrowed' to encode shorter-address instructions. Each level multiplies leftover patterns by 2field width.→ Leftover patterns × 2address bits at every level.
- Addressing modes (know EA of each). Immediate: operand is in the instruction · Direct: EA = A · Indirect: EA = M[A] · Register: operand = R · Reg-indirect: EA = R · Indexed: EA = A + X · Base-register: EA = A + B · Relative: EA = PC + A (PC already points to the next instr) · Auto-inc/dec: EA = R, then R±=size · Stack: implicit SP.→ Immediate = the value; direct = the address; indirect = the address of the address.
- Why each mode exists. Immediate → constants. Direct → globals. Indirect → pointers. Indexed → arrays (A = base, X = index). Base-register → relocation / segments. Relative → position-independent code & branches. Auto-inc → stepping through arrays/stack.→ Pick the mode by the job: constant, variable, pointer, array, branch.
- RISC vs CISC. RISC: fixed-length instrs, load/store only, many registers, few modes, hardwired control, easy to pipeline. CISC: variable length, memory operands, many modes, microprogrammed, complex instrs.→ RISC = simple, fixed, pipeline-friendly. CISC = complex, compact.
- Endianness. Big-endian: MSB at lowest address. Little-endian: LSB at lowest address (x86).→ Little = little end first.
- Stack / postfix evaluation. Scan left→right; operand → PUSH; operator → POP two, compute, PUSH. Convert infix → postfix to count PUSH/POP or minimum registers.→ Operand = push. Operator = pop two, compute, push.
Formulas
What GATE asks
- ★★★EA / operand value for a given mode. Given register & memory contents and instruction fields (indexed, base, relative, indirect), compute EA or final operand. Trap: relative uses updated PC; auto-increment gives EA before increment.
- ★★★Expanding opcode: max number of instructions. '16-bit instr, 4-bit regs; 15 two-addr instrs exist, how many one-addr / zero-addr can be encoded?' Use the formula, subtract used patterns at each level.
- ★★★Instruction size / memory needed. Compute instruction length from #opcodes, #registers, immediate size; then program size or PC increment.
- ★★★Stack machine / postfix code. Count PUSH/POP or evaluate expression on a stack machine; min registers needed.
- ★★★Concept one-liners. Which mode suits array access / relocation / pointer; RISC vs CISC statements; endianness; why immediate is fastest.
Traps
Guaranteed 1–2 questions: speedup/time calculation, stall counting, hazard identification.
- Idea. Overlap execution of instructions by splitting into stages (e.g. IF, ID, EX, MEM, WB). Improves throughput, not the latency of a single instruction.→ Time = (k + n − 1) cycles; speedup approaches k.
- Cycle time. Clock = slowest stage + latch (register) delay. Unbalanced stages waste time.→ Clock = slowest stage + latch.
- Structural hazard. Two instructions need the same hardware in the same cycle (e.g. one memory port for IF and MEM). Fix: duplicate resource or stall.→ Same hardware, same cycle: stall or duplicate.
- Data hazards. RAW (true dependency, read after write), the common one. WAR (anti) and WAW (output) arise with out-of-order completion / different write stages.→ RAW is the real one; WAR and WAW are name clashes.
- Control hazard. Branch outcome known late → wrong-path fetches. Fix: stall, predict (static/dynamic), delayed branch, branch target buffer.→ Wrong guess = flushed instructions = penalty cycles.
- Operand forwarding (bypass). Send ALU result straight to the next EX input. Removes most RAW stalls. A load-use dependency still needs 1 stall.→ Forwarding fixes ALU→ALU. Load-use always costs 1.
- Stall counting (classic 5-stage). Assuming register write in 1st half / read in 2nd half of a cycle: no forwarding → dependent instr right after producer stalls 2 cycles, at distance 2 → 1 stall, distance ≥ 3 → 0. If that split-cycle trick is NOT assumed, use 3 / 2 / 1.→ No forwarding: stalls = 3 − distance.
- Beyond. Superscalar (multiple issue/cycle), VLIW (compiler-scheduled), dynamic scheduling (scoreboard, Tomasulo), mostly conceptual.→ Superscalar: IPC above 1, limited by dependencies.
Formulas
What GATE asks
- ★★★Total cycles / time for n instructions. Plug (k+n−1)·t_p. Often with unequal stage delays: take the max + latch overhead.
- ★★★Speedup vs non-pipelined. Ratio of n·Σdelays to (k+n−1)·t_p. Watch whether latch delay applies to the non-pipelined design (it doesn't).
- ★★★Count stalls / cycles for a code sequence. Given 4–6 instructions with RAW dependencies, with or without forwarding, find total cycles. Draw the Gantt chart.
- ★★★Identify hazard type. Given two instructions, classify as RAW/WAR/WAW; or say which hazards exist in a code fragment.
- ★★★Effect of branches on CPI. CPI = 1 + freq × penalty; compare predict-taken vs not-taken; delayed-branch slots.
Traps
The single highest-yield topic: bits-in-tag, mapping, hit/miss tracing and AMAT appear nearly every year.
- Why cache works. Temporal locality (reuse soon) and spatial locality (neighbours soon). Blocks (lines) are fetched, not single words.→ Locality + blocks = most accesses become hits.
- Direct mapped. Block j → line (j mod #lines). 1 comparator, cheap, fast, but conflict misses.→ One home per block: simple, but conflict-prone.
- Fully associative. Block can go anywhere. Many comparators (one per line), no conflict misses, expensive. Address = tag + offset.→ Anywhere placement: no conflicts, most hardware.
- k-way set associative. Block j → set (j mod #sets), any of k ways inside. Compromise. Address = tag + set + offset.→ Block picks the set; the k ways inside are interchangeable.
- Address split. offset = log₂(block size) · index/set = log₂(#lines or #sets) · tag = the remaining high bits.→ More ways: fewer index bits, more tag bits.
- Replacement. LRU (best usually), FIFO, Random. Direct-mapped needs none.→ LRU uses recency; FIFO uses arrival time.
- Write policies. Write-through: update cache + memory every write (simple, slow, often no-write-allocate, uses write buffer). Write-back: write memory only on eviction; needs a dirty bit; usually write-allocate.→ Write-back saves traffic, needs a dirty bit.
- Miss types (3 C's). Compulsory (first access), Capacity (cache too small), Conflict (set/line contention; none in fully associative).→ Compulsory = first time, capacity = too small, conflict = bad mapping.
- Multi-level cache. L1 small & fast, L2 bigger & slower. Local miss rate of L2 is relative to L2 accesses; global = product.→ AMAT = t1 + miss1 × (t2 + miss2 × t_mem).
Formulas
What GATE asks
- ★★★Number of tag bits / tag-directory size. Given cache size, block size, associativity, address width. Compute offset, index, tag; multiply by lines and add valid/dirty bits.
- ★★★Hit/miss trace for an address sequence. Simulate direct-mapped or k-way LRU for ~8–12 addresses; count misses or find final cache content. (Use the simulator below!)
- ★★★AMAT / effective access time. Single or two-level; sometimes with write-through/back mix or different read/write ratio.
- ★★★CPI / speedup with cache. Base CPI + stalls from instruction & data misses; compare two cache configs.
- ★★★Which bits map to which field / conceptual. Which address bits select the set; effect of increasing block size or associativity on miss types; write-back vs through statements.
Traps
IEEE 754 and 2's-complement range/overflow come up regularly; Booth and carry-lookahead occasionally.
- Unsigned & signed formats. Sign-magnitude, 1's complement (two zeros), 2's complement (one zero, used everywhere). 2's complement of x = invert bits + 1.→ 2's complement: one zero, one extra negative, adders just work.
- Overflow. Adding two same-sign numbers and getting opposite sign. Hardware:
V = Cin ⊕ Coutof the MSB. Unsigned overflow = carry out of MSB.→ Overflow = carry into MSB differs from carry out of MSB. - Sign extension. Copy the MSB into new high bits to keep value when widening a 2's complement number.→ Sign extension copies the sign bit; zero extension is for unsigned.
- IEEE 754 single. 1 sign | 8 exponent (bias 127) | 23 fraction. Normal:
(−1)s × 1.f × 2e−127.→ Stored exponent = true exponent + 127; hidden leading 1. - IEEE 754 double. 1 | 11 (bias 1023) | 52. Normal:
(−1)s × 1.f × 2e−1023.→ Single: 8 bits / bias 127 / 23 fraction. Double: 11 / 1023 / 52. - Special values. e = 0, f = 0 → ±0 · e = 0, f ≠ 0 → denormal
0.f × 2−126· e = all 1s, f = 0 → ±∞ · e = all 1s, f ≠ 0 → NaN.→ All-ones exponent: ∞ or NaN. Zero exponent: 0 or denormal. - Booth's algorithm (radix-2). Inspect (Q₀, Q₋₁): 01 → A ← A + M · 10 → A ← A − M · 00 / 11 → no op. Then arithmetic shift right (A,Q,Q₋₁). n iterations. Skips runs of 1s → fast for strings of 1s. Radix-4 (modified Booth) → n/2 steps.→ 01: add, 10: subtract, 00/11: just shift.
- Adders. Ripple-carry: delay ∝ n. Carry-lookahead:
G = A·B,P = A⊕B,Ci+1 = Gi + PiCi, all carries in constant gate depth (per group).→ Ripple = O(n), lookahead = O(1) levels per group. - Precision & rounding. Mantissa has hidden leading 1. Floating-point addition: align exponents (shift smaller), add, normalise, round. Not associative!→ Floating point is approximate: order of operations matters.
Formulas
What GATE asks
- ★★★IEEE 754: hex ↔ decimal. Given a 32-bit hex pattern, find the value; or represent a decimal such as −5.75 in IEEE format. Mind bias and hidden 1.
- ★★★Range / overflow in 2's complement. Which operations overflow; value after adding two n-bit numbers; result of sign-extension or shift.
- ★★★Booth multiplication trace. Content of A,Q registers after k steps, or number of add/sub operations.
- ★★★Adder delay / carry-lookahead. Gate-delay of ripple vs CLA for n bits.
- ★★★Floating-point properties. Smallest/largest, precision loss, ordering of FP numbers by bit pattern, effect of rounding or non-associativity.
Traps
Regular but low-count: microprogrammed control-word size, hardwired vs micro, and cycles for an instruction on a given bus design.
- Instruction cycle. Fetch: MAR←PC; MDR←M[MAR], PC←PC+1; IR←MDR. Decode. Execute (operand fetch, ALU, write-back). Interrupt check at the end.→ Fetch, decode, execute; PC already points to the next instruction.
- Key registers. PC next instr address · IR current instr · MAR address to memory · MDR data to/from memory · ACC, SP, PSW/flags (Z, C, S, V).→ PC next, IR current, MAR address, MDR data.
- Single-cycle vs multi-cycle. Single-cycle: CPI = 1, clock = longest instruction path. Multi-cycle: clock = longest stage, CPI 3–5 and varies. Pipeline gets CPI ≈ 1 with short clock.→ Single-cycle: slow clock. Multi: variable CPI. Pipeline: both fast.
- Bus organisation. More internal buses ⇒ more parallel transfers per cycle ⇒ fewer cycles per instruction. 1-bus: ALU needs temp registers (Y, Z). 3-bus: two sources + one destination at once.→ More buses, fewer cycles.
- Hardwired control. Control signals from logic gates / state counter. Fast, hard to modify, used in RISC.→ Hardwired = fast, rigid, used in RISC.
- Microprogrammed control. Each instruction → microprogram in control store (ROM); μPC steps through microinstructions. Flexible, slower, used in CISC. Nanoprogramming adds a second level to save space.→ Microprogrammed = flexible, slower, CISC.
- Horizontal microinstruction. One bit per control signal. Wide, much parallelism, no decoding → fast, big control store.→ Horizontal = width equals number of signals.
- Vertical microinstruction. Encoded fields. Narrow, small store, needs decoders → slower, less parallelism.→ Vertical: ⌈log2(n+1)⌉ bits per field.
- Microinstruction sequencing. Next address from: μPC+1, branch field (conditional), or mapping from opcode. Control-store size = #microinstr × width.→ Default μPC + 1; branches and mapping change it.
Formulas
What GATE asks
- ★★★Control word / control-store size. Given signals grouped in mutually-exclusive sets, compute vertical width ⇒ control-store bits; contrast with horizontal.
- ★★★Hardwired vs microprogrammed statements. True/false on speed, flexibility, RISC/CISC, writable control store.
- ★★★Cycles / registers touched for an instruction. Which registers change in each micro-step; number of clock cycles on a 1/2/3-bus datapath.
- ★★★Clock period from datapath delays. Single-cycle clock from component delays along the critical path.
Traps
Short numeric questions that also underpin pipeline and cache problems.
- Iron law. CPU time = Instruction count × CPI × clock period. Three levers: compiler/ISA (IC), microarchitecture (CPI), technology (clock).→ T = IC × CPI ÷ f.
- MIPS isn't everything. MIPS can mislead: different ISAs need different IC. Compare machines by execution time.→ Compare execution time, not MIPS.
- Average CPI. Weighted by instruction mix.→ CPI = Σ (fraction × CPI).
- Amdahl's law. Speeding up fraction f by s overall gives diminishing returns; bound = 1/(1−f).→ The part you cannot improve sets the limit.
Formulas
What GATE asks
- ★★★Average CPI / execution time from an instruction mix. Given % of ALU, load/store, branch and their cycles, compute CPI or time for IC instructions.
- ★★★Compare two designs. e.g. higher clock but higher CPI; or enhancement on part of the instructions (Amdahl).
- ★★★MIPS rating. Compute from CPI and clock.
Traps
Chip-count, address-line, interleaving and virtual-memory (EAT with TLB) problems show up regularly.
- Hierarchy. Registers → L1 → L2/L3 → Main memory (DRAM) → Disk. Going down: bigger, slower, cheaper per bit. Works because of locality.→ Faster means smaller and costlier per bit.
- SRAM vs DRAM. SRAM: flip-flops, fast, expensive, no refresh → cache. DRAM: capacitor, dense, cheap, needs periodic refresh → main memory.→ SRAM = cache, no refresh. DRAM = main memory, refresh.
- ROM family. ROM, PROM, EPROM (UV erase), EEPROM, Flash (block erase).→ ROM < PROM < EPROM < EEPROM < Flash in rewrite flexibility.
- Memory organisation. Capacity = 2n × word width. Build large memory from smaller chips: more words → extra address lines go to a decoder; wider words → chips side-by-side.→ Chips = (words ÷ chip words) × (width ÷ chip width).
- Interleaving. Low-order: consecutive addresses in consecutive banks → sequential access overlaps (high bandwidth). High-order: bank by top bits → contiguous region per bank, no overlap.→ Low-order interleaving makes sequential accesses parallel.
- Virtual memory. Pages of virtual space map to frames. Page table in memory; TLB caches recent translations. Page fault → OS loads page from disk.→ TLB hit is cheap; miss adds a memory access per level; fault is disastrous.
- Page table size. Number of entries = virtual pages. Multi-level reduces memory for sparse use. Inverted page table: one entry per physical frame.→ Table size = (2^VPN bits) × entry size.
Formulas
What GATE asks
- ★★★Number of chips / address lines / decoder size. Build 1M×32 memory from 256K×8 chips: chips = 16, decoder lines etc.
- ★★★Page table size / address translation bits. Given virtual & physical sizes and page size, compute PTE count, VPN/offset bits (shared with OS).
- ★★★EAT with TLB and/or page faults. Hit ratio h, TLB time, memory time, maybe two-level page table (+m per extra level).
- ★★★Interleaving / memory cycle statements. Which interleaving gives parallelism; total time to fetch a block from M banks.
- ★★★SRAM/DRAM, refresh, hierarchy conceptual. One-liner true/false.
Traps
Easy marks: capacity and access-time arithmetic.
- Geometry. Platters have surfaces → concentric tracks → sectors. A cylinder = same track on all surfaces.→ Capacity is a product; addressing is a sum of bits.
- Disk access time. Seek (move arm) + rotational latency (wait for sector) + transfer (read sector) + controller overhead.→ Access = seek + rotation + transfer.
- Rotational latency. On average half a rotation.→ Latency = ½ rotation = 30000 ÷ RPM ms.
- Transfer. One full rotation reads one whole track; so the rate = track capacity × rotations per second.→ Transfer rate = bytes per track × rotations per second.
- SSD vs HDD. SSD: no moving parts, no seek/rotation, flash-based.→ SSD: no moving parts, no seek.
Formulas
What GATE asks
- ★★★Disk capacity / bits to address a block. Given geometry compute capacity or CHS address width.
- ★★★Average access time for a request. Seek + ½ rotation + transfer for k sectors; sometimes with cylinder-change seek.
- ★★★Transfer rate / time for a file. File size ÷ (track bytes × rotations per sec).
Traps
A DMA/interrupt timing or overhead question is common; the rest is theory.
- I/O addressing. Memory-mapped: devices share the address space (use normal LOAD/STORE). Isolated (port-mapped): separate address space, special IN/OUT instructions.→ Memory-mapped: shared address space. Isolated: separate with IN/OUT.
- Programmed I/O (polling). CPU loops checking status. Simple but wastes CPU (busy-wait).→ Polling: simple, wasteful.
- Interrupt-driven I/O. Device raises INTR when ready; CPU saves context, jumps to ISR, returns (IRET). CPU does useful work meanwhile. Still moves each word through the CPU.→ Interrupts: CPU works until the device asks.
- Interrupt handling. Finish current instr → ack → save PC/flags → get vector → run ISR → restore → resume. Vectored = device supplies ISR address. Maskable vs non-maskable. Priority via daisy chain (closest device wins) or priority encoder.→ Save PC and flags, run ISR, restore, resume.
- DMA. A DMA controller moves blocks device ↔ memory without the CPU. CPU only sets up (address, count, direction) and is interrupted at the end.→ DMA = one setup, one completion interrupt.
- DMA modes. Burst: DMA holds the bus for the whole block, CPU stalls. Cycle stealing: DMA takes the bus one cycle at a time between CPU cycles. Transparent: DMA uses the bus only when CPU isn't.→ Burst blocks CPU, stealing slows it, transparent leaves it alone.
- Handshake & bus. Synchronous bus (clocked, fast, needs equal speeds) vs asynchronous (REQ/ACK handshake, flexible).→ Sync = clock; async = handshake.
- Serial transfer. Asynchronous: start bit + data + (parity) + stop bit(s) per character. Synchronous: blocks with sync chars.→ Efficiency = data bits ÷ frame length.
Formulas
What GATE asks
- ★★★% CPU time for polling / interrupt / DMA. Given device speed, clock, cycles per poll/ISR, find fraction of CPU consumed or pick the best technique.
- ★★★DMA mode behaviour. Effect on CPU in burst vs cycle stealing; who is bus master; when interrupt is raised.
- ★★★Interrupt concepts. Daisy-chain priority, vectored vs non-vectored, what is saved, when is an interrupt recognised (after current instr).
- ★★★Serial I/O efficiency / baud. Bits per char including start/stop; effective data rate.