Noam Nisan - The Elements of Computing Systems: Building a Modern Computer from First Principles

Major modules of a typical computer system, consisting of a hardware platform and a software hierarchy. Each module has an abstract view (also called the modules interface) and an implementation. The right-pointing arrows signify that each module is implemented using abstract building blocks from the level below. Each circle represents a Nand to Tetris project and chaptertwelve projects and chapters altogether.

Three elementary Boolean functions.

All the Boolean functions of two binary variables. In general, the number of Boolean functions spanned by n binary variables (here ) is (thats a lot of Boolean functions).

Truth table and functional definitions of a Boolean function (example).

Composite implementation of a three-way And gate. The rectangular dashed outline defines the boundary of the gate interface.

Xor gate interface (left) and a possible implementation (right).

Gate diagram and HDL implementation of the Boolean function Xor (And (a, Not (b)), And (Not (a), b)), used as an example. A test script and an output file generated by the test are also shown. Detailed descriptions of HDL and the testing language are given in appendices 2 and 3, respectively.

A screenshot of simulating an chip in the supplied hardware simulator (other versions of this simulator may have a slightly different GUI). The simulator state is shown just after the test script has completed running. The pin values correspond to the last simulation step Not shown in this screenshot is a compare file that lists the expected output of the simulation specified by this particular test script. Like the test script, the compare file is typically supplied by the client who wants the chip built. In this particular example, the output file generated by the simulation (bottom right of the figure) is identical to the supplied compare file.

Multiplexer. The table at the top right is an abbreviated version of the truth table.

Demultiplexer.

Twos complement representation of signed numbers, in a 4-bit binary system.

Half-adder, designed to add 2 bits.

Full-adder, designed to add 3 bits.

16-bit adder, designed to add two 16-bit numbers, with an example of addition action (on the left).

The Hack ALU, designed to compute the eighteen arithmetic-logical functions shown on the right (the symbols , , and represent, respectively, the 16-bit operations , , and ). For now, ignore the and output bits.

Taken together, the values of the six control bits , , , , , and cause the ALU to compute one of the functions listed in the rightmost column.

The Hack ALU API.

The memory hierarchy built in this chapter.

Discrete time representation: State changes (input and output values) are observed only during cycle transitions. Within cycles, changes are ignored.

The data flip-flop (top) and behavioral example (bottom). In the first cycle the previous input is unknown, so the DFFs output is undefined. In every subsequent time unit, the DFF outputs the input from the previous time unit. Following gate diagramming conventions, the clock input is marked by a small triangle, drawn at the bottom of the gate icon.

Sequential logic design typically involves DFF gates that feed from, and connect to, combinational chips. This gives sequential chips the ability to respond to current as well as to previous inputs and outputs.

1-bit register. Stores and emits a 1-bit value until instructed to load a new value.

16-bit Register. Stores and emits a 16-bit value until instructed to load a new value.

A RAM chip, consisting of n 16-bit Register chips that can be selected and manipulated separately. The register addresses are not part of the chip hardware. Rather, they are realized by a gate logic implementation that will be discussed in the next section.

Program Counter (): To use it properly, at most one of the load, , or reset bits should be asserted.

The (1-bit register) implementation: invalid (left) and correct (right) solutions.

Conceptual model of the Hack memory system. Although the actual architecture is wired somewhat differently (as described in chapter 5), this model helps understand the semantics of Hack programs.

Hack assembly code examples.

A Hack assembly program (example). Note that RAM[0] and RAM[1] can be referred to as and

The Hack instruction set, showing symbolic mnemonics and their corresponding binary codes.

A Hack assembly program that computes a simple arithmetic expression.

Array processing example, using pointer-based access to array elements.

The CPU emulator, with a program loaded in the instruction memory (ROM) and some data in the data memory (RAM). The figure shows a snapshot taken during the programs execution.

A generic von Neumann computer architecture.

The Hack Central Processing Unit (CPU) interface.

The Hack instruction memory interface.

The Hack Screen chip interface.

The Hack Keyboard chip interface.

The Hack data memory interface. Note that the decimal values 16384 and 24576 are 4000 and 6000 in hexadecimal.

Interface of Computer, the topmost chip in the Hack hardware platform.

Proposed implementation of the Hack CPU, showing an incoming 16-bit instruction. We use the instruction notation