The machine underneath your program

Chapter 01

How machines hold a number

A computer never stores a number, a letter, or a color, only patterns of 1s and 0s, and it is the code reading those bits back that decides what they mean.

Counting in binary

A bit is a single 1 or 0. Put several bits in a row and you get unsigned binary, plain place-value counting in base 2 instead of base 10. Each position is worth double the one to its right: 1, 2, 4, 8, 16, and so on. To read a bit pattern as a number, add up the weight of every position that holds a 1.

1011 (binary) = 1x8 + 0x4 + 1x2 + 1x1 = 11 (decimal)

With 8 bits you can make 256 different patterns, so an 8-bit unsigned value covers 0 through 255. Add a bit and the count of patterns doubles, that is the only rule you need: n bits give 2^n distinct values.

Hex, bytes, and words

Two's complement: how negative numbers work

Unsigned binary has no minus sign, so negative numbers need a convention. The one every mainstream CPU uses is two's complement: to negate a number, flip every bit, then add 1.

 5  = 0000 0101
-5: flip bits -> 1111 1010
     add 1     -> 1111 1011

The top bit still works like a sign: 0 means non-negative, 1 means negative, but the value is not just "flip the sign bit," it is the whole flip-and-add-one dance. For 8 bits this gives a range of -128 to 127, one more negative value than positive, because 0 uses up one of the 128 patterns on the non-negative side.

Two engineers before two's complement tried sign-magnitude (a plain sign bit plus a magnitude) and ones' complement (just flip the bits, no add-1). Two's complement beat both for two concrete reasons. First, both of the older schemes have two different bit patterns for zero, +0 and -0, which wastes a value and forces every comparison to special-case it. Two's complement has exactly one zero. Second, and more important for the hardware: with two's complement, the same binary adder circuit produces the correct answer whether you treat the bits as unsigned or as signed. Subtraction becomes addition of a negated number, so the chip never needs to know, or care, which interpretation the programmer intended. That is one fewer circuit to design, test, and pay for in silicon.

Overflow

Overflow happens when the true result of an operation does not fit in the number of bits you have. An 8-bit unsigned adder computing 255 + 1 produces 0, because the 9th bit that would have made it 256 has nowhere to go and is simply dropped. An 8-bit signed adder computing 127 + 1 produces -128, for the same reason, the bit pattern wraps, but the wraparound point lands somewhere different because the top bit is now read as a sign.

Floating point in a hurry

IEEE-754 is the standard nearly every language uses to store numbers with a fractional part. A 32-bit float splits its bits into three fields: one sign bit, 8 exponent bits, and 23 mantissa bits (the significant digits). The value they encode is roughly sign times mantissa times 2 to the exponent, the same idea as scientific notation, just in binary.

Binary fractions can only represent exactly the numbers you get from adding up powers of two, like 1/2, 1/4, 1/8. Plain decimal fractions like 0.1 and 0.2 are not exact in binary any more than 1/3 is exact in decimal, so they get stored as the closest 23-bit approximation. Add two approximations together and the tiny rounding errors do not cancel out.

0.1 + 0.2 === 0.3   // false
0.1 + 0.2            // 0.30000000000000004

Chapter 02

From transistors to an ALU

Every add, compare, and bit-shift your CPU runs is a few million transistors wired to only ever answer yes or no.

The transistor as a switch

A transistor has three terminals. One of them, the gate, controls whether current can flow between the other two. Feed the gate a high voltage and the path conducts, that is a 1. Feed it a low voltage and the path is broken, that is a 0. That is the entire trick: a transistor is a switch with no moving parts, flipped by a voltage instead of a finger.

NAND: the only gate you need

Chain transistors into small groups and you get logic gates: AND, OR, NOT, and one that turns out to be special, NAND (not-and). NAND outputs 0 only when both inputs are 1, otherwise it outputs 1.

Half adder, then full adder

A half adder adds two single bits. XOR gives the sum bit (1 when exactly one input is 1), AND gives the carry bit (1 only when both inputs are 1).

A full adder adds three bits: two operand bits plus a carry-in from the position to the right. Build it from two half adders in series (the second one adds the carry-in into the first one's sum) plus an OR gate to combine the two carries. A full adder is what lets you chain positions together, one per bit, to add whole numbers instead of single digits.

Ripple carry vs carry lookahead

Chain 4 full adders together, bit 0's carry-out feeding bit 1's carry-in, and so on, and you get a 4-bit adder. That is called ripple carry: the carry has to physically propagate through every stage before the top bit's sum is correct. Bit 3 cannot know its answer until bit 2 has settled, which cannot know until bit 1 has settled, and so on down to bit 0.

Every gate takes a small but nonzero amount of time to produce a stable output after its inputs change, that is gate delay. The critical path of a circuit is the longest chain of gate delays that any output depends on, in a ripple-carry adder that is the full carry chain from bit 0 to the top bit. The clock cannot tick faster than the time it takes the critical path to settle, or the circuit will report an answer before the real one has arrived. That is the direct link between "how the carry moves" and "how fast the chip can run."

Carry lookahead is a way to shortcut the wait: extra logic computes, for every bit position, whether that position will generate a carry on its own or merely propagate one coming in, and combines those signals in parallel instead of waiting for each stage in turn. It trades more gates (more silicon, more power) for a shorter critical path, which is why fast adders in real CPUs use it instead of plain ripple carry.

The ALU: a bank of units and a mux

An ALU (arithmetic logic unit) does not pick one circuit per instruction, it runs every operation it supports, adder, AND, OR, XOR, shifter, on the same two inputs at the same time, all in parallel. A multiplexer (mux), a gate structure that selects one of several inputs based on a set of select bits, then picks which of those already-computed results to send to the output based on the opcode. The unused results are simply thrown away that cycle.

Chapter 03

Registers, shift registers and counters

A register is where a machine keeps a value between clock pulses, and everything past this point, the bus, the adder sharing, the whole control unit, is just registers wired together with the right terminal doing the right job on the right edge. This chapter is the parts list: what a register is, how a shift register moves bits, how a counter counts, and the multiplexer that shows up inside almost all of it.

What a register is

A register is a group of flip flops that together hold one binary word. Each flip flop holds one bit, so a 4-bit register is 4 flip flops storing 4 bits, and in general an n-bit register is n flip flops storing an n-bit word. The register's value is just whatever its flip flops currently hold, and that value only changes on a clock edge, never in between.

Register control terminals

Draw a register as a box and every one of these lines has to go somewhere: parallel inputs bring in a full word to load, parallel outputs read the current word back out, a Load control tells the register to capture the parallel inputs on the next edge, a Clear control resets every flip flop to 0, and CP is the clock pulse that makes any of it actually happen. Without an active edge on CP, none of the other controls do anything, they are just sitting there waiting.

Shift registers

A shift register adds two more terminals to a plain register: SI, the serial input, and SO, the serial output. On a shift right, every flip flop takes the value of its higher-order neighbor, the high-order bit position is left vacant and gets filled from SI, and the low-order bit that gets pushed out the other end appears at SO. Shift left runs the same idea in the other direction: SI fills the vacated low-order position, and the high-order bit that falls off appears at SO. A bidirectional shift register keeps a plain register's Load and Clear terminals and adds a Shift control plus a direction line, so one clock edge can load, clear, or shift either way, whichever control is armed for that pulse.

Counters

A counter is a register that can add 1 to its own value without going through the parallel inputs at all. Its terminals are outputs, Load, Clear, and a Count control that increments the register's own current value on the next edge, no parallel input involved. An n-bit counter can hold 2^n different values, 0 through 2^n minus 1, and asserting Count when the counter already holds the maximum value wraps it straight back to 0. There is no overflow terminal on the counter itself, the wraparound is just what the bits do.

The control terminal table

One terminal, one job. This is the table that pins down, for any micro-operation written on a register, which terminal actually does the work:

Multiplexers

Everything from here on shares one part underneath it: the multiplexer. A shared adder, a shared bus, a register that can load from two different sources, all of it is a mux. A multiplexer with n select lines chooses among 2^n inputs, only one of them ever reaching the output at a time. The smallest useful case is a 2x1 mux: one select line S, two data inputs I0 and I1, and the output follows whichever input S currently points at.

(nothing yet, arm a control and pulse CP)

Chapter 04

Register transfer and building the hardware

Everything a hardware question asks for comes down to the same three moves: name the transfer, decide which terminal does it, and wire the control function to that terminal. This chapter is register transfer notation, why a swap is not the same as making two registers equal, and a full worked example that turns a set of register transfer statements into an actual circuit, one adder, two multiplexers, and a handful of control gates.

Register transfer notation

R1 <- R2 means the content of R2 is copied into R1. R2 itself is unchanged, only R1 gets a new value. Most transfers are conditional, and the condition is written as a control function in front of the arrow: xT2: R1 <- R2 means this transfer happens only when x is 1 during timing signal T2, and nowhere else does this line do anything. Two micro-operations written on the same control function, separated by a comma, both happen on that same clock edge, in parallel, not one after the other.

The 3-step method

Every hardware question from here follows the same three steps, in this order:

1. Decide which devices the problem needs: plain registers, a counter, a shift register, an adder, whatever the micro-operations actually call for.
2. Decide which terminal on each device does each micro-operation: Load, Clear, Count, or Shift.
3. Connect the devices, then for every terminal, OR together the control function of every micro-operation that uses it. That sum is the terminal's control gate expression.

Worked example, one adder, three control functions

Using one adder, draw the hardware for
x1'x3: R2 <- R1, R3 <- R3 + 1, R4 <- 0
x1x2:  R2 <- R1 + R3, R4 <- shr R4
x1x2': R4 <- R1 + R2, R3 <- R2

Step 1, devices: 2 registers, R1 and R2, a counter R3, a shift register R4, one adder, and a control unit. The adder is shared by two of the three lines, so a 2x1 mux picks its second input, R3 for the x1x2 line or R2 for the x1x2' line, and a second 2x1 mux picks what actually loads into R2, R1 straight through for the x1'x3 line or the adder's output for the x1x2 line.

Step 2 and 3: terminal per register, then OR the control functions

R1 never appears on the left of an arrow anywhere in these three lines, it is only ever read. No terminal, no control gate, R1 just sits there as one of the adder's steady inputs.

Two lines load R2, none clear or shift it, so OR the two conditions:

Load(R2) = x1'x3 + x1x2

R3 gets one line on Count and one line on Load, each already a single term, nothing to OR together:

Count(R3) = x1'x3
Load(R3)  = x1x2'

R4 uses all three of its non-output terminals, one micro-operation each, so each control gate is just that one condition, confirmed on the board:

Clear(R4) = x1'x3
Shift(R4) = x1x2
Load(R4)  = x1x2'

The two muxes need a control gate too, one select line each instead of a register terminal. MUX A picks R3 when the x1x2 line is active and R2 when the x1x2' line is active. x1x2 has x2=1 and x1x2' has x2=0, so the whole condition collapses to one signal, select R2 whenever x2 is 0: S(MUX A) = x2'. MUX B picks the adder's output when x1x2 is active and R1 directly when x1'x3 is active. x1'x3 has x1=0 and x1x2 has x1=1, so S(MUX B) = x1', select R1 directly whenever x1 is 0.

Chapter 05

The memory unit

Every memory unit boils down to the same three pieces: an address register that says which word, a data register that carries the word in or out, and two control lines, Read and Write, that say which direction. Get the sizing rules for AR and DR right and the rest of this chapter is bookkeeping.

Structure: AR, DR, Read, Write

A memory unit is a collection of words. To use one word out of the collection, hardware needs to know two things: which word, and what to do with it. The Address Register (AR) holds which word. The Data Register (DR) holds the word itself, whatever is going in on a write or coming out on a read. Two control lines, Read and Write, say which of those two directions this access is.

Nothing in the memory unit can be addressed without going through AR first, and nothing can move in or out without passing through DR. That is the whole structure.

The two sizing rules

These two rules answer almost every sizing question this chapter asks. Given a word count, take log base 2 to get AR's width. Given a word size, that number is DR's width directly, no conversion needed. Multiply the two (words times bits per word) for total capacity.

Worked sizing examples

A 4-word memory is the smallest case worth checking by hand: 4 = 2^2, so AR is only 2 bits, enough for addresses 0, 1, 2, 3 and nothing else.

Read and write as micro-operations

Exam questions in this chapter give a register-transfer line and ask what the memory does with it. The method is always the same: work out whether AR is already loaded or needs loading first, then decide whether the transfer moves data into memory, a Write, or out of it, a Read.

The last one is the one people get wrong under time pressure. M[R5] <- M[R3] looks like a single move, but memory cannot talk to memory directly, everything routes through DR. Read the source first, AR <- R3 then DR <- M[AR], only then repoint AR at the destination and write DR back out, AR <- R5 then M[AR] <- DR. DR just sits there holding the value while AR is being reloaded in between, nothing else touches it.

Chapter 06

The bus, built from multiplexers

A bus is not a special piece of hardware, it is a set of shared lines plus a pile of multiplexers, one per bit, all steered by the same selection lines. Once you can count muxes and selection lines from a register count, the rest of this chapter is just reading the diagram.

What a bus is

An m-bit bus is m separate lines connecting 2^n registers, so that any one register can put its contents on the shared lines and any other register can take them off. Only one register drives the bus at a time.

Building an m-bit bus for 2^n registers

That is the exam answer, in full: count the bits in the bus, that is how many muxes to draw. Count the registers, that decides each mux's size and how many selection lines feed all of them at once. The same n selection lines drive every mux together, so all m muxes always pick the same register at the same time, and exactly one register's worth of bits appears on the bus.

Worked example: a 3-bit bus connecting 4 registers

Registers A, B, C, D, each 3 bits wide. m = 3, so 3 multiplexers. 2^n = 4, so n = 2 selection lines. Each mux is a 4-to-1 mux.

Worked example: a 2-bit bus connecting 8 registers

Same rule, different numbers. m = 2, so 2 multiplexers. 2^n = 8, so n = 3 selection lines. Each mux is an 8-to-1 mux.

A transfer over the bus

C <- A on the 4-register bus above: set S1 S0 = 00 to put A on the bus, and assert Load on C. Nothing else changes, every other register's Load stays off, so only C actually captures the value while it passes by.

Why buses matter

Without a shared bus, connecting every register directly to every other register needs a separate path for every pair, and that count explodes, on the order of r^2 wires for r registers, not r. A bus trades that away: only one transfer can happen per pulse, in exchange for one shared set of m lines that scales with r instead of r^2. That saved wiring is the entire reason the mux-based bus exists.

Chapter 07

Instruction formats and how wide each field must be

Mano's second chapter opens with three ideas the lecturer turns straight into exam questions: a program sitting in memory looks no different from the data next to it, an instruction word is built from an opcode field, a memory address field and a register field, each one sized by how many things it has to name, and every address field can either point straight at an operand or at a pointer to one. This chapter works through the sizing arithmetic and the direct versus indirect comparison exactly the way the board asks for them.

A program in memory

Memory holds 2^m words, so naming every one of them takes an m-bit address. A program is nothing more than a run of instruction words sitting in memory, usually starting at the low addresses, with its data operands placed wherever the programmer put them. No bit anywhere in a word says it is an instruction or says it is data, memory just holds patterns. The only thing that decides what gets executed next is the path the program counter walks through memory. Fetch the address of a data word by mistake and the machine will happily try to execute it.

The general instruction format

The format itself is simple: an instruction word is an opcode field, then a memory address field, then a register address field, laid out one after another. What the exam actually tests is how wide each field has to be, and that comes down to three rules.

For 2^n distinct instructions, the opcode field needs n bits, one pattern for every instruction.

For a memory of 2^m words, the memory address field needs m bits, one pattern for every address.

For 2^k registers, the register address field needs k bits, one pattern for every register.

Worked sizing examples

The same rule, applied to the numbers the exam actually hands out. All verified by working the power of two out in full.

4096 = 2^12 256K = 2^18 1M = 2^20 worth recognising on sight, they come up again and again.

The exam question from the sheet: a computer has memory 256K word x 32. 256K is 2^18, so the memory address field needs 18 bits, and each word is 32 bits wide. Spend 18 of those 32 bits on the address and 14 are left over for the opcode and any register field together.

Direct versus indirect addressing

The address field of a memory-reference instruction can be read two ways, controlled by a single bit, I. With I=0, addressing is direct: the address field holds the address of the operand itself, one memory read gets it. With I=1, addressing is indirect: the address field holds the address of a word that itself holds the operand's address, so it takes an extra memory read to get there.

The board's example: ADD 350, I=1. M[350] = 720, and M[720] holds the operand to add. Because I=1, the address field is not the operand's address, it is the address of a pointer. The machine reads M[350] first, gets 720, then reads M[720] to get the actual operand. The effective address, the address the operand actually sits at, is 720, not 350.

Mano's own numbers

Chapter 08

Micro-operations, step by step

Chapter 4 drew fetch, decode, execute, memory, writeback as five soft-edged boxes. Here they get pinned to a clock: a real machine, the basic computer from Mano's Computer System Architecture, ticking through named timing signals T0, T1, T2, one register transfer per pulse.

The registers on the board

Everything the basic computer does is a transfer between a small set of registers, all wired to one common data path. PC (12 bits) holds the address of the next instruction. AR (12 bits) is the address register, whatever memory cell is about to be read or written. IR (16 bits) holds the instruction currently being decoded. DR (16 bits) is the data register, a staging area for an operand fetched from memory. AC (16 bits) is the accumulator, where arithmetic and logic results land. E is a single carry bit sitting just outside AC(15), catching whatever overflows out of an add or a circular shift. SC, the sequence counter, is the register that makes this whole chapter possible: it counts 0, 1, 2, 3... and each value is a timing signal, T0, T1, T2, that pulses exactly one register transfer into existence. Three more one-bit flags, FGI, FGO and IEN, plus two 8-bit registers INPR and OUTR, handle input and output the same way.

Memory is 4096 words of 16 bits, so an address is 12 bits, written as three hex digits, 000 to FFF. A register transfer is the smallest thing that can happen on one clock pulse, one register's value copied, added, or shifted into another. A micro-operation is just the name for that one transfer, written the way it goes on the board: destination on the left, an arrow, source on the right.

The instruction word

Every instruction is one 16-bit word. Bit 15 is I, the indirect flag. Bits 14 to 12 are the opcode, three bits, eight possible patterns, decoded straight into eight signals D0 through D7, one active at a time. Bits 11 to 0 are the address field. For D0 through D6 that field is an address in memory. For D7 it is not an address at all, each of its 12 bits picks out one register-reference or input-output operation, only one bit is ever set.

Fetch and decode: the first three pulses, always

Every instruction, no matter which one, starts the same way. T0 copies PC into AR, aiming the next read at the current instruction. T1 reads that word into IR and, in the same pulse, advances PC to the following instruction, so the return address is already correct before the current instruction has even been decoded. T2 splits IR apart: the opcode bits pick D0-D7, the low 12 bits move into AR as a candidate address, and I is latched from bit 15. Nothing here depends on which instruction it is, D isn't even known until T2 finishes.

What happens at T3 is the first fork. If the opcode is D0-D6, a memory-reference instruction, T3 checks I. When I = 1 the address field is not the final address, it points at a memory cell that holds the real one, so T3 does one extra read, AR <- M[AR], to chase that pointer down to the effective address. When I = 0, AR already holds the effective address, and T3 does nothing at all. If the opcode is D7, there is no address to resolve, T3 is where the instruction actually executes, register-reference if I = 0, input-output if I = 1, and SC is reset to 0 in that same pulse.

Three families, one branch at T2

D0 through D6 are the seven memory-reference instructions, AND, ADD, LDA, STA, BUN, BSA, ISZ, each finishing its own execute states after T3, DR <- M[AR] for the ones that need an operand, then the actual add, load, store, or branch. D7 with I = 0 is the twelve register-reference instructions, CLA, CLE, CMA, CME, CIR, CIL, INC, SPA, SNA, SZA, SZE, HLT, none of them touch memory, each is a single bit in IR(0-11) decoded into one register transfer at T3. D7 with I = 1 is the six input-output instructions, INP, OUT, SKI, SKO, ION, IOF, same shape, also done in one shot at T3.

Trace it yourself

The tracer below runs the exact engine described above, one T state per press of Step. Pick any of the 25 instructions from the preset list, direct or indirect, or hand-edit PC, AC, E and memory yourself. It starts loaded with the worked indirect ADD from the board: PC = 020, AC = 7EC3, M[020] = 932E, M[32E] = 09AC, M[9AC] = 8B9F.

Mano basic computer, every instruction traced

The basic computer has 25 instructions in three families: 7 memory-reference instructions (opcode in D0-D6), 12 register-reference instructions (opcode D7 with I=0), and 6 input/output instructions (opcode D7 with I=1). Every instruction starts with the same fetch and decode, shown once below, then branches into its own execute states. Each trace below has two columns for every T state: the symbolic micro-operation as the book writes it, and the same line with the actual hex values from that example substituted in, so you can see the register transfer happen, not just describe it.

SC is the sequence counter that drives T0, T1, T2... forward. Every instruction below ends by writing SC <- 0, which is what sends control back to T0 for the next fetch. HLT is the one exception: it clears the start-stop flip-flop instead, so SC never gets the chance to restart.

The 7 memory-reference instructions, full traces

Each of these needs an operand or a target address in memory, which is why they go through T3 and T4 (and sometimes T5, T6). The address in the instruction word is only the final address when I = 0. When I = 1, that address instead points at a memory cell holding the real address, so T3 does one extra fetch to chase the pointer, that is the indirect trace below under ADD.

The 12 register-reference instructions

None of these touch memory. Each one is a single control bit in IR(0-11) decoded straight into a register transfer, so they all execute in one shot at T3 and then set SC <- 0.

The four skip instructions all follow the same shape, test a condition on AC or E, and if it holds, add one more increment to PC on top of the one T1 already did during fetch, so the instruction right after the skip is jumped over.

The 6 input/output instructions

These use opcode D7 like the register-reference group, but with I = 1, and they also execute in one shot at T3. They talk to two 1-bit flags: FGI goes to 1 when a character has arrived in INPR and is waiting to be read, FGO goes to 1 when OUTR is free and ready to accept the next character. A program never assumes the device is ready, it polls SKI (or SKO) first and only issues INP (or OUT) once the flag confirms it, otherwise it would read a stale character or overwrite one the device hasn't taken yet.

Chapter 09

The control unit and the common bus

Every register transfer in the basic computer, AR <- PC, DR <- M[AR], AC <- DR, and every other one, is driven by exactly one thing: a control signal that is high for exactly one clock pulse, built by ANDing a decoded opcode with a decoded timing state. This chapter is how that AND-OR machinery gets built, and how one 16-bit bus carries every one of those transfers.

The registers this chapter moves data between

Nothing new here, just the full list in one place, since every example below names one of these.

From instruction word to control signal

Once IR holds the current instruction, three things happen to it at once. IR bit 15 loads straight into the I flip-flop, the indirect bit. IR bits 12 through 14, the opcode, feed a 3x8 decoder that produces eight lines, D0 through D7, one per opcode value. IR bits 0 through 11 are the address field, and they go straight to the control logic as is, no decoding needed, since the address is used directly rather than tested against fixed values.

A decoder is a circuit with a fixed rule: for any binary number on its input, exactly one output line goes high, all the rest stay low. That is the whole reason this design works. Feed the 3x8 decoder a 3-bit opcode and exactly one of D0..D7 is high. Feed a 4x16 decoder a 4-bit number and exactly one of T0..T15 is high. Since D0..D7 and T0..T15 are each guaranteed one-hot, ANDing one specific D with one specific T, a term like D5T4, is true at exactly one instant across the entire run of the machine: the one clock pulse where the current instruction is D5 and the current timing state is T4. That is why a control condition is written as a product of signals like this, and why building a control line is just OR-ing a handful of these products together, a sum of products, one product per micro-operation that needs to fire.

The sequence counter, SC, is a 4-bit counter feeding its own 4x16 decoder to make T0 through T15. SC increments by 1 on every clock pulse by default, which is what walks the timing signal forward, T0, T1, T2, and so on. The micro-operation SC <- 0 is a clear, not an increment, and it is itself one of the control signals the logic below emits. Almost every instruction ends by asserting it, which snaps SC back to 0 so the very next clock pulse lands on T0 again, the start of fetching the next instruction. HLT is the one exception: it clears the run flip-flop instead, so the clock stops advancing SC at all.

The common bus: one line, seven drivers

The whole machine shares one 16-bit path, the common bus. At any instant at most one unit is allowed to put a value on it, chosen by a 3-bit code, S2 S1 S0. Every register also has three control inputs of its own: LD loads whatever is currently on the bus, INR increments the register's own current value by 1, and CLR resets it to 0. INR and CLR never touch the bus at all, they just tell the register to update itself from its own held value, that is why they only need the register's own enable line, not a bus selection.

Reading a register transfer as bus traffic is just naming these three facts every time: who drives the bus, what S2S1S0 that means, and which control input on the destination fires. AR <- PC means set S2S1S0 = 010 so PC drives the bus, and assert LD(AR) so AR captures it on the clock edge. Nothing more happens on that pulse, PC's own value is untouched, only AR changes.

The S bits themselves come from a small encoder, not a hand-picked table. Give it seven inputs, x1 through x7, one per source, with exactly one allowed high at a time, and it produces: S0 = x1 + x3 + x5 + x7, S1 = x2 + x3 + x6 + x7, S2 = x4 + x5 + x6 + x7. Set x2 (PC) high and everything else low: S0 = 0, S1 = 1, S2 = 0, which is 010. That is the whole trick, S2S1S0 is just the binary number of whichever xN is currently 1, computed by three OR gates instead of a lookup table.

Reading a transfer as bus traffic, worked examples

IR <- M[AR]: Memory is the source, so S2S1S0 = 111. That asserts LD(IR), and AR is already holding the address (PC was copied into it one T state earlier), so this is the fetch, reading the instruction word out of memory and into IR.

M[AR] <- AC: AC is the source now, S2S1S0 = 100. But the destination is memory, which has no LD, only a write strobe, and memory's address input is hardwired to AR, not selected by S2S1S0. So this pulse is: AC's value goes out onto the bus, memory's write line fires, and the address it writes to is whatever AR already holds, all in the same clock pulse. This is STA.

AR <- AR + 1: no unit is selected, S2S1S0 = 000, "nothing" is on the bus, because this is an increment, not a load. AR just adds 1 to its own current value and INR(AR) is the only signal that fires. The bus plays no part at all. This is the AR increment inside BSA.

Deriving control gates: the method

Every register on the bus needs three control expressions built for it, LD, CLR, and INR. The method is the same every time: go through the entire instruction set, write down every single micro-operation that loads that register, and OR their control conditions together, that sum is LD for that register. Do the same separately for every micro-operation that clears it, that sum is CLR, and again for every one that increments it, that sum is INR. There is no cleverness beyond collecting the list correctly and OR-ing it.

LD(AR)  = R'T0 + R'T2 + D7'IT3
CLR(AR) = RT0
INR(AR) = D5T4

LD(PC)  = D4T4 + D5T5
CLR(PC) = RT1
INR(PC) = R'T1 + RT2

LD(AC)  = D2T5
CLR(AC) = D7I'T3B11
INR(AC) = D7I'T3B5

The interrupt cycle, for completeness

When R = 1, the machine is not fetching and executing the next instruction, it is running the interrupt cycle instead, using the same T0, T1, T2 timing states for a completely different purpose.

This parks the interrupted program's return address (PC, saved into TR then written to memory location 0) and sends PC to address 1, where the interrupt service routine starts. IEN <- 0 stops the machine from interrupting itself again mid-service, and R <- 0 at RT2 is what hands control back to the normal R'T0 fetch on the very next pulse.

Chapter 10

Programming the basic computer

The instruction set only matters once you can write a program with it. This chapter turns the opcode table into working code: an assembly source file, an assembler that turns it into hex, and a method for tracing that hex by hand, register by register, the way it gets checked on the board.

The instruction word

Every word the machine fetches as an instruction has the same shape: bit 15 is the indirect bit I, bits 14 to 12 are the opcode, and bits 11 to 0 are a 12-bit address, which is why every address in this machine is written as 3 hex digits.

A worked decode, the kind an exam gives you cold: M[21] = A222. Split the top hex digit into bits, A = 1010, so I=1 and opcode=010=D2. D2 is LDA. So A222 is an indirect LDA through address 222, not LDA of 222 itself. The effective address is whatever is stored at location 222, not 222.

7 memory-reference 12 register-reference 6 input-output for 25 instructions total. Keep this table open while reading hex.

From assembly source to machine code

The path is source, assembler, binary. You write mnemonics and labels, the assembler turns each line into one 16-bit word, and the machine only ever sees the words. The assembler does this in two passes over the same source.

Pass one walks the source top to bottom, keeping a running address called the location counter. It does not emit any code yet, it just watches for labels, a name written with a trailing comma at the start of a line, and records each one in a symbol table as label to address. Pass two walks the source again, and this time it emits a word for every instruction and every DEC or HEX, looking up any label it meets in the symbol table built in pass one. That is why a label can be used before it is defined, LDA can reference a data word three lines further down, because by the time pass two runs, pass one already knows where everything landed.

Program structure

The convention the source always follows: ORG N to set the starting address, then the instructions, then HLT, then the data words with their DEC or HEX labels, then END.

The 4 pseudo-instructions

Worked example: F = A + B

Load A, add B, store the sum in F, stop. The line-by-line source next to the hex it assembles to:

LDA A and STA F assemble with direct addresses 104 and 106 because A and B are labels the symbol table already resolved by the time pass two ran. Result: F = 30.

Worked example: F = A - B

The machine has no subtract instruction, so subtraction is done as addition: A minus B is the same value as A plus the two's complement of B. Complementing every bit of B and adding 1 turns it into -B, so CMA then INC then ADD A computes A + (-B).

With A=50 and B=18: result F = 32.

Writing a loop

ISZ is what makes a loop possible without an extra compare instruction: it increments a memory word and skips the next instruction only if that word becomes 0. Set a counter to -(count), ISZ it once per pass, and the skip fires exactly when the counter reaches 0, right after the loop has run count times. BUN at the bottom sends control back to the top for every pass except the last.

This program sums a small array using that technique, and also uses ISZ a second time to walk a pointer through the array, since this machine has no indexed addressing.

PTR starts pointing at NUM1 and is incremented by ISZ PTR every pass, so ADD PTR I reads a different array element each time through. CTR starts at -3 and reaches 0 after three passes, which is the pass where the skip finally fires and BUN LOP gets skipped. Result: SUM = 5 + 15 + 20 = 40.

Hand-tracing a program

The exam version of tracing is a table: one row per instruction executed, PC before the fetch, the instruction in hex and mnemonic, AC and E after it runs, and a note if it wrote memory. Tracing F = A + B from AC=0000, E=0:

Two isolated instruction traces, the kind used to check a single register-reference or memory-reference instruction in isolation:

Try it: two-pass assembler

Try it: program tracer

Chapter 11

The instruction set is the contract

Software never touches a transistor directly, it only ever touches a fixed list of instructions the hardware promises to run, and that list is the entire deal between the two sides.

The line between hardware and software

The instruction set architecture, or ISA, is the list of instructions a processor understands, plus the rules for how they are encoded, what registers exist, and how memory is addressed. It is a contract, the chip promises every instruction on the list will do exactly what it says, and in exchange the software never has to know whether it is running on a cheap embedded core or a fast server core, as long as both implement the same ISA. A program compiled for RISC-V runs unmodified on either one, because both honor the same contract underneath very different circuitry.

Two philosophies: RISC and CISC

RISC (reduced instruction set computer) keeps every instruction simple and the same fixed size, and only load and store instructions touch memory, everything else works on registers. CISC (complex instruction set computer) allows instructions of varying length that can read and write memory directly as part of an arithmetic operation. RISC-V and ARM are RISC, x86 is CISC.

add x1, x2, x3

add eax, ebx

Neither approach is free. CISC packs more work into one instruction, so a compiled program can be smaller, but the chip needs extra circuitry to handle instructions of different lengths and memory-touching arithmetic. RISC keeps every instruction the same size and shape, which makes the hardware that fetches and decodes them simpler and faster to build, at the cost of needing more instructions to do the same job.

Anatomy of an encoded instruction

An instruction is not text, it is a 32-bit number. The bits are split into fields, and which field means what depends on the instruction's format. This is the R-type format, used by register-to-register instructions like add, shown with the real bits for add x1, x2, x3:

Addressing modes

An addressing mode is a rule for where an instruction's data comes from. RISC-V keeps the list short:

x86 adds several more, including register-indirect and scaled index, base plus index times 1, 2, 4, or 8, for stepping through arrays. Every addressing mode adds address-calculation logic that every instruction pays for in chip area and delay, whether it uses that mode or not, which is why RISC-V deliberately stops at these four.

Registers versus memory

A register is a storage slot built directly into the processor. RISC-V has 32 of them, and reading or writing one takes a fraction of a clock cycle. Memory sits off to the side, is enormously larger, and takes many cycles to reach. That is why every arithmetic instruction works on registers only, and why loading a value from memory, doing the math, then storing the result back, is a distinct, deliberate step rather than something arithmetic ever does for free.

Registers stay few on purpose. Every register number an instruction names has to fit inside the instruction's fixed 32 bits, RISC-V spends 5 bits per register field, and 5 bits counts exactly 32 values, doubling to 64 registers would cost another bit on every field of every instruction that names a register. More registers also means more wiring, the register file needs a physical read or write connection for every register it can touch in one cycle, and that circuitry still has to finish inside a single clock tick. A handful of fast registers, backed by a large, slower main memory, is the right trade, because most values a program is actively working with fit in a handful of variables at any one time anyway.

What the assembler and the compiler each do

A compiler turns source code in a language like C into assembly, or directly into machine code. Along the way it decides which instructions to use and which values live in which registers, and it can reorder or eliminate work while preserving the program's behavior. An assembler takes assembly, the human-readable mnemonics like addi and beq, and translates each line into its exact 32-bit encoding, turning labels like loop into real addresses. Compiling is a many-to-many translation full of judgment calls, assembling is close to a one-to-one lookup.

A small C function, and roughly what an unoptimized compiler produces for it:

int sum_to(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++) {
        s += i;
    }
    return s;
}

sum_to:
    addi t0, x0, 0     # s = 0
    addi t1, x0, 1     # i = 1
loop:
    blt  a0, t1, done  # if n < i, exit loop
    add  t0, t0, t1    # s += i
    addi t1, t1, 1     # i++
    beq  x0, x0, loop  # repeat
done:
    add  a0, t0, x0    # return s
    ret

a0 holds the argument n, and later the return value, by RISC-V's calling convention. This is close to what an unoptimized compiler emits, a real optimizing compiler might keep s and i in different registers, unroll part of the loop, or, for a simple case like this one, work out the closed-form answer and skip the loop entirely.

Chapter 12

One instruction, one trip through the machine

Every instruction a processor runs takes the same five-step trip through the same physical hardware, once per clock tick.

Five stages, one instruction

A single-cycle processor runs every instruction through the same five steps, in the same clock cycle:

In a single-cycle design, all five steps for one instruction finish inside one clock tick, then the next instruction starts its own five steps from scratch. Nothing overlaps.

The datapath: the wiring that makes it happen

The datapath is the physical hardware the five stages run on, the PC (a register holding the address of the current instruction), instruction memory, the register file, the ALU, and data memory, all connected by wires. Because the same wires carry every instruction, whether it is an add or a load, some of them need to carry one signal or another depending on what is running. That is what a mux, short for multiplexer, is for, a switch that picks one of several input wires to pass through, based on a control signal.

Watching one instruction cross the datapath

The diagram below draws the same five stages as hardware blocks and wires. Step through it and watch which parts light up and why, then check the six control signals underneath, they are what tell the muxes which input to pass through for this particular instruction.

The control unit is a lookup table

The control unit does not compute anything, it looks up the opcode bits from the fetched instruction and outputs a fixed set of control signals, wires holding a 0 or a 1, connected straight into the muxes and into the enable pins of data memory and the register file. Six signals decide almost everything in this datapath:

For six opcodes, the whole control unit is a six-row table, opcode in, six bits out, no arithmetic involved. add and sub are 1,0,0,0,0,0. addi is 1,1,0,0,0,0. lw is 1,1,1,0,1,0. sw is 0,1,0,1,0,0. beq is 0,0,0,0,0,1. The table above the diagram shows the live row for whatever instruction the walkthrough is on.

The clock, and why the slowest instruction sets the pace

Every block in the datapath takes real time to produce an answer, a register file read takes some fraction of a nanosecond, an ALU add takes a bit more, a data memory access takes more still. In a single-cycle design, the clock period, the length of one tick, has to be long enough for the slowest instruction to finish its entire trip through fetch, register read, ALU, memory access, and writeback, all in series. That is normally lw, since it is the only instruction that uses every stage for real work. Every other instruction, including one that never touches memory, like add, still has to wait out the same fixed clock period, because the clock ticks at one fixed rate for the whole chip. A single-cycle processor is simple to build and simple to reason about, and it wastes most of a clock cycle on every instruction that is not the slowest one.

Chapter 13

The memory hierarchy

No single kind of memory is both fast and big enough, so every real computer fakes it with a hierarchy, and how well your code respects that hierarchy can change its speed by an order of magnitude.

The gap

Registers are tiny (a few dozen to a few hundred) and about as fast as the CPU itself. Below that sit caches, usually three levels, each bigger and slower than the last: L1 (smallest, fastest, often per core), L2 (bigger, a bit slower), and L3 (bigger still, shared across cores). Below the caches is DRAM, the main memory, gigabytes in size but far slower than any cache. Below that is an SSD, terabytes in size but far slower again. Every step down trades speed for capacity, by a lot.

The numbers below are approximate, real hardware varies by chip and generation, but the order of magnitude is stable and worth knowing. The last column rescales everything to human time by pretending a register access takes one second.

Why locality saves you

Caches only help because real programs are not random. Temporal locality is reusing the same data again soon, like a loop counter touched every iteration. Spatial locality is using data that sits near data you just used, like walking through an array. Caches exploit spatial locality by never fetching a single word alone, they fetch a whole cache line, a contiguous chunk of memory, usually 64 bytes on a modern chip. Touch one word and its neighbors come along for free, ready for when you need them a few instructions later.

Where a line can live: direct-mapped, set-associative, fully associative

Given an address, the cache needs to know where to look for it, and how much freedom it has to place it there. In a direct-mapped cache, every address maps to exactly one line, decided by a few bits of the address, simple and fast to check but two addresses that land on the same line will keep evicting each other even if the rest of the cache sits empty. A set-associative cache (say, 2-way) groups lines into sets, and an address can live in any line within its set, so the cache checks a couple of tags in parallel instead of just one, trading a bit of complexity for fewer of those needless evictions. A fully associative cache drops the grouping entirely, an address can live anywhere, which removes that kind of eviction completely but means checking every single line's tag on every access, so it is only practical for very small caches, like a TLB with a few dozen entries.

To find or place a line, the address splits into three fields. The low bits are the offset, which word within the line. The next bits are the index, which line (or set) it maps to. Everything above that is the tag, stored alongside the line so the cache can confirm it actually holds the address you asked for, not just some other address that happens to share the same index. In the simulator below, with 4 words per line, the offset is 2 bits. With 8 lines direct-mapped, the index is 3 bits. Switch to 2-way and there are only 4 sets, so the index shrinks to 2 bits and the tag grows by one bit to make up for it.

Hits, misses, and the three Cs

A hit means the line is already in the cache, a miss means it is not and has to be fetched from further down the hierarchy. Misses come in three flavors. A compulsory miss is the first time you ever touch a piece of data, no cache policy can prevent that one, you saw exactly this in the sequential scan above, one miss to open each new line, three hits to use the rest of it, 75 percent hits. A capacity miss happens when your working set is bigger than the whole cache, it would miss even with full associativity and infinite cleverness in placement. A conflict miss happens when several addresses fight over the same line even though the cache overall has room to spare, that is exactly what the strided-by-64 pattern does on a direct-mapped cache, two addresses colliding on the same line, evicting each other on every single access. Switch to 2-way and both addresses fit in the same set at once, the conflict misses disappear and the pattern turns almost entirely into hits.

Write-through versus write-back

Reads are not the only traffic, writes need a policy too. Write-through sends every write to the cache and immediately down to the next level as well, simple and always consistent, but it turns every single write into a slow trip to memory. Write-back writes only touch the cache line, which gets marked with a dirty bit, and the update only travels down to memory when that line is eventually evicted. Write-back does far less memory traffic for code that writes the same location repeatedly, at the cost of needing that extra bit of bookkeeping and a slightly trickier recovery story if something goes wrong before the write-back happens.

Why row-major beats column-major

How you loop over a 2D array matters more than it looks like it should, because most languages store a 2D array in row-major order, one full row after another in memory. Walking it in that same order is cache-friendly, walking it the other way, column-major, jumping a full row on every step, is cache-hostile.

for i in 0..N-1:
    for j in 0..N-1:
        sum += A[i][j]

for j in 0..N-1:
    for i in 0..N-1:
        sum += A[i][j]

Same additions, same data, same array, just a different loop order. In practice, summing a large matrix this way, big enough that it does not fit in any cache, is commonly measured at roughly 10 to 20 times slower in column-major order than row-major, purely from cache misses, the arithmetic itself is identical.