From Nand to Tetris

Building a Modern Computer from First Principles

Lecture 5

Computer Architecture

These slides support chapter 5 of the book

The Elements of Computing Systems
By Noam Nisan and Shimon Schocken
MIT Press, 2021

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 1
Nand to Tetris Roadmap: Hardware

abstraction

machine
language p4 Previous lecture:
Introducing a
machine language
developing
an assembler

abstraction
hardware platform
building a p2 p3
computer abstraction
computer
building
abstraction
p1
ALU, RAM
chips building
elementary
logic gates gates

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 2
Nand to Tetris Roadmap: Hardware

abstraction

machine
language p4 Previous lecture:
Introducing a
machine language
developing
an assembler

abstraction p5 hardware platform

building a p2 p3
computer abstraction
computer
building
abstraction
p1
ALU, RAM
chips building
elementary
logic gates gates

This lecture: Building a

computer that realizes the
machine language

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 3
Nand to Tetris Roadmap: Hardware

The challenge … into an architecture that

Integrate the chips built executes any program written in
in chapters 1, 2, 3... the machine language introduced
in chapter 4
f
// Computes R1 = 1 + 2 + 3 + ... + R0
x // i = 1
16 @i
M=1
16 out // sum = 0
RAM ALU @sum
16 16 M=0
14 (LOOP)
y // if (i > R0) goto STOP
16 @i
D=M
@R0
D=D-M
@STOP
D;JGT
...
PC Register
16 16 16 16

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 4
Computer Architecture
Memory CPU

data register
program data register



input ALU output
data register

data address register

Program Counter

• Processor, registers, memory

• Stored program concept
• General-purpose

We’ll build the Hack computer – a variant of this architecture.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 5
Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 6
Early computers: 17th century

Blaise Pascal
1623 – 1662

Pascal’s Calculator
(Pascaline, 1652)
• Add
• Subtract

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 7
Early computers: 17th century

Gottfried Leibniz
1646 – 1716

Leibniz Calculator (1673)

• Add
• Subtract
• Multiply
• Divide.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 8
Early computers: 19th century

Milestone:
punched cards / software
Programmable!

mechanical loom mechanical calculator

(Jacquard, 1804) (Babbage, 1837)
Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 9
Modern computers: 20th century

John Von Neumann John Mauchly Presper Eckert

John Atanasoff Howard Aiken Konrad Zuse

ENIAC: First digital, programmable,

stored program computer
University of Pennsylvania, 1946,
(Inspired by many other
Tommy Flowers early computers and innovators)
Colossus: First digital, programmable,
computer, UK, 1945
Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 10
Modern computers: 20th century

Kathleen McNulty, Jean Jennings, Frances Snyder, Eniac women

Marlyn Wescoff, Frances Bilas, Ruth Lichterman
Pioneered reusable code, subroutines,
flowcharts, compilation, ...
many other software innovations

Grace Hopper Adele Koss

Compilation pioneers
Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 11
Modern computers: 20th century
Same hardware can run many different programs (software)

“If it should turn out that the basic logic of a machine designed for the numerical
solution of differential equations coincides with the logic of a machine intended to
make bills for department stores, I would regard this as the most amazing coincidence
I have ever encountered” –– Howard Aiken (Mark 1 computer architect, 1956)

“The stored program computer, as conceived by Alan Turing and delivered by

John von Neumann, broke the distinction between numbers that mean things and
numbers that do things. Our universe would never be the same” (George Dyson)

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 12
Basic architecture
Memory CPU

data register
program data register



ALU
data register

data address register

Program Counter

Computer:
A machine that uses instructions to manipulates data

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 13
Basic architecture
Memory CPU

data register
program data register

 The computer can be viewed


data register
ALU as a set of chips, connected by
pathways (buses).
data address register

Program Counter

instructions control bus

addresses address bus

data values data bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 14
Computer architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 15
Computer architecture
Memory CPU
Basic loop
data register • Fetch
program an instruction
data register
(by supplying

 an address)

ALU • Execute
data register
the instruction
data address register
• (and figure out the
PC
address of the next
instruction)

Program Counter
Always emits the address
of the next instruction

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 16
Fetch an instruction
Memory CPU
Basic loop
data register • Fetch
program an instruction
data register
(by supplying

 an address)

ALU • Execute
data register
the instruction
data address register
• (and figure out the
PC
address of the next
instruction)

Program Counter
Always emits the address
address instruction of the next instruction

address bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 17
Fetch an instruction
Memory CPU
Basic loop
data register • Fetch
program an instruction
data register
(by supplying

 an address)

ALU • Execute
data register
the instruction
data address register
• (and figure out the
PC
address of the next
instruction)

instruction instruction

control bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 18
Execute the instruction
Memory CPU
Basic loop
data register • Fetch
program an instruction
data register
(by supplying

 an address)

ALU • Execute
data register
the instruction
data address register
• (and figure out the
PC
address of the next
instruction)

instruction instruction

control bus

The instruction bits specify:

• Which ALU operation to perform,
• On which operands
• (CPU registers / memory registers)
Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 19
Fetch – Execute issues
Memory
Should the Memory output be interpreted
as an instruction, or as data?

program instruction
out
ALU
data

(for the instruc.

data to operate on)

Possible solutions:
address • Two-cycle, one-memory machine
• One-cycle, two-memory machine

instruc. data
address address
Should we feed the instruction
control address,
bus or the data address?

address bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 20
Two-cycle, one-memory machine
Memory

program instruction
out
ALU
data

(for the instruc.

data to operate on)

address

instruc. data
address address

control bus

address bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 21
Two-cycle, one-memory machine
Memory

when
program fetching instruction instruction
register
out
DMux ALU
data

when (for the instruc.

data executing to operate on)

address

Mux

(when instruc. data (when

fetching) address address executing)

control bus

address bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 22
Two-cycle, one-memory machine
Memory

when
program fetching instruction instruction
register
out
DMux ALU
data

when (for the instruc.

data executing to operate on)

fetch /
address
execute Fetch cycle: Loads an instruction into the
bit instruction register
Mux
Execute cycle: Loads a data value from
(when
memory, and executes the instruction
instruc. data (when
fetching) address address executing)

control bus

address bus

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 23
Single cycle, two-memory machine

Instruction Memory CPU Data Memory

data register

data register write

instruc-
tion 


ALU read
program data register
data
address
address register
address
PC

• Instructions and data are stored in two separate physical memories

• Both memories are accessed simultaneously, in the same cycle
• (for historical reasons, referred to as ”Harvard architecture”)

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 24
Single cycle, two-memory machine

Instruction Memory CPU Data Memory

data register

data register write

instruc-
tion 


ALU read
program data register
data
address
address register
address
PC

Advantages Disadvantages
• Simple architecture • Two memory chips
• Fast processing • Separate address spaces

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 25
Chapter 5: Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 26
The Hack computer

Instruction Memory CPU Data Memory

instruc- write
D register
tion
read
program A register ALU data
address
address PC

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 27
CPU abstraction
A chip that implements the Hack instruction set:

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 28
CPU abstraction

D register

A register

Instruction
examples:
// D = RAM[5] + 1 1. Executes the current instruction
@5
2. Figures out which instruction to execute next
DM=M+1
…
// goto 200
@200
0;JMP
…

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 29
CPU abstraction

D register

A register

Instruction
examples:
// D = RAM[5] + 1 1. Executes the current instruction:
@5 If it’s an A-instruction (@ xxx), sets the A register to xxx
DM=M+1 Else (C-instruction):
… • Computes the ALU function specified by the instruction (on the values of A, D, inM)
// goto 200 • Puts the ALU output in A, D, outM, as specified by the instruction
@200 • If the instruction writes to M, sets addressM to A and asserts writeM
0;JMP
…

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 30
CPU implementation

In this diagram, “c“ denotes “control bit”;

The control bits come from the instruction;
They tell the CPU chip-parts what to do.

pc

Hack CPU architecture

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 31
CPU implementation: Instruction handling

pc

Hack CPU architecture

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 32
CPU implementation: Instruction handling

if c = 1
outM
if c = 0

@5 0000000000000101

inM
writeM

Handling A-instructions

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 33
CPU implementation: Instruction handling

if c = 1
outM
if c = 0

@5 0000000000000101

inM
writeM

Handling A-instructions
Use the instruction’s MSB (op-code) to manipulate the control bits
of the A register and the Mux16 before it.
Effect: A-register  instruction (treated as a value)
(Exactly what the @ xxx instruction specifies: “set A to xxx”)
Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 34
CPU implementation: Instruction handling

if c = 1
outM
if c = 0

1110011111010111
D=D+1;JMP
inM
writeM

Handling C-instructions

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 35
CPU implementation: Instruction handling

opcode bit
comp bits
dest bits
jump bits
if c = 1
outM
if c = 0

1110011111010111
D=D+1;JMP
inM
writeM

Handling C-instructions
Each instruction field (opcode, comp, dest, and jump bits) is handled separately
Each group of bits is used to ”tell” a CPU chip-part what to do
Taken together, the chip-parts end up executing the instruction.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 36
CPU implementation: Instruction handling

opcode bit
comp bits
dest bits
jump bits
if c = 1
outM
if c = 0

1110011111010111
D=D+1;JMP 1

inM
writeM

Handling C-instructions: The opcode bit

Routes the instruction’s MSB to the Mux16

Effect: Primes the A register to get the ALU output.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 37
CPU implementation: Instruction handling

opcode bit
comp bits
011111
dest bits
jump bits
if c = 1
outM
if c = 0

1110011111010111
D=D+1;JMP
inM
writeM

Handling C-instructions: The computation bits

• Routes the instruction’s c-bits to the ALU control bits
• Routes the instruction’s a-bit to the Mux16

Effect: the ALU computes the specified function

and emits the resulting value to the ALU output

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 38
CPU implementation: Instruction handling

opcode bit
comp bits
dest bits
jump bits

outM

1110011111010111
D=D+1;JMP
inM
writeM

ALU output:
• Result of ALU calculation
• Fed simultaneously to D-register, A-register, data memory
• Each enabled/disabled by its control bit

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 39
CPU implementation: Instruction handling

opcode bit
comp bits
dest bits
jump bits

outM

1110011111010111
D=D+1;JMP
inM
writeM

Handling C-instructions: The destination bits

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 40
CPU implementation: Instruction handling

opcode bit
comp bits
dest bits 1
jump bits 0

outM

1110011111010111
D=D+1;JMP
inM
writeM
0

Handling C-instructions: The destination bits

Routes the instruction's d-bits to the control (load) bits of the
A-register, D-register, and to the writeM bit

Effect: Only the enabled destinations commit to the ALU output

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 41
CPU implementation: Instruction handling

opcode bit
comp bits
1 011111
dest bits
jump bits 0

outM

1110011111010111
D=D+1;JMP 1

inM
writeM
0
0

Handling C-instructions: Recap

• Executes dest = comp

• Figures out which instruction to execute next

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 42
CPU implementation: Control

pc

Hack CPU architecture

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 43
CPU implementation: Control

111accccccdddjjj

16

load zr ng
1

pc
16
...
address of next
PC abstraction instruction
Outputs the address of the next instruction, has three states:
reset: PC  0

no jump: PC++

jump: if (condition) PC  A // Note: A was already set to the jump address

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 44
CPU implementation: Control

111accccccdddjjj

16

load zr ng
1

pc
16
...
address of next
PC abstraction instruction
Outputs the address of the next instruction, has three states:
reset: PC  0

no jump: PC++

jump: if (condition) PC  A // Note: A was already set to the jump address

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 45
CPU implementation: Control
Symbolic
syntax:
dest = comp ; jump

Binary
1 1 1 a c c c c c c d d d j1 j2 j3
syntax:

jump j1 j2 j3 condition f
null 0 0 0 no jump
JGT 0 0 1 if (ALU out > 0) jump
JEQ 0 1 0 if (ALU out = 0) jump
out
JGE 0 1 1 if (ALU out ≥ 0) jump ALU
JLT 1 0 0 if (ALU out < 0) jump
JNE 1 0 1 if (ALU out ≠ 0) jump
JLE 1 1 0 if (ALU out ≤ 0) jump
zr = (out == 0, 1, 0)
JMP 1 1 1 Unconditional jump
zr ng ng = (out < 0, 1, 0)

We can use gate logic to compute:

J (j1, j2, j3, zr, ng) = 1 if condition is true
0 otherwise

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 46
CPU implementation: Control

111accccccdddjjj

16

load zr ng
1

pc
16
...
PC implementation address of next
instruction
if (reset = 1) PC  0 // reset
else
if ( J (jump bits, zr, ng) = 1) PC  A // jump
else PC++ // next instruction

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 47
CPU implementation

pc

• Executes the current instruction

• Figures out which instruction to execute next.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 48
Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 49
Hack computer

Instruction Memory CPU Data Memory

instruc- write
D register
tion
read
program A register ALU Data
address
address PC

screen memory map

keyboard mem. map

I/O devices
• Screen
• Keyboard

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 50
Screen
load
Physical screen
Screen 0 1 2 3 4 5 6 7 8 ... 511
0 0000000010101111 0 ...
Screen refresh ...
1 0000000000000000 1
...
in 31 1000000000000000
32 0000101000000000
16
... ...
33 0000000000000000 out
...
63 0000000000000000
address 16
... ...
255
8159 0000000010101101
13 8160 0000000000000000
...
/** Memory of 8K 16-bit registers
8191 0000000000000000 with a display-unit side effect. */
CHIP Screen {
IN address[13], in[16], load;
OUT out[16];
Implemented as a built-in 8K BUILTIN Screen;
memory chip named Screen CLOCKED in, load;
}

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 51
Keyboard

Keyboard
out
0000000000000000
16

refresh

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 52
Keyboard

Keyboard
out
0000000000000000
0000000001001011 k
16

refresh

code('k') = 75

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 53
Keyboard

Keyboard
out
0000000000000000
16

refresh

/** 16-bit register, outputs the character code of the currently

Implemented as a built-in
pressed keyboard key, or 0 if no key is pressed */
16-bit memory register CHIP Keyboard {
named Keyboard OUT
out[16];
BUILTIN Keyboard;
}

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 54
Chapter 5: Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 55
Memory

Overview
Instruction Memory CPU Symbolic programming
Memory
• Intro • Control
• Computer architecture • Variables
instruc- write
D register
• The Hack CPU
tion • Labels
read
•program
Input / output A register ALU Data
address
• Memory address PC

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 56
Memory: Implementation
load

Memory
0

in

16 RAM16K
out
address 16
16383
15 16384
Screen
(8K)
24575
24576 Keyboard

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 57
Memory: Implementation
load
in
built in project 3
Memory 16
0 out
RAM16K
16
in address

16 14
RAM16K
out
address 16 in
16383
15 16
16384 Screen out
Screen address
16
(8K) 13
24575 built-in chip
24576 Keyboard
out
Keyboard
16
built-in chip
Memory architecture
• An aggregate of three chip-parts: RAM16K, Screen, Keyboard
• Single address space, 0 to 24576 (0x6000)
• Maps the address input onto the address input of the relevant chip-part.
Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 58
Instruction memory

Overview
Instruction Memory CPU Symbolic programming
Memory
• Intro • Control
• Computer architecture • Variables
instruc- write
D register
• The Hack CPU
tion • Labels
read
•program
Input / output A register ALU Data
address
• Memory address PC

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 59
Instruction memory

Hack Program Overview

Instruction Memory CPU Symbolic programming
Memory
0000000000001101 • Intro • Control
1110101001010101
0000000000000001
1110101001101011
• Computer architecture • Variables
instruc- write
0000001100110101 D register
1110010111011111 • The Hack CPU
tion • Labels
. read
. load •program
Input / output A register ALU Data
.
1111001001100111 address
• Memory address PC

Instruction memory Loading a program

Implemented as a built-in plug-
• Physical: Replace the ROM chip
and-play chip named ROM32K
• Simulator: Load a file containing instructions
(pre-loaded with a program)

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 60
Instruction memory

Hack Program Overview

Instruction Memory CPU Symbolic programming
Memory
0000000000001101 • Intro • Control
1110101001010101
0000000000000001
1110101001101011
• Computer architecture • Variables
instruc- write
0000001100110101 D register
1110010111011111 • The Hack CPU
tion • Labels
. read
. load •program
Input / output A register ALU Data
.
1111001001100111 address
• Memory address PC

/** Read-Only memory (ROM),

Instruction memory acts as the Hack computer instruction memory. */
Implemented as a built-in plug- CHIP ROM32K {
and-play chip named ROM32K IN address[15];
OUT out[16];
(pre-loaded with a program) BUILTIN ROM32K;
}

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 61
Chapter 5: Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 62
Hack computer architecture

ROM32K
Overview CPU Memory
Symbolic programming
• Intro • Control
• Computer architecture • Variables
instruc- write
D register
• The Hack CPU
tion • Labels
read
•program
Input / output A register ALU Data
address
• Memory address PC

Remaining challenge
Integrate into a single chip, named Computer

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 63
Computer abstraction

Assumption

The computer Computer

is loaded with
a program
written in the
Hack machine
language

reset
To execute the stored program:
set reset ← 1, then
set reset ← 0

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 64
Computer abstraction

Assumption

The computer Computer

is loaded with
a program if (reset == 1), executes the first
written in the
instruction in the stored program
Hack machine
language if (reset == 0), executes the next
instruction in the stored program

reset
To execute the stored program:
set reset ← 1, then
set reset ← 0

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 65
Computer implementation

reset

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 66
Computer implementation

reset
Implementation
Connect the three chip-parts
along these lines.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 67
Computer implementation

reset

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 68
Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Guidelines

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 69
Computer Architecture

reset

Project 5
• CPU

• Memory

• Computer

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 70
CPU

/** Central Processing unit.

Executes instructions written in Hack machine language.
CHIP CPU {
IN
inM[16], // Value of M (RAM[A])
instruction[16], // Instruction to execute
reset; // Signals whether to execute the first instruction
// (reset==1) or next instruction (reset == 0)
OUT
outM[16] // Value to write to the selected RAM register
writeM, // Write to the RAM?
addressM[15], // Address of the selected RAM register
pc[15]; // Address of the next instruction

PARTS:
//// Put you code here
}

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 71
CPU

111001 1111010 111

Implementation tips
• All the chip-parts seen here were built in projects 1, 2, 3
• But: we’ll use their built-in versions
• Use HDL to unpack the instruction bits and connect them to the control bits of chip-parts
• Use gate logic to compute the address of the next instruction.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 72
Computer Architecture

reset

Project 5:
• CPU

• Memory

• Computer

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 73
Memory
load Memory.hdl
/** Complete address space of the computer’s data memory,
Memory including RAM, screen memory map, and keyboard memory map.
0 Outputs the value of the memory location specified by address.
If (load==1), the in value is loaded into the memory location specified by address.
Addressing space rules:
in
Only the upper 16K+8K+1 words of the memory are used.
16 RAM16K Access to address 0 to 16383 (0x0000 to 0x3FFF) results in accessing the RAM;
out Access to address 16384 to 24575 (0x4000 to 0x5FFF) results in accessing the Screen memory map;
16 Access to address 24576 (0x6000) results in accessing the Keyboard memory map.
address 16383 */
16384
15 CHIP Memory {
Screen
IN address[15], in[16], load;
(8K memory map)
OUT out[16];
24575
PARTS:
24576 Keyboard //// Put your code here.
}

Implementation tips
• Two bits in the address input can be used to determine the target memory-part (RAM16K, Screen, Keyboard)
• The remaining bits of the address input are the target address within the target memory-part
• Do the read/write specified by the Memory’s inputs,
and output the value of the selected memory-part[address] to the Memory’s out output.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 74
Memory
load Memory.hdl
/** Complete address space of the computer’s data memory,
Memory including RAM, screen memory map, and keyboard memory map.
0 Outputs the value of the memory location specified by address.
If (load==1), the in value is loaded into the memory location specified by address.
Addressing space rules:
in
Only the upper 16K+8K+1 words of the memory are used.
16 RAM16K Access to address 0 to 16383 (0x0000 to 0x3FFF) results in accessing the RAM;
out Access to address 16384 to 24575 (0x4000 to 0x5FFF) results in accessing the Screen memory map;
16 Access to address 24576 (0x6000) results in accessing the Keyboard memory map.
address 16383 */
16384
15 CHIP Memory {
Screen
IN address[15], in[16], load;
(8K memory map)
OUT out[16];
24575
PARTS:
24576 Keyboard //// Put your code here.
}

Implementation tips (continued)

• Use builtin memory-parts (RAM16K, Screen, Keyboard), and builtin logic gates, as needed.
• Optional: Start by building a basic Memory chip that outputs two bits, say, loadRAM and loadScreen,
indicating if the addressed memory-part is the RAM or the Screen
• Then complete the final Memory chip, in which these two bits can become internal pins.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 75
Computer

reset

Project 5:
• CPU

• Memory

• Computer

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 76
Computer

reset

/** The Hack computer, including CPU, RAM and ROM, loaded with a program.
When (reset==1), the computer executes the first instruction in the program;
When (reset==0), the computer executes the next instruction in the program. */
CHIP Computer {
IN reset; Implementation tips
PARTS: Use the built-in ROM32K
// Put your code here.
}
Follow the diagram, and use HDL to connect the three chip-parts

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 77
Computer Architecture

• Basic architecture • Memory

• Fetch-Execute cycle • Computer
• The Hack CPU • Project 5: Chips
• Input / output • Project 5: Testing

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 78
Testing the Computer chip
Testing logic Computer.hdl

/** The Hack computer, including CPU, RAM and ROM,

• Load Computer.hdl into the loaded with a program. */
hardware simulator CHIP Computer {
IN reset;
• Load a Hack program
PARTS:
into the ROM32K chip-part //// Completed HDL code
}
• Run the clock enough cycles
to execute the program

Test programs
• Add.hack:
RAM[0] ← 2 + 3

• Max.hack:
RAM[2] ← max(RAM[0], RAM[1])

• Rect.hack:
Draws a rectangle of RAM[0] rows
of 16 pixels each.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 79
Testing the Computer chip
ComputerMax.tst
Testing logic load Computer.hdl,
output-file ComputerMax.out,
• Load Computer.hdl into the compare-to ComputerMax.cmp,
hardware simulator output-list time reset ARegister[] DRegister[] PC[]
RAM16K[0] RAM16K[1] RAM16K[2];

• Load a Hack program // Loads a Hack program (that computes R2 = max(R0,R1))

ROM32K load Max.hack,
into the ROM32K chip-part
// Test 1: computes max(3,5)
• Run the clock enough cycles set RAM16K[0] 3,
set RAM16K[1] 5,
to execute the program output;
repeat 14 {
tick, tock, output;
Test programs }

• Add.hack: // Resets the PC

set reset 1,
RAM[0] ← 2 + 3 tick, tock, output;

• Max.hack: // Test 2: computes max(23456,12345)

set reset 0,
RAM[2] ← max(RAM[0], RAM[1])
set RAM16K[0] 23456,
set RAM16K[1] 12345,
• Rect.hack: output;
Draws a rectangle of RAM[0] rows repeat 14 {
of 16 pixels each. tick, tock, output;
}

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 80
Testing the Computer chip
Testing logic
• Load Computer.hdl into the
hardware simulator
• Load a Hack program
into the ROM32K chip-part
Rect.hack output:
• Run the clock enough cycles
to execute the program
R0

Test programs
• Add.hack:
RAM[0] ← 2 + 3

• Max.hack:
RAM[2] ← max(RAM[0], RAM[1]) Test script
• Rect.hack: • ComputerRect.tst
Draws a rectangle of RAM[0] rows
of 16 pixels each. • Inspect it, understand the testing logic.

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 81
What’s next?

abstraction
writing
machine low-level
language p4
programs

developing
an assembler p6 Next lecture

abstraction p5 hardware platform

building a p2 p3
computer abstraction
computer
building
abstraction
p1
ALU, RAM
chips building
elementary
logic gates gates

This lecture

Nand to Tetris / www.nand2tetris.org / Chapter 5 / Copyright © Noam Nisan and Shimon Schocken Slide 82