¿Número mínimo teórico de registros para una computadora moderna?

Tomé un curso sobre compiladores en mis estudios universitarios en el que escribimos un compilador que compila programas fuente en un lenguaje similar a Java de juguete a un lenguaje ensamblador de juguetes (para el cual teníamos un intérprete). En el proyecto hicimos algunas suposiciones sobre la máquina de destino estrechamente relacionada con los ejecutables nativos "reales", que incluyen:

una pila en tiempo de ejecución, rastreada por un registro de puntero de pila dedicado ("SP")
un montón para la asignación dinámica de objetos, seguido por un registro dedicado de puntero de montón ("HP")
un registro de contador de programa dedicado ("PC")
la máquina de destino tiene 16 registros
Las operaciones sobre datos (en oposición a, por ejemplo, saltos) son operaciones de registro a registro

Cuando llegamos a la unidad sobre el uso de la asignación de registros como optimización, me pregunté: ¿Cuál es el número mínimo teórico de registros para una máquina de este tipo? Puede ver por nuestras suposiciones que utilizamos cinco registros (SP, HP, PC, más dos para usar como almacenamiento para operaciones binarias) en nuestro compilador. Si bien las optimizaciones como la asignación de registros sin duda pueden hacer uso de más registros, ¿hay alguna forma de sobrevivir con menos mientras se conservan estructuras como la pila y el montón? Supongo que con el direccionamiento de registros (operaciones de registro a registro) necesitamos al menos dos registros, pero ¿necesitamos más de dos?

compilers computer-architecture BlueBomber
fuente

Un "puntero de pila" parece una idea extraña. Porque al contrario de la pila, el montón no es LIFO y no se reduce a la semántica push / pop. Debería ver la asignación de memoria dinámica como llamadas a malloc / rutinas libres.

Yves Daoust

Respuestas:

Si permite el acceso directo a la memoria por dirección de memoria, entonces no necesita ningún "registro" porque puede usar ubicaciones de memoria en su lugar. Por ejemplo, la memoria en la ubicación 0 puede ser el contador del programa, en la ubicación 1 tenemos el puntero de la pila, etc. Pero eso es trampa.

Entonces, para evitar hacer trampa, supongamos que no hay acceso directo a la memoria, porque podríamos usar ubicaciones de memoria fija como registros. Entonces podemos salir con dos registros, un contador de programa y un puntero de pila, como se explica en el artículo de Wikipedia sobre máquinas de pila . Solo se puede acceder a la pila a través del puntero de la pila, y solo se puede acceder al programa a través del contador del programa.

Otra posibilidad es utilizar máquinas de mostrador. Una máquina de dos contadores está completa en Turing, es decir, puede calcular cualquier máquina de Turing. Esto nuevamente se explica muy bien en el artículo de Wikipedia sobre máquinas de mostrador .

Andrej Bauer
fuente

¡Gracias por la respuesta! Sin embargo, el artículo sobre máquinas apiladas menciona que la máquina es capaz de acceder directamente a la memoria (para realizar operaciones en los elementos de la pila más altos y volver a activar el resultado), por lo que todavía es trampa, ¿verdad? En cuanto a la máquina de mostrador, leí ese artículo. También he leído una prueba similar de TC de un 2-CM, pero ambos implican efectivamente almacenar toda la RAM en dos registros, lo que me parece aún más una trampa.

BlueBomber

Bueno, en algún momento ya no es trampa. Las operaciones de pila no son trampas, siempre y cuando no permitan el acceso directo a una ubicación fija en la memoria. Está bien poder, por ejemplo, rotar los tres elementos superiores de la pila. De todos modos, su pregunta es un poco extraña, por lo que no vale la pena obsesionarse con lo que es y lo que no es trampa.

Andrej Bauer

Gracias de nuevo por la respuesta. Cada vez que el tema se relaciona con límites teóricos, ¡hacer trampa es aún menos aceptable! Sin embargo, eso no significa que no sea instructivo. El punto cuando no es trampa es cuando, bueno, no hay trampa, supongo. Encontré su respuesta inicial informativa, pero el problema es que nuestro modelo se superpone a todos los modelos de Turing Machine, Counter Machine y Stack Machine, y dadas nuestras suposiciones (incluidos finitos registros finitos y sin acceso directo a memoria), ¿podemos superarlo? con solo dos registros?

BlueBomber

La pregunta me parece extraña porque es difícil precisar conceptos del mundo real como procesador, registro, acceso a la memoria, etc., pero necesita precisarlos para poder probar algo. Entonces, el resultado final será que todo lo que demuestre es fácil de probar, pero depende mucho de cómo formalice la pregunta (cuál es su noción teórica de "procesador", "registro", "memoria", etc.).

Andrej Bauer

Un libro de texto del compilador no nos permite probar mucho, al menos no en el sentido matemático de la palabra "probar". Debe ir un paso más allá en la formalización del hardware para llegar a algo que permita la prueba . De todos modos, nos estamos partiendo los pelos, y ya te di mi mejor respuesta.

Andrej Bauer

La arquitectura PIC que fue introducida por General Instruments en la década de 1970 y que todavía se usa hoy en día tenía los siguientes registros:

W register (not addressible)
01    Timer/Counter
02    Program Counter
03    Status
04    File-Select Register
05-07 One register for each I/O port
08-1F General-purpose registers/"memory"

Una instrucción típica leerá un registro, realizará un cálculo utilizando el valor leído y W, y luego almacenará el resultado del cálculo en W o en el registro que se leyó. Uno de los cálculos disponibles produce "el valor leído, ignorando W"; otro es "tomar W, ignorando el valor leído". Los patrones de bits que corresponderían a "leer XX, luego tomar W, ignorar el valor leído y almacenar el resultado en W" se usan para NOP, así como una variedad de instrucciones especiales.

Para permitir cálculos de dirección, la unidad de ejecución del procesador buscará instrucciones que codifiquen una dirección de 00, y sustituirá el contenido del Registro de selección de archivo por la dirección.

Aunque tener que alimentar todos los valores a través del registro W puede ser un cuello de botella, la arquitectura PIC tiene un conjunto de trabajo más grande que otras arquitecturas que usan la misma palabra de instrucción de longitud. En el PIC16C54 (todavía fabricado hoy, y muy similar a los PIC de la década de 1970) las instrucciones tienen 12 bits de longitud. En muchas otras partes 16Cxx o 16Fxx, las instrucciones tienen una longitud de 14 bits y pueden acceder directamente a un espacio de direcciones de 128 bytes. Si el conjunto de trabajo de un programa encaja bien con el conjunto de trabajo del conjunto de instrucciones, una declaración como "total + = valor", donde "total" y "valor" son de tipo unsigned char, se compilaría para:

movf  value,w
addwf total,f

En algo como el ARM, incluso si uno tiene un registro precargado con la dirección base de las variables, el código sería más parecido a:

ldr    r0,[r7+value]
ldr    r1,[r7+total]
add    r1,r1,r0
str    r1,[r7+total]

En muchos casos, un compilador podría evitar cargar y almacenar con cada operación, pero en algo como el PIC, los beneficios del conjunto de trabajo más grande a veces superan las limitaciones de tener que pasar por W todo el tiempo.

Super gato
fuente