Computer architecture — from logic gates to modern CPUs

Intuition Beginner

A computer is built from billions of tiny switches called transistors. On their own, switches just turn on and off. Computer architecture is the discipline of arranging those switches so that, clock tick by clock tick, they carry out useful work: adding numbers, fetching a web page, decoding a video. The accomplishment is not the switches themselves but the organization that lets them act in concert at four billion coordinated steps per second.

Every CPU speaks a fixed vocabulary called its instruction set. x86 drives most laptops and servers; ARM drives nearly every phone and an increasing share of laptops; RISC-V is the free, open vocabulary used in research and a growing number of chips. A program is just a long list of these instructions stored in memory. The CPU reads one, does what it says, then reads the next. This read-interpret-act loop — fetch, decode, execute — is the heartbeat of every processor.

Speed comes from hierarchy and overlap. Fast memory is small; large memory is slow, so the chip keeps a ladder of caches between its innermost registers and main memory, each level roughly ten times slower than the one above it. At the same time the CPU works on several instructions at once, like a chef with four burners, so that while one instruction waits on memory another can make progress. Architecture is the art of keeping that pipeline full.

Visual Beginner

The diagram below sketches the two organizing ideas of this unit: the fetch-decode-execute pipeline that turns an instruction stream into work, and the memory hierarchy that trades size for speed.

The same idea as a latency ladder, with round-trip times a 4 GHz processor actually experiences for a single access:

Level	Typical time	CPU cycles at 4 GHz
Register	~0.3 ns	~1
L1 cache	~1 ns	~4
L2 cache	~4 ns	~16
L3 cache	~12 ns	~48
DRAM (main memory)	~100 ns	~400
NVMe SSD	~16,000 ns (16 µs)	~64,000
HDD	~10,000,000 ns (10 ms)	~40,000,000

Worked example Beginner

Consider how long it takes the CPU to obtain one piece of data, depending on where it lives. The table above gives the round-trip time for each level. Let us turn those raw numbers into the ratios a programmer actually feels.

The gap between the L1 cache and main memory is about one hundred to one: 1 ns against 100 ns. The gap between main memory and an NVMe SSD is another one hundred and sixty to one: 100 ns against roughly 16,000 ns. And the gap between that SSD and a spinning hard drive is roughly six hundred to one.

So a single access that misses all the way out to SSD costs about as much time as sixteen thousand L1 hits. A cache miss that reaches DRAM costs as much as several hundred arithmetic operations. This is why a program that keeps its active data inside the cache can run a hundred times faster than an identical program that constantly reaches out to RAM, even though both execute exactly the same instructions.

What this tells us: on a modern CPU the location of data matters more than the count of operations, and the whole job of computer architecture is to make the slow, capacious levels behave as though they were as fast as the small, quick ones.

Check your understanding Beginner

Formal definition Intermediate+

Instruction set architecture (ISA). The ISA is the contract between software and hardware: the set of instructions the CPU understands, the programmer-visible registers, the memory-addressing and data types, and the semantics of each instruction (including the programming model for exceptions, privileges, and memory ordering). An implementation that honours this contract is free to use any microarchitecture it likes. x86-64, AArch64 (ARM), and RISC-V are three distinct ISAs; the same C program compiles to three different instruction streams.

Instruction. A single ISA-level operation, encoded as a fixed or variable-length bit pattern in memory. Examples on a RISC machine: add x1, x2, x3 (register add), ld x1, 0(x2) (load), beq x1, x2, offset (branch if equal).

The fetch-decode-execute cycle. The processor repeatedly:

$${\text{fetch}}_t=\text{mem}[{\text{PC}}_t],{\text{PC}}_{t+1}={\text{PC}}_t+\ell ,$$

where $\ell$ is the instruction length, then decodes the fetched word into an opcode and operands, executes it against the register file and arithmetic units, optionally accesses memory, and writes the result back. A scalar processor completes at most one such instruction per cycle.

Pipelining. A $k$-stage pipeline overlaps $k$ consecutive instructions, one per stage. With stages Fetch, Decode, Execute, Memory, Write-back, five instructions are in flight at once. In the ideal (no-stall) limit the pipeline completes one instruction per cycle, so a $k$-stage pipeline can approach a $k$-fold throughput gain over a non-pipelined design. Stalls arise from three hazard classes: structural (two instructions need the same unit), data (one instruction needs a result a predecessor has not yet produced), and control (a branch's target is not yet known).

Cycles per instruction and execution time. With instruction count $\mathrm{IC}$, average cycles per instruction $\mathrm{CPI}$, and clock cycle time $T_{\text{clk}}$ (equivalently clock rate $f=1/T_{\text{clk}}$),

$$T_{\text{exec}}=\mathrm{IC}\cdot \mathrm{CPI}\cdot T_{\text{clk}}=\frac{\mathrm{IC}\cdot \mathrm{CPI}}{f}.$$

Every architectural optimization attacks exactly one of these three factors: fewer instructions, fewer cycles per instruction, or a faster clock.

The memory hierarchy and AMAT. A multi-level cache reduces the average access time seen by the pipeline. With hit time $t_i$ and miss rate $m_i$ at level $i$ (where $m_i$ is the probability of missing at level $i$ given that all upper levels have already missed), the average memory access time satisfies the recurrence

$${\mathrm{AMAT}}_i=t_i+m_i\cdot {\mathrm{AMAT}}_{i+1},{\mathrm{AMAT}}_{k+1}=P,$$

where $P$ is the penalty of reaching backing store (DRAM or SSD).

Amdahl's law (preview). If a fraction $p$ of execution time is enhanced by a factor $s>1$ and the rest is unchanged, the overall speedup is $\mathrm{Speedup}(p,s)=1/((1-p)+p/s)$. This single formula governs every parallel-speedup claim in the field.

Counterexamples to common slips Intermediate+

• More cores does not mean proportionally more speed. A workload with a 5% serial portion cannot exceed $1/0.05=20\times$ speedup, no matter how many cores are added. This is Amdahl's law, not a flaw in the hardware.
• A higher clock rate does not guarantee a faster program. Doubling $f$ helps only if $\mathrm{IC}\cdot \mathrm{CPI}$ is unchanged; if the higher clock forces more cache misses or branch mispredictions, $\mathrm{CPI}$ rises and can erase the gain.
• CISC is not "more powerful" than RISC. Both are universal ISAs. The RISC/CISC distinction is about instruction richness versus cycle-time and CPI; modern x86 chips translate CISC instructions into internal RISC-like micro-operations, so the boundary has largely dissolved at the microarchitecture level.

Key result: Amdahl's law Intermediate+

Theorem (Amdahl 1967). Let a computation have original execution time $T$. Suppose a fraction $p\in [0,1]$ of that time is enhanced so that it runs $s>1$ times faster, while the remaining fraction $1-p$ is unchanged. Then the overall speedup is

$$\mathrm{Speedup}(p,s)=\frac{1}{(1-p)+p/s}.$$

Proof. The enhanced portion originally took $pT$ and the unenhanced portion took $(1-p)T$. After enhancement the enhanced portion takes $(pT)/s$ (it is $s$ times faster), and the unenhanced portion is unchanged at $(1-p)T$. The new execution time is therefore

$$T^{\prime }=(1-p)T+\frac{pT}{s}=T\left((1-p)+\frac{p}{s}\right).$$

The speedup is the ratio of old time to new time:

$$\mathrm{Speedup}(p,s)=\frac{T}{T^{\prime }}=\frac{1}{(1-p)+p/s}.\square$$

Corollary (the serial bound). Even with unbounded enhancement ($s\to \infty$), the speedup is bounded by $1/(1-p)$. A program that is 95% parallelizable can never run more than twenty times faster, regardless of how many cores are thrown at it.

Numeric illustration. Take $p=0.8$ (80% of the work is parallelizable) and a 16-core machine ($s=16$). The speedup is $1/(0.2+0.8/16)=1/(0.2+0.05)=1/0.25=4\times$. Doubling the cores to 32 yields $1/(0.2+0.025)\approx 4.44\times$. The marginal return on the extra sixteen cores is under twelve percent.

Bridge. Amdahl's law builds toward the multicore and GPU analysis in the Advanced results below, where $p$ becomes the fraction of a workload that genuinely parallelizes across cores, and appears again in 50.03.01 algorithmic complexity, where the same $1/((1-p)+p/s)$ denominator measures the gap between a parallel decomposition and its serial bottleneck. This is exactly the foundational reason a program with even a 1% serial portion can never exceed $100\times$ speedup, and the central insight connects the instruction-set abstraction to the operating-system scheduler in 50.05.01, which must keep enough independent work in flight to mask memory and I/O latency. Putting these together, Amdahl's law identifies latency with throughput: the bridge is between a single instruction's wait for data and the whole machine's delivered instructions per cycle.

Exercises Intermediate+

Advanced results Master

Superscalar and out-of-order execution

A scalar pipeline issues at most one instruction per cycle. A superscalar processor issues several — typically four to eight on a modern core — to multiple functional units, exploiting instruction-level parallelism (ILP) found in ordinary sequential code. Out-of-order execution lets the hardware reorder instructions dynamically: as soon as an instruction's operands are ready and a functional unit is free, it may execute ahead of an older stalled instruction, subject to data dependencies. Tomasulo's algorithm ^{[Tomasulo1967]} introduced register renaming and reservation stations to make this practical; it removes false dependencies (write-after-write, write-after-read) by mapping architectural registers to a larger pool of physical ones. Realized IPC is bounded both by the program's inherent ILP and by the issue width; studies of the available parallelism in ordinary programs place it in the low tens, which is why issue widths have plateaued near four to eight rather than climbing indefinitely.

Branch prediction

Control hazards dominate because a mispredicted branch forces a pipeline flush costing tens of cycles. Branch predictors have evolved from simple 2-bit saturating counters per branch to two-level adaptive schemes (Yeh and Patterson) that track branch-history patterns, and to perceptron-based and neural predictors in contemporary designs. State-of-the-art predictors exceed 95% accuracy on integer workloads, and the marginal value of the last few percent is large: halving the misprediction rate from 2% to 1% can cut branch-cost CPI by half. The fundamental limit is information-theoretic: some branches (data-dependent comparisons on freshly loaded values) are genuinely unpredictable, which motivates predication and if-conversion in the compiler.

The memory wall and cache coherence

Processor clock rates improved far faster than DRAM latency through the 1990s and 2000s, producing the memory wall: by 2010 a cache miss could cost several hundred cycles. Caches offset this only when the working set fits. On a multicore chip, each core's private caches must stay coherent with the others, enforced by a cache-coherence protocol such as MESI (Modified, Exclusive, Shared, Invalid) or its MOESI/HESI extensions. These protocols attach a state to every cache line and exchange invalidation and transfer messages over an interconnect. Coherence cost grows with core count, which is why large shared last-level caches and directory-based (rather than broadcast) coherence dominate server chips.

The power wall and the end of Dennard scaling

Dennard's 1974 scaling theory ^{[Dennard1974]} held that as transistors shrank, voltage and current could shrink proportionally, keeping power density constant even as clocks rose. This held until roughly 2005, when threshold-voltage floors and leakage current broke the voltage scaling. Clock rates then levelled near 3-5 GHz: pushing higher would exceed the chip's thermal budget. The consequence was the multicore turn — designers spent additional transistors on more cores rather than faster single threads. The surplus transistors that cannot be powered simultaneously are called dark silicon, and managing them is a first-order concern in mobile and server chips alike.

RISC versus CISC, quantitatively

The RISC movement (Hennessy at Stanford, Patterson at Berkeley, early 1980s ^{[HennessyPatterson1990]}) argued from the iron triangle $T_{\text{exec}}=\mathrm{IC}\cdot \mathrm{CPI}\cdot T_{\text{clk}}$. CISC designs reduced IC by enriching each instruction but inflated CPI and $T_{\text{clk}}$ through complex decode and microcode. RISC designs accepted slightly higher IC in exchange for substantially lower CPI and faster clocks, yielding a net win. The historical verdict is nuanced: the two have converged. Modern x86 cores decode CISC instructions into internal RISC-like micro-operations ($\mu$ops), and ARM has adopted some richer operations. The surviving lesson is the quantitative method itself — measure IC, CPI, and cycle time separately — rather than any particular ISA dogma.

Multicore, SIMD, and GPU throughput

Once single-thread ILP saturated and Dennard scaling ended, performance gains came from explicit parallelism: multiple cores (thread-level parallelism), SIMD lanes (data-level parallelism within a core), and GPUs (massive data parallelism across thousands of lanes). The Roofline model ^{[WilliamsWatermanPatterson2009]} summarizes the achievable throughput of a kernel as $\min (\text{peak compute},\text{bandwidth}\times \text{operational intensity})$, where operational intensity is FLOPs per byte of traffic. A compute-bound kernel rides the horizontal ceiling; a memory-bound kernel rides the diagonal bandwidth slope. The model explains why dense linear algebra scales well on GPUs (high operational intensity) while graph traversal and pointer-chasing do not (low operational intensity, latency-bound on random access).

Memory consistency models

Once multiple cores share memory and caches reorder accesses, programmers need a contract on what orderings are actually visible. Sequential consistency (Lamport 1979) is the intuitive model — the result of any execution is as if all cores' operations interleaved in a single global order — but it is expensive to enforce. Real machines provide weaker models: x86 offers total store order (TSO), in which stores are buffered; ARM and RISC-V offer formally relaxed models. Locks and memory fences restore stronger ordering where needed. The correctness of lock-free data structures and of operating-system primitives 50.05.01 depends on reasoning precisely against the hardware's consistency model, not against intuition.

Synthesis. The through-line of modern architecture is that the foundational reason chips got faster for forty years was not faster clocks alone but ever deeper hiding of latency behind parallelism — instruction-level, data-level, and thread-level. The central insight is that the performance equation $T_{\text{exec}}=\mathrm{IC}\cdot \mathrm{CPI}\cdot T_{\text{clk}}$ decomposes every optimization into exactly three knobs, and this is exactly why the RISC movement ^{[HennessyPatterson1990]} attacked CPI and instruction count while the memory-hierarchy work attacked effective CPI through cache misses. Putting these together with the end of Dennard scaling ^{[Dennard1974]} forces the multicore turn: the bridge is between single-thread ILP, which stalled near a few instructions per cycle, and the data- and thread-parallel throughput of GPUs and vector units. The pattern generalises to distributed and warehouse-scale computing in 50.11.01, where Amdahl's law reappears as the tail-latency and straggler bound, and where cache coherence is dual to the consistency models of replicated state across nodes.

Full proof set Master

Proposition 1 (Multi-level AMAT). For a memory hierarchy of levels $1,\dots ,k$ in which level $i$ has hit time $t_i$ and conditional miss rate $m_i$ (the probability of missing at level $i$ given that every higher level has already missed), with final backing-store penalty $P$, the average memory access time observed at level 1 is

$${\mathrm{AMAT}}_1=t_1+m_1{t}_2+m_1{m}_2{t}_3+\cdots +(m_1{m}_2\cdots m_{k-1})t_k+(m_1{m}_2\cdots m_k)P.$$

Proof. Define $A_i$ to be the expected access time for a request that arrives at level $i$. At level $i$ the hardware always pays $t_i$ to perform the lookup; with probability $1-m_i$ the lookup hits and the access is complete, and with probability $m_i$ it misses and the request falls through to level $i+1$ at expected further cost $A_{i+1}$. This gives the recurrence

$$A_i=t_i+m_i\cdot A_{i+1},A_{k+1}=P,$$

where $A_{k+1}=P$ is the cost of going to backing store after the last cache level misses. Unrolling the recurrence from $i=1$:

$$A_1=t_1+m_1{A}_2=t_1+m_1(t_2+m_2{A}_3)=t_1+m_1{t}_2+m_1{m}_2{A}_3,$$

and iterating to $A_{k+1}=P$ yields the stated telescoping sum. $\square$

Numeric instance. Take $t_1=1$ ns with $m_1=0.05$, $t_2=4$ ns with $m_2=0.20$, $t_3=12$ ns with $m_3=0.50$, and $P=100$ ns. Then $A_3=12+0.50\cdot 100=62$ ns, $A_2=4+0.20\cdot 62=16.4$ ns, and $A_1=1+0.05\cdot 16.4=1.82$ ns. Despite three levels of caching with a 100 ns backing penalty, the pipeline observes an average access of under 2 ns — a fiftyfold improvement over going straight to DRAM, achieved entirely through the hierarchy.

Proposition 2 (Pipelined CPI with hazard stalls). Consider a $k$-stage pipeline with ideal CPI of 1 executing $N$ instructions and incurring $S$ total stall cycles from structural, data, and control hazards. Then the realized CPI and throughput are

$${\mathrm{CPI}}_{\text{actual}}=1+\frac{S}{N},\text{throughput}=\frac{f}{1+S/N}\text{instructions/second},$$

for $N$ large enough that pipeline fill and drain costs are negligible.

Proof. The pipeline takes $k-1$ cycles to fill (one cycle per stage before the first instruction completes). Once filled, each instruction completes one per cycle in the ideal case, so $N$ instructions complete in $N$ useful cycles, plus $S$ cycles lost to stalls, plus the $k-1$ fill cycles. The total cycle count is therefore $(k-1)+N+S$, which for $N\gg k$ is dominated by $N+S$. Dividing total cycles by instruction count gives ${\mathrm{CPI}}_{\text{actual}}=(N+S)/N=1+S/N$. At clock frequency $f$ the cycle time is $1/f$, so instructions per second equals $N$ divided by $(N+S)/f$, namely $f/(1+S/N)$. $\square$

The proposition makes the cost of a single stall visible: if $S/N=0.3$, the pipeline loses 23% of its peak throughput ($1/1.3\approx 0.77$), even though no individual instruction is particularly slow.

Connections Master

• Data structures 50.02.01. The memory hierarchy makes the layout of a data structure as important as its asymptotic complexity. A linked list and an array both perform an insertion in $O(1)$, but the array touches one cache line while the list chases pointers across many, each potentially a cache miss. This is the motivation for cache-oblivious algorithms, B-trees in databases, and the struct-of-arrays layout in graphics and simulation: data structures are designed against the latency ladder, not just against abstract operation counts.

• Algorithmic complexity 50.03.01. Big-O describes how work grows with input size but says nothing about the constant factor the hardware multiplies it by. Two $O(n\log n)$ sorts can differ by an order of magnitude on real hardware because one is cache-friendly and branch-predictable while the other is not. The iron triangle $T_{\text{exec}}=\mathrm{IC}\cdot \mathrm{CPI}\cdot T_{\text{clk}}$ is the bridge from asymptotic complexity to wall-clock time, and Amdahl's law is the bridge from parallel decomposition to realized speedup.

• Operating systems 50.05.01. The kernel is the first program written against the ISA's privilege model: it runs in supervisor mode and uses the same instruction set plus a handful of privileged operations (page-table manipulation, exception return, halt). Virtual memory, context switching, and system calls are all built directly on hardware features — page tables and the TLB, timer interrupts, and the syscall instruction — that this unit defines. The operating system is, in effect, the ISA's most demanding client.

• Distributed systems 50.11.01. The move from one core to many recapitulates the move from one machine to many. Cache-coherence protocols and memory-consistency models are the single-box instance of the consistency problems that reappear in distributed databases, and Amdahl's law scales up into Gustafson's law and the tail-latency bounds that govern warehouse-scale systems.

Historical & philosophical context Master

The stored-program computer was articulated by John von Neumann in the 1945 First Draft of a Report on EDVAC ^{[vonNeumann1945]}, which described a single memory holding both instructions and data — the von Neumann architecture that still underlies nearly every general-purpose processor. The fetch-decode-execute cycle is the operational form of that idea. Earlier machines such as ENIAC were reprogrammed by rewiring; the stored-program insight made software a first-class, mutable artifact and separated programming from hardware engineering.

Gordon Moore's 1965 observation ^[Moore1965] that transistor counts doubled roughly every two years became Moore's law, the exponential that drove the semiconductor industry for half a century. Robert Dennard's 1974 scaling theory ^{[Dennard1974]} explained why that exponential could be harvested as higher performance rather than just denser chips: as transistors shrank, voltage and current could shrink with them, holding power density constant. When Dennard scaling failed around 2005, the industry could keep adding transistors (Moore) but could not keep raising clocks (Dennard), forcing the multicore turn.

Gene Amdahl stated his speedup law in 1967 ^[Amdahl1967] as a caution against over-claiming for parallel machines: the serial fraction caps the gain. The RISC movement of the early 1980s, led by John Hennessy (MIPS at Stanford) and David Patterson (RISC at Berkeley) ^{[HennessyPatterson1990]}, made computer architecture a quantitative science. Their argument — measure instruction count, CPI, and cycle time separately, and let the data decide — crystallized in Computer Architecture: A Quantitative Approach (1990), which reframed the field around measurement and the iron triangle $T_{\text{exec}}=\mathrm{IC}\cdot \mathrm{CPI}\cdot T_{\text{clk}}$, and which remains the canonical reference. Hennessy and Patterson shared the 2017 Turing Award for this work.

Bibliography Master

@techreport{vonNeumann1945,
  author      = {von Neumann, John},
  title       = {First Draft of a Report on the {EDVAC}},
  institution = {Moore School of Electrical Engineering, University of Pennsylvania},
  year        = {1945},
  note        = {Annotated typescript, 30 June 1945},
}

@article{Moore1965,
  author  = {Moore, Gordon E.},
  title   = {Cramming More Components onto Integrated Circuits},
  journal = {Electronics},
  volume  = {38},
  number  = {8},
  year    = {1965},
  pages   = {114--117},
}

@article{Dennard1974,
  author  = {Dennard, Robert H. and Gaensslen, Fritz H. and Yu, Hwa-Nien and Rideout, V. Leo and Bassous, Ernest and LeBlanc, Andre R.},
  title   = {Design of Ion-Implanted {MOSFET}'s with Very Small Physical Dimensions},
  journal = {IEEE Journal of Solid-State Circuits},
  volume  = {9},
  number  = {5},
  year    = {1974},
  pages   = {256--268},
}

@article{Amdahl1967,
  author  = {Amdahl, Gene M.},
  title   = {Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities},
  journal = {AFIPS Conference Proceedings},
  volume  = {30},
  year    = {1967},
  pages   = {483--485},
}

@article{Tomasulo1967,
  author  = {Tomasulo, Robert M.},
  title   = {An Efficient Algorithm for Exploiting Multiple Arithmetic Units},
  journal = {IBM Journal of Research and Development},
  volume  = {11},
  number  = {1},
  year    = {1967},
  pages   = {25--33},
}

@book{HennessyPatterson1990,
  author    = {Hennessy, John L. and Patterson, David A.},
  title     = {Computer Architecture: A Quantitative Approach},
  edition   = {1},
  publisher = {Morgan Kaufmann},
  year      = {1990},
}

@book{HennessyPatterson2017,
  author    = {Hennessy, John L. and Patterson, David A.},
  title     = {Computer Architecture: A Quantitative Approach},
  edition   = {6},
  publisher = {Morgan Kaufmann},
  year      = {2017},
}

@book{PattersonHennessy2020,
  author    = {Patterson, David A. and Hennessy, John L.},
  title     = {Computer Organization and Design: The Hardware/Software Interface ({RISC-V} Edition)},
  edition   = {2},
  publisher = {Morgan Kaufmann},
  year      = {2020},
}

@book{TanenbaumAustin2013,
  author    = {Tanenbaum, Andrew S. and Austin, Todd},
  title     = {Structured Computer Organization},
  edition   = {6},
  publisher = {Pearson},
  year      = {2013},
}

@article{WilliamsWatermanPatterson2009,
  author  = {Williams, Samuel and Waterman, Andrew and Patterson, David},
  title   = {Roofline: An Insightful Visual Performance Model for Multicore Architectures},
  journal = {Communications of the ACM},
  volume  = {52},
  number  = {4},
  year    = {2009},
  pages   = {65--76},
}

@article{Lamport1979,
  author  = {Lamport, Leslie},
  title   = {How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs},
  journal = {IEEE Transactions on Computers},
  volume  = {C-28},
  number  = {9},
  year    = {1979},
  pages   = {690--691},
}