Aquí hay una pregunta teórica, una que no ofrece una respuesta fácil en ningún caso, ni siquiera la trivial.

En el Juego de la vida de Conway, existen construcciones como el metapíxel que permiten que el Juego de la vida simule también cualquier otro sistema de reglas del Juego de la vida. Además, se sabe que el Juego de la Vida está completo en Turing.

Su tarea es construir un autómata celular utilizando las reglas del juego de la vida de Conway que permitirán jugar un juego de Tetris.

Su programa recibirá información al cambiar manualmente el estado del autómata en una generación específica para representar una interrupción (por ejemplo, mover una pieza hacia la izquierda o hacia la derecha, soltarla, rotarla o generar aleatoriamente una nueva pieza para colocar en la cuadrícula), contando un número específico de generaciones como tiempo de espera y mostrando el resultado en algún lugar del autómata. El resultado mostrado debe parecerse visiblemente a una cuadrícula de Tetris real.

Su programa se puntuará en los siguientes aspectos, en orden (con criterios más bajos que actúen como desempate para criterios más altos):

• Tamaño del cuadro delimitador: gana el cuadro rectangular con el área más pequeña que contiene completamente la solución dada.

• Pequeños cambios en la entrada: la menor cantidad de celdas (para el peor de los casos en su autómata) que deben ajustarse manualmente para una interrupción gana.

• Ejecución más rápida: gana la menor cantidad de generaciones para avanzar una marca en la simulación.

• Recuento inicial de células vivas: el recuento más pequeño gana.

• Primero en publicar: la publicación anterior gana.

Esto comenzó como una búsqueda pero terminó como una odisea.

Búsqueda del procesador Tetris, 2,940,928 x 10,295,296

El archivo de patrones, en todo su esplendor, se puede encontrar aquí , visible en el navegador aquí .

Este proyecto es la culminación de los esfuerzos de muchos usuarios en el transcurso de los últimos 1 y 1/2 años. Aunque la composición del equipo ha variado con el tiempo, los participantes al momento de escribir son los siguientes:

• PhiNotPi
• El'endia Starman
• K Zhang
• Azul (Muddyfish)
• Graznido de vacas (Kritixi Lithos)
• Mego
• Quartata

También nos gustaría extender nuestro agradecimiento a 7H3_H4CK3R, Conor O'Brien y los muchos otros usuarios que se han esforzado por resolver este desafío.

Debido al alcance sin precedentes de esta colaboración, esta respuesta se divide en partes en múltiples respuestas escritas por los miembros de este equipo. Cada miembro escribirá sobre subtemas específicos, que corresponden aproximadamente a las áreas del proyecto en las que estuvieron más involucrados.

Distribuya cualquier voto a favor o recompensa entre todos los miembros del equipo.

Tabla de contenido

1. Visión de conjunto
2. Metapixels y VarLife
3. Hardware
4. QFTASM y Cogol
5. Asamblea, traducción y el futuro
6. Nuevo lenguaje y compilador

También considere revisar nuestra organización GitHub donde hemos puesto todo el código que hemos escrito como parte de nuestra solución. Las preguntas pueden dirigirse a nuestra sala de chat de desarrollo .

Parte 1: Descripción general

La idea subyacente de este proyecto es la abstracción . En lugar de desarrollar un juego de Tetris en Life directamente, aumentamos lentamente la abstracción en una serie de pasos. En cada capa, nos alejamos más de las dificultades de la vida y nos acercamos a la construcción de una computadora que es tan fácil de programar como cualquier otra.

Primero, usamos metapíxeles OTCA como la base de nuestra computadora. Estos metapíxeles son capaces de emular cualquier regla "realista". Wireworld y la computadora Wireworld sirvieron como fuentes importantes de inspiración para este proyecto, por lo que buscamos crear una construcción similar con metapíxeles. Aunque no es posible emular Wireworld con metapíxeles OTCA, es posible asignar diferentes reglas de metapíxeles diferentes y construir disposiciones de metapíxeles que funcionen de manera similar a los cables.

El siguiente paso fue construir una variedad de puertas lógicas fundamentales para que sirvan de base para la computadora. Ya en esta etapa estamos tratando con conceptos similares al diseño del procesador del mundo real. Aquí hay un ejemplo de una puerta OR, cada celda en esta imagen es en realidad un metapíxel OTCA completo. Puede ver que los "electrones" (cada uno representa un bit de datos) entran y salen de la puerta. También puede ver todos los diferentes tipos de metapíxeles que utilizamos en nuestra computadora: B / S como fondo negro, B1 / S en azul, B2 / S en verde y B12 / S1 en rojo.

A partir de aquí, desarrollamos una arquitectura para nuestro procesador. Dedicamos un esfuerzo significativo al diseño de una arquitectura que fuera tan no esotérica como tan fácilmente implementable como fuera posible. Mientras que la computadora Wireworld usaba una arquitectura rudimentaria activada por el transporte, este proyecto usa una arquitectura RISC mucho más flexible completa con múltiples códigos de operación y modos de direccionamiento. Creamos un lenguaje ensamblador, conocido como QFTASM (Quest for Tetris Assembly), que guió la construcción de nuestro procesador.

Nuestra computadora también es asíncrona, lo que significa que no hay un reloj global que controle la computadora. Más bien, los datos van acompañados de una señal de reloj a medida que fluye alrededor de la computadora, lo que significa que solo necesitamos enfocarnos en los tiempos locales pero no globales de la computadora.

Aquí hay una ilustración de nuestra arquitectura de procesador:

A partir de aquí, solo es cuestión de implementar Tetris en la computadora. Para ayudar a lograr esto, hemos trabajado en múltiples métodos de compilación de lenguaje de nivel superior para QFTASM. Tenemos un lenguaje básico llamado Cogol, un segundo lenguaje más avanzado en desarrollo, y finalmente tenemos un backend GCC en construcción. El programa actual de Tetris fue escrito / compilado desde Cogol.

Una vez que se generó el código final de Tetris QFTASM, los pasos finales fueron ensamblar desde este código a la ROM correspondiente, y luego desde los metapíxeles al Juego de la Vida subyacente, completando nuestra construcción.

Tetris corriendo

Para aquellos que desean jugar Tetris sin perder el tiempo con la computadora, pueden ejecutar el código fuente de Tetris en el intérprete QFTASM . Establezca las direcciones de pantalla RAM en 3-32 para ver el juego completo. Aquí hay un enlace permanente para mayor comodidad: Tetris en QFTASM .

Características del juego:

• Los 7 tetrominoes
• Movimiento, rotación, gotas suaves.
• Línea despejada y puntuación
• Vista previa de pieza
• Las entradas del jugador inyectan aleatoriedad

Monitor

Nuestra computadora representa la placa Tetris como una cuadrícula dentro de su memoria. Las direcciones 10-31 muestran el tablero, las direcciones 5-8 muestran la pieza de vista previa y la dirección 3 contiene el puntaje.

Entrada

La entrada al juego se realiza editando manualmente el contenido de la dirección RAM 1. Usando el intérprete QFTASM, esto significa realizar escrituras directas en la dirección 1. Busque "Escritura directa en RAM" en la página del intérprete. Cada movimiento solo requiere editar un solo bit de RAM, y este registro de entrada se borra automáticamente después de que se haya leído el evento de entrada.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

Sistema de puntuación

Obtienes una bonificación por despejar varias líneas en un solo turno.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Parte 2: OTCA Metapixel y VarLife

OTCA Metapixel

( Fuente )

El OTCA Metapixel es una construcción en el juego de la vida de Conway que se puede utilizar para simular cualquier autómata celular similar a la vida. Como dice LifeWiki (vinculado anteriormente),

El metapíxel OTCA es una celda de unidad 35328 de período 2048 × 2048 que fue construida por Brice Due ... Tiene muchas ventajas ... incluida la capacidad de emular cualquier autómata celular realista y el hecho de que, cuando se aleja, el ON y las celdas OFF son fáciles de distinguir ...

Lo que significa aquí un autómata celular realista es esencialmente que las células nacen y las células sobreviven de acuerdo con cuántas de sus ocho células vecinas están vivas. La sintaxis de estas reglas es la siguiente: una B seguida por el número de vecinos vivos que provocarán un nacimiento, luego una barra oblicua, luego una S seguida por el número de vecinos vivos que mantendrán viva la célula. Un poco prolijo, así que creo que un ejemplo ayudará. El juego canónico de la vida puede ser representado por la regla B3 / S23, que dice que cualquier célula muerta con tres vecinos vivos se volverá viva y cualquier célula viva con dos o tres vecinos vivos permanecerá viva. De lo contrario, la célula muere.

A pesar de ser una celda de 2048 x 2048, el metapíxel OTCA en realidad tiene un cuadro delimitador de celdas de 2058 x 2058, la razón es que se superpone en cinco celdas en cada dirección con sus vecinos diagonales . Las celdas superpuestas sirven para interceptar planeadores, que se emiten para indicar a las vecinas de las metaceldas que está activada, para que no interfieran con otros metapíxeles o vuelen indefinidamente. Las reglas de nacimiento y supervivencia están codificadas en una sección especial de células en el lado izquierdo del metapíxel, por la presencia o ausencia de comedores en posiciones específicas a lo largo de dos columnas (una para el nacimiento, la otra para la supervivencia). En cuanto a la detección del estado de las células vecinas, así es como sucede:

Una secuencia de 9-LWSS luego gira en sentido horario alrededor de la celda, perdiendo un LWSS por cada celda adyacente 'activada' que desencadenó una reacción de miel. El número de LWSS faltantes se cuenta detectando la posición del LWSS delantero al estrellar otro LWSS en la dirección opuesta. Esta colisión libera planeadores, lo que desencadena otras una o dos reacciones de miel si los comedores que indican que las condiciones de nacimiento / supervivencia están ausentes.

Se puede encontrar un diagrama más detallado de cada aspecto del metapíxel OTCA en su sitio web original: ¿Cómo funciona? .

VarLife

Creé un simulador en línea de reglas realistas en las que podía hacer que cualquier célula se comportara de acuerdo con cualquier regla real y lo llamé "Variaciones de la vida". Este nombre se ha acortado a "VarLife" para ser más conciso. Aquí hay una captura de pantalla (enlace aquí: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):

Características notables:

• Alternar celdas entre vivo / muerto y pintar el tablero con diferentes reglas.
• La capacidad de iniciar y detener la simulación, y de hacer un paso a la vez. También es posible realizar un número determinado de pasos lo más rápido posible o más lentamente, a la velocidad establecida en las casillas de verificación por segundo y milisegundos por marca.
• Borre todas las celdas activas o restablezca completamente el tablero a un estado en blanco.
• Puede cambiar el tamaño de la celda y el tablero, y también para permitir el envoltorio toroidal horizontal y / o verticalmente.
• Permalinks (que codifican toda la información en la url) y urls cortas (porque a veces hay demasiada información, pero de todos modos son agradables).
• Conjuntos de reglas, con especificación B / S, colores y aleatoriedad opcional.
• ¡Y por último, pero no menos importante, renderizando gifs!

La función de renderizar a gif es mi favorita, ya que me llevó un montón de trabajo implementarla, por lo que fue muy satisfactorio cuando finalmente la descifré a las 7 de la mañana, y porque hace que sea muy fácil compartir las construcciones de VarLife con otros. .

Circuitos básicos de VarLife

Con todo, ¡la computadora VarLife solo necesita cuatro tipos de células! Ocho estados en todos contando los estados muertos / vivos. Son:

• B / S (negro / blanco), que sirve como un búfer entre todos los componentes ya que las células B / S nunca pueden estar vivas.
• B1 / S (azul / cian), que es el tipo de célula principal utilizado para propagar señales.
• B2 / S (verde / amarillo), que se utiliza principalmente para el control de la señal, asegurando que no se propague hacia atrás.
• B12 / S1 (rojo / naranja), que se utiliza en algunas situaciones especializadas, como el cruce de señales y el almacenamiento de un poco de datos.

Use esta breve URL para abrir VarLife con estas reglas ya codificadas: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Alambres

Hay algunos diseños de cables diferentes con diferentes características.

Este es el cable más sencillo y básico de VarLife, una franja azul bordeada por franjas verdes.

URL corta: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Este cable es unidireccional. Es decir, matará cualquier señal que intente viajar en la dirección opuesta. También es una celda más estrecha que el cable básico.

URL corta: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

También existen cables diagonales, pero no se usan mucho.

URL corta: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Puertas

En realidad, hay muchas maneras de construir cada puerta individual, por lo que solo mostraré un ejemplo de cada tipo. Este primer gif muestra las puertas AND, XOR y OR, respectivamente. La idea básica aquí es que una celda verde actúa como un AND, una celda azul actúa como un XOR, y una celda roja actúa como un OR, y todas las demás celdas a su alrededor están ahí para controlar el flujo correctamente.

URL corta: http://play.starmaninnovations.com/varlife/EGTlKktmeI

La compuerta AND-NOT, abreviada como "compuerta ANT", resultó ser un componente vital. Es una puerta que pasa una señal de A si y solo si no hay señal de B. Por lo tanto, "A Y NO B".

URL corta: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Si bien no es exactamente una puerta , un azulejo de cruce de alambre sigue siendo muy importante y útil.

URL corta: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Por cierto, no hay una puerta NO aquí. Esto se debe a que sin una señal entrante, se debe producir una salida constante, que no funciona bien con la variedad de tiempos que requiere el hardware actual de la computadora. Nos llevamos muy bien sin eso de todos modos.

Además, muchos componentes fueron diseñados intencionalmente para caber dentro de un cuadro delimitador de 11 por 11 (un mosaico ) donde toma señales de 11 tics de entrar en el mosaico para salir del mosaico. Esto hace que los componentes sean más modulares y más fáciles de juntar según sea necesario sin tener que preocuparse por ajustar los cables para el espaciado o el tiempo.

Para ver más puertas que se descubrieron / construyeron en el proceso de exploración de componentes de circuitos, consulte esta publicación de blog de PhiNotPi: Building Blocks: Logic Gates .

Componentes de retraso

En el proceso de diseño del hardware de la computadora, KZhang ideó múltiples componentes de retardo, que se muestran a continuación.

Retardo de 4 tick: URL corta: http://play.starmaninnovations.com/varlife/gebOMIXxdh

Retardo de 5 tics: URL corta: http://play.starmaninnovations.com/varlife/JItNjJvnUB

Retardo de 8 tick (tres puntos de entrada diferentes): URL corta: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

11-tick delay: URL corta: http://play.starmaninnovations.com/varlife/kfoADussXA

Retardo de 12 tics: URL corta: http://play.starmaninnovations.com/varlife/bkamAfUfud

Retardo de 14 tick: URL corta: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Retardo de 15 ticks (verificado comparando con esto ): URL corta: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Bueno, eso es todo para los componentes de circuitos básicos en VarLife! ¡Vea la publicación de hardware de KZhang para los principales circuitos de la computadora!

Parte 3: Hardware

Con nuestro conocimiento de las puertas lógicas y la estructura general del procesador, podemos comenzar a diseñar todos los componentes de la computadora.

Demultiplexor

Un demultiplexor, o demux, es un componente crucial para la ROM, RAM y ALU. Dirige una señal de entrada a una de las muchas señales de salida en función de algunos datos del selector. Se compone de 3 partes principales: un convertidor de serie a paralelo, un verificador de señal y un divisor de señal de reloj.

Comenzamos por convertir los datos del selector de serie a "paralelo". Esto se hace dividiendo estratégicamente y retrasando los datos para que el bit de datos más a la izquierda se cruce con la señal de reloj en el cuadrado de 11x11 más a la izquierda, el siguiente bit de datos se cruce con la señal de reloj en el siguiente cuadrado de 11x11, y así sucesivamente. Aunque cada bit de datos se generará en cada cuadrado de 11x11, cada bit de datos se intersectará con la señal del reloj solo una vez.

A continuación, verificaremos si los datos paralelos coinciden con una dirección preestablecida. Hacemos esto usando compuertas AND y ANT en el reloj y datos paralelos. Sin embargo, debemos asegurarnos de que los datos paralelos también se emitan para que puedan compararse nuevamente. Estas son las puertas que se me ocurrieron:

Finalmente, simplemente dividimos la señal del reloj, apilamos un montón de verificadores de señal (uno para cada dirección / salida) y tenemos un multiplexor.

ROM

Se supone que la ROM toma una dirección como entrada y envía la instrucción a esa dirección como salida. Comenzamos usando un multiplexor para dirigir la señal del reloj a una de las instrucciones. Luego, necesitamos generar una señal usando algunos cruces de cables y compuertas OR. Los cruces de cables permiten que la señal del reloj descienda por los 58 bits de la instrucción, y también permite que una señal generada (actualmente en paralelo) se mueva hacia abajo a través de la ROM para que salga.

A continuación, solo necesitamos convertir la señal paralela en datos en serie, y la ROM está completa.

La ROM se genera actualmente ejecutando un script en Golly que traducirá el código de ensamblaje de su portapapeles a la ROM.

SRL, SL, SRA

Estas tres puertas lógicas se usan para cambios de bits, y son más complicadas que las típicas AND, OR, XOR, etc. Para hacer que estas puertas funcionen, primero demoraremos la señal del reloj una cantidad de tiempo adecuada para provocar un "cambio" en los datos El segundo argumento dado a estas puertas dicta cuántos bits cambiar.

Para el SL y el SRL, necesitamos

1. Asegúrese de que los 12 bits más significativos no están activados (de lo contrario, la salida es simplemente 0), y
2. Retrase la cantidad correcta de datos en función de los 4 bits menos significativos.

Esto es factible con un montón de compuertas AND / ANT y un multiplexor.

El SRA es ligeramente diferente, porque necesitamos copiar el bit de signo durante el turno. Hacemos esto marcando la señal del reloj con el bit de signo, y luego copiamos esa salida varias veces con divisores de cable y compuertas OR.

Pestillo de restablecimiento (SR)

Muchas partes de la funcionalidad del procesador dependen de la capacidad de almacenar datos. Usando 2 celdas rojas B12 / S1, podemos hacer exactamente eso. Las dos celdas pueden mantenerse juntas y también pueden permanecer juntas. Usando algunos circuitos adicionales de configuración, reinicio y lectura, podemos hacer un simple enganche SR.

Sincronizador

Al convertir los datos en serie en datos paralelos, y luego configurar un montón de pestillos SR, podemos almacenar una palabra completa de datos. Luego, para volver a obtener los datos, podemos leer y restablecer todos los pestillos y retrasar los datos en consecuencia. Esto nos permite almacenar una (o más) palabras de datos mientras esperamos otra, lo que permite sincronizar dos palabras de datos que llegan en diferentes momentos.

Leer contador

Este dispositivo realiza un seguimiento de cuántas veces más necesita direccionar desde la RAM. Lo hace usando un dispositivo similar al pestillo SR: un flip flop T. Cada vez que el flip flop T recibe una entrada, cambia de estado: si estaba encendido, se apaga y viceversa. Cuando el flip flop T se cambia de encendido a apagado, envía un pulso de salida, que se puede alimentar a otro flip flop T para formar un contador de 2 bits.

Para hacer el contador de lectura, necesitamos establecer el contador en el modo de direccionamiento apropiado con dos puertas ANT, y usar la señal de salida del contador para decidir dónde dirigir la señal del reloj: hacia la ALU o la RAM.

Leer cola

La cola de lectura necesita realizar un seguimiento de qué contador de lectura envió una entrada a la RAM, de modo que pueda enviar la salida de la RAM a la ubicación correcta. Para hacer eso, utilizamos algunos pestillos SR: un pestillo para cada entrada. Cuando se envía una señal a la RAM desde un contador de lectura, la señal del reloj se divide y establece el bloqueo de SR del contador. La salida de la RAM se ANDA con el pestillo SR, y la señal de reloj de la RAM restablece el pestillo SR.

ALU

La ALU funciona de manera similar a la cola de lectura, ya que utiliza un pestillo SR para realizar un seguimiento de dónde enviar una señal. Primero, el pestillo SR del circuito lógico correspondiente al código de operación de la instrucción se establece usando un multiplexor. A continuación, los valores del primer y segundo argumento son AND con el pestillo SR, y luego se pasan a los circuitos lógicos. La señal del reloj restablece el pestillo a medida que pasa para que la ALU pueda usarse nuevamente. (La mayoría de los circuitos están reducidos a golf, y se introduce una tonelada de gestión de retrasos, por lo que parece un poco desordenado)

RAM

La RAM fue la parte más complicada de este proyecto. Se requería un control muy específico sobre cada pestillo SR que almacenaba datos. Para leer, la dirección se envía a un multiplexor y se envía a las unidades RAM. Las unidades RAM emiten los datos que almacenan en paralelo, que se convierten en serie y se emiten. Para escribir, la dirección se envía a un multiplexor diferente, los datos a escribir se convierten de serie a paralelo, y las unidades de RAM propagan la señal a través de la RAM.

Cada unidad RAM de 22x22 metapíxeles tiene esta estructura básica:

Al juntar toda la RAM, obtenemos algo parecido a esto:

Poniendo todo junto

¡Usando todos estos componentes y la arquitectura general de la computadora descrita en la Descripción general , podemos construir una computadora que funcione!

Descargas: - Computadora Tetris terminada - Script de creación de ROM, computadora vacía y computadora principal de búsqueda

Parte 4: QFTASM y Cogol

Descripción de la arquitectura

En resumen, nuestra computadora tiene una arquitectura RISC Harvard asincrónica de 16 bits. Cuando se construye un procesador a mano, una arquitectura RISC ( computadora con conjunto de instrucciones reducido ) es prácticamente un requisito. En nuestro caso, esto significa que el número de códigos de operación es pequeño y, mucho más importante, que todas las instrucciones se procesan de manera muy similar.

Como referencia, la computadora Wireworld utilizó una arquitectura activada por transporte , en la que la única instrucción era MOVy los cálculos se realizaban escribiendo / leyendo registros especiales. Aunque este paradigma conduce a una arquitectura muy fácil de implementar, el resultado también es inutilizable: todas las operaciones aritméticas / lógicas / condicionales requieren tres instrucciones. Para nosotros estaba claro que queríamos crear una arquitectura mucho menos esotérica.

Para mantener nuestro procesador simple y aumentar la usabilidad, tomamos varias decisiones de diseño importantes:

• No hay registros Cada dirección en RAM se trata por igual y se puede usar como cualquier argumento para cualquier operación. En cierto sentido, esto significa que toda la RAM podría tratarse como registros. Esto significa que no hay instrucciones especiales de carga / almacenamiento.
• En una línea similar, mapeo de memoria. Todo lo que podría escribirse o leerse comparte un esquema de direccionamiento unificado. Esto significa que el contador del programa (PC) es la dirección 0, y la única diferencia entre las instrucciones regulares y las instrucciones del flujo de control es que las instrucciones del flujo de control usan la dirección 0.
• Los datos son seriales en transmisión, paralelos en almacenamiento. Debido a la naturaleza basada en "electrones" de nuestra computadora, las sumas y restas son significativamente más fáciles de implementar cuando los datos se transmiten en forma serial little-endian (primer bit menos significativo). Además, los datos en serie eliminan la necesidad de buses de datos engorrosos, que son realmente anchos y engorrosos a la hora adecuada (para que los datos permanezcan juntos, todos los "carriles" del bus deben experimentar el mismo retraso de viaje).
• Arquitectura de Harvard, que significa una división entre la memoria del programa (ROM) y la memoria de datos (RAM). Aunque esto reduce la flexibilidad del procesador, esto ayuda con la optimización del tamaño: la longitud del programa es mucho mayor que la cantidad de RAM que necesitaremos, por lo que podemos dividir el programa en ROM y luego centrarnos en comprimir la ROM , que es mucho más fácil cuando es de solo lectura.
• Ancho de datos de 16 bits. Esta es la potencia más pequeña de dos que es más ancha que una placa Tetris estándar (10 bloques). Esto nos da un rango de datos de -32768 a +32767 y una longitud máxima del programa de 65536 instrucciones. (2 ^ 8 = 256 instrucciones son suficientes para la mayoría de las cosas simples que podríamos querer que haga un procesador de juguetes, pero no Tetris).
• Diseño asincrónico. En lugar de tener un reloj central (o, de manera equivalente, varios relojes) que dicta la sincronización de la computadora, todos los datos van acompañados de una "señal de reloj" que viaja en paralelo con los datos a medida que fluye alrededor de la computadora. Ciertas rutas pueden ser más cortas que otras, y si bien esto plantearía dificultades para un diseño con reloj centralizado, un diseño asincrónico puede manejar fácilmente operaciones de tiempo variable.
• Todas las instrucciones son de igual tamaño. Consideramos que una arquitectura en la que cada instrucción tiene 1 código de operación con 3 operandos (valor valor destino) era la opción más flexible. Esto abarca operaciones de datos binarios, así como movimientos condicionales.
• Sistema de modo de direccionamiento simple. Tener una variedad de modos de direccionamiento es muy útil para admitir cosas como matrices o recursividad. Logramos implementar varios modos de direccionamiento importantes con un sistema relativamente simple.

Una ilustración de nuestra arquitectura está contenida en la publicación general.

Funcionalidad y Operaciones ALU

A partir de aquí, se trataba de determinar qué funcionalidad debería tener nuestro procesador. Se prestó especial atención a la facilidad de implementación, así como a la versatilidad de cada comando.

Movimientos condicionales

Los movimientos condicionales son muy importantes y sirven como flujo de control tanto a pequeña como a gran escala. "Pequeña escala" se refiere a su capacidad para controlar la ejecución de un movimiento de datos en particular, mientras que "a gran escala" se refiere a su uso como una operación de salto condicional para transferir el flujo de control a cualquier fragmento de código arbitrario. No hay operaciones de salto dedicadas porque, debido al mapeo de memoria, un movimiento condicional puede copiar datos a la RAM normal y copiar una dirección de destino a la PC. También elegimos renunciar a movimientos incondicionales y saltos incondicionales por una razón similar: ambos pueden implementarse como un movimiento condicional con una condición que está codificada como VERDADERA.

Elegimos tener dos tipos diferentes de movimientos condicionales: "mover si no es cero" ( MNZ) y "mover si es menor que cero" ( MLZ). Funcionalmente, MNZequivale a verificar si algún bit en los datos es un 1, mientras que MLZequivale a verificar si el bit de signo es 1. Son útiles para las igualdades y las comparaciones, respectivamente. La razón por la que elegimos estos dos sobre otros como "mover si es cero" ( MEZ) o "mover si es mayor que cero" ( MGZ) fue que MEZrequeriría crear una señal VERDADERA a partir de una señal vacía, mientras que MGZes una verificación más compleja, que requiere el el bit de signo será 0 mientras que al menos otro bit será 1.

Aritmética

Las siguientes instrucciones más importantes, en términos de guiar el diseño del procesador, son las operaciones aritméticas básicas. Como mencioné anteriormente, estamos utilizando datos en serie little-endian, con la elección de endianness determinada por la facilidad de las operaciones de suma / resta. Al hacer que el bit menos significativo llegue primero, las unidades aritméticas pueden seguir fácilmente el bit de acarreo.

Elegimos usar la representación del complemento 2 para números negativos, ya que esto hace que la suma y la resta sean más consistentes. Vale la pena señalar que la computadora Wireworld usó el complemento de 1.

La suma y la resta son el alcance del soporte aritmético nativo de nuestra computadora (además de los cambios de bits que se analizan más adelante). Otras operaciones, como la multiplicación, son demasiado complejas para ser manejadas por nuestra arquitectura y deben implementarse en software.

Operaciones bit a bit

Nuestro procesador tiene AND, ORe XORinstrucciones que hacen lo que usted esperaría. En lugar de tener una NOTinstrucción, elegimos tener una instrucción "and-not" ( ANT). La dificultad con la NOTinstrucción es nuevamente que debe crear señal a partir de la falta de señal, lo cual es difícil con un autómata celular. La ANTinstrucción devuelve 1 solo si el primer bit de argumento es 1 y el segundo bit de argumento es 0. Por lo tanto, NOT xes equivalente a ANT -1 x(así como XOR -1 x). Además, ANTes versátil y tiene su principal ventaja en el enmascaramiento: en el caso del programa Tetris lo usamos para borrar tetrominoes.

Bit Shifting

Las operaciones de desplazamiento de bits son las operaciones más complejas manejadas por la ALU. Toman dos entradas de datos: un valor para cambiar y una cantidad para cambiarlo. A pesar de su complejidad (debido a la cantidad variable de desplazamiento), estas operaciones son cruciales para muchas tareas importantes, incluidas las muchas operaciones "gráficas" involucradas en Tetris. Los cambios de bits también servirían como base para algoritmos eficientes de multiplicación / división.

Nuestro procesador tiene operaciones de desplazamiento de tres bits, "desplazamiento a la izquierda" ( SL), "desplazamiento a la derecha lógica" ( SRL) y "desplazamiento a la derecha aritmética" ( SRA). Los primeros dos cambios de bit ( SLy SRL) completan los nuevos bits con todos los ceros (lo que significa que un número negativo desplazado a la derecha ya no será negativo). Si el segundo argumento del cambio está fuera del rango de 0 a 15, el resultado son todos ceros, como es de esperar. Para el último desplazamiento de bit SRA, el desplazamiento de bit conserva el signo de la entrada y, por lo tanto, actúa como una verdadera división entre dos.

Tubería de instrucciones

Ahora es el momento de hablar sobre algunos de los detalles arenosos de la arquitectura. Cada ciclo de CPU consta de los siguientes cinco pasos:

1. Obtenga las instrucciones actuales de la ROM

El valor actual de la PC se utiliza para obtener la instrucción correspondiente de la ROM. Cada instrucción tiene un código de operación y tres operandos. Cada operando consta de una palabra de datos y un modo de direccionamiento. Estas partes se dividen entre sí a medida que se leen desde la ROM.

El código de operación es de 4 bits para admitir 16 códigos de operación únicos, de los cuales se asignan 11:

0000  MNZ    Move if Not Zero
0001  MLZ    Move if Less than Zero
0010  ADD    ADDition
0011  SUB    SUBtraction
0100  AND    bitwise AND
0101  OR     bitwise OR
0110  XOR    bitwise eXclusive OR
0111  ANT    bitwise And-NoT
1000  SL     Shift Left
1001  SRL    Shift Right Logical
1010  SRA    Shift Right Arithmetic
1011  unassigned
1100  unassigned
1101  unassigned
1110  unassigned
1111  unassigned

2. Escriba el resultado (si es necesario) de la instrucción anterior en la RAM

Dependiendo de la condición de la instrucción anterior (como el valor del primer argumento para un movimiento condicional), se realiza una escritura. La dirección de la escritura está determinada por el tercer operando de la instrucción anterior.

Es importante tener en cuenta que la escritura se produce después de buscar instrucciones. Esto lleva a la creación de una ranura de retardo de rama en la que la instrucción inmediatamente después de una instrucción de rama (cualquier operación que escribe en la PC) se ejecuta en lugar de la primera instrucción en el destino de la rama.

En ciertos casos (como saltos incondicionales), el intervalo de retardo de ramificación se puede optimizar. En otros casos no puede, y las instrucciones después de una rama deben dejarse vacías. Además, este tipo de intervalo de retraso significa que las sucursales deben usar un objetivo de sucursal que sea 1 dirección menos que la instrucción de destino real, para dar cuenta del incremento de PC que ocurre.

En resumen, debido a que la salida de la instrucción anterior se escribe en la RAM después de obtener la siguiente instrucción, los saltos condicionales deben tener una instrucción en blanco después de ellos, de lo contrario, la PC no se actualizará correctamente para el salto.

3. Lea los datos para los argumentos de la instrucción actual de RAM

Como se mencionó anteriormente, cada uno de los tres operandos consta de una palabra de datos y un modo de direccionamiento. La palabra de datos es de 16 bits, el mismo ancho que la RAM. El modo de direccionamiento es de 2 bits.

Los modos de direccionamiento pueden ser una fuente de complejidad significativa para un procesador como este, ya que muchos modos de direccionamiento del mundo real implican cálculos de varios pasos (como agregar compensaciones). Al mismo tiempo, los modos de direccionamiento versátiles juegan un papel importante en la usabilidad del procesador.

Intentamos unificar los conceptos de usar números codificados como operandos y usar direcciones de datos como operandos. Esto condujo a la creación de modos de direccionamiento basados ​​en contador: el modo de direccionamiento de un operando es simplemente un número que representa cuántas veces se deben enviar los datos alrededor de un bucle de lectura de RAM. Esto abarca el direccionamiento inmediato, directo, indirecto y doble indirecto.

00  Immediate:  A hard-coded value. (no RAM reads)
01  Direct:  Read data from this RAM address. (one RAM read)
10  Indirect:  Read data from the address given at this address. (two RAM reads)
11  Double-indirect: Read data from the address given at the address given by this address. (three RAM reads)

Después de realizar esta desreferenciación, los tres operandos de la instrucción tienen roles diferentes. El primer operando suele ser el primer argumento para un operador binario, pero también sirve como condición cuando la instrucción actual es un movimiento condicional. El segundo operando sirve como segundo argumento para un operador binario. El tercer operando sirve como la dirección de destino para el resultado de la instrucción.

Dado que las dos primeras instrucciones sirven como datos mientras que la tercera sirve como una dirección, los modos de direccionamiento tienen interpretaciones ligeramente diferentes según la posición en la que se usen. Por ejemplo, el modo directo se usa para leer datos de una dirección RAM fija (ya que se necesita una lectura de RAM), pero el modo inmediato se usa para escribir datos en una dirección de RAM fija (ya que no se necesitan lecturas de RAM).

4. Calcular el resultado

El código de operación y los dos primeros operandos se envían a la ALU para realizar una operación binaria. Para las operaciones aritméticas, bit a bit y de desplazamiento, esto significa realizar la operación relevante. Para los movimientos condicionales, esto significa simplemente devolver el segundo operando.

El código de operación y el primer operando se usan para calcular la condición, que determina si se escribe o no el resultado en la memoria. En el caso de movimientos condicionales, esto significa determinar si algún bit en el operando es 1 (para MNZ) o determinar si el bit de signo es 1 (para MLZ). Si el código de operación no es un movimiento condicional, entonces la escritura siempre se realiza (la condición siempre es verdadera).

5. Incremente el contador del programa

Finalmente, el contador del programa se lee, se incrementa y se escribe.

Debido a la posición del incremento de la PC entre la lectura de la instrucción y la escritura de la instrucción, esto significa que una instrucción que incrementa la PC en 1 no es operativa. Una instrucción que copia la PC en sí misma hace que la siguiente instrucción se ejecute dos veces seguidas. Pero, tenga en cuenta que varias instrucciones de PC seguidas pueden causar efectos complejos, que incluyen bucles infinitos, si no presta atención a la canalización de instrucciones.

Búsqueda de la Asamblea Tetris

Creamos un nuevo lenguaje ensamblador llamado QFTASM para nuestro procesador. Este lenguaje ensamblador corresponde 1 a 1 con el código de máquina en la ROM de la computadora.

Cualquier programa QFTASM se escribe como una serie de instrucciones, una por línea. Cada línea tiene el siguiente formato:

[line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

Lista de códigos de operación

Como se discutió anteriormente, hay once códigos de operación compatibles con la computadora, cada uno de los cuales tiene tres operandos:

MNZ [test] [value] [dest]  – Move if Not Zero; sets [dest] to [value] if [test] is not zero.
MLZ [test] [value] [dest]  – Move if Less than Zero; sets [dest] to [value] if [test] is less than zero.
ADD [val1] [val2] [dest]   – ADDition; store [val1] + [val2] in [dest].
SUB [val1] [val2] [dest]   – SUBtraction; store [val1] - [val2] in [dest].
AND [val1] [val2] [dest]   – bitwise AND; store [val1] & [val2] in [dest].
OR [val1] [val2] [dest]    – bitwise OR; store [val1] | [val2] in [dest].
XOR [val1] [val2] [dest]   – bitwise XOR; store [val1] ^ [val2] in [dest].
ANT [val1] [val2] [dest]   – bitwise And-NoT; store [val1] & (![val2]) in [dest].
SL [val1] [val2] [dest]    – Shift Left; store [val1] << [val2] in [dest].
SRL [val1] [val2] [dest]   – Shift Right Logical; store [val1] >>> [val2] in [dest]. Doesn't preserve sign.
SRA [val1] [val2] [dest]   – Shift Right Arithmetic; store [val1] >> [val2] in [dest], while preserving sign.

Modos de direccionamiento

Cada uno de los operandos contiene tanto un valor de datos como un movimiento de direccionamiento. El valor de los datos se describe mediante un número decimal en el rango de -32768 a 32767. El modo de direccionamiento se describe mediante un prefijo de una letra al valor de los datos.

mode    name               prefix
0       immediate          (none)
1       direct             A
2       indirect           B
3       double-indirect    C 

Código de ejemplo

Secuencia de Fibonacci en cinco líneas:

0. MLZ -1 1 1;    initial value
1. MLZ -1 A2 3;   start loop, shift data
2. MLZ -1 A1 2;   shift data
3. MLZ -1 0 0;    end loop
4. ADD A2 A3 1;   branch delay slot, compute next term

Este código calcula la secuencia de Fibonacci, con la dirección RAM 1 que contiene el término actual. Se desborda rápidamente después de 28657.

Código gris:

0. MLZ -1 5 1;      initial value for RAM address to write to
1. SUB A1 5 2;      start loop, determine what binary number to covert to Gray code
2. SRL A2 1 3;      shift right by 1
3. XOR A2 A3 A1;    XOR and store Gray code in destination address
4. SUB B1 42 4;     take the Gray code and subtract 42 (101010)
5. MNZ A4 0 0;      if the result is not zero (Gray code != 101010) repeat loop
6. ADD A1 1 1;      branch delay slot, increment destination address

Este programa calcula el código Gray y almacena el código en direcciones sucesivas que comienzan en la dirección 5. Este programa utiliza varias características importantes, como el direccionamiento indirecto y un salto condicional. Se detiene una vez que el código Gray resultante es 101010, lo que sucede para la entrada 51 en la dirección 56.

Intérprete en línea

El'endia Starman ha creado un intérprete en línea muy útil aquí . Puede recorrer el código, establecer puntos de interrupción, realizar escrituras manuales en la RAM y visualizar la RAM como una pantalla.

Cogol

Una vez que se definió la arquitectura y el lenguaje ensamblador, el siguiente paso en el lado del "software" del proyecto fue la creación de un lenguaje de nivel superior, algo adecuado para Tetris. Así creé Cogol . El nombre es un juego de palabras con "COBOL" y un acrónimo de "C of Game of Life", aunque vale la pena señalar que Cogol es para C lo que nuestra computadora es para una computadora real.

Cogol existe en un nivel justo por encima del lenguaje ensamblador. Generalmente, la mayoría de las líneas en un programa Cogol corresponden a una sola línea de ensamblaje, pero hay algunas características importantes del lenguaje:

• Las características básicas incluyen variables con nombre con asignaciones y operadores que tienen una sintaxis más legible. Por ejemplo, se ADD A1 A2 3convierte z = x + y;, con el compilador, en el mapeo de variables en direcciones.
• Looping construcciones tales como if(){}, while(){}y do{}while();por lo que el compilador de mangos de ramificación.
• Matrices unidimensionales (con aritmética de puntero), que se utilizan para la placa Tetris.
• Subrutinas y una pila de llamadas. Son útiles para evitar la duplicación de grandes fragmentos de código y para admitir la recursividad.

El compilador (que escribí desde cero) es muy básico / ingenuo, pero he intentado optimizar a mano varias de las construcciones del lenguaje para lograr una corta longitud del programa compilado.

Estas son algunas breves descripciones generales sobre cómo funcionan las distintas características del lenguaje:

Tokenización

El código fuente se tokeniza linealmente (paso único), usando reglas simples sobre qué caracteres pueden estar adyacentes dentro de un token. Cuando se encuentra un personaje que no puede ser adyacente al último personaje de la ficha actual, la ficha actual se considera completa y el nuevo personaje comienza una nueva ficha. Algunos caracteres (como {o ,) no pueden ser adyacentes a ningún otro personaje y, por lo tanto, son su propia ficha. Otros (como >o =) sólo se les permite ser adyacente a otros caracteres dentro de su clase, y por lo tanto pueden formar tokens como >>>, ==, o >=, pero no como =2. Los caracteres de espacio en blanco fuerzan un límite entre los tokens pero no se incluyen en el resultado. El personaje más difícil de tokenizar es- porque puede representar sustracción y negación unaria, y por lo tanto requiere un revestimiento especial.

Analizando

El análisis también se realiza de una sola pasada. El compilador tiene métodos para manejar cada una de las diferentes construcciones de lenguaje, y los tokens se sacan de la lista global de tokens a medida que los diversos métodos del compilador los consumen. Si el compilador alguna vez ve un token que no espera, genera un error de sintaxis.

Asignación de memoria global

El compilador asigna a cada variable global (palabra o matriz) sus propias direcciones RAM designadas. Es necesario declarar todas las variables usando la palabra clave mypara que el compilador sepa asignarle espacio. Mucho más genial que las variables globales nombradas es la gestión de memoria de la dirección de memoria virtual. Muchas instrucciones (especialmente condicionales y muchos accesos a arreglos) requieren direcciones temporales "temporales" para almacenar cálculos intermedios. Durante el proceso de compilación, el compilador asigna y desasigna direcciones reutilizables según sea necesario. Si el compilador necesita más direcciones reutilizables, dedicará más RAM como direcciones reutilizables. Creo que es típico que un programa solo requiera unas pocas direcciones reutilizables, aunque cada dirección reutilizable se usará muchas veces.

IF-ELSE Declaraciones

La sintaxis para las if-elsedeclaraciones es la forma estándar de C:

other code
if (cond) {
  first body
} else {
  second body
}
other code

Cuando se convierte a QFTASM, el código se organiza así:

other code
condition test
conditional jump
first body
unconditional jump
second body (conditional jump target)
other code (unconditional jump target)

Si se ejecuta el primer cuerpo, se salta el segundo cuerpo. Si se salta el primer cuerpo, se ejecuta el segundo cuerpo.

En el ensamblaje, una prueba de condición generalmente es solo una resta, y el signo del resultado determina si se debe dar el salto o ejecutar el cuerpo. Una MLZinstrucción se utiliza para manejar desigualdades como >o <=. Se MNZutiliza una instrucción para manejar ==, ya que salta sobre el cuerpo cuando la diferencia no es cero (y, por lo tanto, cuando los argumentos no son iguales). Los condicionales de múltiples expresiones no son compatibles actualmente.

Si elsese omite la declaración, también se omite el salto incondicional y el código QFTASM se ve así:

other code
condition test
conditional jump
body
other code (conditional jump target)

WHILE Declaraciones

La sintaxis de las whiledeclaraciones también es la forma estándar de C:

other code
while (cond) {
  body
}
other code

Cuando se convierte a QFTASM, el código se organiza así:

other code
unconditional jump
body (conditional jump target)
condition test (unconditional jump target)
conditional jump
other code

La prueba de condición y el salto condicional se encuentran al final del bloque, lo que significa que se vuelven a ejecutar después de cada ejecución del bloque. Cuando la condición es falsa, el cuerpo no se repite y el ciclo termina. Durante el inicio de la ejecución del bucle, el flujo de control salta sobre el cuerpo del bucle al código de condición, por lo que el cuerpo nunca se ejecuta si la condición es falsa la primera vez.

Una MLZinstrucción se utiliza para manejar desigualdades como >o <=. A diferencia de durante las ifdeclaraciones, MNZse usa una instrucción para manejar !=, ya que salta al cuerpo cuando la diferencia no es cero (y por lo tanto cuando los argumentos no son iguales).

DO-WHILE Declaraciones

La única diferencia entre whiley do-whilees que el do-whilecuerpo de un bucle no se omite inicialmente, por lo que siempre se ejecuta al menos una vez. Generalmente uso do-whiledeclaraciones para guardar un par de líneas de código de ensamblado cuando sé que el bucle nunca tendrá que omitirse por completo.

Matrices

Las matrices unidimensionales se implementan como bloques contiguos de memoria. Todos los arreglos son de longitud fija según su declaración. Las matrices se declaran así:

my alpha[3];               # empty array
my beta[11] = {3,2,7,8};   # first four elements are pre-loaded with those values

Para la matriz, esta es una posible asignación de RAM, que muestra cómo las direcciones 15-18 están reservadas para la matriz:

15: alpha
16: alpha[0]
17: alpha[1]
18: alpha[2]

La dirección etiquetada alphase llena con un puntero a la ubicación de alpha[0], por lo que en este caso la dirección 15 contiene el valor 16. La alphavariable se puede usar dentro del código de Cogol, posiblemente como un puntero de pila si desea usar esta matriz como una pila .

El acceso a los elementos de una matriz se realiza con la array[index]notación estándar . Si el valor de indexes una constante, esta referencia se completa automáticamente con la dirección absoluta de ese elemento. De lo contrario, realiza una aritmética de puntero (solo suma) para encontrar la dirección absoluta deseada. También es posible anidar la indexación, como alpha[beta[1]].

Subrutinas y Llamadas

Las subrutinas son bloques de código que pueden llamarse desde múltiples contextos, evitando la duplicación de código y permitiendo la creación de programas recursivos. Aquí hay un programa con una subrutina recursiva para generar números de Fibonacci (básicamente el algoritmo más lento):

# recursively calculate the 10th Fibonacci number
call display = fib(10).sum;
sub fib(cur,sum) {
  if (cur <= 2) {
    sum = 1;
    return;
  }
  cur--;
  call sum = fib(cur).sum;
  cur--;
  call sum += fib(cur).sum;
}

Se declara una subrutina con la palabra clave suby se puede colocar una subrutina en cualquier lugar dentro del programa. Cada subrutina puede tener múltiples variables locales, que se declaran como parte de su lista de argumentos. Estos argumentos también pueden tener valores predeterminados.

Para manejar llamadas recursivas, las variables locales de una subrutina se almacenan en la pila. La última variable estática en RAM es el puntero de la pila de llamadas, y toda la memoria posterior sirve como pila de llamadas. Cuando se llama a una subrutina, se crea un nuevo marco en la pila de llamadas, que incluye todas las variables locales, así como la dirección de retorno (ROM). Cada subrutina del programa recibe una única dirección RAM estática para que sirva como puntero. Este puntero proporciona la ubicación de la llamada "actual" de la subrutina en la pila de llamadas. La referencia a una variable local se realiza utilizando el valor de este puntero estático más un desplazamiento para proporcionar la dirección de esa variable local en particular. También se incluye en la pila de llamadas el valor anterior del puntero estático. Aquí'

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

fib map:
0: return
1: previous_call
2: cur
3: sum

Una cosa que es interesante sobre las subrutinas es que no devuelven ningún valor en particular. Por el contrario, todas las variables locales de la subrutina se pueden leer después de que se realiza la subrutina, por lo que se puede extraer una variedad de datos de una llamada de subrutina. Esto se logra almacenando el puntero para esa llamada específica de la subrutina, que luego se puede utilizar para recuperar cualquiera de las variables locales desde el marco de la pila (recientemente desasignado).

Hay varias formas de llamar a una subrutina, todas utilizando la callpalabra clave:

call fib(10);   # subroutine is executed, no return vaue is stored

call pointer = fib(10);   # execute subroutine and return a pointer
display = pointer.sum;    # access a local variable and assign it to a global variable

call display = fib(10).sum;   # immediately store a return value

call display += fib(10).sum;   # other types of assignment operators can also be used with a return value

Se puede dar cualquier número de valores como argumentos para una llamada de subrutina. Cualquier argumento no proporcionado se completará con su valor predeterminado, si lo hay. Un argumento que no se proporciona y que no tiene un valor predeterminado no se borra (para guardar instrucciones / tiempo), por lo que podría tomar cualquier valor al comienzo de la subrutina.

Los punteros son una forma de acceder a múltiples variables locales de subrutina, aunque es importante tener en cuenta que el puntero es solo temporal: los datos a los que apunta el puntero se destruirán cuando se realice otra llamada de subrutina.

Etiquetas de depuración

Cualquier {...}bloque de código en un programa Cogol puede estar precedido por una etiqueta descriptiva de varias palabras. Esta etiqueta se adjunta como un comentario en el código ensamblado compilado, y puede ser muy útil para la depuración, ya que facilita la localización de fragmentos específicos de código.

Optimización de ranura de retardo de ramificación

Para mejorar la velocidad del código compilado, el compilador Cogol realiza una optimización de ranura de retardo realmente básica como un paso final sobre el código QFTASM. Para cualquier salto incondicional con una ranura de retardo de rama vacía, la primera instrucción en el destino de salto puede llenar el espacio de retardo, y el destino de salto se incrementa en uno para apuntar a la siguiente instrucción. Esto generalmente ahorra un ciclo cada vez que se realiza un salto incondicional.

Escribir el código Tetris en Cogol

El programa final de Tetris fue escrito en Cogol, y el código fuente está disponible aquí . El código QFTASM compilado está disponible aquí . Para mayor comodidad, se proporciona un enlace permanente aquí: Tetris en QFTASM . Dado que el objetivo era desarrollar el código de ensamblaje (no el código de Cogol), el código de Cogol resultante es difícil de manejar. Muchas partes del programa normalmente se ubicarían en subrutinas, pero esas subrutinas en realidad eran lo suficientemente cortas como para duplicar las instrucciones guardadas del código sobre elcalldeclaraciones. El código final solo tiene una subrutina además del código principal. Además, se eliminaron muchas matrices y se reemplazaron por una lista de variables individuales de longitud equivalente o por una gran cantidad de números codificados en el programa. El código QFTASM compilado final está bajo 300 instrucciones, aunque es solo un poco más largo que la fuente de Cogol.

Parte 5: Asamblea, traducción y el futuro

¡Con nuestro programa de ensamblaje del compilador, es hora de ensamblar una ROM para la computadora Varlife y traducir todo en un gran patrón GoL!

Montaje

El ensamblaje del programa de ensamblaje en una ROM se realiza de la misma manera que en la programación tradicional: cada instrucción se traduce a un equivalente binario, y luego se concatenan en un gran blob binario que llamamos ejecutable. Para nosotros, la única diferencia es que ese blob binario debe traducirse en circuitos de Varlife y conectarse a la computadora.

K Zhang escribió CreateROM.py , un script de Python para Golly que realiza el ensamblaje y la traducción. Es bastante sencillo: toma un programa de ensamblaje del portapapeles, lo ensambla en un binario y traduce ese binario en un circuito. Aquí hay un ejemplo con un simple probador de primalidad incluido con el script:

#0. MLZ -1 3 3;
#1. MLZ -1 7 6; preloadCallStack
#2. MLZ -1 2 1; beginDoWhile0_infinite_loop
#3. MLZ -1 1 4; beginDoWhile1_trials
#4. ADD A4 2 4;
#5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
#6. SUB A5 A4 5;
#7. SUB 0 A5 2;
#8. MLZ A2 5 0;
#9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
#10. MLZ A5 3 0;
#11. MNZ 0 0 0; endDoWhile1_trials
#12. SUB A4 A3 2;
#13. MNZ A2 15 0; beginIf3_prime_found
#14. MNZ 0 0 0;
#15. MLZ -1 A3 1; endIf3_prime_found
#16. ADD A3 2 3;
#17. MLZ -1 3 0;
#18. MLZ -1 1 4; endDoWhile0_infinite_loop

Esto produce el siguiente binario:

0000000000000001000000000000000000010011111111111111110001
0000000000000000000000000000000000110011111111111111110001
0000000000000000110000000000000000100100000000000000110010
0000000000000000010100000000000000110011111111111111110001
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011110100000000000000100000
0000000000000000100100000000000000110100000000000001000011
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000110100000000000001010001
0000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000001010100000000000000100001
0000000000000000100100000000000001010000000000000000000011
0000000000000001010100000000000001000100000000000001010011
0000000000000001010100000000000000110011111111111111110001
0000000000000001000000000000000000100100000000000001000010
0000000000000001000000000000000000010011111111111111110001
0000000000000000010000000000000000100011111111111111110001
0000000000000001100000000000000001110011111111111111110001
0000000000000000110000000000000000110011111111111111110001

Cuando se traduce a los circuitos de Varlife, se ve así:

Luego, la ROM se conecta con la computadora, que forma un programa completamente funcional en Varlife. Pero aún no hemos terminado ...

Traducción al juego de la vida

Todo este tiempo, hemos estado trabajando en varias capas de abstracción sobre la base de Game of Life. Pero ahora, es hora de retirar el telón de la abstracción y traducir nuestro trabajo en un patrón de Juego de la Vida. Como se mencionó anteriormente, estamos utilizando el OTCA Metapixel como base para Varlife. Entonces, el paso final es convertir cada celda en Varlife en un metapíxel en Game of Life.

Afortunadamente, Golly viene con un script ( metafier.py ) que puede convertir patrones en diferentes conjuntos de reglas a patrones de Game of Life a través del OTCA Metapixel. Desafortunadamente, solo está diseñado para convertir patrones con un único conjunto de reglas global, por lo que no funciona en Varlife. Escribí una versión modificada que aborda ese problema, de modo que la regla para cada metapíxel se genera celda por celda para Varlife.

Entonces, nuestra computadora (con la ROM de Tetris) tiene un cuadro delimitador de 1,436 x 5,082. De las 7.297.752 celdas en esa caja, 6.075.811 son espacios vacíos, lo que deja un recuento de población real de 1.221.941. Cada una de esas celdas debe traducirse a un metapíxel OTCA, que tiene un cuadro delimitador de 2048x2048 y una población de 64,691 (para un metapíxel ON) o 23,920 (para un metapíxel OFF). Eso significa que el producto final tendrá un cuadro delimitador de 2,940,928 x 10,407,936 (más unos pocos miles adicionales para los bordes de los metapíxeles), con una población entre 29,228,828,720 y 79,048,585,231. Con 1 bit por celda viva, se necesitan entre 27 y 74 GiB para representar toda la computadora y la ROM.

Incluí esos cálculos aquí porque me olvidé de ejecutarlos antes de comenzar el script, y rápidamente se quedó sin memoria en mi computadora. Después de un killcomando de pánico , hice una modificación en el script de metafier. Cada 10 líneas de metapíxeles, el patrón se guarda en el disco (como un archivo RLE comprimido) y la cuadrícula se vacía. Esto agrega tiempo de ejecución adicional a la traducción y utiliza más espacio en disco, pero mantiene el uso de la memoria dentro de límites aceptables. Debido a que Golly usa un formato RLE extendido que incluye la ubicación del patrón, esto no agrega más complejidad a la carga del patrón, solo abra todos los archivos de patrones en la misma capa.

K Zhang se basó en este trabajo y creó un script de metafier más eficiente que utiliza el formato de archivo MacroCell, que es mucho más eficiente que RLE para patrones grandes. Este script se ejecuta considerablemente más rápido (unos pocos segundos, en comparación con varias horas para el script metafier original), crea una salida mucho más pequeña (121 KB versus 1.7 GB), y puede metafizar todo el equipo y la ROM de una sola vez sin usar una cantidad masiva de la memoria Aprovecha el hecho de que los archivos MacroCell codifican árboles que describen los patrones. Al usar un archivo de plantilla personalizado, los metapíxeles se cargan previamente en el árbol, y después de algunos cálculos y modificaciones para la detección de vecinos, el patrón Varlife simplemente se puede agregar.

El archivo de patrones de toda la computadora y la ROM en Game of Life se puede encontrar aquí .

El futuro del proyecto

Ahora que hemos hecho Tetris, hemos terminado, ¿verdad? Ni siquiera cerca. Tenemos varios objetivos más para este proyecto en los que estamos trabajando:

• muddyfish y Kritixi Lithos continúan trabajando en el lenguaje de nivel superior que compila QFTASM.
• El'endia Starman está trabajando en las actualizaciones del intérprete QFTASM en línea.
• quartata está trabajando en un backend de GCC, que permitirá la compilación de código independiente C y C ++ (y potencialmente otros lenguajes, como Fortran, D u Objective-C) en QFTASM a través de GCC. Esto permitirá crear programas más sofisticados en un lenguaje más familiar, aunque sin una biblioteca estándar.
• Uno de los mayores obstáculos que tenemos que superar antes de que podamos avanzar más es el hecho de que nuestras herramientas no pueden emitir código independiente de la posición (por ejemplo, saltos relativos). Sin PIC, no podemos hacer ningún enlace, por lo que nos perdemos las ventajas de poder enlazar a bibliotecas existentes. Estamos trabajando para tratar de encontrar una manera de hacer PIC correctamente.
• Estamos discutiendo el próximo programa que queremos escribir para la computadora QFT. En este momento, Pong parece un buen gol.

Parte 6: El compilador más nuevo de QFTASM

Aunque Cogol es suficiente para una implementación rudimentaria de Tetris, es demasiado simple y de muy bajo nivel para la programación de propósito general en un nivel fácilmente legible. Comenzamos a trabajar en un nuevo idioma en septiembre de 2016. El progreso en el idioma fue lento debido a los errores difíciles de entender, así como a la vida real.

Creamos un lenguaje de bajo nivel con una sintaxis similar a Python, que incluye un sistema de tipo simple, subrutinas que admiten la recursividad y operadores en línea. El compilador de texto a QFTASM se creó con 4 pasos: el tokeniser, el árbol de gramática, un compilador de alto nivel y un compilador de bajo nivel.

El tokeniser

El desarrollo comenzó con Python utilizando la biblioteca de tokeniser integrada, lo que significa que este paso fue bastante simple. Solo se requirieron algunos cambios en la salida predeterminada, incluidos los comentarios de eliminación (pero no los #includes).

El árbol de la gramática

El árbol de gramática fue creado para ser fácilmente extensible sin tener que modificar ningún código fuente.

La estructura de árbol se almacena en un archivo XML que incluye la estructura de los nodos que pueden formar el árbol y cómo están formados con otros nodos y tokens.

La gramática necesitaba admitir nodos repetidos, así como los opcionales. Esto se logró mediante la introducción de metaetiquetas para describir cómo se debían leer los tokens.

Los tokens que se generan luego se analizan a través de las reglas de la gramática, de modo que la salida forma un árbol de elementos de gramática como subsy generic_variables, que a su vez contienen otros elementos de gramática y tokens.

Compilación en código de alto nivel

Cada característica del lenguaje debe poder compilarse en construcciones de alto nivel. Estos incluyen assign(a, 12) y call_subroutine(is_prime, call_variable=12, return_variable=temp_var). Características como la alineación de elementos se ejecutan en este segmento. Estos se definen como operatorsy son especiales porque están en línea cada vez que se usa un operador como +o %se usa. Debido a esto, están más restringidos que el código normal: no pueden usar su propio operador ni ningún operador que se base en el que se está definiendo.

Durante el proceso de alineación, las variables internas se reemplazan con las llamadas. Esto en efecto da vuelta

operator(int a + int b) -> int c
    return __ADD__(a, b)
int i = 3+3

dentro

int i = __ADD__(3, 3)

Sin embargo, este comportamiento puede ser perjudicial y propenso a errores si las variables de entrada y salida apuntan a la misma ubicación en la memoria. Para usar un comportamiento 'más seguro', la unsafepalabra clave ajusta el proceso de compilación de modo que se creen variables adicionales y se copien desde y hacia la línea según sea necesario.

Rasguño de variables y operaciones complejas

Las operaciones matemáticas como las que a += (b + c) * 4no se pueden calcular sin usar celdas de memoria adicionales. El compilador de alto nivel se ocupa de esto separando las operaciones en diferentes secciones:

scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

Esto introduce el concepto de variables reutilizables que se utilizan para almacenar información intermedia de cálculos. Se asignan según sea necesario y se desasignan en el grupo general una vez finalizado. Esto disminuye el número de ubicaciones de memoria de memoria virtual necesarias para su uso. Las variables de rasguño se consideran globales.

Cada subrutina tiene su propio VariableStore para mantener una referencia a todas las variables que usa la subrutina, así como su tipo. Al final de la compilación, se traducen en compensaciones relativas desde el inicio de la tienda y luego se les da direcciones reales en RAM.

Estructura RAM

Program counter
Subroutine locals
Operator locals (reused throughout)
Scratch variables
Result variable
Stack pointer
Stack
...

Compilación de bajo nivel

Las únicas cosas que el compilador de nivel bajo tiene que tratar son sub, call_sub, return, assign, ify while. Esta es una lista muy reducida de tareas que se pueden traducir a las instrucciones de QFTASM más fácilmente.

sub

Esto ubica el inicio y el final de una subrutina con nombre. El compilador de bajo nivel agrega etiquetas y, en el caso de la mainsubrutina, agrega una instrucción de salida (saltar al final de la ROM).

if y while

Tanto los intérpretes whilecomo los de ifbajo nivel son bastante simples: obtienen punteros a sus condiciones y saltan dependiendo de ellos. whilelos bucles son ligeramente diferentes ya que se compilan como

...
condition
jump to check
code
condition
if condtion: jump to code
...

call_sub y return

A diferencia de la mayoría de las arquitecturas, la computadora para la que estamos compilando no tiene soporte de hardware para empujar y hacer estallar desde una pila. Esto significa que tanto empujar como saltar de la pila toman dos instrucciones. En el caso de estallidos, disminuimos el puntero de la pila y copiamos el valor a una dirección. En el caso de empujar, copiamos un valor de una dirección a la dirección en el puntero de la pila actual y luego incrementamos.

Todos los locales para una subrutina se almacenan en una ubicación fija en la RAM determinada en el momento de la compilación. Para que la recursividad funcione, todos los locales para una función se colocan en la pila al comienzo de una llamada. Luego, los argumentos de la subrutina se copian en su posición en la tienda local. El valor de la dirección de retorno se coloca en la pila y se ejecuta la subrutina.

Cuando returnse encuentra una declaración, la parte superior de la pila se abre y el contador del programa se establece en ese valor. Los valores para los locales de la subrutina de llamada se sacan de la pila y se colocan en su posición anterior.

assign

Las asignaciones de variables son las cosas más fáciles de compilar: toman una variable y un valor y se compilan en una sola línea: MLZ -1 VALUE VARIABLE

Asignación de objetivos de salto

Finalmente, el compilador resuelve los objetivos de salto para las etiquetas adjuntas a las instrucciones. Se determina la posición absoluta de las etiquetas y luego las referencias a esas etiquetas se reemplazan con esos valores. Las etiquetas mismas se eliminan del código y finalmente los números de instrucción se agregan al código compilado.

Ejemplo de compilación paso a paso

Ahora que hemos pasado por todas las etapas, veamos un proceso de compilación real para un programa real, paso a paso.

#include stdint

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, lo suficientemente simple. Debería ser obvio que al final del programa, a = 8, b = 12, c = 96. En primer lugar, incluyamos las partes relevantes de stdint.txt:

operator (int a + int b) -> int
    return __ADD__(a, b)

operator (int a - int b) -> int
    return __SUB__(a, b)

operator (int a < int b) -> bool
    bool rtn = 0
    rtn = __MLZ__(a-b, 1)
    return rtn

unsafe operator (int a * int b) -> int
    int rtn = 0
    for (int i = 0; i < b; i+=1)
        rtn += a
    return rtn

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, un poco más complicado. Pasemos al tokeniser y veamos qué sale. En esta etapa, solo tendremos un flujo lineal de tokens sin ninguna forma de estructura

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP )
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT     
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP )
...

Ahora todos los tokens pasan por el analizador gramatical y generan un árbol con los nombres de cada una de las secciones. Esto muestra la estructura de alto nivel que lee el código.

GrammarTree file
 'stmts': [GrammarTree stmts_0
  '_block_name': 'inline'
  'inline': GrammarTree inline
   '_block_name': 'two_op'
   'type_var': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'a'
    '_global': False

   'operator': GrammarTree operator
    '_block_name': '+'

   'type_var_2': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'b'
    '_global': False
   'rtn_type': 'int'
   'stmts': GrammarTree stmts
    ...

Este árbol de gramática configura la información que debe analizar el compilador de alto nivel. Incluye información como los tipos de estructura y los atributos de una variable. El árbol de gramática luego toma esta información y asigna las variables que se necesitan para las subrutinas. El árbol también inserta todas las líneas.

('sub', 'start', 'main')
('assign', int main_a, 8)
('assign', int main_b, 12)
('assign', int op(*:rtn), 0)
('assign', int op(*:i), 0)
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'start', 1, 'for')
('call_sub', '__ADD__', [int op(*:rtn), int main_a], int op(*:rtn))
('call_sub', '__ADD__', [int op(*:i), 1], int op(*:i))
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'end', 1, global bool scratch_2)
('assign', int main_c, int op(*:rtn))
('sub', 'end', 'main')

Luego, el compilador de bajo nivel tiene que convertir esta representación de alto nivel en código QFTASM. Las variables son ubicaciones asignadas en la RAM de esta manera:

int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int <result>
global int <stack>

Luego se compilan las instrucciones simples. Finalmente, se agregan números de instrucciones, lo que resulta en un código QFTASM ejecutable.

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

La sintaxis

Ahora que tenemos el lenguaje básico, tenemos que escribir un pequeño programa en él. Estamos usando sangría como lo hace Python, dividiendo bloques lógicos y control de flujo. Esto significa que el espacio en blanco es importante para nuestros programas. Cada programa completo tiene una mainsubrutina que actúa igual que la main()función en lenguajes tipo C. La función se ejecuta al inicio del programa.

Variables y tipos

Cuando las variables se definen por primera vez, deben tener un tipo asociado a ellas. Los tipos definidos actualmente son inty boolcon la sintaxis para las matrices definidas pero no el compilador.

Bibliotecas y operadores.

stdint.txtEstá disponible una biblioteca llamada que define los operadores básicos. Si esto no está incluido, incluso los operadores simples no serán definidos. Podemos usar esta biblioteca con #include stdint. stdintdefine operadores tales como +, >>e incluso *y %, ninguno de los cuales son códigos de operación QFTASM directos.

El lenguaje también permite llamar directamente a los códigos de operación QFTASM __OPCODENAME__.

La adición en stdintse define como

operator (int a + int b) -> int
    return __ADD__(a, b)

Que define lo +que hace el operador cuando se le dan dos ints.