Computation Structures
Introduces the design of digital systems from logic gates to complete processors. Covers combinational and sequential logic, finite-state machines, instruction-set architectures, pipelines, caches, and virtual memory.
From Electrons to Logic Gates
Overview Bridge analog to digital design. Key ideas MOSFETs as switches; CMOS as logic. Digital signal is a voltage range. Noise margins make it reliable. Worked example 3.3V logic high might be...
Overview
Bridge analog to digital design.
Key ideas
- MOSFETs as switches; CMOS as logic.
- Digital signal is a voltage range.
- Noise margins make it reliable.
Worked example
3.3V logic high might be 2.4-3.3V. Above 2.0V is 1.
Common pitfalls
- Assuming exact voltages.
Why it matters
Ladder: transistors -> gates -> modules -> processor.
Combinational Logic and Boolean Algebra
Overview Boole algebra is the math of digital logic. Key ideas AND, OR, NOT, XOR, NAND, NOR. Truth tables. Karnaugh maps. Worked example Simplify A_NOT_B + A_B_NOT + AB to A + B. Common pitfalls ...
Overview
Boole algebra is the math of digital logic.
Key ideas
- AND, OR, NOT, XOR, NAND, NOR.
- Truth tables.
- Karnaugh maps.
Worked example
Simplify A_NOT_B + A_B_NOT + AB to A + B.
Common pitfalls
- Ignoring dont-cares.
Why it matters
Fewer gates is not always faster.
Sequential Logic and Flip-Flops
Overview Storage requires feedback. Key ideas Latch: level-sensitive. Flip-flop: edge-triggered. Setup and hold times. Worked example D flip-flop stores one bit on rising edge. Common pitfalls ...
Overview
Storage requires feedback.
Key ideas
- Latch: level-sensitive.
- Flip-flop: edge-triggered.
- Setup and hold times.
Worked example
D flip-flop stores one bit on rising edge.
Common pitfalls
- Ignoring setup/hold violations.
Why it matters
Synchronous design makes timing tractable.
Finite State Machines
Overview States, inputs, transitions, outputs. Key ideas Moore: output = f(state). Mealy: output = f(state, input). Any FSM can be built from flip-flops and gates. Worked example Traffic light states...
Overview
States, inputs, transitions, outputs.
Key ideas
- Moore: output = f(state).
- Mealy: output = f(state, input).
- Any FSM can be built from flip-flops and gates.
Worked example
Traffic light states red/yellow/green with timer transitions.
Common pitfalls
- Missing transitions.
Why it matters
Traffic lights, protocols, and CPU control units.
Instruction Set Architectures
Overview The ISA is the contract between hardware and software. Key ideas Registers, memory, PC. RISC vs CISC. Beta ISA is a clean RISC for teaching. Worked example To add two numbers: load, add,...
Overview
The ISA is the contract between hardware and software.
Key ideas
- Registers, memory, PC.
- RISC vs CISC.
- Beta ISA is a clean RISC for teaching.
Worked example
To add two numbers: load, add, store.
Common pitfalls
- Assuming complex ISAs are faster.
Why it matters
Compilers target an ISA; OSes save and restore its state.
Pipelining
Overview Execute instructions in parallel by overlapping stages. Key ideas Five stages: fetch, decode, execute, memory, write-back. Hazards: data, control, structural. Forwarding handles most. Worked...
Overview
Execute instructions in parallel by overlapping stages.
Key ideas
- Five stages: fetch, decode, execute, memory, write-back.
- Hazards: data, control, structural.
- Forwarding handles most.
Worked example
Ideal CPI = 1.
Common pitfalls
- Forgetting pipeline fill/drain.
Why it matters
Ideal speedup 5x, real workloads 3-4x.
Caches and Memory Hierarchy
Overview CPU speed grows faster than memory speed. Key ideas Temporal and spatial locality. Direct-mapped, set-associative, fully associative. Write-through vs write-back. Worked example Good...
Overview
CPU speed grows faster than memory speed.
Key ideas
- Temporal and spatial locality.
- Direct-mapped, set-associative, fully associative.
- Write-through vs write-back.
Worked example
Good locality runs several times faster on identical hardware.
Common pitfalls
- Ignoring cache-line effects.
Why it matters
Programming for locality is highest-leverage.
Virtual Memory
Overview Private, contiguous address space per process. Key ideas Pages, page tables, TLB. Page faults load from disk. Protection falls out of translation. Worked example Two processes both use...
Overview
Private, contiguous address space per process.
Key ideas
- Pages, page tables, TLB.
- Page faults load from disk.
- Protection falls out of translation.
Worked example
Two processes both use virtual 0x1000, mapped differently.
Common pitfalls
- Forgetting TLB is a cache.
Why it matters
On 64-bit, VM is more about protection.
๐ Boolean Logic
Q1. Simplify A'B + AB' + AB.
Show Solution
A + B.
๐ FSM Design
Q1. Detect sequence 1011.
Show Solution
4 states S0-S3.
๐ฏ Midterm Exam
Q1. 2-bit counter with D flip-flops.
Show Solution
Next-state logic for 00->01->10->11.
๐ฏ Final Exam
Q1. 5-stage pipeline speedup.
Show Solution
Ideal ~5x, reduced by hazards.