El computador - CS04/CS05
En esta ocasión se implementaá un computador siguiendo una arquitectura Von Neumann, se empezará implementando un mapa de memoria, pasando luego por la CPU y concluyendo finalmente con la combinación de todas las piezas para llegar a un computador basico.
Este capitulo no contara con muchos diagramas, pero se espera que el HDL sea lo suficientemente auto-explicativo.
- Las piezas que se necesitaran
- Implementando la Memoria
- Implementando la CPU - reto2-1
- Combinando las piezas
- Agregando bugs a la CPU - reto2-2 - reto2-3
- Des-ensamblando codigo - reto1
- Creando un nuevo tipo de instrucciones para la CPU - reto3
Table of contents generated with markdown-toc
Las piezas que se necesitaran
Para construir el computador basico necesitaremos tres chips:
- Una memoria ROM que almacenara las instrucciones a ejecutar por la CPU.
- Una CPU que ejecutara las instrucciones almacenadas en la ROM.
- Una memoria RAM que nos permitira guardar “variables” y datos.
Nosotros unicamente implementaremos la CPU y la RAM ya que usaremos una built-in ROM previamente desarrollada por los autores del curso nand2tetris.
Implementando la Memoria
Conviene aclarar que en nuestra arquitectura la memoria y la RAM no son lo mismo, la memoria es un dispositivo que mapea otros dispositivos incluido la RAM para que puedan ser accedidos y modificados por la CPU.
Para su implementación se siguio una idea similar a la seguida para implementar la RAM, usando los bits mas significativos como bits selectores de dispositivos.
Por ejemplo, nuestra memoria es de 32K registros, y nuestra RAM es de 16K, se ve entonces que con un bus de direcciones de 15 bits los primeros 16k direcciones empiezan en 0.
CHIP Memory {
IN in[16], load, address[15];
OUT out[16];
PARTS:
// Put your code here:
DMux(in=load, sel=address[14], a=selram, b=selscrorkbd);
DMux(in=selscrorkbd, sel=address[13], a=selscr, b=selkbd);
RAM16K(in=in, load=selram, address=address[0..13], out=a);
Screen(in=in, load=selscr, address=address[0..12], out=b);
Keyboard(out=c);
Mux16(a=b, b=c, sel=address[13], out=d);
Mux16(a=a, b=d, sel=address[14], out=out);
}
Implementando la CPU - reto2-1
La parte del circuito encargada de decodificar las condiciones de salto en la CPU
CHIP CPU {
IN inM[16], // M value input (M = contents of RAM[A])
instruction[16], // Instruction for execution
reset; // Signals whether to re-start the current
// program (reset==1) or continue executing
// the current program (reset==0).
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:
//i xx a c1c2c3c4c5c6 d1d2d3 j1j2j3
// Is C instruction?
And(a=instruction[15], b=instruction[14], out=and1);
And(a=and1, b=instruction[13], out=isCInstruction);
// Put your code here:
Mux16(a=instruction, b=aluout, sel=isCInstruction, out=val); // NOTICE
// i
Not(in=instruction[15], out=noti);
// Can write on A register?
Mux(a=false, b=instruction[5], sel=isCInstruction, out=saveOnA);
Or(a=noti, b=saveOnA, out=canWriteARegister); //NOTICE, DONE
ARegister(in=val, load=canWriteARegister, out=aOut, out[0..14]=addressM[0..14]);
// sel=a
Mux16(a=aOut, b=inM, sel=instruction[12], out=A-M);
Mux(a=false, b=instruction[4], sel=isCInstruction, out=canWriteDRegister);
DRegister(in=aluout, load=canWriteDRegister, out=dOut); // NOTICE
// Si i==1, los c deben entrar a la ALU
// Si i==0, debe entrar 0 a la ALU
//Mux16(a[6..15]=false, a[5]=true, a[4]=false, a[3]=true, a[2]=false, a[1]=true, a[0]=false, b[6..15]=false, b[0..5]=instruction[6..11], out=computation);
// @32767
// 0 111111111111111
// si i==0, instruction[6..11] no entran en la ALU
ALU(x=dOut, y=A-M, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], zr=isZero, ng=isNotGreatThanZero, out=outM, out=aluout);
//ALU(x= ,y= ,zx= ,nx= ,zy= ,ny= ,f= ,no= ,out= ,zr= ,ng= );
// JJJ Condition (Jump condition)
Mux(a=false, b=isNotGreatThanZero, sel=instruction[2], out=isNotGreatThanZeroMux);
Mux(a=false, b=isZero, sel=instruction[1], out=isZeroMux);
// si isZero == true
// entonces isZeroMux == true, si instruction[1] == true
Not(in=isNotGreatThanZero, out=isGreatThanZero);
Not(in=isZero, out=isNotZero);
And(a=isNotZero, b=instruction[0], out=instr);
Mux(a=false, b=isGreatThanZero, sel=instr, out=isGreatThanZeroMux);
// Instrucciones tipo-c deben chequear que los tres bits mas significativos sean == 1
Or(a=isZeroMux, b=isNotGreatThanZeroMux, out=isLessOrEqualZero);
Or(a=isLessOrEqualZero, b=isGreatThanZeroMux, out=JJJCondition);
And(a=JJJCondition, b=isCInstruction, out=JJJConditionC);
Not(in=reset, out=resetNeg);
Not(in=JJJConditionC, out=condNeg); // NOTICE, if condition is true, no increment
Or(a=resetNeg, b=condNeg, out=canInc);
PC(in=aOut, reset=reset, inc=canInc, load=JJJConditionC, out[0..14]=pc);
And(a=instruction[3], b=isCInstruction, out=writeM);
//Mux(a=false, b=instruction[4], sel=instruction[15], out=writeM);
//CPU line 29 error
}
Combinando las piezas
Ahora ya podemos unir las piezas y darle vida al Computer:
CHIP Computer {
IN reset;
PARTS:
// Put your code here:
CPU(inM=outMMemory, instruction=actualInstruction, reset=reset, outM=outMCpu, writeM=canWriteM, addressM=addressMCpu, pc=nextInstruction);
ROM32K(address=nextInstruction, out=actualInstruction);
Memory(in=outMCpu, load=canWriteM, address=addressMCpu, out=outMMemory);
}
Agregando bugs a la CPU - reto2-2 - reto2-3
Vamos ahora a realizar un ejercicio extraño, introducir un error en la CPU para mejorar nuestro entendimiento de la misma.
Supongase que el bug que se quiere introducr es como se describe a continuación:
Considere que la implementación de la CPU tiene un error. Dicho error ocurre al ejecutar la instrucción 0000 0011 0000 0110 que está almacenada en la posición de memoria 16. Luego de ejecutar la instrucción el programa continúa en la posición de memoria 32. Indique qué valores podrían tener los registros A, D y PC justo antes y justo después de ejecutar la instrucción.
Al decodificar manualmente la instrucción vemos como deberia funcionar la instrucción: 0 00 0 001100 000 110
Funcionamiento correcto: @774
Funcionamiento con bug: D;JLE
Esto nos dice que el problema viene de no validar que la instruccion sea tipo C en el decodificador JJJ de salto.
CHIP CPUerror2 {
IN inM[16], // M value input (M = contents of RAM[A])
instruction[16], // Instruction for execution
reset; // Signals whether to re-start the current
// program (reset==1) or continue executing
// the current program (reset==0).
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:
//i xx a c1c2c3c4c5c6 d1d2d3 j1j2j3
// Is C instruction?
And(a=instruction[15], b=instruction[14], out=and1);
And(a=and1, b=instruction[13], out=isCInstruction);
// Put your code here:
Mux16(a=instruction, b=aluout, sel=isCInstruction, out=val); // NOTICE
// i
Not(in=isCInstruction, out=noti);
// d1
Mux(a=false, b=instruction[5], sel=isCInstruction, out=saveOnA);
Or(a=noti, b=saveOnA, out=canWriteARegister); //NOTICE, DONE
ARegister(in=val, load=canWriteARegister, out=aOut, out[0..14]=addressM[0..14]);
// sel=a
Mux16(a=aOut, b=inM, sel=instruction[12], out=A-M);
Mux(a=false, b=instruction[4], sel=isCInstruction, out=canWriteDRegister);
DRegister(in=aluout, load=canWriteDRegister, out=dOut); // NOTICE
// Si i==1, los c deben entrar a la ALU
// Si i==0, debe entrar 0 a la ALU
//Mux16(a[6..15]=false, a[5]=true, a[4]=false, a[3]=true, a[2]=false, a[1]=true, a[0]=false, b[6..15]=false, b[0..5]=instruction[6..11], out=computation);
// @32767
// 0 111111111111111
// si i==0, instruction[6..11] no entran en la ALU
ALU(x=dOut, y=A-M, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], zr=isZero, ng=isNotGreatThanZero, out=outM, out=aluout);
//ALU(x= ,y= ,zx= ,nx= ,zy= ,ny= ,f= ,no= ,out= ,zr= ,ng= );
// JJJ Condition (Jump condition)
Mux(a=false, b=isNotGreatThanZero, sel=instruction[2], out=isNotGreatThanZeroMux);
Mux(a=false, b=isZero, sel=instruction[1], out=isZeroMux);
// si isZero == true
// entonces isZeroMux == true, si instruction[1] == true
Not(in=isNotGreatThanZero, out=isGreatThanZero);
Not(in=isZero, out=isNotZero);
And(a=isNotZero, b=instruction[0], out=instr); // Se swap j3 y j1
Mux(a=false, b=isGreatThanZero, sel=instr, out=isGreatThanZeroMux);
// Instrucciones tipo-c deben chequear que los tres bits mas significativos sean == 1
Or(a=isZeroMux, b=isNotGreatThanZeroMux, out=isLessOrEqualZero);
Or(a=isLessOrEqualZero, b=isGreatThanZeroMux, out=JJJConditionC);
//Not(in=foo, out=JJJConditionC);
//And(a=JJJCondition, b=isCInstruction, out=JJJConditionC);
Not(in=reset, out=resetNeg);
Not(in=JJJConditionC, out=condNeg); // NOTICE, if condition is true, no increment
Or(a=resetNeg, b=condNeg, out=canInc);
PC(in=aOut, reset=reset, inc=canInc, load=JJJConditionC, out[0..14]=pc);
And(a=instruction[3], b=isCInstruction, out=writeM);
//Mux(a=false, b=instruction[4], sel=instruction[15], out=writeM);
//CPU line 29 error
}
Considerando lo anterior, los los registros A, D y PC podrian almacenar los siguientes valores antes de ejecutar la instruccion: D=-33, A=32, PC=16 y luego de ejecutar la instrucción: D=-33, A=774, PC=32.
Tengase en cuenta que no se necesita que el registro D tenga el valor -33, sino que sea menor o igual a 33, ademas tambien es importante hacer notar que gracias a los tiempos de propagación es factible decir que se carga primero en el PC el valor 32 y luego A se hace igual a 774.
Para resumir, el cambio que se efectuo en la CPU original fue el siguiente:
- Se quito la comprobacion de intruccion tipo C en la seccion del circuito dedicada a las condiciones JJJ
Des-ensamblando codigo - reto1
// A instruction
0 11 1 111111 111 111 // @32767
// C instruction
1 11 0 110000 010 000 // D=A
// var foo = 32767
// A instruction
0 00 0 000000 000 001 // @1
// C instruction
1 11 0 000010 010 000 // D=D+A
// foo = foo + 1
// A instruction
0 00 0 000000 000 000 // @0
// C instruction
1 11 0 001100 001 000 // M=D
// RAM[0]=foo
Comportamiento esperado, ilustrado en un lenguaje de alto nivel:
var foo = 32767;
foo = foo + 1; // 32768
RAM[0] = foo;
Se espera que el codigo binario dado guarde en el primer registro de la RAM el resultado de sumar 32767 + 1 y por lo tanto que se guarde el numero 32768 en el registro RAM[0], sin embargo esto no es lo que pasa, cuando ponemos el codigo en el HardwareSimulator, obtenemos un -32768 en RAM[0] en lugar de 32768, lo cual debe su explicación a que el simulador supone que el numero esta en complemento a 2 de 16 bits (cuando en realidad no es asi), razon por la cual interpreta el 100 0 000000 000 000 como un -32768.
Creando un nuevo tipo de instrucciones para la CPU - reto3
Vamos a definir un nuevo tipo de instruccion: Instrucciones tipo-E, E de eraser, este tipo de instrucciones borra (setea a 0) el contenido en un registro determinado a continuacion se especifica la sintaxis:
101 0000000 000 ADC
- A: Si A==true: registro A se setea a 0
- D: Si D==true: registro D se setea a 0
- P: Si C==true: ProgramCounter register se setea a 0
Las instrucciones tipo-E tienen en sus bits mas significativos el codigo 101 el cual especifica que es una instuccion tipo E.
Se inventara la siguiente sintaxis en el lenguaje de ensamblador para este tipo de instrucciones:
- EADC: Borra el valor en A, D y C.
- EA: Borra el valor en A.
- ED: Borra el valor en D.
- EC: Borra el valor en el Program Counter (“lo resetea”)
- EAC: Borra el valor en A y el program counter.
- EDC: Borra el valor en D y el program counter.
- EAD: Borra el valor en A y D.
- E: No borra ningun valor.
Si esta instrucción no existiera, setear a 0 el registro A y el registro D seria relativamente mas tedioso:
@0
D=A
Mientras con con la instruccion tipo E se puede hacer todo en una unica linea.
EAD
Programa de ejemplo en assembly:
@55
D=A+1
EAD // Setea a 0 los registros A y D.
El siguiente enfoque tambien se siguio para setear el registro A.
El program counter y la instruccion tipo-E
A continuación se muestra la implementación de la CPU con la E instruction:
CHIP CPUNewInstruction {
IN inM[16], // M value input (M = contents of RAM[A])
instruction[16], // Instruction for execution
reset; // Signals whether to re-start the current
// program (reset==1) or continue executing
// the current program (reset==0).
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:
//i xx a c1c2c3c4c5c6 d1d2d3 j1j2j3
// Is an E instruction?
Not(in=instruction[14], out=notinstr14);
And(a=instruction[15], b=notinstr14, out=ande1);
And(a=ande1, b=instruction[13], out=isEInstruction);
// Is an C instruction?
And(a=instruction[15], b=instruction[14], out=and1);
And(a=and1, b=instruction[13], out=isCInstruction);
// Input to A register:
Mux16(a=instruction, b=aluout, sel=isCInstruction, out=val1); // NOTICE
Mux16(a[0..15]=val1, b[0..15]=false, sel=canWriteARegister2, out=ainput);
// not(i)
Not(in=instruction[15], out=noti);
// Can write on A Register? d1
Mux(a=false, b=instruction[5], sel=isCInstruction, out=saveOnA);
Or(a=noti, b=saveOnA, out=canWriteARegister1); //NOTICE, DONE
And(a=instruction[2], b=isEInstruction, out=canWriteARegister2);
Or(a=canWriteARegister1, b=canWriteARegister2, out=canWriteARegister);
ARegister(in=ainput, load=canWriteARegister, out=aOut, out[0..14]=addressM[0..14]);
// Input Y to ALU
Mux16(a=aOut, b=inM, sel=instruction[12], out=A-M);
// Can write on D Register?
Mux(a=false, b=instruction[4], sel=isCInstruction, out=canWriteDRegister1);
And(a=isEInstruction, b=instruction[1], out=canWriteDRegister2);
Or(a=canWriteDRegister1, b=canWriteDRegister2, out=canWriteDRegister);
// Input to D register
Mux16(a=aluout, b[0..15]=false, sel=canWriteDRegister2, out=dinput);
DRegister(in=dinput, load=canWriteDRegister, out=dOut); // NOTICE
// Si i==1, los c deben entrar a la ALU
// Si i==0, debe entrar 0 a la ALU
//Mux16(a[6..15]=false, a[5]=true, a[4]=false, a[3]=true, a[2]=false, a[1]=true, a[0]=false, b[6..15]=false, b[0..5]=instruction[6..11], out=computation);
// @32767
// 0 111111111111111
// si i==0, instruction[6..11] no entran en la ALU
ALU(x=dOut, y=A-M, zx=instruction[11], nx=instruction[10], zy=instruction[9], ny=instruction[8], f=instruction[7], no=instruction[6], zr=isZero, ng=isNotGreatThanZero, out=outM, out=aluout);
//ALU(x= ,y= ,zx= ,nx= ,zy= ,ny= ,f= ,no= ,out= ,zr= ,ng= );
// JJJ Condition (Jump condition)
Mux(a=false, b=isNotGreatThanZero, sel=instruction[2], out=isNotGreatThanZeroMux);
Mux(a=false, b=isZero, sel=instruction[1], out=isZeroMux);
// si isZero == true
// entonces isZeroMux == true, si instruction[1] == true
Not(in=isNotGreatThanZero, out=isGreatThanZero);
Not(in=isZero, out=isNotZero);
And(a=isNotZero, b=instruction[0], out=instr);
Mux(a=false, b=isGreatThanZero, sel=instr, out=isGreatThanZeroMux);
// Instrucciones tipo-c deben chequear que los tres bits mas significativos sean == 1
Or(a=isZeroMux, b=isNotGreatThanZeroMux, out=isLessOrEqualZero);
Or(a=isLessOrEqualZero, b=isGreatThanZeroMux, out=JJJCondition);
And(a=JJJCondition, b=isCInstruction, out=JJJConditionC);
//
And(a=isEInstruction, b=instruction[0], out=resetPCEinstruction);
Not(in=reset, out=resetNeg);
Not(in=JJJConditionC, out=condNeg); // NOTICE, if condition is true, no increment
Or(a=resetNeg, b=condNeg, out=canInc);
Or(a=resetPCEinstruction, b=reset, out=restartPC);
PC(in=aOut, reset=restartPC, inc=canInc, load=JJJConditionC, out[0..14]=pc);
And(a=instruction[3], b=isCInstruction, out=writeM);
//Mux(a=false, b=instruction[4], sel=instruction[15], out=writeM);
//CPU line 29 error
}
Hasta pronto.