* From Nand to Tetris / Part I
Nand2Tetris Software Suite From Nand to Tetris in 12 steps - talk
In a nutshell: course introduction and overview, the roles of abstraction and implementation in systems design, the road ahead.
read Introduction chapter of The Elements of Computing Systems (the course’s textbook)
In a nutshell: We will start with a brief introduction of Boolean algebra, and learn how Boolean functions can be physically implemented using logic gates. We will then learn how to specify gates and chips using a Hardware Description Language (HDL), and how to simulate the behaviour of the resulting chip specifications using a hardware simulator. This background will set the stage for Project 1, in which you will build, simulate, and test 15 elementary logic gates. The chipset that you will build this week will be later used to construct the computer’s Arithmetic Logic Unit (ALU) and memory system. This will be done in weeks 2 and 3, respectively.
▶2 way to describe FUnctions • Formula • Truth Table ▶Boolean Identities • Commutative lows x && y = y && x x || y = y || x • Associative lows (x && (y && z)) = ((x && y) && z) (x || (y || z)) = ((x || y) || z) • Distributive lows (x && (y || z)) = (x && y) || (x && z) (x || (y && z)) = (x || y) && (x || z) • De Morgan laws ~(x && y) = ~x || ~y ~(x || y) = ~x && ~y • Idempotence low x && x = x • Double negation ~(~x) = x • • • • • ▶Truth table to Boolean expression? Given truth table how find boolean expression?| x | y | z | f | |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | ~x & ~y & ~z |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | ~x & y & ~z |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | x & ~y & ~z |
| 1 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 |
Constructing a disjunctive normal form formula for it, and it goes like this.
- look at rows which has value 1
- construct expression for that rows
- or all expressions
▶NAND function
| x | y | NAND |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
(x NAND y) = ~(x & y)
▶Theorem: Any Boolean function can be represented using an expression containing &, ~ operations. Proof: (x || y) = ~(~x & ~y)
▶Theorem: Any Boolean function can be represented using an expression containing NAND operations. Proof:
- ~x = (x NADN x)
- (x & y) = ~(x NAND y)
- (x || y) = NOT[ NOT( A AND A ) AND NOT( B AND B )]
- gate diagram:
- functional specification: if(a==1 and b==1) then out=0 else out=1
- truth table
• And functional spec: if (a==1 and b==1) then out=1 else out=0 • Or functional spec: if (a==1 or b==1) then out=1 else out=0 • Not functional spec: if (in==0) then out=1 else out=0 •
▶Composite (Mux, Adder) • 3-wire and functional spec: if (a==1 and b==1 and c==1) then out=1 else out=0
HDL Simulation Test Build in Hardware ▶Xor Gate Requirements • spec: output 1 if one, and only one, of its input is 1. • Truth table:| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
• From Truth table out = 1 when: a And Not(b) Or Not(a) And b
▶Gate Interface • HDL ** Xor gate: out = (a And Not(b)) Or (Not(a) And b)) *
CHIP Xor { IN a, b; OUT out; PARTS: Not (in=a, out=nota); Not (in=b, out=notb); And (a=a, b=notb, out=aAndNotb); And (a=aAndNotb, b=notaAndb, out=out); Or (a=aAndNotb, b=notaAndb, out=out);
}
▶Arrays of Bits • Sometimes we manipulate “together” an array of bits • It is conceptually convenient to think about such a group of bits as a single entity, sometimes termed “bus” - latin word menaing many, multiple. • HDLs will usually provide some convenient notation for handling these buses. ▶Elementary Logic gates- Not
- And
- Or
- Xor
- Mux - Multiplexer if (sel==0) out=a else out=b
- DMux - Demultiplexer
▶16-bit wariants
- Not16
- And16
- Or16
- Mux16
▶Multi-way varianrs
- Or8Way
- Mux4Way16
- Mux8Way16
- DMux4Way
- DMux8Way
DO Project 1: Elementary Logic Gates.
read Chapter 1 of The Elements of Computing Systems.
read Appendix A: Hardware Description Language (HDL) of The Elements of Computing Systems
Manipulating Binary numbers • Addition - Implement
• Subtraction - get fro “free” • Which is Greater? - get for “free” • Multiplication - Postphone to Software • Division - Postphone to software
• Half adder input: a b output: sum carry
| a | b | sum | carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
• Full adder input: a b c output: sum carry
| a | b | c | sum | carry |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| bits | number | 2^n-x |
|---|---|---|
| 0000 | 0 | |
| 0001 | 1 | |
| 0010 | 2 | |
| 0011 | 3 | |
| 0100 | 4 | |
| 0101 | 5 | |
| 0110 | 6 | |
| 0111 | 7 | |
| 1000 | -8 | |
| 1001 | -7 | |
| 1010 | -6 | |
| 1011 | -5 | |
| 1100 | -4 | |
| 1101 | -3 | |
| 1110 | -2 | |
| 1111 | -1 |
▶Computing -x Input: x Output: -x Idea: 2^n-x=1+(2^n-1)-x 2^n-1 = 111111
• Subtracting from 1111 1111 - 0100 = 1011 (we just flip the bits)
• Add 1 fli the bits from right to left, stopping the first time 0 is flipped to 1 1011 + 1 = 1100
▶ The ALU coputes a function on the two inputs, and outputs the result f: one out of a family of pre-defined arithmetic and logical functions. some these functions are arithmetic and some of these functions are logical. • Arithmetic operations integer addition multiplication division • logical operations And Or Xor▶ Whne building ALU should consider how much operations should provide Which operations should the ALU perform? A hardware/software tradeoff.
▶ The Hack ALU • imput: two 16 bit, two’s complement values • output: a 16 bit, two’s complement values • output: two 1-bit values zr,ng
- if out == 0, zr = 1; otherwise zr = 0;
- If out < 0, ng = 1; otherwise ng = 0.
• Which function to compute is set by six 1-bit inputs called zx,nx,zy,ny,f,no
IN x[16], y[16], // 16-bit inputs zx, // zero the x input? nx, // negate the x input? zy, // zero the y input? ny, // negate the y input? f, // compute out = x + y (if 1) or x & y (if 0) no; // negate the out output?
OUT out[16], // 16-bit output zr, // 1 if (out == 0), 0 otherwise ng; // 1 if (out < 0), 0 otherwise
| zx | nx | zy | ny | f | no | Out |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | -1 |
| 0 | 0 | 1 | 1 | 0 | 0 | x |
| 1 | 1 | 0 | 0 | 0 | 0 | y |
| 0 | 0 | 1 | 1 | 0 | 1 | !x |
| 1 | 1 | 0 | 0 | 0 | 1 | !y |
| 0 | 0 | 1 | 1 | 1 | 1 | -x |
| 1 | 1 | 0 | 0 | 1 | 1 | -y |
| 0 | 1 | 1 | 1 | 1 | 1 | x+1 |
| 1 | 1 | 0 | 1 | 1 | 1 | y+1 |
| 0 | 0 | 1 | 1 | 1 | 0 | x-1 |
| 1 | 1 | 0 | 0 | 1 | 0 | y-1 |
| 0 | 0 | 0 | 0 | 1 | 0 | x+y |
| 0 | 0 | 0 | 1 | 1 | 1 | y-x |
| 0 | 0 | 0 | 0 | 0 | 0 | x&y |
| 0 | 1 | 0 | 1 | 0 | 1 | xory |
Combinational vs Sequential:
Combinational: output[t] = function( in[t] ); Sequential: output[t] = function( in[t - 1] );
**************************************************************************************** One should not read too much meaning into the terms “combinational” and “sequential”. They are just terms, not necessarily descriptive. Combinational chips “don’t pay attention” to time, and therefore they cannot maintain what computer scientists sometimes call “state”. For example, they cannot use values that were computed in the previous cycle. In fact, they don’t even know what is a cycle. Sequential chips, on the other hand, can take into account the state in the previous cycle, since they have a clock input. In principle, the HDL programmer can manipulate this clock input just like any other binary input (for example, we can AND a clock input with a data input). But, in this course, all the manipulations of the clock inputs are done by the built-in DFF gate, which is considered primitive (that is, “given”). And, every chip that uses a DFF directly, or uses another chip that uses a DFF, becomes sequential by association. That is, it inherits the sequential time-dependency from its sequential chip parts. – Shimon
Flip Flop out[t]=in[t-1] ▶Memory • Main memory: RAM,…- Data
- Instruction
• Secondary memory: disks,… • Perspective
- Physical
- Logical
▶ The most basic memory element: Register In,Load,out - 1 bit register 16 bit register • Register’s state: the value which is currently stored inside the register • ▶ RAM Unit • RAM abstraction: A sequence of n addressable registers, with address 0 to n-1 • At any given point of time, only one register in the RAM is selected. • k(with of address input): k=log2n • w(word width): No impact on the RAM logic(Hack computer w=16) • RAM is a sequential chip, with a clocked behaviour ▶ •
▶ • ▶ • ▶ Registers • Data Registers Add R1,R2 • Address Registers Store R1,@A▶ Addressing mode Register - Add R1,R2 // R2 <- R2+R1 Direct - Add R1,M[200] // Mem[200] <- Mem[200] + R1 Indirect - Add R1,@A // Mem[A] <- Mem[A] + R1 Immediate - Add 73,R1 // R1 <- R1 + 73
▶ Flow control • loop jump 101 Load R1,0 102 Add 1,R1 103 … … 156 Jump 102
- using label
Load R1,0
loop: Add 1,R1 … Jump loop
• conditional jump JGT R1,0,cont // Jump if R1>0, Jump greater than Subtract R1,0,R1 // R1 <- (0-R1) cont: … //Do something with positive R1
▶ Hack comuter hardware - 3 main elements, 16-bit computer[instruction memory] –instruction bus–> [CPU] <–data in bus, data out bus–> [data memory]
• Data Memory(RAM): a sequence of 16-bit registers: RAM[0], RAM[1], RAM[2] • Instruction Memory(ROM): a sequence of 16-bit registers: ROM[0], ROM[1], ROM[2] seperate memory space • Central Processing Unit (CPU): performs 16-bit instructions • Instruction bus / data bus / address buses
▶ Hack comuter software(written in Hack machine language) - How do we control this computer [ROM] –instruction bus–> [CPU] <–data in bus, data out bus–> [RAM], reset button
• Hack machine language 16-bit A instructions 16-bit C instrcutions
• Hack program = sequence of instructions written in the Hack machine language • reset button
• control
- The ROM is loaded with a Hack program - The program is 16 bit numbers, i place somehow this program into the ROM
- The reset button is pushed
- The programms start running
▶ Hack computer: registers - the Hack machine language recognizes three registers: • D register: Holds 16-bit value which represents a data • A register: Holds 16-bit value which represents either a data value or an address • M register: the 16-bit RAM register address by A, selected memory register, at any given time only one of them is selected
▶ The A-instruction • Syntax: @value value is either
- a non-negative decimalconstant
- a symbol referring to such a constant(later)
• Semantics: @21
- Sets the A register to value
- Side effect RAM[A] becomes the selected RAM register
Example: @21 (1) Sets the A register to 21 (2) RAM[21] becomes the selected RAM register
Usage Example: how set RAM[100] to -1 @100 // A=100 M=-1 // RAM[100]=-1
▶ The C-instruction • Syntax: dest = comp ; jump (both dest and jump are optional) destination,computation where: comp=0,1,-1,D,A,!D,!A,-D,-A,D+1,A+1,D-1,A-1,D+A,D-A,A-D,D&A,D|A,M,!M,-M,M+1,M-1,D+M,D-M,M-D,D&M,D|M pneumonics or symbols that represents some operations.
dest = null, M, D, MD, A, AM, AD, AMD // M refers to RAM[A] jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP // if (comp jump 0) jump to execute the isnstruction in ROM[A]
• Semantics:
- Compute the value of comp
- Stores the result in dest;
- if the Boolean expression (comp jump 0) is true jumps to execute the instruction stored in ROM[A]
Examples: • set the D register to -1 D=-1 // dest = comp
• Set RAM[300] to the value of the D register minus 1 @300 // A=300 M=D-1 // RAM[300]=D-1
• If (D-1==0) jump to execute the instruction stored in ROM[56] @56 // A=56 D-1;JEQ // if (D-1 == 0) goto 56
We can write programs in machine language using two different flavors, ro two different languages, if you will. You can write them symbolically, using, mnemonics and firendly, symbols. If we write programs symbolically we need someone to translate these programs from symbols to binary code.▶ Two ways to express the same semantics • Binary code • Symbolic language
▶ Tha A-instruction: symbolic and binary syntax (16-bit) Semantics: Set the A register to value • Symbolic syntax: @value Where value is either:
- a non-negative decimal constant <= 32767 (2^15 - 1)
- a symbol referring to such a constant(later)
ExampleL: @21 Effect: sets the A register to 21 • Binary syntax: 0value - we start with symbol ‘0’ which tell the computer that this is a A-instruction where value is a 15-bit binary number Example: 0000000000010101 Effect: sets the A register to 21
▶ Tha C-instruction: symbolic and binary syntax (16-bit) • Symbolic syntax: dest = comp ; jump • Binary syntax: 1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
| op code | 1 1 | a c1 c2 c3 c4 c5 c6 | d1 d2 d3 | j1 j2 j3 |
|---|---|---|---|---|
| 1 | not used | comp bits, control | dest bits, represent the destination | jump bits |
| bits that will be | ||||
| send to ALU |
• comp field examination
| comp | comp | c1 | c2 | c3 | c4 | c5 | c6 |
| a=0 | a=1 | ||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| -1 | 1 | 1 | 1 | 0 | 1 | 0 | |
| D | 0 | 0 | 1 | 1 | 0 | 0 | |
| A | M | 1 | 1 | 0 | 0 | 0 | 0 |
| !D | 0 | 0 | 1 | 1 | 0 | 1 | |
| !A | !M | 1 | 1 | 0 | 0 | 0 | 1 |
| -D | 0 | 0 | 1 | 1 | 0 | 1 | |
| -A | -M | 1 | 1 | 0 | 0 | 1 | 1 |
| D+1 | 0 | 1 | 1 | 1 | 1 | 1 | |
| A+1 | M+1 | 1 | 1 | 0 | 1 | 1 | 1 |
| D-1 | 0 | 0 | 1 | 1 | 1 | 0 | |
| A-1 | M-1 | 1 | 1 | 0 | 0 | 1 | 0 |
| D+A | D+M | 0 | 0 | 0 | 0 | 1 | 0 |
| D-A | D-M | 0 | 1 | 0 | 0 | 1 | 1 |
| A-D | M-D | 0 | 0 | 0 | 1 | 1 | 1 |
| D&A | D&M | 0 | 0 | 0 | 0 | 0 | 0 |
| DorA | DorM | 0 | 1 | 0 | 1 | 0 | 1 |
• dest filed mapping
| dest | d1 | d2 | d3 | effect: the value is stored in: |
|---|---|---|---|---|
| null | 0 | 0 | 0 | The value is not stored |
| M | 0 | 0 | 1 | RAM[A] |
| D | 0 | 1 | 0 | D register |
| MD | 0 | 1 | 1 | RAM[A] and D register |
| A | 1 | 0 | 0 | A register |
| AM | 1 | 0 | 1 | A register and RAM[A] |
| AD | 1 | 1 | 0 | A register and D register |
| AMD | 1 | 1 | 1 | A register, RAM[A], and D register |
• jump field mapping
| jump | j1 | j2 | j3 | effect |
|---|---|---|---|---|
| null | 0 | 0 | 0 | no jump |
| JGT | 0 | 0 | 1 | if out>0 jump |
| JEQ | 0 | 1 | 0 | if out=0 jump |
| JGE | 0 | 1 | 1 | if out≥0 jump |
| JLT | 1 | 0 | 0 | if out<0 jump |
| JNE | 1 | 0 | 1 | if out≠0 jump |
| JLE | 1 | 1 | 0 | if out≤0 jump |
| JMP | 1 | 1 | 1 | unconditional jump |
▶ Hack program • A Hack program is a sequence of Hack instructions • White space is permitted(թույլատրված է) • Comments are welcome • They are better way to write Hack program; stay tuned
Symbolic code example of Hack program
// Computes RAM[1]=1+..+RAM[0] // Usage: put a number in RAM[0] @16 // RAM[16] represents i M=1 // i=1 @17 // RAM[17] represents sum M=0 // sum=0
@16 D=M @0 D=D-M @17 // if i>RAM[0] goto 17 D;JGT
@16 D=M @17 M=D+M // sum += i @16 M=M+1 // i++ @4 // goto 4 (loop) 0;JMP
@17 D=M @1 M=0 // RAM[1]=sum @21 // program’s end 0;JMP // infinite loop
▶ Peripherial I/O devices: • Keyboard: used to enter inputs - getting data from users • Screen: used to display outputs - displaying data to users ▶ Screen Memory map (Screen) 256x512 matrix 256 * 512 = 131072 131072 / 16 = 8192 memory map is sequence of 16 bits 0 1 … … 8191we need connect 256x512 2d abstraction with 1d abstraction of Screen[8192]. [0..31] –> [0][0..511] [32..63] –> [1][0..511] ........ • mapping formula screen (row, col) (1) i = 32*row+col/16 word = Screen[i] relative address within chip of Screen, the chip Screen embedded in main RAM word = RAM[16384 + i] absolute address (2) Set the (col%16)th bit of word to 0 or 1 (3) Commit word to the RAM
▶ Keyboard Memory map (Kbd) keyboard 16-bit register - RAM[24576]
• To check which key is currently pressed: (1) probe the contents of the keyboard chip (2) In the Hack computer: probe the contents of RAM[24576] If the register contain 0 no key is pressed
▶ Hack assembly instructions • A-instruction: @value //A=value value is a constant or a symbol referring to such a constant. • C-instruction: dest = comp ; jump M reffres to RAM[A] Semantics: (1) Computes the value of comp (2) Stores the result in dest (3) If the Boolean expression (comp jump 0) is true, jumps to execute the isntruction stored RAM[A].▶ Hack programming • Working with registers and memory • Branching • Variables • Iteration • Pointers • Input / Output
▶ Working with registers and memory • Two standard registers that we have A and D which reside inside the CPU. D: data register A: address / data register • M-register: (Mnemonic) the currently selelcted memory register M=RAM[A], reside inside RAM
- Examples:
// D=10, we want to store number 10 in register D.
// there is no C-instruction to do this
@10
D=A
// D++ //there is C-instrcution to do this D=D+1
// D=RAM[17] @17 D=M
// RAM[17]=0 @17 M=0
// RAM[17]=10 @10 D=A @17 M=D
// RAM[5]=RAM[3] @3 D=M @5 M=D
- Add to numbers example
// Program: Add2.asm
// Computes: RAM[2] = RAM[0] + RAM[1]
// Usage: put values in RAM[0], RAM[1]
@0 D=M @1 D=D+M @2 M=D
- Buil in symbols
symbol value R0 0 R1 1 R2 2 … … R15 15 Screen 16384 KBD 24576 SP 0 LCL 1 ARG 2 THIS 3 THAT 4
- Branching (go to)
// Program: Signum.asm
// Computes: if R0>0
// R1=1
// else
// R1=0
@R0 D=M // D=RAM[0]
@8 D;JGT // if R0>0 goto 8
@R1 M=0 // RAM[1]=0 @10 0;JMP // end of program
@R1 M=1 // R1=1
@10 0;JMP
**************************************************************************************** we can use labels for jump @LABEL translates to @n, where n is the instruction number following the (LABEL) declaration. // tha same program using labels @R0 D=M // D=RAM[0]
@POSITIVE //using a label D;JGT // if R0>0 goto 8
@R1 M=0 // RAM[1]=0 @10 0;JMP // end of program
(POSITIVE) // declaring a label @R1 M=1 // R1=1
(END) @END 0;JMP
- Variables
@temp: find some available memory register (say register n) and use it to represent the variable temp. form now on, each occurance of @temp in the program will be translated into @n.
Variable usage example:
// program flip.asm // flips the values // RAM[0] and RAM[1]
// temp = R1 // R1=R0 // R0=temp
@R1 D=M @temp M=D // temp=R1
@R0 D=M @R1 M=D // R1=R0
@temp D=M @R0 M=D // R0=temp
(END) @END 0;JMP
- Iteration
// Computes: RAM[1] = 1+2+…+n
// Usage: put a number (n) in RAM[0]
@R0 D=M @n M=D // n = R0 @i M=1 // i = 1 @sum M=0 // sum = 0
(LOOP) @i D=M D=D-M @STOP D;JGT // if i > n goto STOP
@sum D=M @i D=D+M @sum M=D // sum = sum + 1 @i M=M+1 // i = i + 1 @LOOP 0;JMP
(STOP) @sum D=M @R1 M=D // RAM[1] = sum
(END) @END 0;JMP
• pseudo code compute: 1+2+…+n n=R0 i=1 sum=0 LOOP: if i > n goto STOP sum = sum + i i = i + 1 goto LOOP STOP: R1=sum •
- Pointers
Variables that stores memory address like arr and i is called pointers.
//for(i=0;i<n;i++)arrr[i]=-1;
(LOOP) // if i ==n goto END @i D=M @n D=D-M @END D;JEQ
// RAM[arr+i]=-1 @arr D=M @i A=D+M M=-1
// i++ @i M=M+1
@LOOP 0;JMP
(END) @END 0;JMP
- Input / Output
Hack RAM
data memory - [0..16K]
screen memory map - [16384..+8k]
keyboard memory map - [24576]
predefined symbols for base addres(offset) SCREEN KBD
// Program: Rectangle.asm // Draws a filled rectangle at the screen’s top left corner. // The rectangle’s width is 16 pixels, and its height is RAM[0]. // Usage: put a non-negtive number (rectangle’s height) in RAM[0].
@R0 D=M @n M=D //n=RAM[0]
@i M=0 // i = 0
@SCREEN D=A @address M=D // address = 16384 (LOOP) @i D=M @n D=D-M @END D;JGT // if i>n goto END
@address A=M M=-1 // RAM[address]=-1 (16 pixels)
@i M=M+1 //i=i+1 @32 D=A @address M=D+M // address=address+32 @LOOP 0;JMP // got LOOP
(END) @END 0;JMP
• Fetching
- Put the location ot the next instruction into the “address” of the program memory
- Get the instruction code itself by reading the memory contents at that location