1 Switches (transistors)

The key component that lets processors work is two kinds of pressure-activated switches, called transistors in an electrical setting or valves in a water setting. One type of switch connects two channels into one when pressure is applied and disconnects them when it is removed; the other type does the complement, disconnecting two channels when pressure is applied and connecting them when it is removed. Both have some kind of threshold pressure, a pressure strong enough to activate the switch, and some noise or variation in individual switches; to deal with that variation 1 is chosen as a pressure high enough that even the stiffest switch is activated and 0 as a pressure low enough that even the softest switch is not.

Illustrations of several switches

Switches require a source of power to operate. Power provides the computer with two pools, one with high pressure (1) and one with low pressure (0). As a computer operates, the pressure carrier (electricity, water, etc) will move from the high- to low-pressure pool, reducing the pressure differential between the pools; energy is required to restore the previous pressures and continue operation. If we disconnect the power source, the two pools will quickly reach the same pressure and all operation will stop.

With switches and power, a processor is designed in many layers. We design gates out of switches, and adders out of gates, and multipliers out of adders, and so on until we have a full computer. You could readily understand each individual step, but each would take time to understand and there are so many steps we can’t hope to cover them all in this course. Instead, we’ll illustrate a few steps to give a sense of how computers can be built.

2 Switches to Gates

Gates are small collections of transistors connected to a power source with 1 output wire and usually 2 input wires. They are designed so that specific combinations of voltage on the input wires will connect the output wire to the power source, while other combinations will not.

The simplest gate is the not gate. A not gate has the property that its output has voltage if and only if its input does not. A not gate can be built from two switches: one connects the output to the high voltage and is disconnected when there’s input voltage, the other connects the output to the low voltage and is connected when there’s input voltage.

A simple two-input gate is the and gate. An and gate has the property that its output has voltage if and only both of its inputs have voltage. An and gate can be built from four switches¹¹ Modern computers build and gates out of 6 switches instead of 4 to handle some nuances of transistor performance, but the 4-switch version is clearer to understand.:

• A 0-connecting switch with input A, connecting the output to the 0 power
• A 0-connecting switch with input B, connecting the output to the 0 power
• A 1-connecting switch with input A, connecting the output to the next switch in this list
• A 1-connecting switch with input B, connecting the previous switch in this list to the 1 power

An or gate is like an and gate except its output is 1 if either of its inputs is 1. If you swap the 1 and 0 power connections of an and gate you get an or gate.

These gates are named after English words because they have some relationship to how we use those words. If we think of inputs set to 1 as being true statements and inputs set to 0 as being false statements, then modifying those statements with the word a gate is named after gives a statement with the same truth as the gate’s output.

But some English words have more than one meaning. For example, if at a restaurant you are asked would you like salt or pepper? you can answer yes meaning you want one or both; but if you are asked is that for here or to go? then yes is not an option: you’re to pick one and only one of the two.

This leads to another kind of or-like gate, the exclusive or xor. This gate outputs 1 if either one of its inputs is 1 and the other is 0, but outputs 0 if both inputs are the same. We can make an xor out of switches, but we can also make it out of other gates:

• Put the inputs into an or gate
• Also put the inputs into an and gate
• Put the output of the and gate into a not gate
• Put the outputs of the or and not gates into a second and gate
• Use the output of the second and gate as the output of the xor gate

While such a gate made from other gates may not be optimal (we can probably use fewer than the 14 switches this would need), it does show how we can design new components out of pieces we’ve already designed.

Sometimes gates are summarized by making a table of all their possible input and output combinations. In keeping with the true/false interpretation of 1/0 that inspires the gate names, these are called truth tables. The four gates we’ve see so far would have the following truth tables:

3 Gates to Addition

Consider adding two 1-bit numbers

• 0 + 0 = 0; in 2-bit binary that’s 00
• 0 + 1 = 1; in 2-bit binary that’s 01
• 1 + 0 = 1; in 2-bit binary that’s 01
• 1 + 1 = 2; in 2-bit binary that’s 10

The 2s bit of the answer is the same as the and gate: it’s 0 except when both input bits are 1.

The 1s bit of the answer is the same as the xor gate: 0+0 and 1+1 both have a 0, while 0+1 and 1+0 both have a 1.

Thus, one and and one xor can add two 1-bit numbers.

To add three 1-bit numbers we

• Add the first two
• Add the third to the ones’ place of the result
• add the twos’ places of the two addition results (this never has a twos’ place)

With three 1-bit additions we can now build arbitrary-bit addition, using the same digit-by-digit algorithm that you learned as a child.

• Starting with the low-order digit (right end)
• Add the carry (initially 0) and a digit from each number – a total of three digits
  • Put the ones’ place digit of the result in the answer
  • Put the other digit of the result as the new carry
• Move on to the next higher digit (one step to the left)

This algorithm is just three 2-bit adders per bit, where a 2-bit adder is an and and an xor, where each of those is just a few switches.

We don’t have to stop there. Subtraction is a lot like addition; multiplication uses a 1-digit multiplication table (which in binary is just an and gate) and a bunch of additions; and so on.

4 Gates to Muxes

In a programmable computer, we often want to pick an option based on an input. For example, we want to add if we see a + but subtract if we see a -. Picking complicated things like that will be built off of picking a single wire, a tool that is called a multiplexer or mux.

A mux has 3 inputs: two things to pick between and one to use in picking one of them. We can write this out as a truth table:

Note that in this table, the result us the same as A when S=0 and the same as B when S=1.

We could try to find switches for this entire set of inputs, but it’s much easier to just use gates. ((not S) and A) or (S and B) will give us the result we want:

5 And so much more

Registers are a kind of high-speed memory that is designed by connecting the inputs and outputs of specific gates in a loop that can store one bit at a time.

Gated²² Here gate does not mean a few-input one-output collection of switches; instead if means there’s a barrier that prevents things usually but can be opened sometimes. registers use a few more gates to add a special clock input that makes them ignore their input except at specific moments in time. They allow the entire processor to operate in synchronized steps, doing one thing to conclusion before the clock ticks and they move on to the next thing.

A counter is a gated register with its output run through a + 1 computation and put into its input, causing it to count up by one each time the clock ticks.

A variant on muxes lets us do indexing or addressing, picking not between just two things but between billions of things stored in a giant grid of register-like storage we call memory.

In memory we put a sequence of instructions. By having the selector that picks a value out of memory be the output of a counter, we see the instructions one at a time in order.

Instructions (which are many bits in size) are broken into groups of bits which are used to pick which values to operate on (by using them as selectors for memory) and what operation to do with those values (by using muxes to pick one arithmetic circuits outputs to keep).

Some instructions use a mux to pick whether to let the counter act like normal (moving from one instruction to the next) or to change the counter to a new value. This allows the program to run through the same set of instructions several times in a loop, jump to a set of instructions of interest and later jump back, and otherwise do much more complicated things then simply doing a specific set of actions in order.

And each of these ideas has multiple variants, ways of being more complicated and faster and fancier in ways that make new computers able to run faster than old ones.

6 How computers are built

Most processors are made from silicon transistors. The basic steps are:

1. Make a single monocrystal of 100% pure silicon the size of a small tree trunk.
2. Slice it into perfectly smooth wafers.
3. Cover the wafer in a photoreactive chemical.
4. Use a super-accurate microprojector to expose some of it to light and others not.
5. Wash it with something that cleans off the exposed parts but not the unexposed (or vice-versa).
6. Repeat steps 3–5 with different materials to build up the full computer chip.

There are variants on this process, but the overall design (atomically-perfect silicon crystals and microscopically-accurate light delivery) allows creating chips of mindbogglingly tiny dimensions. Entire transistors may be no more than a few hundred atoms across³³ Chip component sizes are measured in nanometers, not atoms, but most of us have no concept of how small a nanometer is. The atomic radius of silicon (the principle element in most chips today) is about .11 nm and silicon bonds with itself at about 4.3 atoms per nm.. That extreme small size has three big benefits:

• The smaller the transistor, the more we can fit on a chip.

  More transistors implies more things the computer can do at the same time.

  Moore’s Law predicts that the number of transistors on newly-produced computer chips will double every 2 years, and has proven true for more than 50 years, resulting tens of billions of transistors per chip on modern computers.

• The smaller the transistor, the less energy it takes to push current through it.

  This means that the electricity per unit of computation decreases as transistors shrink.

  This is not a perfectly smooth relationship: two chips with the same transistor size might use very different amounts of energy. But it is a strong overall trend.

• The smaller the transistors, the faster each computation can complete.

  Nothing can go faster than the speed of light. But computers run in the multiple GHz speed range, meaning they do multiple entire arithmetic computations each nanosecond⁴⁴ 1 GHz means 1 thing per nanosecond. Common computers today have a clock speed somewhere around 3 GHz, meaning they do 3 steps of computation (roughly a many-digit addition) each nanosecond. A nanosecond is roughly the time it takes light to travel 1 foot⁵⁵ The speed of light is exactly 29.979246 cm per ns. Information in a computation needs to travel back and forth across the chip in a non-straight path, and doing work (like changing from low- to high-voltage) takes time beyond what information flow does. The smaller the chip components get, the less time it takes information to flow across them.

Moore’s Law

In 1965 a reporter writing for Electronics Magazine asked Gordon Moore, director of R&D at Fairchild Semiconductor, to predict the future of semiconductors over the next ten years. Moore observed that the number of components per chip had been doubling each year and predicted it would continue doing so for the next ten years.

This doubling claim was was a bold enough to make some impact, but likely would have faded in importance quickly had not Carver Mead, one of Moore’s collaborators at CalTech, named it Moore’s Law and that term often enough that it became common.

In 1975 Moore revised his prediction from doubling every year to doubling every two years, which has been a roughly accurate prediction ever since. Arguably this is partially a self-fulfilling prophesy: it has held for so long that chip manufacturers expect someone will find a way to keep it up and don’t want to fall behind, so they set it as an internal goal driving design and development. User-visible chip performance, realized in part by transistor count increases, improves much more slowly.

The success of Moore’s Law, both as a name and as a prediction, has led to a variety of spin-offs and variants. It is common to hear a wide variety of exponential-growth predictions related to computers being called Moore’s Law, even if the prediction being discussed is about speed, power, size, concurrency, cost, or almost anything else.