A computer is a machine that follows instructions. You give it some input, it runs through the instructions step by step, and out comes the answer. Every later article in this series is a refinement of that one sentence. The everyday object that fits in your bag, runs your browser, and plays your videos is one kind of computer. The chip in a microwave that counts down the timer is another. The controller inside a car engine that decides exactly when to fire each spark plug is a third. They look nothing alike from the outside, but on the inside they all do the same thing: read inputs, follow a procedure, produce outputs. Before we can study how modern processors do this work — and why it has gotten so fast that a billion steps a second can feel instantaneous — we need to be careful with a few words. What is *computation*? What is the difference between hardware and software? Why is it useful that programs live in the same memory as data? When chip designers say "architecture", what do they actually mean? Each of those questions gets a section below. ## What computation is Computation is what a machine does when it follows a procedure. A *procedure* is a list of steps. Anyone who has followed a recipe to bake a cake has carried out a procedure. Read the next instruction, do what it says, move to the next one. Cooks call this a recipe; mathematicians call it an algorithm; computer engineers call it a program. The vocabulary shifts from field to field; the underlying idea is the same. Three things show up in every procedure: - **Input** — what you start with. For the cake, it is flour, eggs, and sugar. For a calculator, it is the numbers you typed in. For a phone, it might be the photo you just took, or the song you tapped on, or the network packet that just arrived. - **Output** — what you end with. For the cake, it is the cake. For the calculator, it is the answer on the screen. For the phone, it is whatever the program produces: a smaller image, a decoded song, a reply on the network. - **State** — the work-in-progress in between. Halfway through baking, the batter exists; that is state. Halfway through a calculation, partial results exist somewhere inside the machine; that is also state. State is the reason a computer can do anything more interesting than one-shot arithmetic: it can remember where it is. A *computation* is the act of starting with some input, going step by step through the procedure (carrying state forward as you go), and arriving at the output. The same idea is sometimes clearer when written as a piece of math. Let $x$ stand for the input, $y$ for the output, $s_0$ for the starting state — what the machine looks like before it begins — and $\delta$ for the rule that takes the state from one step to the next. Then a computation is exactly: $$ y = f(x), \quad \text{where} \quad f(x) = \mathrm{out}\big(\delta^{k}(s_0, x)\big) \text{ for some finite } k. $$ The notation looks dense, but each piece names something we already used in plain English. $f$ is the function the machine computes — give it an input $x$, get an output $y$. $\delta^{k}$ means "apply the step rule $\delta$ a total of $k$ times" — take $k$ steps in a row. $\mathrm{out}(\cdot)$ reads the answer out of the final state. The phrase "for some finite $k$" is the load-bearing constraint: the machine must stop after a finite number of steps. A procedure that loops forever computes nothing. Read aloud and it says exactly what the paragraph above said: starting from some input, take a finite number of steps, end with an output. The math is shorthand, never a replacement; the two always agree. We will reach for math like this whenever it sharpens an idea more cleanly than prose can — and we will introduce every new symbol the same way, in plain words first. It is worth separating two words that often get used as if they meant the same thing. An **algorithm** is the idea — the recipe stated in the abstract, independent of who or what is going to follow it. A **program** is the recipe written down in a particular language for a particular machine. "Add these two numbers" is an algorithm. The actual bytes a chip reads when it carries out that addition are a program. The same algorithm can be written in many languages and produce many different programs; the underlying idea is one. Why do we want machines that can carry out procedures? Two answers, and both matter. The first answer is mathematical. A surprising amount of what we treat as "thinking" is actually procedure. Solving an arithmetic problem, sorting a stack of papers by date, looking a name up in a phone book, finding the shortest route through a city — each of these is a step-by-step procedure that any patient person can follow without insight or creativity. If a person can follow it patiently, a machine can follow it quickly. That is the practical promise of the entire field. The second answer is physical. Computers also automate tasks in the world. They control the spark timing in a car engine, decode a radio signal back into voice, regulate the dose of insulin from a pump, and turn the light hitting a camera sensor into a JPEG file. Most of those jobs are not what mathematicians would call "computation" — they are about reacting to physical events fast enough to matter. But the same machine handles both kinds of work, because at a deep enough level they have the same shape: read inputs, run a procedure, emit outputs. For the rest of this series, when we say *computer* we mean any machine that runs procedures in this way. A pocket calculator is a computer. A microwave's timer chip is a computer. A laptop is a computer. A datacenter rack with thousands of cores is a computer. The architectural ideas we are about to study apply to all of them; only the cost, the speed, and the power use change. ## Hardware, software, and firmware These three words come up constantly, and they mean different things. The differences matter, so we will be strict. **Hardware** is the physical machine. It is the chip you can hold in your hand, the wires inside your laptop, the screen, the keyboard, the speakers. Hardware is what breaks if you drop it. Once it leaves the factory, its behaviour is fixed: a chip does whatever its transistors and wires tell it to do, and you cannot change that without physically replacing the chip. **Software** is a list of instructions, written in some language, stored as data. A web browser is software. The operating system on your phone is software. The compiler a programmer uses to translate code into machine instructions is software. Software's defining property is that it can be replaced without rebuilding the hardware. You install a new version of an app; the silicon underneath does not care. **Firmware** sits between the two. It is software, in the sense that it is a list of instructions stored as data, but it ships with the hardware and the user usually never thinks about it. The bit of code that runs the moment you press the power button on your laptop is firmware. The little processor inside an SSD has firmware that decides where on the flash chips to put your files. Sometimes the manufacturer pushes a firmware update — when your wireless headphones get a "firmware update" notification, that is what is happening — but mostly it just sits there, doing its job invisibly. Take a phone as a concrete example. The metal, glass, transistors, screen, and battery are all hardware. The operating system (iOS or Android), the apps, the keyboard you type with, the camera app — all software. The bit of code that boots the phone before the operating system loads, the controller code inside the camera module, the radio firmware that runs the cellular antenna — all firmware. The phone is one device, but it has all three layers, and each layer has different rules about who is allowed to change it and how often. Why does this distinction matter? Because the cost and consequence of a change is very different at each layer. Replacing hardware means buying a new device. Replacing firmware usually means a special update process and a reboot. Replacing software is usually as easy as opening the app store. When something is wrong, knowing which layer to look at saves you days of guessing. ## The stored-program idea We now come to one of the most important ideas in computing — important enough that almost every later article in this series builds on it. Here is the idea: in a modern computer, the program and the data live in the same memory. The CPU reads the program out of memory one instruction at a time, just as it would read any other piece of data. That is so obvious to anyone who has used a computer that it deserves a moment of patience. In the 1940s it was not obvious. The first electronic computers did not store their programs at all — programs *were* the configuration of the hardware itself. ENIAC, the famous 1945 American electronic computer, was programmed by physically rerouting cables and toggling switches across a wall of panels. To run a different program, you rewired the machine. It took hours. Some of the very first programmers in history — Kay McNulty, Jean Jennings, Marlyn Wescoff, Frances Bilas, Ruth Lichterman, and Betty Snyder — spent their days literally moving wires. In 1945, John von Neumann wrote a report describing a different idea : store the program in memory, the same memory that holds the data, and have the machine read it one step at a time. To run a different program, just write a different sequence of bits into memory. No rewiring. Mechanically, the machine works like . Inside the CPU is a small storage location called the **program counter**, written *PC*. The PC always holds the address of the next instruction the CPU should read. The CPU then sits in a loop: 1. Look at what address the PC is pointing to. 2. Read the bits at that address out of memory. 3. Treat those bits as an instruction; do what it says. 4. Update the PC to point to the next instruction. 5. Go back to step 1. ```tikz caption="The stored-program (von Neumann) machine. The CPU's program counter (PC) holds the address of the next instruction to fetch — the highlighted cell. Both instructions and data live in the same memory; the CPU decides which is which by what it does with the bits, not by anything in the bits themselves." id="fig:stored-program" \definecolor{cardbg}{HTML}{0E2545} \definecolor{cardborder}{HTML}{2D76FF} \definecolor{accentborder}{HTML}{00C7FD} \definecolor{cellbg}{HTML}{0C2A4A} \definecolor{highlightbg}{HTML}{1A3E72} \definecolor{labeltext}{HTML}{E6EDF7} \definecolor{muted}{HTML}{8FA3C0} \begin{tikzpicture}[ >=Stealth, font=\sffamily, cpu/.style={rectangle, rounded corners=3pt, draw=cardborder, line width=0.7pt, fill=cardbg, text=labeltext, minimum width=2.8cm, minimum height=2.5cm, align=center}, cell/.style={rectangle, draw=accentborder, line width=0.5pt, fill=cellbg, text=labeltext, minimum width=1.8cm, minimum height=0.55cm, font=\footnotesize\ttfamily, outer sep=0pt, inner sep=2pt}, cellh/.style={rectangle, draw=accentborder, line width=0.9pt, fill=highlightbg, text=labeltext, minimum width=1.8cm, minimum height=0.55cm, font=\footnotesize\ttfamily, outer sep=0pt, inner sep=2pt}, arr/.style={->, line width=0.7pt, draw=labeltext}, arrbi/.style={<->, line width=0.7pt, draw=labeltext}, addrlabel/.style={font=\scriptsize\ttfamily, text=muted} ] \node (cpu) [cpu] {\textbf{CPU}\\[4pt]\footnotesize PC \quad Registers\\\footnotesize ALU \quad Control}; \node (c0) [cell, right=2.4cm of cpu, yshift=0.825cm] {instr}; \node (c1) [cellh, below=0pt of c0] {instr}; \node (c2) [cell, below=0pt of c1] {data}; \node (c3) [cell, below=0pt of c2] {data}; \node[font=\bfseries, text=labeltext, above=3pt of c0] {Memory}; \node[addrlabel, right=4pt of c0] {addr 0}; \node[addrlabel, right=4pt of c1] {addr 1}; \node[addrlabel, right=4pt of c2] {addr 2}; \node[addrlabel, right=4pt of c3] {addr 3}; \draw [arr] (cpu.east|-c1) -- node[above, midway, font=\scriptsize, text=labeltext] {fetch (PC)} (c1.west); \draw [arrbi] (cpu.east|-c3) -- node[below, midway, font=\scriptsize, text=labeltext] {load / store} (c3.west); \end{tikzpicture} ``` We can write one step of this loop more compactly in math. Let $\mathrm{PC}$ stand for the program counter and $M$ for the contents of memory. Then one step of the machine is the transition $$ (\mathrm{PC},\, M) \;\longrightarrow\; (\mathrm{PC}',\, M'). $$ The pair on the left is the state of the machine *before* the step: a program counter and a memory. The long arrow $\longrightarrow$ means "becomes, after one step". The pair on the right is the state *after* the step: a new program counter ($\mathrm{PC}'$) and a possibly updated memory ($M'$). The primes are just naming convention for "the new value of". What actually happens during one step? The CPU reads the instruction stored at address $\mathrm{PC}$ inside $M$, carries it out (which can change some bits inside $M$), and updates $\mathrm{PC}$ to point at the next instruction — usually $\mathrm{PC} + 1$, except when the instruction is a branch or a jump, in which case $\mathrm{PC}'$ can be anywhere. Repeat that transition billions of times a second and you have a running program. This loop, called *fetch–decode–execute*, is what every CPU on Earth is doing right now. Three things follow from putting programs and data in the same memory. **Programming becomes loading.** To run a different program, you just write its bits into memory and set the PC to the program's first instruction. No rewiring. The compile–link–load process described later in this article is the modern form of that idea. This is also what makes a computer *general-purpose*: the same chip can run a calculator, an operating system, a compiler, a web browser, and a game, just by feeding it different bytes. By contrast, *fixed-function* hardware — the chip in a microwave, the part of a phone that decodes video — is fast and cheap exactly because it has given up that flexibility. We will come back to this tradeoff often. **Programs can be data.** A compiler is a program whose input is another program (in a high-level language) and whose output is a third program (in machine code). A debugger is a program that inspects another running program. None of that would even make sense if instructions and data lived in different worlds. **Instructions can be modified, accidentally or on purpose.** This is the part working engineers spend their careers on. Because the bits of a program look just like any other bits in memory, a malicious or buggy piece of input can sometimes cause the machine to start executing the wrong bits as if they were instructions. Most of the security mechanisms in modern hardware — page protections, control-flow integrity, pointer authentication — exist to claw back some of the safety we lost when we accepted the stored-program idea. The flexibility was worth the cost, but the cost is real. The stored-program idea is the source of almost every flexible feature of modern software *and* almost every memory-corruption vulnerability. Later articles in the series will revisit this tradeoff under different names, but it is the same tension every time. When this series later talks about "code" versus "data", remember that the distinction is not in the bits themselves. It is enforced by hardware and software conventions. The CPU treats bits as an instruction when the PC points at them, and as data otherwise. That is the entire difference. ## Architecture, organization, and micro-architecture These three terms come up constantly in the rest of the series, and they are not interchangeable. A short detour through them now will save a lot of confusion later. **Architecture** is the contract between a CPU and the software that runs on it. It says what instructions exist, what each one does, what the programmer can see (registers, status flags, and so on), how memory is addressed, and how the machine handles unexpected events like errors and interrupts. The architecture is what a programmer writing in machine code or assembly language sees; everything else is hidden. The three architectures studied later in the series are *x86-64* (the chips Intel and AMD make for laptops, desktops, and servers), *ARM* (the chips inside almost every phone, and now many laptops too), and *RISC-V* (a newer open standard that anyone is free to use). **Organization** is the block-level description of how a *particular* CPU is built to follow that architecture. How big are the caches? How are the cores connected to memory? Are instructions and data fetched through the same path or different ones? Two CPUs with the same architecture can be organized very differently and still run exactly the same software. **Micro-architecture** is one level deeper still: the actual circuits and clock cycles that carry out each instruction. How many stages are in the instruction pipeline? How does the chip guess whether a branch will be taken? How are register names mapped to physical storage? Intel's Skylake and AMD's Zen 4 are both x86-64 chips — same architecture — but their micro-architectures are completely different inside. They run the same programs; they do not run them the same way. A useful analogy is building a house. - The **architecture** is the legal blueprint: how many rooms, where doors and walls go, what services (water, electricity, gas) the house has. - The **organization** is the contractor's plan: how the plumbing connects to the kitchen sink, where the wiring is routed, where the electrical panel sits. - The **micro-architecture** is the actual nails, screws, and pipe joints. How exactly is each connection made? Two contractors can build the same house from the same blueprint and end up with very different work hidden inside the walls. | Layer | Question it answers | Who needs to know? | Example | | --- | --- | --- | --- | | Architecture | What can a program do? | Compiler writers, OS authors, anyone writing assembly. | "ADD x1, x2, x3" is defined by the AArch64 manual. | | Organization | What blocks make up this CPU? | Performance engineers; sometimes ordinary programmers. | This chip has 8 cores, 64 KB of fast cache per core, and 16 MB of slower shared cache. | | Micro-architecture | How is each instruction actually carried out? | CPU designers, performance specialists. | This chip can execute six instructions per cycle and reads memory in 4 cycles when the data is in cache. | This separation is one of the most important ideas in modern computing. It is what lets Intel and AMD compete on the same software ecosystem: they agree on the architecture, and then race each other on organization and micro-architecture. Apple's switch from Intel chips to its own M-series chips in 2020 was a *change of architecture*; the operating system, the apps, and the developer tools all had to adapt. By contrast, every new Intel laptop chip is just a new micro-architecture: ordinary software does not even notice. The rest of this series follows the same hierarchy. The early articles cover organization and architecture in the abstract. After that come the micro-architecture articles. Then three case studies of x86-64, ARM, and RISC-V each revisit all three layers concretely. ## How a program actually runs The clearest way to understand what a computer does, before we have any of the formalism, is to follow a single program from your text editor down to the silicon. Take this small program written in C. C is a programming language; do not worry if you have not seen it before. The program adds the numbers 1 through 10 and prints the result, which is `55`. ```c #include int main(void) { int sum = 0; for (int i = 1; i <= 10; ++i) { sum += i; } printf("%d\n", sum); return 0; } ``` Save this in a file called `sum.c`. The path from this text file to the number `55` showing up on a terminal has five stages, and four different things along the way actually do work: a *compiler*, a *linker*, a *loader*, and the *CPU* itself. shows the whole pipeline. ```tikz caption="The lifecycle of a program. The first three stages are software services run on the host computer (compiler, linker, loader); the fourth is the CPU itself executing the loaded program. System calls hand control briefly to the operating system whenever the program needs to interact with the world outside it." id="fig:lifecycle" \definecolor{cardbg}{HTML}{0E2545} \definecolor{cardborder}{HTML}{2D76FF} \definecolor{accentbg}{HTML}{0A3859} \definecolor{accentborder}{HTML}{00C7FD} \definecolor{labeltext}{HTML}{E6EDF7} \begin{tikzpicture}[ >=Stealth, stage/.style={rectangle, rounded corners, draw=cardborder, line width=1.2pt, fill=cardbg, text=labeltext, minimum width=2.1cm, minimum height=1.2cm, align=center, font=\small}, final/.style={rectangle, rounded corners, draw=accentborder, line width=1.2pt, fill=accentbg, text=labeltext, minimum width=2.1cm, minimum height=1.2cm, align=center, font=\small}, arr/.style={->, line width=1.1pt, draw=labeltext}, lab/.style={text=labeltext, font=\footnotesize\itshape} ] \node (src) [stage] {\texttt{sum.c}\\source}; \node (obj) [stage, right=1.5cm of src] {\texttt{sum.o}\\object}; \node (exe) [stage, right=1.5cm of obj] {\texttt{sum}\\executable}; \node (proc) [stage, right=1.5cm of exe] {process\\image}; \node (cpu) [final, right=1.5cm of proc] {CPU\\execution}; \draw [arr] (src) -- node[lab, above]{compile} (obj); \draw [arr] (obj) -- node[lab, above]{link} (exe); \draw [arr] (exe) -- node[lab, above]{load} (proc); \draw [arr] (proc) -- node[lab, above]{run} (cpu); \end{tikzpicture} ``` **1. Compilation** turns the C text into instructions a chip can actually execute. A program called the *compiler* (often `clang` on Macs and `gcc` on most Linux systems) reads `sum.c`, checks that it is well-formed C, and translates it into the kind of low-level instructions a CPU understands. The result is a file with the extension `.o` — short for *object file* — that contains the compiled machine code, plus a few loose ends. (For example, the compiler does not yet know where the function `printf` lives in memory; that has to wait for the next stage.) **2. Linking** ties the loose ends together. A program called the *linker* takes all the object files for your program (here, just one) plus any libraries the program depends on (here, the C standard library, which provides `printf`), and stitches them into a single executable file. After this step, every reference inside the program knows exactly where to go. The executable is still just a file on disk; nothing has actually run yet. **3. Loading** copies the executable into memory and gets the CPU ready to execute it. When you type `./sum` at the command line, the operating system reads the executable, sets up a fresh region of memory for the program, copies the instructions and data into it, and arranges for the CPU's program counter (the PC from earlier) to point at the program's first instruction. **4. Execution** is the part the rest of this series is about. The CPU now sits in its fetch–decode–execute loop on the program's instructions. Modern CPUs are extraordinarily good at this: they actually carry out many instructions in parallel, they look ahead and guess what is coming next, and they do all of this so quickly that a loop of ten additions like the one above finishes in well under a hundred nanoseconds. Most of those nanoseconds are spent waiting for memory, not actually computing. The micro-architecture articles later in the series will explain why. **5. System calls.** When the program eventually wants to interact with the world — in this case, to print `55` on the screen — it cannot do that on its own. The CPU executes a special instruction that hands control over to the operating system. The OS, running with more privileges than ordinary user code, does the actual printing on the program's behalf and then returns control. From the program's point of view, it is just a function call; under the hood, a great deal more has happened. A later article on exceptions and traps takes the trap mechanism apart in detail; for now it is enough to know that the boundary between user code and operating-system code is enforced by the hardware itself, not by trust. That is the lifecycle in one breath: write the code, compile it, link it, load it, run it, and talk to the operating system whenever you need something from the outside world. Most of the rest of this series is about stage four — the CPU actually running the instructions — but every other stage will come up again as we need it. ## Exercises These prompts are not graded and there are no answers at the back. Work them in your head, on a piece of paper, or in conversation with someone else. The goal is to make the ideas of this article your own. 1. A microwave's timer chip is a computer in the sense given in this article. Identify its inputs, its outputs, and at least one piece of state it has to keep while it is running. 2. A chess engine running on your laptop and the rule book a human follows when playing chess both describe the same game. One of them is an *algorithm*; the other is a *program*. Which is which, and why? 3. Your laptop boots up, you launch a browser, you scroll a web page. For each of those three actions, which of hardware, software, and firmware was at work? You may decide that more than one was running at the same time. 4. Suppose you had a computer whose memory could hold only data, never instructions — the instructions were hard-wired into the chip itself, the way ENIAC's were. Name two ordinary things you do today on a phone or laptop that would no longer be possible. 5. Two CPUs implement the same architecture (say, x86-64) but have very different micro-architectures. They run the same compiled program correctly. Name three things that might differ between them, and explain how a programmer would notice the difference. 6. Walk through what has to happen between the moment you press Enter on `./sum` and the moment `55` appears on the screen. You do not need to list every detail — just name the four agents (compiler, linker, loader, CPU) plus one system call, and say when each does its work. ## What comes next The next article in the series, *Number Systems and Data Representation*, is about what the bits actually mean. What is the difference between unsigned and signed integers? How do computers represent text and other non-numeric data? What is alignment? You need that vocabulary before instructions like `add` or `compare` can carry any precise meaning. After that, articles on Boolean logic and digital design build up the gates, latches, and registers that make up a CPU's circuits. With that foundation in place we can talk about instruction sets in detail, and from there we move on to memory systems, micro-architecture, and the case studies of x86-64, ARM, and RISC-V. Read the series in order if this is new ground. If the foundations are already familiar, you can skim ahead — but expect later articles to refer back to ideas first introduced here.

Computer Architecture