6. BUILDING A COMPUTER

This chapter under major construction.

Architecture refers both to the art of designing computers and to the process of building them. Our coverage of this topic is centered around an imaginary machine that is similar to real computers. In Chapter 5, we specified the machine in full detail. We continue with a treatment of circuits and logical design, culminating in a description of how such a machine might be built from the ground up. Our intent is to demystify this apparently formidable challenge while also providing a context for understanding how Java programming and other familiar high-level tasks relate to actual machines.

Boolean and logical gates
Combinational circuits
Sequential circuits
Components
TOY machine architecture

Here are some notes on digital circuits [pdf].

Credits: Doug Clark for TOY machine architecture.

Circuit simulator. Here is our first pass. Ternary.java represents three value logic (true, false, or unknown) Wire.java represents a wire. Each wire has a ternary signal value which can be set and propagated to downstream wires. Each wires can be soldered to one other wire. Circuit.java represents a generic circuit. It consists of an array of input wires, an array of output wires, and accessor methods. And.java is a circuit that represents an AND gate. Switch.java is the input interface with the real world. It is a circuit with zero inputs and one output. It has special methods turnOn and turnOff to turn the switch to the on or off position. Light.java is the output interface with the real world. It is a circuit with one input and zero outputs. It has a special method isOn to determine whether the light is on or off (or unknown). Splitter.java is a useful circuit that takes one input and propagates it to two output wires. MultiwayAnd.java is a higher level circuit that represents an M-way AND gate. It is built up from several And gates using a divide-and-conquer strategy.

Intel Pentium bug. Designing circuits for more complicated arithmetic functions like multiplication and division is a challenging engineering task. Sometimes the engineers get it wrong. In 1994, Intel recalled a huge number of chips after a flaw surfaced in the division operation. This infamous and widely-publicized flaw was exposed by Thomas Nicely who was investigating a series involve twin primes (two consecutive odd numbers which are prime, e.g., 17 and 19 or 824,633,702,441 and 824,633,702,443). He discovered that the Pentium chip reported 1 / 824,633,702,441.0 to only 8 decimal places, whereas it was guaranteed to many more.

Master-slave. Banned in Los Angelos County.

Linear feedback shift register. Build a LFSR in hardware. Need clock and flip-flops. See this site.

Exercises.

Design a circuit to control a single light bulb by three switches. The circuit has three inputs (the switch settings x, y, and z) and one output (the light control). At any time, you should be able to turn the light off (if on) or on (if off) by changing the position of any one of the three switches. When all three switches are 0 (down position), the light control is 0 (light off).
Which of the following TOY machine components are not combinational circuits?
1. Control
2. Counter
3. Registers
4. Main memory
5. Adder

Creative Exercises.

Read only wire. Wrapper type for read only wire.
Sum-of-products. Disjunctive normal form. Algebraic properties: sum and product are commutative and associative, distributive property, etc.
Product-of-sums. Conjunctive normal form. Include a term for each 0 in the truth table trow.
DeMorgan laws.
XOR using NAND. Implement an XOR gate using only NAND gates. Assume you can have inputs that are 0 or 1.
XOR using NAND. Implement an XOR gate using only 4 NAND gates. You may not use constant input symbols. Answer: XOR(a, b) = NAND(d, e), where c = NAND(a, b), d = NAND(a, c), and e = NAND(b, c).
The 2-NOTs problem. Give three inputs a, b, and c, design a circuit that outputs a', b', and c'. You may use as many AND and OR gates as you like, but at most two NOT gates. Hint: high degree of difficulty.
Flat computer. Show that, in principle, you can draw and circuit in the plane. Assume two input AND, OR, and NOT can be drawn in the plane. It suffices to draw a crossover circuit. planar cross-over circuit.
Comparator circuit.
At least k. A n-way majority circuit takes n inputs and returns 1 if and only if at least strictly more of its inputs are 1 than 0. Given an n-way majority circuit, describe how to build an At-Least-k circuit that returns 1 if and only if at least k of its inputs are 1. Answer: consider a 2n-way majority circuit. Make n-k+1 of the inputs 1, k-1 of the inputs 0, and the original n inputs.
Exactly k circuit. Describe how to build a circuit that outputs 1 if and only if exactly k of its inputs are 1. Answer: If k = n, use an n-way and gate. Otherwise build up an At-least-k circuit and an At-least-k+1 circuit as in the previous exercise. It has exactly k inputs that are 1 if the first circuit outputs 1, but the second one outputs 0.
Odd parity from majority gates. Describe how to build an n-way odd parity circuit using only majority gates. You may assume that you have 0s and 1s as inputs.
Adder from majority gates. Describe how to build an n-bit adder circuit using only majority gates. You may assume that you have 0s and 1s available as inputs. Hint: build up a 3-way odd parity circuit out of 3-way majority circuits. Note that MAJ(x, y) = AND(x, y) and MAJ(x, y, 1) = OR(x, y).
Boolean logic puzzle. You must transport a wolf, a goat, and a cabbage to the other side of the river using a boat. Due to natural predator relationships, you cannot leave the goat and the wolf alone on the same side of the river at the same time. Nor can you leave the goat and the cabbage together.