[WIP] The Elements of Computing Systems: Building a Modern Computer from First Principles

Chapter 1: Boolean logic

Binary variables

Modern computers store and process information stored as two-valued signals — called bits (i.e. binary digits). Two-value signals were chosen because they can readily be represented, stored, and transmitted. For example, as:

• The presence or absence of a hole in a punched card
• High or low voltage on a wire
• A magnetic domain oriented clockwise or counterclockwise.

A binary variable or a bit can represent two possible states: 0 and 1; off and on; false and true; no and yes; etc. $n$ binary variables can be used to represent $2^n$ states. e.g.

Boolean functions

Boolean algebra is used to manipulate binary values. A boolean function (aka boolean operator) is a function that operates on binary inputs and returns binary outputs.

The total number of boolean functions for $n$ binary variables is $2^{2^n}$. Explanation:

• There are $2^n$ input combinations.
• Each of these input combinations can be mapped to either 0 or 1.
• The total number of boolean functions is thus: $2^{2^n}$
• e.g. There are 16 distinct boolean functions for 2 binary variables.

Logic gates

A gate (also called chip in the book) is a physical device that implements a boolean function. Every digital device is based on a set of chips designed to store and process binary information. These chips are all made of elementary logic gates. Elementary logic gates can be physically realized using many different hardware technologies, but their logical behavior, or abstraction, is consistent across implementations.

Since all logic gates have the same input and output data type (i.e. binary), they can be combined, creating composite gates of arbitrary complexity. e.g. Xor = Or( And(a, Not(b)), And(Not(a), b) ).

Any given logic gate can be viewed from two perspective:

1. External: The interface of the gate, outlining its input pins, output pins, and its behavior.
2. Internal: The implementation of the gate. There can be multiple implementations of a gate’s interface. The goal is to find an implementation that is correct (functional requirement) and efficient (performance requirement).

Hardware description language (HDL)

Hardware description language is a formalism used by hardware designers to design chip architecture.

The designer specifies the chip logic by writing a HDL program, which is then subjected to a rigorous battery of tests. The tests are carried out virtually, using computer simulation: A special software tool, called a hardware simulator, takes the HDL program as input and creates a software representation of the chip logic. Next, the designer can instruct the simulator to test the virtual chip on various sets of inputs. The simulator computes the chip outputs, which are then compared to the desired outputs.

The hardware simulator can also simulate and quantify the performance characteristics (energy consumption, computational speed, cost) of a chip.

Gates specification

The specifications of the logic gates needed to build the chips of our computer system are given below.

Primitive gates

Nand gate

Shorthand for Not-And because its equivalent to Not(And(a, b)).

Truth table:

API:

The NAND gate is a primitive gate because it can be used to implement any boolean function. Proof:

• Various subsets of logical operators can be used for expressing any boolean function, and { And, Or, Not } is one such subset. NAND can be used to implement each member of the subset as demonstrated below.
• NOT(a) = NAND(a, a)
• AND(a, b) = NOT(NAND(a, b))
• OR(a, b) = NOT(NOT(a) AND NOT(b)) (De morgan law)

Classical logical gates

These gates implement classical logical operators.

Not (aka inverter) gate

This gate outputs the opposite value of its input’s value.

Truth table:

API:

HDL:

Copycopy code to clipboard
1CHIP Not {
2    IN in;
3    OUT out;
4
5    PARTS:
6    Nand(a= in, b= in, out= out);
7}

And gate

Returns $1$ when both its inputs are $1$, and $0$ otherwise.

Truth table:

API:

HDL:

Copycopy code to clipboard
1CHIP And {
2    IN a, b;
3    OUT out;
4    
5    PARTS:
6    Nand(a= a, b= b, out= nandout);
7    Not(in= nandout, out= out);
8}

Or gate

Returns $1$ when at least one of its inputs is $1$, and $0$ otherwise.

Truth table:

API:

HDL:

Copycopy code to clipboard
1CHIP Or {
2    IN a, b;
3    OUT out;
4
5    PARTS:
6    Not(in= a, out= nota);
7    Not(in= b, out= notb);
8    And(a= nota, b= notb, out= notaandnotb);
9    Not(in= notaandnotb, out= out);
10}

Xor (aka exclusive or) gate

Returns $1$ when exactly one of its input is $1$, and $0$ otherwise.

Truth table:

API:

HDL:

Copycopy code to clipboard
1CHIP Xor {
2    IN a, b;
3    OUT out;
4
5    PARTS:
6    Not(in= a, out= nota);
7    Not(in= b, out= notb);
8    And(a= a, b= notb, out= aandnotb);
9    And(a= b, b= nota, out= bandnota);
10    Or(a= aandnotb, b= bandnota, out= out);
11}

Control flow gates

These gates provide means for controlling flows of information.

Multiplexer

A multiplexer is a three-input gate. Two input bits, named a and b, are interpreted as data bits, and a third bit, named sel, is interpreted as a selection bit. The multiplexer uses sel to select and output the value of either a or b.

Fig1.9

Truth table:

API:

HDL:

Copycopy code to clipboard
1CHIP Mux {
2    IN a, b, sel;
3    OUT out;
4
5    PARTS:
6    Not(in= sel, out= notsel);
7    And(a= a, b= notsel, out= aandnotsel);
8    And(a= b, b= sel, out= bandsel);
9    Or(a= aandnotsel, b= bandsel, out= out);
10}

Demultiplexer

A demultiplexer performs the opposite function of a multiplexer: it takes a single input value and routes it to one of two possible outputs, according a selector bit that selects the destination output.

Fig1.10

API: | | | |-----------|--------------------------------------------------------------| | Chip name | DMux | | Input | in, sel | | Output | a, b | | Function | if (sel == 0) then {a, b} = {in, 0}, else {a, b} = {0, in} |

HDL:

Copycopy code to clipboard
1CHIP DMux {
2    IN in, sel;
3    OUT a, b;
4
5    PARTS:
6    Not(in= sel, out= notsel);
7    And(a= in, b= notsel, out= a);
8    And(a= in, b= sel, out= b);
9}

Multi-bit versions of basic gates

This section describes several 16-bit logic gates that will be needed for constructing our target computer platform. HDL programs treat multi-bit values like single-bit values, except that the values can be indexed in order to access individual bits. For example, if in and out represent 16-bit values, then out [3] = in[5] sets the 3rd bit of out to the value of the 5th bit of in. The bits are indexed from right to left, the rightmost bit being the 0’th but and the leftmost bit being the 15’th bit (in a 16-bit setting).

16-bit Not gate

Applies the Boolean operation Not to every one of the input bits.

API:

HDL:

Copycopy code to clipboard
1CHIP Not16 {
2    IN in[16];
3    OUT out[16];
4
5    PARTS:
6    Not(in= in[0], out= out[0]);
7    Not(in= in[1], out= out[1]);
8    Not(in= in[2], out= out[2]);
9    Not(in= in[3], out= out[3]);
10    Not(in= in[4], out= out[4]);
11    Not(in= in[5], out= out[5]);
12    Not(in= in[6], out= out[6]);
13    Not(in= in[7], out= out[7]);
14    Not(in= in[8], out= out[8]);
15    Not(in= in[9], out= out[9]);
16    Not(in= in[10], out= out[10]);
17    Not(in= in[11], out= out[11]);
18    Not(in= in[12], out= out[12]);
19    Not(in= in[13], out= out[13]);
20    Not(in= in[14], out= out[14]);
21    Not(in= in[15], out= out[15]);
22}

16-bit And gate

Applies the Boolean operation And to every one of the input bits.

API:

HDL:

Copycopy code to clipboard
1CHIP And16 {
2    IN a[16], b[16];
3    OUT out[16];
4
5    PARTS:
6    And(a= a[0], b= b[0], out= out[0]);
7    And(a= a[1], b= b[1], out= out[1]);
8    And(a= a[2], b= b[2], out= out[2]);
9    And(a= a[3], b= b[3], out= out[3]);
10    And(a= a[4], b= b[4], out= out[4]);
11    And(a= a[5], b= b[5], out= out[5]);
12    And(a= a[6], b= b[6], out= out[6]);
13    And(a= a[7], b= b[7], out= out[7]);
14    And(a= a[8], b= b[8], out= out[8]);
15    And(a= a[9], b= b[9], out= out[9]);
16    And(a= a[10], b= b[10], out= out[10]);
17    And(a= a[11], b= b[11], out= out[11]);
18    And(a= a[12], b= b[12], out= out[12]);
19    And(a= a[13], b= b[13], out= out[13]);
20    And(a= a[14], b= b[14], out= out[14]);
21    And(a= a[15], b= b[15], out= out[15]);
22}

16-bit Or gate

Applies the Boolean operation Or to every one of the input bits.

API:

HDL:

Copycopy code to clipboard
1CHIP Or16 {
2    IN a[16], b[16];
3    OUT out[16];
4
5    PARTS:
6    Or(a= a[0], b= b[0], out= out[0]);
7    Or(a= a[1], b= b[1], out= out[1]);
8    Or(a= a[2], b= b[2], out= out[2]);
9    Or(a= a[3], b= b[3], out= out[3]);
10    Or(a= a[4], b= b[4], out= out[4]);
11    Or(a= a[5], b= b[5], out= out[5]);
12    Or(a= a[6], b= b[6], out= out[6]);
13    Or(a= a[7], b= b[7], out= out[7]);
14    Or(a= a[8], b= b[8], out= out[8]);
15    Or(a= a[9], b= b[9], out= out[9]);
16    Or(a= a[10], b= b[10], out= out[10]);
17    Or(a= a[11], b= b[11], out= out[11]);
18    Or(a= a[12], b= b[12], out= out[12]);
19    Or(a= a[13], b= b[13], out= out[13]);
20    Or(a= a[14], b= b[14], out= out[14]);
21    Or(a= a[15], b= b[15], out= out[15]);
22}

16-bit Multiplexer gate

Operates exactly as the basic multiplexer, except that its input and output are 16-bits wide.

API:

HDL:

Copycopy code to clipboard
1CHIP Mux16 {
2    IN a[16], b[16], sel;
3    OUT out[16];
4
5    PARTS:
6    Mux(a= a[0], b= b[0], sel= sel, out= out[0]);
7    Mux(a= a[1], b= b[1], sel= sel, out= out[1]);
8    Mux(a= a[2], b= b[2], sel= sel, out= out[2]);
9    Mux(a= a[3], b= b[3], sel= sel, out= out[3]);
10    Mux(a= a[4], b= b[4], sel= sel, out= out[4]);
11    Mux(a= a[5], b= b[5], sel= sel, out= out[5]);
12    Mux(a= a[6], b= b[6], sel= sel, out= out[6]);
13    Mux(a= a[7], b= b[7], sel= sel, out= out[7]);
14    Mux(a= a[8], b= b[8], sel= sel, out= out[8]);
15    Mux(a= a[9], b= b[9], sel= sel, out= out[9]);
16    Mux(a= a[10], b= b[10], sel= sel, out= out[10]);
17    Mux(a= a[11], b= b[11], sel= sel, out= out[11]);
18    Mux(a= a[12], b= b[12], sel= sel, out= out[12]);
19    Mux(a= a[13], b= b[13], sel= sel, out= out[13]);
20    Mux(a= a[14], b= b[14], sel= sel, out= out[14]);
21    Mux(a= a[15], b= b[15], sel= sel, out= out[15]);
22}

Multi-way versions of basic gates

Logic gates that operate on one or two inputs have natural generalization to multi-way variants that operate on more than two inputs.

Multi-way 16-bit demultiplexer gate

An m-way n-bit demultiplexer routes its single n-bit input to one of its m n-bit outputs. The other outputs are set to 0. The selection is specified by a set of k selection bits, where $k = log_2{m}$.

Our target computer platform requires two variants of this chip: a 4-way 1-bit demultiplexer and an 8-way 1-bit demultiplexer.

API: | | | |-----------|--------------------------------------------------------------| | Chip name | DMux4Way | | Input | in, sel[2] | | Output | a, b, c, d | | Function | if (sel == 00) then {a, b, c, d} = {1, 0, 0, 0},<br><br>else if (sel == 01) then {a, b, c, d} = {0, 1, 0, 0},<br><br>else if (sel == 01) then {a, b, c, d} = {0, 0, 1, 0},<br><br>else if (sel == 11) then {a, b, c, d} = {0, 0, 0, 1}<br> |

HDL:

Copycopy code to clipboard
1

HDL:

Copycopy code to clipboard
1