Implementando una Static RAM y un Program Counter - CS03

Hoy, el objetivo es implementar una RAM estatica (SRAM), esta RAM no es la tipica tarjeta RAM que normalmente se compra para los computadores ya que una SRAM es mas cara que una Dynamic RAM (DRAM), por lo general las SRAM estan dentro de la CPU.

Para completar los objetivos de este capitulo vamos implementar los siguientes chips:

  • Data Flip-Flop (primitive) (Ya implementado)
  • 1-bit Register
  • 16-bit Register
  • 16-bit / 8-register memory
  • 16-bit / 64-register memory
  • 16-bit / 512-register memory
  • 16-bit / 4096-register memory
  • 16-bit / 16384-register memory
  • 16-bit program counter (PC)

Para lograrlo tendremos a nuestra disposicion un Data Flip-Flop que ya ha sido implementado, es decir dicha complejidad se abstrae.

Tabla de contenidos

Table of contents generated with markdown-toc

Conceptos importantes

La grafica de una señal de reloj - concepto1

Como se puede ver en la imagen el tick es la parte de la señal de reloj que vale 0 y el tock es la parte que vale 1, por otra parte el flanco de subida es el momento en el que la señal pasa de 0 a 1, y el flanco de subida el momento en el que la señal pasa de 1 a 0.

En nuestra arquitectura con el flanco de bajada termina un ciclo y empieza el siguiente (Notese que en otras arquitecturas esto puede ser diferente).

Un ciclo tarda un tiempo desde que inicia en el tick hasta que finaliza el tock con un flanco de bajada, este tiempo se conoce como periodo.

El periodo es el tiempo que tarda un ciclo en completarse.

La cantidad de ciclos que se pueden realizar en un segundo es entonces la frecuencia y estas dos magnitudes se relacionan de la siguiente forma:

Diagramas de tiempo - concepto2

A continuación se analiza el estado de los pines a travez del tiempo.

Flip-Flop tipo D

Bit

  • Notese que en ciclo 24 el load(t-1)=1 y el out(t)=0 cuando el out(t-1)=0 porque el in(t-1)=0
  • Notese que en el ciclo 28 load(t-1)=1 y el out(t)=1 cuando el out(t-1)=1 porque el in(t-1)=1

Registro

Memoria RAM

Notas:

  1. En el ciclo 22 se supone que en la posicion en memoria con dirección 01 fue escrito en un ciclo anterior el valor 01.
  2. En el ciclo 23 se supone que en la posición en memoria con dirección 00 fue escrito en un ciclo anterior el valor 55.
  3. En el ciclo 23 aunque en algunos momento el pin load se activa no tiene efecto de escritura en dicha posición porque las operaciones de escritura son sincronicas (circuitos secuenciales).
  4. En el ciclo 25 “05/ 01 “ quiere decir que durante un pequeño plazo de tiempo la salida fue 05 t luego al cambiar la direccion del bus de direcciones se obtiene en la salida el valor que hay almacenado en la posición 01 de la memoria RAM.
  5. En el ciclo 25 el 05 que se observa en el output corresponde al valor escrito en el registro con dirección 00 en el ciclo anterior.
  6. En el ciclo 26 tan pronto cambia el addres cambia el out de la RAM puesto que las operaciones de lectura son combinacionales (asincronicas).
  7. En el ciclo 26 se supone que en un ciclo anterior x RAM7=12, donde x>7.
  8. En el ciclo 28 notese que aunque el pin load esta activado, la RAM sigue realizando operaciones de lectura, solo realizara operaciones de escritura cuando ocurra el flanco de bajada y el load este activado en ese momento.

Observaciones de la RAM: Despues del flanco de bajada la address puede cambiar en cualquier momento y se reflejara “instantaneamente” en el out de la RAM el valor almacenado en el registro que indique el bus de direcciones.

Si un Load cambia de 1 a 0, de 0 a 1 y luego de 0 a 1.

Sus cambios intermedios no tendran efecto (de escritura) en ninguno de los posibles registros a los que apunte el bus de direcciones, puesto que los registros son dispositivos sincronicos cuyo cambio ocurre en el flanco de bajada del reloj.

Si el pin load esta en 0 cuando ocurra el flanco de bajada el registro al que apunte el bus de direcciones sera leido, pero a diferencia de las operaciones de escritura cualquier registro de la ram puede ser leido en cualquier momento t y no se debe esperar al proximo flanco de bajada.

Notese tambien que cuando en el load de los registros el valor es 0 en el tiempo t, en el tiempo t+1 el out del registro sera out(t-1) lo que indica que el registro tiene un out disponble para el multiplexor en cualquier momento.

Notese que el registro es un dispositivo sincronica tanto en operaciones de lectura como de escritura, pero las operaciones de lectura de la RAM se hacen con un circuito combinacional que selecciona la salida del registro que indique el address-bus mediante un Multiplexor8Way16bits por lo que, las operaciones de lectura de la RAM no son sincronicas.

Logica secuencial vs Logica combinacional - concepto3 y concepto4

Se puede explicar con la imagen que un circuito de logica combinacional se puede usar en conjunto con uno de lógica secuencial, por ejemplo en una RAM8 se puede usar un demultiplexor para seleccionar un registro determinado (lógica combinacional) para determinar en que registro almacenar un dato determinado (lógica secuencial), luego se puede usar un circuito combinacional para seleccionar una de las salidas.

Dicho lo anterior podemos enumerar unas diferencias fundamentales entre un circuito lógico combinacional y un circuito lógico secuencial:

  1. Cuando se cambia la entrada en un circuito combinacional su salida cambia asincronamente.
  2. Cuando se cambia la entrada en un circuito secuencial su salida cambia en sincronizacion con el flanco de bajada.

En la RAM implementada, ¿son las operaciones de escritura secuenciales y las de lectura combinacionales? - concepto5

Para detallar mas la pregunta: En relación a las memorias RAM implementadas, ¿se puede decir que las operaciones de escritura son secuenciales y las de lectura son combinacionales?

La respuesta a esta pregunta es si como se ha comprobado anteriormente cuando ocurre un cambio en el bus de direcciones en el out de la RAM se ve reflejado “inmediatemente” el valor almacenado actualmente en el registro al que apunte bus, no es necesario esperar por el flanco de bajada para que este cambio se vea reflejado, en cambio no sucede lo mismo para las operaciones de escritura que al depender del register y al ser estos dispositivos secuenciales, las operaciones de escritura ocurriran unicamente cuando ocurra el flanco de bajada.

Direccion en memoria VS contenido de dicha direccion - concepto6

Son dos conceptos relacionados pero diferentes, si nos referimos a una direccion de memoria nos estamos referiendo a un registro especifico de la memoria RAM, seria como señalar el registro al cual nos referimos con el dedo, en cambio el contenido de una dirección de memoria es la información almacenada en dicho registro, seria similar a leer la información almacenada en el registro señalado anteriormente con el dedo.

NOTA: El contenido de una direción en memoria puede ser a su vez otra dirección en memoria, esto se conoce como puntero.

Calculando en bits el tamaño de una memoria RAM - concepto8

Supongamos que conocemos que el bus de direcciones de nuestra memoria RAM tiene n bits y que cada registro en la memoria tiene un ancho de m bits, ¿Cual es la capacidad de la memoria RAM?

Para responder a esta pregunta primero debemos responder cuantos registros tiene la memoria RAM, esto se puede calcular facilmente con la siguiente ecuación.

La cual es la ecuación de la variación con repetecion de un grupo de 2 elementos (true y false) tomados de n en n, en otras palabras esta es la ecuación que nos dice cuantos numeros (en este caso registros) se pueden representar con los n bits del bus de la RAM.

En este punto ya conocemos el numero de registros de nuestra memoria RAM y tambien conocemos el ancho de cada registro (m bits) con esta información sería simplemente cuestion de multiplicar estos dos valores para obtener la capacidad de la memoria RAM en bits.

Y la anterior es la formula general en función de n y m para calcular el tamaño en bits de una memoria RAM.

Importancia del flanco de bajada del reloj - concepto9

En nuestra arquitectura el flanco de bajada es importante porque es en el momento en el que este ocurre cuando se toma la “instantanea” del tiempo t-1 para realizar las operaciones de escritura.

Entiendase “instantanea” como el valor de los busses in, load y address en el momento en el que ocurre el flanco de bajada, esto quiere decir que dichos valores pueden variar todo lo que quieran antes de que ocurra el flanco de bajada y dicha variación no afectara la entrada en el tiempo t si justo antes de que ocurra el flanco de bajada se deja todo como estaba al principio (refiriendonos a operaciones de escritura)

Este funcionamiento es el que ocasiona que cuando cambiemos el bit de Load en un register su efecto no se vea inmediatamente reflejado en la salida, es decir si el cambio ocurrio en el tiempo t, el efecto no se vera en el tiempo t, sino en el tiempo t+1, ademas cabe decir que si el cambio se revierte antes de que ocurra el proximo flanco de bajada es como si no hubiera ocurrido nada en el tiempo t.

Nota: No en todas las arquitecturas la “instantanea” es tomada en el flanco de bajada.

Utilidad del program counter en un computador - concepto10

La utilidad del program counter (PC) en una CPU reside en que con este se puede “caminar” las instrucciones a ejecutar, en otras palabras, si lo vieramos desde el punto de vista de un lenguaje de alto nivel, este chip es el que dice que se busque la siguiente linea de codigo, y luego la siguiente y luego la siguiente, en caso de que el programa entre en un alterador de flujo de ejecución (como un while) la ALU activaria el pin LOAD y le pasaria por IN al PC la linea a la que debe ir para seguir con la ejecución del programa.

Los retardos de propagacion - reto

Por definicion el retardo de propagación es el tiempo que le toma al Ouput cambiar cuando el Input ha cambiado.

Implicaciones para el funcionamiento del un circuito combinacional

Este retardo puede producir resultados inesperados en circuitos relativamente complejos, por ejemplo en el Full-adder implementado en el capitulo 1, si tuviesemos que sumar numeros de muchos mas bits la propagación del carry podria en ocasiones no llegar a tiempo a la penultima compuerta y por tanto el circuito supondria que no hay carry, cuando en realidad no es asi.

Implicaciónes para el funcionamiento de un circuito secuencial

Este retardo implica que el periodo (la duracion de un ciclo) debe ser lo suficientemen larga para que la información tenga tiempo de llegar al punto en el que se requiere, es decir el periodo de un circuito secuencial deberia depender del tiempo de propagación mas largo del circuito completo.

Esto implica que un cambio en el tiempo t no se vera reflejado inmediatamente en la salida, sino en un tiempo t+1.

Implementando el 1-bit register

Su implementación esta explicada en el capitulo 3 de nand2tetris por lo cual no requiere de segunda explicación.

/**
 * 1-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 *                 else out does not change (out[t+1] = out[t])
 */

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    // Put your code here:
    Mux(a=ff1, b=in, sel=load, out=mux1);
    DFF(in=mux1, out=ff1, out=out);
}

Implementando el 16-bit register

En este caso la implementación consiste de un array de 1-bit registers que estan conectados todos al mismo load.

/**
 * 16-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 * else out does not change
 */

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:
    // Put your code here:
    Bit(in=in[0], load=load, out=out[0]);
    Bit(in=in[1], load=load, out=out[1]);
    Bit(in=in[2], load=load, out=out[2]);
    Bit(in=in[3], load=load, out=out[3]);
    Bit(in=in[4], load=load, out=out[4]);
    Bit(in=in[5], load=load, out=out[5]);
    Bit(in=in[6], load=load, out=out[6]);
    Bit(in=in[7], load=load, out=out[7]);
    Bit(in=in[8], load=load, out=out[8]);
    Bit(in=in[9], load=load, out=out[9]);
    Bit(in=in[10], load=load, out=out[10]);
    Bit(in=in[11], load=load, out=out[11]);
    Bit(in=in[12], load=load, out=out[12]);
    Bit(in=in[13], load=load, out=out[13]);
    Bit(in=in[14], load=load, out=out[14]);
    Bit(in=in[15], load=load, out=out[15]);

}

Implementando el 16-bit - 8 register memory

Como se ve en el diagrama el LOAD se conecta a un dmux8way, y el address se conecta al selector del dmux, esto con el fin de que envie la operacion de lectura/escritura unicamente al resgistro que indique el address-bus.

Luego la salida de cada registro se envia a un Mux8Way16 cuyo selector se conecta al address-bus de la ram para que seleccione el registro sobre el cual se realizo la instrucción.

/**
 * Memory of 8 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

// El addres tiene 3 bits porque log2(8)=3
// load == 1 write
// load == 0 read
CHIP RAM8 {
    IN in[16], load, address[3];
    OUT out[16];

    PARTS:
      // Put your code here:
      DMux8Way(in=load, sel=address, a=loadreg0, b=loadreg1, c=loadreg2, d=loadreg3, e=loadreg4, f=loadreg5, g=loadreg6, h=loadreg7);

      Register(in=in, load=loadreg0, out=reg0);
      Register(in=in, load=loadreg1, out=reg1);
      Register(in=in, load=loadreg2, out=reg2);
      Register(in=in, load=loadreg3, out=reg3);
      Register(in=in, load=loadreg4, out=reg4);
      Register(in=in, load=loadreg5, out=reg5);
      Register(in=in, load=loadreg6, out=reg6);
      Register(in=in, load=loadreg7, out=reg7);

      Mux8Way16(a=reg0, b=reg1, c=reg2, d=reg3, e=reg4, f=reg5, g=reg6, h=reg7, sel=address, out=out);
}

Implementando el 16-bit - 64 register memory

En un principio se penso en usar la tecnica de los miniterminos para realizar esta implementación pero se observo que seria un trabajo muy tedioso conectar cables a medida que la cantidad de registros de la RAM fuese aumentando, por esta razon se penso en este otro enfoque que es explicado en los comentarios del codigo fuente.

// Esta es una ram de 64regx16bits=1024bits
// Esta RAM tiene una capacidad de 128bytes (Ni siquiera es un MegaByte)
/*
Esta RAM debe tener 64 registros cada uno de 16bits.
64reg/8reg = 8. quiere decir que se nesecitan 8 rams
de 8 registros para hacer una RAM de 64 registros

address: tiene 6 bits

xxx yyy

Los 3 bits mas significativos seleccionan una de las 8 rams
los 3 bits menos significativos seleccionan un registro de la ram
seleccionada.

*/
CHIP RAM64 {
    
    IN in[16], load, address[6];
    OUT out[16];

    PARTS:
    // Put your code here:
    DMux8Way(in=load, sel=address[3..5], a=selram8-0, b=selram8-1, c=selram8-2, d=selram8-3, e=selram8-4, f=selram8-5, g=selram8-6, h=selram8-7);

    // Las 8 RAM8
    RAM8(in=in, load=selram8-0, address=address[0..2], out=ram8-0);
    RAM8(in=in, load=selram8-1, address=address[0..2], out=ram8-1);
    RAM8(in=in, load=selram8-2, address=address[0..2], out=ram8-2);
    RAM8(in=in, load=selram8-3, address=address[0..2], out=ram8-3);
    RAM8(in=in, load=selram8-4, address=address[0..2], out=ram8-4);
    RAM8(in=in, load=selram8-5, address=address[0..2], out=ram8-5);
    RAM8(in=in, load=selram8-6, address=address[0..2], out=ram8-6);
    RAM8(in=in, load=selram8-7, address=address[0..2], out=ram8-7);

    // Retornando la salida
    Mux8Way16(a=ram8-0, b=ram8-1, c=ram8-2, d=ram8-3, e=ram8-4, f=ram8-5, g=ram8-6, h=ram8-7, sel=address[3..5], out=out);

}

Nota: Todas las RAM siguientes siguen el mismo enfoque por lo tanto no se mostrara diagrama de circuito.

Implementando el 16-bit - 512 register memory

/*
	Esta RAM debe tener 512 registros cada uno de 16bits.
	512reg/64reg = 8. quiere decir que se nesecitan 8 rams
	de 64 registros para hacer una RAM de 512 registros

	address: tiene 9 bits

	xxx yyy yyy

	Los 3 bits mas significativos seleccionan una de las 8 rams
	los 6 bits menos significativos seleccionan un registro de la ram
	seleccionada.

	512reg*16bits=8192bits (8.2Kb)
 */

CHIP RAM512 {
    IN in[16], load, address[9];
    OUT out[16];

    PARTS:
    // Put your code here:
    DMux8Way(in=load, sel=address[6..8], a=selram-0, b=selram-1, c=selram-2, d=selram-3, e=selram-4, f=selram-5, g=selram-6, h=selram-7);

    // Las 8 RAM64
    RAM64(in=in, load=selram-0, address=address[0..5], out=ram-0);
    RAM64(in=in, load=selram-1, address=address[0..5], out=ram-1);
    RAM64(in=in, load=selram-2, address=address[0..5], out=ram-2);
    RAM64(in=in, load=selram-3, address=address[0..5], out=ram-3);
    RAM64(in=in, load=selram-4, address=address[0..5], out=ram-4);
    RAM64(in=in, load=selram-5, address=address[0..5], out=ram-5);
    RAM64(in=in, load=selram-6, address=address[0..5], out=ram-6);
    RAM64(in=in, load=selram-7, address=address[0..5], out=ram-7);

    // Retornando la salida
    Mux8Way16(a=ram-0, b=ram-1, c=ram-2, d=ram-3, e=ram-4, f=ram-5, g=ram-6, h=ram-7, sel=address[6..8], out=out);

}

Implementando el 16-bit - 4096 register memory

/*
	Esta RAM debe tener 4096 registros cada uno de 16bits.
	4096reg/512reg = 8. quiere decir que se nesecitan 8 rams
	de 512 registros para hacer una RAM de 4096 registros

	address: tiene 12 bits

	xxx yyy yyy yyy

	Los 3 bits mas significativos seleccionan una de las 8 rams
	los 9 bits menos significativos seleccionan un registro de la ram
	seleccionada.

	4096reg*16bits=65536bits (65.5Kb)
 */

CHIP RAM4K {
    IN in[16], load, address[12];
    OUT out[16];

    PARTS:
    // Put your code here:
    DMux8Way(in=load, sel=address[9..11], a=selram-0, b=selram-1, c=selram-2, d=selram-3, e=selram-4, f=selram-5, g=selram-6, h=selram-7);

    // Las 8 RAM64
    RAM512(in=in, load=selram-0, address=address[0..8], out=ram-0);
    RAM512(in=in, load=selram-1, address=address[0..8], out=ram-1);
    RAM512(in=in, load=selram-2, address=address[0..8], out=ram-2);
    RAM512(in=in, load=selram-3, address=address[0..8], out=ram-3);
    RAM512(in=in, load=selram-4, address=address[0..8], out=ram-4);
    RAM512(in=in, load=selram-5, address=address[0..8], out=ram-5);
    RAM512(in=in, load=selram-6, address=address[0..8], out=ram-6);
    RAM512(in=in, load=selram-7, address=address[0..8], out=ram-7);

    // Retornando la salida
    Mux8Way16(a=ram-0, b=ram-1, c=ram-2, d=ram-3, e=ram-4, f=ram-5, g=ram-6, h=ram-7, sel=address[9..11], out=out);


}

Implementando el 16-bit - 16384 register memory

 /*
	Esta RAM debe tener 16384 registros cada uno de 16bits.
	16384reg/4096reg = 4. quiere decir que se nesecitan 4 rams
	de 4096 registros para hacer una RAM de 16384 registros

	address: tiene 14 bits

	xx yyy yyy yyy yyy

	Los 2 bits mas significativos seleccionan una de las 4 rams
	los 12 bits menos significativos seleccionan un registro de la ram
	seleccionada.

	16384reg*16bits=264144bits (264.1Kb)
 */

CHIP RAM16K {
    IN in[16], load, address[14];
    OUT out[16];

    PARTS:
    // Put your code here:
    DMux4Way(in=load, sel=address[12..13], a=selram-0, b=selram-1, c=selram-2, d=selram-3);

	// Las 8 RAM8
    RAM4K(in=in, load=selram-0, address=address[0..11], out=ram-0);
    RAM4K(in=in, load=selram-1, address=address[0..11], out=ram-1);
    RAM4K(in=in, load=selram-2, address=address[0..11], out=ram-2);
    RAM4K(in=in, load=selram-3, address=address[0..11], out=ram-3);

    // Retornando la salida
    Mux4Way16(a=ram-0, b=ram-1, c=ram-2, d=ram-3, sel=address[12..13], out=out);
}

Implementando el 16-bit program counter

La implementación de este circuito se puede hacer usando multiplexores, un incrementer y un registro para manterner el estado anterior (t-1) del counter.

/**
 * A 16-bit counter with load and reset control bits.
 * if      (reset[t] == 1) out[t+1] = 0
 * else if (load[t] == 1)  out[t+1] = in[t]
 * else if (inc[t] == 1)   out[t+1] = out[t] + 1  (integer addition)
 * else                    out[t+1] = out[t]
 */

CHIP PC {
    IN in[16],load,inc,reset;
    OUT out[16];

    PARTS:
    // Put your code here:
    Mux16(a=in, b=lastOutIncremented, sel=inc, out=mux1);
    Mux16(a=mux1, b=in, sel=load, out=mux2);
    Mux16(a=mux2, b=false, sel=reset, out=mux3);

    Register(in=mux3, load=true, out=out, out=lastOut);

    Inc16(in=lastOut, out=lastOutIncremented);
}

Codigo fuente

Lista de chequeo y autoevaluacion

Fuentes

Written on August 12, 2017