From Nand to Tetris(Nand2tetris) Project 5
Von Neumann Architecture and the CPU
Turing Machine is such a concept that one machine can do different kinds of tasks, it’s a machine of machines. Von Neumann designed this architecture and make Turing machine possible.
The picture above is an abstract of the modern computer system, let’s start from the heart of the computer — CPU.
INPUTS:
The CPU will take in 3 inputs
- Instruction. CPU can take address instruction and computing instruction, so how do we distinguish them? Remember all the instructions, data, or label are all represented by a 16 bit binary number. Noam and Shimon decided to use the first bit from left to right to represent the type of instruction. If the first bit is zero then it’s an address instruction, otherwise it’s a computing instruction. For example:
0000 0000 0000 0001 will be translated into @1, this is an A-instruction.
1000 0000 0000 0001 will be translated into D&A;JGT, and this is a C-instruction.If we want to know how to translate the C-instruction, we will have to look at the picture below.
2. Data Memory: the data stored in the current working memory slot.
3. reset: 1 bit in charge of resetting the whole system(which is to set PC to 0).
OUTPUT:
- outM: the result of the previous cycle of computation.
- writeM: the load bit deciding whether we write to RAM or not.
- addressM: the location of the the RAM slot that we want to write to.
- PC: program counter, it could take a 16 bit data as input, and it has 3 load bits: inc, reset, load. this PC register is deciding which line of code to process, and if we reset the PC, all the program will be terminated and we are back to line 0.
Now we can take a closer look at the whole CPU system.
the left most Mux16 is dealing with the instruction input. Remember the instruction can be an Address, or it can also be an Instruction. The control bit for the Mux. Let’s imagine we are dealing with a @100 instruction, the 100 should go into the A-register, and we should set the A-register’s load bit to 1. And this 100 will also go into the Mux16 in the middle of the picture. We still want this Mux16 to output 100 because we don’t care at this point what the input from Memory is, we only want the system to remember the value stored at RAM[100], after this whole process, the ALU should only output “y”, so we can zero the “x” input and return “x + y”, then the output will be saved into D-Register, A-Register, and also be copied to PC’s input. so @100’s next instruction can be a lot of things. It can be D=A, if that’s the case we can set the D-Register’s control bit to 1 and the value of previous output, which is 100, will be stored in D-Register; or the next instruction can be “0;JMP”, then the control bit of PC will be set into load =1, and now the PC’s output will be 100, and we will go to ROM[100] to process the next line of instruction; or it can be M=A, in the previous cycle, the output of A register was also emitted by the system in the name of “addressM”, and if we set the writeM bit to 1, then RAM[100] will be given a value which is the output of CPU — 100, M=A. It can really do a lot of things with this CPU, we just need to know how to manipulate those control bits to let them do the right things.
CHIP CPU { IN inM[16], // M value input (M = contents of RAM[A])
instruction[16], // Instruction for execution
reset; // Signals whether to re-start OUT outM[16], // M value output writeM, // Write to M? addressM[15], // Address in data memory (of M) pc[15]; // address of next instruction PARTS: //ARegister Not(in=instruction[15], out=aload); And(a=instruction[15], b=instruction[5], out=instructionloadA); /** the first bit(instruction[15] and d1(instruction[5] is deciding whether we save the value to A-Regis, if the first bit is 1 and instruction[5] is 1, we are going to save the output to A-Register, because in the instruction, d1(instruction[5]) is deciding where to store value's when it is a C-Instruction. if the first bit is 0, no matter what, we will save the input to A-Register.*/ Or(a=aload, b=instructionloadA, out=aregload); ARegister(in=mux1out, load=aregload, out=aregisterout, out[0..14]=addressM); //DRegister And(a=instruction[15], b=instruction[4], out=dregload);
/** only if the first bit is 1, and d2(instruction[4] is 1, then we save to D register */ DRegister(in=aluOut, load=dregload, out=alux); //Mux1: the reason why we need this is for situations like A=A+1, to make it simple I'm testing to see if aload decide the output of Mux1, if Aload=1 means this is an A-instruction, then we will save this value into our a-register, if it is a c instruction, we will use our previous alu output. //*************** REMEMBER: if it's not an A-instruction, we should never let the Mux's sel to take in the value of the instruction.*/ Mux16(a=aluOut, b=instruction, sel=aload, out=mux1out); //Mux2 And(a=instruction[15], b=instruction[12], out=mux2load);
/** only if both of the first bit and the "a" bit is 1, then we start to use the value we get from M, otherwise we will work on A */ Mux16(a=aregisterout, b=inM, sel=mux2load, out=aluy); //ALU /** the load bit of the ALU is decided by instruction[6..11] */
/** I have to say that this design is really elegant, we have two numbers, how could the ALU output 1? well, first, it turns both input into 0, and negate them on the bit level, so both of them will be 1111 1111 1111 1111, and then add them up, we will get a 1111 1111 1111 1110, then we negate it again on the bit level, then we get 0000 0000 0000 0001, which is 1, this is awesome*/ ALU(x=alux, y=aluy, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], out=aluOut, out=outM, zr=zr, ng=ng); //PC /** Program Counter is deciding where to jump to */
/** if the j bits(instruction[0..2]) are not 000, we should start to manipulate the PC's load bits */ Jmp(in=instruction, ng=ng, zr=zr, load=pcload, inc=inc); PC(in=aregisterout, load=pcload, inc=inc, reset=reset, out[0..14]=pc); //WriteM And(a=instruction[3], b=instruction[15], out=writeM);}CHIP Jmp { IN in[16], zr, ng; OUT load, inc; PARTS: Not(in=ng, out=notng); Not(in=zr, out=notzr); //remember notng is not equal to pos!!! And(a=notng, b=notzr, out=pos); And(a=in[0], b=pos, out=checkpositive); And(a=in[1], b=zr, out=checkzero); And(a=in[2], b=ng, out=checknegative); Or(a=checkpositive, b=checkzero, out=positiveorzero); Or(a=positiveorzero, b=checknegative, out=preload); And(a=in[15], b=preload, out=notinc, out=load); Not(in=notinc, out=inc);
/** if the load bit is zero, then inc is 1, else, inc is 0 */}After we understand the CPU, let's look at the full picture.
the instruction is from the ROM32K, and the return value of the PC will go to ROM to tell which line of code are we processing next.
inM is from the RAM, the RAM location that we will work on is actually decided by the last cycle’s A-Register’s output. REMEMBER we are in a sequential system. This inputM is decided by the addressM output, which was a side product of the A-Register, for example, if we have a command @128; M=5, the first @128 command has set the A-Register’s value to 128, and at the same time, the output of A-Register will go to addressM, and the next round, memory use the addressM, to find the RAM[128] and set the writeM bit to 1, because we are about to change the value stored there to be 5. “reset” is just a one time thing, it will be pressed at the beginning, PC will go to line 0 of ROM to start taking commands, and after we read a command from the ROM, we put the command into the instruction bus and send it to CPU, CPU will decide what kind of calculation it would take.
Actually, for me, the most interesting part of the CPU emulation is understanding the control bits of ALU. How to manipulate the control bits of ALU to get the answer that we want. This is related to binary manipulations, and if we take some time to look at this table to think about the zx, nx, zy, ny, f, no bits of ALU, and why they can yield +1, -1 & | results, we will find them interesting and elegantly designed.
