📘 Digital Logic and Computer Architecture

This page climbs from single transistors to a modern out-of-order CPU. You do not need to design chips, but knowing how a CPU executes instructions explains why some code is fast and some is slow.

Table of Contents

1. Transistors and Logic Gates
2. Boolean Algebra
3. Combinational Circuits
4. Sequential Circuits
5. The von Neumann Architecture
6. Inside the CPU
7. The Instruction Cycle
8. Instruction Set Architectures
9. Pipelining
10. Branch Prediction and Speculation
11. Superscalar and Out-of-Order Execution
12. Measuring CPU Performance
13. Questions

1. Transistors and Logic Gates

A transistor is an electrically controlled switch. CMOS chips pair complementary transistors so that almost no current flows except while switching. A modern high-end chip has tens of billions of them; Apple's M3 Max has about 92 billion, and large GPUs over 200 billion across multiple dies.

Gates combine transistors into Boolean functions:

NAND and NOR are universal: any Boolean function can be built from NAND gates alone (or NOR alone). For example, NOT A = A NAND A, and A AND B = NOT (A NAND B).

2. Boolean Algebra

De Morgan's laws show up in everyday code: !(a && b) equals !a || !b.

Circuits are simplified with algebra or Karnaugh maps (grids that group adjacent 1s), producing fewer gates, less area, and lower delay. Real chip design uses hardware description languages (Verilog, VHDL, Chisel) and synthesis tools that do this automatically.

3. Combinational Circuits

Output depends only on current inputs; no memory.

Subtraction reuses the adder: A - B = A + (~B) + 1, which is why two's complement won (see Number Systems).

4. Sequential Circuits

Output depends on inputs and stored state; this is where memory comes from.

The clock synchronizes everything: on each tick, flip-flops capture new values computed by combinational logic since the last tick. The clock period must be longer than the slowest path through the logic (critical path), which limits the frequency. Clock speeds have hovered around 3 to 6 GHz since the mid-2000s because power density (heat) grows with frequency; performance gains now come from parallelism, caches, and specialized units instead.

SRAM (caches, registers) stores a bit in a 6-transistor latch: fast, large, expensive. DRAM (main memory) stores a bit as charge in a capacitor with 1 transistor: dense and cheap, but it leaks and must be refreshed every few milliseconds, and reads are slower.

5. The von Neumann Architecture

Almost every computer follows the design John von Neumann described in 1945: instructions and data live in the same memory, and the CPU fetches both over the same path.

The stored-program idea is what makes software possible: a program is just data that the CPU executes, which is also why code injection attacks exist and why pages are marked non-executable.

Buses:

• Address bus: which location (its width limits addressable memory).
• Data bus: the value.
• Control bus: read or write, interrupts, clock.

Modern systems replace shared buses with point-to-point links: PCIe for devices, DDR channels for memory, and on-chip networks between cores.

6. Inside the CPU

A modern chip packs many cores, each a complete CPU, plus shared cache, memory controllers, often a GPU, and neural engines on one die or several chiplets in one package.

7. The Instruction Cycle

Example: ADD R1, R2, R3 (R1 = R2 + R3).

1. Fetch: send the PC to memory (via the cache), load the instruction, increment PC.
2. Decode: opcode says ADD; source registers R2, R3; destination R1.
3. Execute: the ALU adds the two register values.
4. Memory: nothing to do for ADD.
5. Write back: store the sum in R1.

Addressing modes

8. Instruction Set Architectures

The ISA is the contract between software and hardware: instructions, registers, memory model, and encoding. The microarchitecture is how a particular chip implements it (Intel and AMD both implement x86-64 very differently).

The line has blurred: modern x86 chips decode CISC instructions into RISC-like micro-ops internally, and ARM added some complex instructions.

Apple's move to ARM (2020) and cloud providers' ARM server chips shifted the industry: ARM servers often cost 20 to 40 percent less for the same work, so multi-architecture container images (linux/amd64, linux/arm64) are now standard.

9. Pipelining

Like a laundry line (wash, dry, fold), a pipeline overlaps the stages of consecutive instructions.

Cycle:        1    2    3    4    5    6    7    8
Instr 1:      IF   ID   EX   MEM  WB
Instr 2:           IF   ID   EX   MEM  WB
Instr 3:                IF   ID   EX   MEM  WB
Instr 4:                     IF   ID   EX   MEM  WB

Ideal: after filling, one instruction completes per cycle. Without pipelining 4 instructions take 4 x 5 = 20 cycles; with it they take 5 + 3 = 8. For n instructions in a k-stage pipeline: k + (n - 1) cycles; speedup approaches k for large n.

Pipelining improves throughput, not the latency of a single instruction.

Hazards

Data hazard types: RAW (read after write, the true dependency), WAR and WAW (false dependencies removed by register renaming).

A load-use hazard cannot be fully forwarded: the loaded value arrives at the end of MEM, so the dependent instruction must stall at least a cycle.

10. Branch Prediction and Speculation

Pipelines are 15 to 20 stages deep in modern CPUs, so waiting for every branch to resolve would waste most cycles. The CPU predicts the branch and speculatively executes the predicted path. On a misprediction it throws away the speculative work, costing roughly 15 to 20 cycles.

The classic demonstration: summing values above a threshold in an array runs several times faster when the array is sorted, because the branch becomes predictable. Branchless code (cmov, arithmetic masks) avoids the problem when data is random.

Spectre and Meltdown (2018) showed that speculative execution leaves traces in the cache that can leak secrets across security boundaries. Mitigations (retpolines, kernel page-table isolation, speculation barriers) cost some performance, especially for system calls.

11. Superscalar and Out-of-Order Execution

The practical lesson: modern CPUs can do several operations per cycle, but only if the code has independent work and data is in cache. A chain of dependent operations (each needing the previous result) or a cache miss stalls everything.

12. Measuring CPU Performance

The CPU performance equation:

CPU time = Instruction count x CPI x Clock period
         = Instructions x (Cycles / Instruction) x (Seconds / Cycle)

Example: a program runs 2 billion instructions at a CPI of 1.5 on a 3 GHz CPU: 2 x 10^9 x 1.5 / (3 x 10^9) = 1 second.

Benchmarks: SPEC CPU for general compute, Geekbench for consumer comparisons, and your own workload for anything that matters. perf stat shows instructions, cycles, IPC, cache misses, and branch mispredictions for a real program.

13. Questions

Next: Memory Hierarchy and Caches.