pila de caché en lugar de registros

¿Existe un procesador que haga operaciones aritméticas en una pila y no en registros? Por supuesto, para mantener el rendimiento, ese procesador debe almacenar en caché el bloque superior de una pila en el mismo tipo de memoria que se usa para los registros.

Leí en un artículo (David R. Ditzel, HR McLellan. Register Allocation for Free: The C Machine Stack Cache. ) que un caché es 2 veces más lento que los registros debido a:

  • direccionamiento indirecto durante cada acceso al caché;
  • Caché falla cuando la pila crece.

El papel es viejo. ¿Quizás aparecieron mejoras en el diseño del procesador que hacen viable la caché de pila? Siento que reducirá la complejidad de los compiladores y optimizará la copia entre registros y el resto de la memoria.

Actualización 2012-10-18. Como este concepto era bien conocido (no para mí), cambio la pregunta a "... ¿Procesadores modernos?"

Actualización 2012-10-18. Siento que debo decir explícitamente que no estoy hablando de una "máquina de dirección cero". El almacenamiento en caché y la "dirección cero" son ortogonales. Mi procesador hipotético puede tener incluso una suma de 5 arios como "r3 := r0+r2+r11+r5+r8". “rn” significa la celda de memoria en sp+n, donde sp es un puntero de pila. sp cambia antes y después de un bloque de código. Un programa muy inusual cambia sp en cada operación aritmética.

Como dije en mi respuesta, una dificultad fundamental con tales máquinas es que, en general, es difícil para la lógica de programación de instrucciones mantener algún tipo de coherencia si el puntero de la pila cambia. Habiendo dicho eso, puedo imaginar que en algunos casos podría ser útil tener una pila especial de 'guardar registro' para los registros que deberán conservarse, pero a los que no será necesario acceder excepto para restaurarlos. En un sistema con 16 registros de "usuario" de 32 bits, dicha pila podría tener, por ejemplo, 16 bits de profundidad y 512 bits de ancho (más algunos bits de control).
Cuando sea necesario guardar algún subconjunto de registros, los 128 bits del archivo de registro se copiarán en la pila en paralelo; si la pila está llena, el "derrame" se escribiría en la caché principal como una o dos líneas de caché (dependiendo del tamaño de la línea de caché). Al restaurar registros, solo se recargarían los registros programados para la restauración. En muchos casos, una arquitectura de este tipo podría minimizar la cantidad de tráfico de registro guardado/restauración que va y viene del caché principal, pero no estoy seguro de que el efecto general en el rendimiento sea suficiente para justificarlo.
De acuerdo, dado que no está hablando de máquinas apiladoras, localicé el documento al que hace referencia y lo leí. Las razones que dan al principio de por qué el caché siempre es más lento que los registros son cuestiones arquitectónicas, independientes de la tecnología de implementación. El caché administrado explícitamente que proponen se encuentra en algún punto intermedio. En los 30 años transcurridos desde que se escribió ese documento, la tecnología de compilación se ha vuelto mucho más sofisticada y puede aprovechar al máximo el hardware creado para obtener la máxima velocidad (usando registros).
@supercat: "Me imagino que en algunos casos podría ser útil tener una pila especial de 'guardar registro' para los registros que deberán conservarse" ¿En algunos casos? Je-je. Esta es la única manera de que funcionen las funciones recursivas. ;)
@Dave Tweed: eliminé su enlace pagado; el primer enlace en los resultados de búsqueda de Google es descarga gratuita.
@Dave Tweed: Bueno, los compiladores generan instrucciones para mover datos entre la pila y los registros. En mi humilde opinión, hacer esto automáticamente sería más rápido. De todos modos, el objetivo original era acortar la especificación de un procesador.

Respuestas (5)

Sí, toda la línea de computadoras centrales de Burroughs a partir de 1961 con la B5000 utilizó una arquitectura de pila.

En esta arquitectura, administrar el flujo de datos hacia y desde la pila en realidad no es un gran cuello de botella para el rendimiento. Un problema mayor es el hecho de que una máquina de "dirección cero" necesita muchas más instrucciones para completar una tarea determinada que una máquina de una, dos o tres direcciones. La decodificación de instrucciones y la tubería de ejecución se convierten en el cuello de botella principal.

Cuando trabajé allí a principios de la década de 1980, se hizo un esfuerzo por construir una CPU que pudiera precargar secuencias relativamente grandes de instrucciones de dirección cero y traducirlas sobre la marcha a operaciones de tres direcciones que se alimentarían a la canalización de ejecución. (Piense en un compilador Java JIT implementado en hardware). Se volvió bastante complejo, especialmente para las tecnologías de implementación disponibles en ese momento, y no sé si esta estrategia finalmente tuvo éxito.

En caso de que se lo pregunte, la terminología de "dirección N" se refiere a la cantidad de operandos que se pueden especificar en una sola instrucción. Todas las operaciones en una máquina de pila están implícitamente en una o dos ubicaciones superiores en la pila, por lo que no hay operandos en las instrucciones. Una máquina que tiene un acumulador que se usa para todas las operaciones junto con otro registro o ubicación de memoria es una máquina de una sola dirección. Una máquina de dos direcciones puede especificar un operando de origen y destino arbitrario en una instrucción, y una máquina de tres direcciones puede especificar dos operandos de origen y poner el resultado en un destino independiente.

+1. Para poner la dirección N en el contexto actual, los PIC de 8 bits como PIC 16 y PIC 18 tienen principalmente instrucciones de una dirección, ya que la mayoría de las operaciones implican el registro W para uno de los operandos y el resultado es el registro W o volver a la ubicación de la fuente. El dsPIC y sus derivados (PIC 24, 30 y 33) son en gran parte máquinas de 3 direcciones, aunque las operaciones están limitadas al conjunto de registros de 16 W. No obstante, muchas operaciones se pueden realizar con dos registros W como operandos y el resultado escrito en un tercero. Esta es básicamente la versión RISC de 3 direcciones.
Si uno tiene una cantidad específica de bits en un código de operación para codificar todas las direcciones que necesitarán las instrucciones, creo que el conjunto de trabajo más grande habilitado por una arquitectura de una o dos direcciones a menudo superaría las ventajas de uno de tres direcciones, siempre que el conjunto de instrucciones minimice la "penalización" para los casos en que pasar por un solo registro fue inadecuado. La dirección cero no funciona muy bien, pero creo que una máquina de pila de una dirección podría ser bastante buena si no estuviera tratando de superponer las instrucciones de manera demasiado agresiva.
@OlinLathrop: consideraría algo similar a las instrucciones de dirección única del PIC con destino seleccionable como casi ideal, si la entrada "W" a la ALU viniera de un registro que normalmente reflejaría W excepto después de un "uselw" o " usefw" (que lo cargaría con una constante o el contenido de otro registro). En lugar de un código de operación "movff" dedicado de dos palabras, usaría la secuencia "usefw src / movwf dest" [después de lo cual, el registro temporal se volvería a cargar con W]. Eso permitiría "usefw src / addwf dest,f" como un medio de "dest += src" sin molestar a W.
@OlinLathrop: para aplicaciones donde todas las partes de uso común del conjunto de trabajo pueden caber dentro del rango de direccionamiento de una instrucción sin banca, movf src / addwf dest,fes más rápido que ldr r0,[src+r13] / ldr r1,[dest+r13] / add r0,r0,r1 / str [src+r13](y realiza su actualización de destino atómicamente). Lástima que agregar un número a otro mientras el valor de Wse necesita para otra cosa cuesta cuatro ciclos (uno para guardar W, uno para cargar un operando, uno para hacer la operación y uno para restaurar W). Algo como usefwpodría reducir eso a dos.
No, no estoy hablando de una máquina de "dirección cero". Por ejemplo, el operando "R5" significa la celda de memoria en SP+5, y esta celda de memoria se almacena en caché porque está cerca de la parte superior de la pila.

Recuerdo haber leído un artículo similar (quizás el mismo) hace unos 17 años. Tal enfoque podría ser bueno si uno estuviera desarrollando un procesador para ejecutar una instrucción a la vez rápidamente. Desafortunadamente, no funciona bien con la programación de instrucciones desordenadas. Si uno tiene un código como:

  ldr r1,[r0]
  ... hacer algunas cosas que no involucren a r1, r2 o [r2]
  cadena r1,[r2]

Un programador de instrucciones es libre de cambiar esas dos instrucciones como mejor le parezca. Si bien puede ser difícil para el programador de instrucciones saber si una escritura en alguna ubicación de memoria podría ser una escritura en [r2], muchos lenguajes compilados requieren que los programadores indiquen qué cosas pueden o no tener un alias.

Por el contrario, las instrucciones eran más como:

  mov.l [r0],[--sp] ; Empuje [r0] en la pila
  ... hacer algunas cosas, lo que afecta sp
  mov.l [sp++],[r2] ; Pop [r2] de la pila

Sería mucho más difícil para un motor de ejecución fuera de orden determinar si el operando de origen para la última instrucción siempre sería el mismo que el operando de destino de la primera, y si alguna instrucción intermedia podría afectarlo.

En el pasado trabajé con el Saab Ericsson Space Thor, un microprocesador para aplicaciones espaciales. Funcionó, pero tenía algunos inconvenientes serios. Solo uno: se expuso la canalización de instrucciones: la instrucción que cargó una palabra de la memoria utilizada como dirección hace 2 instrucciones en la parte superior de la pila . Escribí una rutina de copia de memoria rápida para él, pero Saab dijo que no podía usarse porque las interrupciones causarían problemas...

Había procesadores Forth dedicados que solían usarse en el procesador de arranque para máquinas Sun/Sparc cuya arquitectura dedicada se asignaba al idioma. Pero generalmente no está disponible.

El x86 es casi uno de esos :-) (y la parte x87 fp aún más cerca)

Sin embargo, en los sistemas modernos, la pila es terrible, porque puede crear alias entre núcleos o incluso nodos NUMA, por lo que puede estar involucrada una gran cantidad de señalización lenta y de larga distancia. O, como mínimo, más enclavamientos de los que obtiene con un archivo de registro y cambio de nombre de registro.

Considere que ni siquiera las CPU, pero otros dispositivos pueden incluir datos DMA en su pila, ¡piense en leer búferes!

Sí, casi. x86 tiene AX, BX, CX, DX, BP, SI, DI. Esta lista no es particularmente corta. :) En realidad, probé la pila frente a los registros en AMD Athlon y descubrí que los registros son 2 veces más rápidos que la pila. DMA u otro procesador que accede a la pila del procesador generalmente es un error del programador, por lo que el procesador no necesita resolver este conflicto, diga "el comportamiento no está definido" en tales casos.
No, el acceso de DMA a la pila es común: considere los búferes en la pila para las llamadas a read() o write(). Esto no es un error del programador, y las CPU no pueden decir "comportamiento indefinido" para eso. Recuerdo una placa base PowerPC antigua donde este comportamiento no estaba definido debido a un error en el hardware de Apple; eso fue "divertido" de manejar... El x87 es un conjunto de instrucciones completamente basado en pilas, aunque la "pila de trabajo" es muy limitada y necesita extenderse a la pila "real".
"considere los búferes en la pila para llamadas a leer () o escribir ()" Podemos deshacernos de esto.
@JonWatte: Poner un búfer DMA en la pila parece una mala idea cuando se usa E/S síncrona, y una muy, muy mala idea para usar E/S asíncrona. Como mínimo, incluso en el caso de E/S síncrona, requiere que cualquier ejecutivo multitarea sepa cómo cancelar cualquier operación DMA pendiente si necesita eliminar un subproceso. Y en el caso de E/S asíncrona, es una receta para el desastre si la rutina que configura el DMA se cierra inesperadamente antes de que se complete el DMA.
Claramente, la E/S asíncrona no puede usar búferes de pila. Sin embargo, UNIX no es muy bueno en la E/S asíncrona; la mayoría de los programas en realidad usan E/S síncrona. El kernel no necesariamente tiene que esperar a que se complete la E/S antes de eliminar una asignación de pila, siempre que las páginas físicas aún tengan un recuento de referencias y no se eliminen hasta que se complete la E/S. Recuerde: DMA generalmente se realiza con direcciones físicas, fuera de la capa de traducción de VM. Sé de núcleos que hacen referencia a páginas físicas; No sé si todos hacen eso.
pila de caché en lugar de registros
RespuestasAquíPolítica de privacidad1y, 0v