Clocks, Registers and Counters

At the end of the last chapter we found that flip-flops only change at the edge of a clock tick, and that this is what makes it safe to build loops. Now we'll organize those flip-flops into the pieces a processor is actually made of. By the end of this chapter you'll have every building block needed for the toy CPU in Part II.

The clock: a computer's heartbeat

Inside a computer, almost every flip-flop is connected to the same clock signal, a square wave that goes 0, 1, 0, 1, forever. Between two ticks, the gates do their work: adders add, signals spread through the logic and settle down. Then the clock rises, and every flip-flop captures its new value at the same instant. Then the gates get to work on those new values, and so on. The whole machine moves in lock-step, one tick at a time, like rowers following a drum.

We could make a clock from a ring oscillator, but its speed drifts with temperature and voltage. Real computers use a tiny slice of quartz crystal. Quartz has a remarkable property: squeeze it and it produces a voltage, and put a voltage on it and it flexes. Cut to the right size, a crystal vibrates at one very precise frequency, and a small circuit turns that vibration into a clean square wave.

Clock speed is measured in hertz (Hz), meaning ticks per second. 1 MHz (megahertz) is a million ticks per second, and 1 GHz (gigahertz) is a billion.

So why not just turn the clock up as far as it goes? Because of that settling time. Between two flip-flops there's always some chain of gates, and the signal has to make it all the way through before the next edge arrives. Otherwise the flip-flop captures a half-finished, wrong answer. The slowest such chain in the whole chip is called the critical path, and it sets the top clock speed.

This is exactly why real CPUs don't use the ripple-carry adder from Chapter 1. Its carry has to crawl through all 64 bits. Cleverer adders, which work out the carries in parallel, spend more gates to make the critical path short. At 5 GHz there's another limit too: in one tick, light itself travels only about 6 cm, and electrical signals in a chip's tiny wires are much slower than that.

Choosing: the multiplexer

Before we improve our registers we need one more building block, and it's one of the most common in any processor. A multiplexer ("mux" for short) is a selector switch. It has two data inputs, A and B, and a select input, SEL. When SEL is 0, the output copies A; when SEL is 1, it copies B.

It's built from gates we already know. One AND gate lets A through only when SEL is 0 (thanks to a NOT gate); the other lets B through only when SEL is 1. Exactly one of them is open at a time, and an OR gate combines them.

In diagrams a multiplexer is drawn as a trapezoid. Wider ones choose between 4, 8 or more inputs using more select bits: two select bits can pick one of four inputs, three can pick one of eight. A processor is full of them. When you write add rax, rbx rather than add rax, rcx, some of the instruction's bits go straight to the select inputs of multiplexers that decide which register gets connected to the adder. We'll build exactly that in Part II.

A register that waits

A plain D flip-flop captures its input on every clock edge. But in a computer, most registers should keep their value most of the time, and only change when an instruction writes to them. We need a LOAD switch.

The trick is a multiplexer in front of each flip-flop. Its "1" input is the new data D, and its "0" input is the flip-flop's own output Q, fed back around. When LOAD is 0, the flip-flop is fed its own value, so each clock edge stores what was already there and nothing changes. When LOAD is 1, the new data goes in.

Four flip-flops, four multiplexers, one shared clock and one shared LOAD wire: that's a 4-bit register. Make it 64 bits wide and you have rax.

Counting: the ripple counter

In Chapter 3 we built a flip-flop that flips itself on every clock tick, which makes its output run at exactly half the clock's speed. What happens if we feed that output into the clock of a second self-flipping flip-flop? The second one runs at a quarter of the speed. A third runs at an eighth, and so on.

Wire them so that each flip-flop flips whenever the one before it drops from 1 to 0, and something lovely happens: together, their outputs count in binary.

Compare those waveforms with the bit flipper in Chapter 1: the "ones" bit flips every time, the "twos" bit every second time, the "fours" bit every fourth time. Same pattern, now produced by a machine.

This is a ripple counter, and it has the same weakness as the ripple adder. Each flip-flop has to wait for the one before it. Going from 7 (0111) to 8 (1000), the counter briefly passes through 6, 4 and 0 as the change ripples along. For anything that needs a clean value at every tick, that's no good. But for simply dividing a frequency, it's perfect.

The program counter

For a clean counter, we go back to registers. Take a register, run its output through an adder that adds 1, and feed the result back into the register's input. Every clock tick, the register loads its own value plus one. All the bits change together on the same edge, and the adder has a whole tick to settle, so there's no rippling garbage at the output.

Then add one more multiplexer, so that instead of "plus one", the register can load a completely different number. Now we have a counter that normally counts up by one, but can jump anywhere when told to. This is the single most important register in a processor: the program counter, or PC.

Here's why it matters. A program is a list of instructions stored in memory, one after another, and each one sits at a numbered address. The program counter holds the address of the next instruction to run. Normally it just steps forward to the next instruction. But a jump instruction loads a new address into it, and that's how a program makes loops and decisions. Everything you'll ever see a computer do, from a simple loop to a whole operating system, comes down to this counter stepping and jumping.

Meanwhile, inside a real CPU

On x86-64 the program counter is called RIP (the "instruction pointer"); on RISC-V it's simply pc. Here's a tiny loop that counts forever, in both:

; x86-64
loop:  add  rax, 1      ; RIP steps past this instruction (4 bytes long)
       jmp  loop        ; RIP = address of "loop": JUMP = 1!

# RISC-V
loop:  addi a0, a0, 1   # pc = pc + 4
       j    loop        # pc = address of "loop"

Notice one detail: real program counters don't step by 1. Memory addresses count bytes, and instructions take several bytes each. Every RISC-V instruction is 4 bytes long, so the PC normally adds 4. (An optional "compressed" extension adds 2-byte versions of common instructions.) x86 instructions vary from 1 to 15 bytes, so the processor works out each instruction's length as it reads it, and steps by that much. That add rax, 1 happens to be 4 bytes, and the short jmp is 2.

Part I: the toolbox

Look at what we've built since that first switch and lamp:

• Logic gates, made from transistors that work like switches.
• Adders and subtractors, made from gates: the heart of arithmetic.
• Multiplexers to choose between signals.
• Flip-flops and registers to remember values.
• A clock to keep everything in step.
• Counters, including the program counter that steps through a program.

Remarkably, that's all a processor needs. Every CPU ever made, from the 8088 to the chip in your phone, is these same parts, arranged very cleverly and repeated billions of times.

Try it yourself

1. Set the clock to 5 GHz. How long is one tick, and how far does light travel in that time?
   Show answer

   0.2 nanoseconds (200 picoseconds). Light covers about 6 cm in that time, less than the width of your hand.
2. In the ripple counter's analyzer, how does the speed of Q1 compare with Q0? And Q3 with the clock?
   Show answer

   Q1 runs at half the speed of Q0. Each stage halves it again, so Q3 runs at 1/16 of the clock: one full up-and-down for every 16 ticks.
3. A quartz watch's crystal runs at 32,768 Hz. How many divide-by-two stages does it need to get one tick per second?
   Show answer

   15, because 2¹⁵ = 32,768. Each stage halves the frequency: 16,384, 8,192, … , 2, 1.
4. In the register demo, with LOAD off, the flip-flops still capture a value on every clock edge. So why doesn't anything change?
   Show answer

   With LOAD = 0, each multiplexer feeds the flip-flop its own Q. The flip-flops faithfully store a new value on each edge, but it's the same value they already had.
5. In the program counter demo, what happens if you Tick when the PC is 15 and JUMP is off?
   Show answer

   It wraps around to 0: 15 + 1 = 16 doesn't fit in 4 bits. A real 64-bit program counter would wrap the same way, but it would take a very, very long time to get there.

What we learned

• The clock, usually driven by a quartz crystal, makes every flip-flop update at the same instant. Speed is measured in hertz.
• The critical path, the slowest chain of gates between flip-flops, limits how fast the clock can go.
• A multiplexer picks one of several inputs using select bits.
• A mux in front of each flip-flop gives a register a LOAD control, so it changes only when asked.
• Chained self-flipping flip-flops form a ripple counter, which is perfect for dividing frequencies.
• Register + adder + mux makes a counter that can step or jump: the program counter (RIP on x86-64, pc on RISC-V).

That completes Part I. In Part II we put the pieces together. We'll design Tiny-8, a complete toy processor, give it a small memory with a program in it, and watch it fetch, decode and execute instructions one clock tick at a time.