De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Para máquinas apiladas en la teoría de autómatas, consulte Autómata de empuje .

En las implementaciones de lenguajes de programación , ingeniería informática y ciencias de la computación , una máquina de pila es un modo de cálculo en el que el control de ejecución se mantiene completamente mediante la adición (inserción), la lectura y el truncamiento (pop) de un primero en entrar, el último en salir (FILO, también búfer de memoria último en entrar, primero en salir o LIFO) , conocido como pila , que requiere muy pocos registros de procesador . Una máquina apiladora es suficiente para coordinar el funcionamiento de toda una computadora y el sistema operativo, por ejemplo, el Burroughs B5000 , puede definir un programa de software en particular, por ejemplo, el intérprete de PostScript de Adobe . lenguaje de formato de impresión, o puede usarse solo en una parte del hilo de ejecución de un programa.

Robert proporcionó por primera vez en la conferencia la descripción de un método de este tipo que requiere solo dos valores a la vez, con un conjunto limitado de operandos predefinidos que podían ampliarse mediante la definición de más operandos, funciones y subrutinas. S. Barton en 1961. [1] [2]

Esto contrasta con el flujo de programa típico, que podría saltar de un lado a otro aparentemente al azar, que todavía se encuentra con frecuencia hoy en día, donde comúnmente, numerosos valores mantenidos en registros proporcionan ubicaciones de memoria para el control del flujo del programa, donde también se puede usar una pila, pero es no se cumple estrictamente como único medio de control.

En una máquina de pila, los operandos usados ​​en las instrucciones están siempre en un desplazamiento conocido (establecido en el puntero de pila), desde una ubicación fija (la parte inferior de la pila, que en un diseño de hardware siempre podría estar en la ubicación de memoria cero), evitando que el valioso almacenamiento en caché o en la CPU se utilice para almacenar tantas direcciones de memoria o números de índice. Esto conduce a un estilo de arquitectura de conjunto de instrucciones (ISA) conocido como formato de dirección cero , [3] y puede preservar dichos registros y caché para su uso en cálculos sin flujo. [ cita requerida ]

Dado que una pila es un componente de la mayoría de los programas de software, incluso cuando el software utilizado no es estrictamente una máquina de pila, una máquina de pila de hardware podría imitar más de cerca el funcionamiento interno de sus programas. Los registros del procesador tienen un alto costo térmico y una máquina apiladora puede reclamar una mayor eficiencia energética. [4] Sin embargo, estos diseños han sido superados de forma rutinaria por los sistemas tradicionales de máquinas de registro y se han mantenido como un jugador de nicho en el mercado. [ cita requerida ]

La máquina virtual del lenguaje de programación Java , núcleo del sistema operativo Android que se usa en los teléfonos inteligentes , es un ejemplo muy común de una máquina de pila.

Máquinas prácticas de pila de expresiones [ editar ]

Una "máquina de pila" es una computadora que usa una pila de último en entrar, primero en salir para almacenar valores temporales de corta duración. La mayoría de sus instrucciones asumen que los operandos serán de la pila y los resultados se colocarán en la pila.

Para una instrucción típica, como Addla computadora, toma ambos operandos de los valores más altos (más recientes) de la pila. La computadora reemplaza esos dos valores con la suma, que la computadora calcula cuando ejecuta la Addinstrucción. Los operandos de la instrucción se "extraen" de la pila y sus resultados se "empujan" de nuevo a la pila, listos para la siguiente instrucción. La mayoría de las instrucciones de pila tienen solo un código de operación que ordena una operación, sin campos adicionales para identificar una constante, un registro o una celda de memoria. La pila contiene fácilmente más de dos entradas o más de un resultado, por lo que se puede calcular un conjunto más rico de operaciones. Los operandos enteros constantes a menudo son empujados por Load Immediateinstrucciones separadas . A menudo se accede a la memoria por separado LoadoStore instrucciones que contienen una dirección de memoria o que calculan la dirección a partir de los valores de la pila.

Para mayor velocidad, una máquina de pila a menudo implementa una parte de su pila con registros. Para ejecutar rápidamente, los operandos de la unidad aritmética lógica (ALU) pueden ser los dos registros superiores de la pila y el resultado de la ALU se almacena en el registro superior de la pila. Algunas máquinas de pila tienen una pila de tamaño limitado, implementada como un archivo de registro. La ALU accederá a esto con un índice. Algunas máquinas tienen una pila de tamaño ilimitado, implementada como una matriz en la RAM a la que se accede mediante un registro de direcciones "superior de la pila". Esto es más lento, pero la cantidad de flip-flops es menor, lo que hace que la CPU sea menos costosa y más compacta. Sus valores N superiores pueden almacenarse en cachépor velocidad. Algunas máquinas tienen una pila de expresiones en la memoria y una pila de registros separada. En este caso, el software o una interrupción pueden mover datos entre ellos.

El conjunto de instrucciones realiza la mayoría de las acciones de ALU con operaciones de sufijo ( notación polaca inversa ) que funcionan solo en la pila de expresiones, no en registros de datos o celdas de memoria principal. Esto puede ser muy conveniente para ejecutar lenguajes de alto nivel, porque la mayoría de las expresiones aritméticas se pueden traducir fácilmente a la notación de sufijo.

Por el contrario, las máquinas de registro contienen valores temporales en una matriz de registros pequeña y rápida . Las máquinas acumuladoras tienen un solo registro de uso general. Las máquinas de banda usan una cola FIFO para almacenar valores temporales. Las máquinas de memoria a memoria no tienen registros temporales que pueda utilizar un programador.

Las máquinas de pila pueden tener su pila de expresiones y su pila de devolución de llamadas separadas o como una estructura integrada. Si están separados, las instrucciones de la máquina apiladora se pueden canalizar con menos interacciones y menos complejidad de diseño. Por lo general, puede funcionar más rápido.

Algunas calculadoras de mano técnicas utilizan la notación polaca inversa en su interfaz de teclado, en lugar de tener teclas entre paréntesis. Esta es una forma de máquina apiladora. La tecla Plus se basa en que sus dos operandos ya se encuentran en las posiciones superiores correctas de la pila visible para el usuario.

Ventajas de los conjuntos de instrucciones de la máquina de pila [ editar ]

Código objeto muy compacto [ editar ]

En el código de máquina de pila, las instrucciones más frecuentes consisten en solo un código de operación que selecciona la operación. Esto puede caber fácilmente en 6 bits o menos. Las ramificaciones, los inmediatos de carga y las instrucciones de carga / almacenamiento requieren un campo de argumento, pero las máquinas de apilado a menudo establecen que los casos frecuentes de estos todavía encajan con el código de operación en un grupo compacto de bits. La selección de operandos de resultados anteriores se realiza implícitamente ordenando las instrucciones. En contraste, las máquinas de registro requieren dos o tres campos de número de registro por instrucción ALU para seleccionar operandos; las máquinas de registro más densas promedian alrededor de 16 bits por instrucción más los operandos.

Las instrucciones para máquinas acumuladoras o de memoria a memoria no se completan con varios campos de registro. En su lugar, utilizan variables anónimas administradas por el compilador para los valores de subexpresión. Estas ubicaciones temporales requieren instrucciones de referencia de memoria adicionales que ocupan más espacio de código que para la máquina de pila, o incluso las máquinas de registro compactas.

Todas las máquinas de pila prácticas tienen variantes de los códigos de operación de almacenamiento de carga para acceder a variables locales y parámetros formales sin cálculos de dirección explícitos. Esto puede ser por compensaciones de la dirección actual de la parte superior de la pila, o por compensaciones de un registro base de trama estable. Las máquinas de registro manejan esto con un modo de dirección de registro + desplazamiento, pero utilizan un campo de desplazamiento más amplio.

El código de máquina denso era muy valioso en la década de 1960, cuando la memoria principal era muy cara y muy limitada incluso en los mainframes. Volvió a ser importante en las memorias inicialmente minúsculas de las miniordenadores y luego en los microprocesadores. La densidad sigue siendo importante en la actualidad, para las aplicaciones de teléfonos inteligentes, las aplicaciones descargadas en los navegadores a través de conexiones lentas a Internet y en las ROM para las aplicaciones integradas. Una ventaja más general del aumento de la densidad es la eficacia mejorada de los cachés y la captación previa de instrucciones.

Parte de la densidad del código Burroughs B6700 se debió a que la información vital del operando se movía a otra parte, a 'etiquetas' en cada palabra de datos o en tablas de punteros. La instrucción Add en sí era genérica o polimórfica. Tenía que buscar el operando para descubrir si se trataba de una suma entera o una suma de punto flotante. La instrucción Load podría encontrarse disparándose en una dirección indirecta , o peor, una llamada disfrazada a una rutina de procesador de llamada por nombre . Los códigos de operación genéricos requerían menos bits de código de operación, pero hacían que el hardware se pareciera más a un intérprete, con menos oportunidades de canalizar los casos comunes.

Compiladores simples [ editar ]

Los compiladores para máquinas apiladas son más simples y rápidos de construir que los compiladores para otras máquinas. La generación de código es trivial e independiente del código anterior o posterior. La imagen muestra el árbol de sintaxis correspondiente a la expresión de ejemplo A * ( B - C ) + ( D + E ).

Árbol de sintaxis binaria para la expresión A * ( B - C ) + ( D + E )

El código compilado para una máquina de pila simple tomaría la forma (correspondiente a la notación polaca inversa de las expresiones A B C - * D E + +):

 # apilar contenido (más a la izquierda = arriba): empujar A # A empujar B # BA empujar C # CBA restar # BC A multiplicar # A * (BC) presione D # DA * (BC) presione E # EDA * (BC) agregar # D + EA * (BC) agregar # A * (BC) + (D + E)

Las operaciones aritméticas 'restar', 'multiplicar' y 'sumar' actúan sobre los dos operandos superiores de la pila.

Esta compilación simple se puede realizar mediante el pase de análisis. No se necesita gestión de registros. La mayoría de las máquinas de pila pueden copiar entradas de pila para evitar el acceso a la memoria (que es mucho más lento), pero estas suelen ser triviales. El mismo código de operación que maneja el caso común frecuente de una adición, una carga indexada o una llamada de función también manejará el caso general que involucra subexpresiones complejas y llamadas anidadas. El compilador y la CPU no necesitan casos especiales para instrucciones que tienen rutas de cálculo separadas para direcciones.

Esta simplicidad ha permitido que los compiladores se adapten a máquinas muy pequeñas. Los compiladores simples permitieron que nuevas líneas de productos llegaran al mercado rápidamente y permitieron que los nuevos sistemas operativos se escribieran completamente en un lenguaje de alto nivel en lugar de en ensamblador. Por ejemplo, UCSD p-System admitía un entorno completo de programación para estudiantes en los primeros microprocesadores de 8 bits con conjuntos de instrucciones deficientes y poca RAM, compilando en una máquina de pila virtual en lugar del hardware real.

La desventaja de la simplicidad de los compiladores para máquinas de pila es que las máquinas de pila pura tienen menos optimizaciones (ver subsecciones en § Desventajas de rendimiento de las máquinas de pila ). Sin embargo, la optimización del código de pila compilado es bastante posible. Se ha demostrado que la optimización de back-end de la salida del compilador mejora significativamente el código, [5] [6] y potencialmente el rendimiento, mientras que la optimización global dentro del propio compilador logra mayores ganancias. [7]

Intérpretes simples [ editar ]

Algunos conjuntos de instrucciones de la máquina de pila están pensados ​​para la ejecución interpretativa de una máquina virtual, en lugar de controlar el hardware directamente. Los intérpretes para máquinas de pila virtual son más fáciles de construir que los intérpretes para máquinas de registro o de memoria a memoria; la lógica para manejar los modos de dirección de memoria está en un solo lugar en lugar de repetirse en muchas instrucciones. Las máquinas apiladas también tienden a tener menos variaciones de un código de operación; un código de operación generalizado manejará tanto los casos frecuentes como los casos oscuros de las esquinas de referencias de memoria o configuración de llamadas a funciones. (Pero la densidad del código a menudo se mejora agregando formas cortas y largas para la misma operación).

Acceso rápido al operando [ editar ]

Dado que no hay campos de operandos para decodificar, las máquinas de pila obtienen cada instrucción y sus operandos al mismo tiempo. Las máquinas de pila pueden omitir la etapa de búsqueda de operandos de una máquina de registro. [8] Además, excepto la carga explícita de las instrucciones de memoria, el orden de uso de los operandos es idéntico al orden de los operandos en la pila de datos. Por lo tanto, la obtención previa excelente se logra fácilmente al mantener los operandos en la parte superior de la pila en un almacenamiento rápido. Por ejemplo, en el microprocesador Java Optimized Processor (JOP), los 2 operandos superiores de la pila entran directamente en un circuito de reenvío de datos que es más rápido que el archivo de registro. [9]

Evita el paso de datos a través de la memoria, intérpretes más rápidos [ editar ]

El acceso rápido también es útil para los intérpretes. La mayoría de los intérpretes de registros especifican sus registros por número. Pero no se puede acceder a los registros de una máquina host en una matriz indexada, por lo que se asigna una matriz de memoria para registros virtuales. Por lo tanto, las instrucciones de un intérprete de registros deben usar la memoria para pasar los datos generados a la siguiente instrucción. Esto obliga a los intérpretes de registro a ser mucho más lentos en microprocesadores fabricados con una regla de proceso fina (es decir, transistores más rápidos sin mejorar la velocidad del circuito, como el Haswell x86). Estos requieren varios relojes para acceder a la memoria, pero solo un reloj para acceder al registro. En el caso de una máquina de pila con un circuito de reenvío de datos en lugar de un archivo de registro, los intérpretes de pila pueden asignar los registros de la máquina host para los varios operandos superiores de la pila en lugar de la máquina host 's memoria.

Estado mínimo del procesador [ editar ]

Una máquina con una pila de expresiones puede funcionar con solo dos registros que son visibles para un programador: la dirección de la parte superior de la pila y la dirección de la siguiente instrucción. La implementación de hardware mínima tiene muchos menos bits de flipflops o registros. Los diseños más rápidos pueden simplemente almacenar en búfer las N celdas de pila superiores en registros para reducir los ciclos de pila de memoria.

Responder a una interrupción implica guardar los registros en una pila y luego bifurcar al código del controlador de interrupciones. En una máquina de pila, la mayoría de los parámetros ya están en una pila. Por lo tanto, no es necesario empujarlos allí. A menudo, las máquinas apiladoras responden más rápidamente a las interrupciones. Algunas máquinas de registro se ocupan de esto al tener varios archivos de registro que se pueden intercambiar instantáneamente [10], pero esto aumenta los costos y ralentiza el archivo de registro.

Desventajas de rendimiento de las máquinas apiladoras [ editar ]

Más referencias de memoria [ editar ]

Algunos en la industria creen que las máquinas de pila ejecutan más ciclos de caché de datos para valores temporales y variables locales que las máquinas de registro. [11]

En las máquinas de pila, los valores temporales a menudo se derraman en la memoria, mientras que en las máquinas con muchos registros, estas temperaturas suelen permanecer en los registros. (Sin embargo, estos valores a menudo deben dividirse en "marcos de activación" al final de la definición de un procedimiento, bloque básico, o al menos, en un búfer de memoria durante el procesamiento de interrupciones). Los valores derramados en la memoria agregan más ciclos de caché. Este efecto de derrame depende del número de registros ocultos utilizados para almacenar en búfer los valores de la parte superior de la pila, de la frecuencia de las llamadas a procedimientos anidados y de las tasas de procesamiento de interrupciones de la computadora host.

Algunas máquinas de pila simples o intérpretes de pila no utilizan registros de hardware de la parte superior de la pila. Esas implementaciones mínimas son siempre más lentas que las máquinas de registro estándar. Una expresión típica como X+1compila a Load X; Load 1; Add. Esto hace escrituras y lecturas implícitas de la pila de memoria que no fueron necesarias:

  • Cargar X, empujar a la memoria
  • Carga 1, empuja a la memoria
  • Extraer 2 valores de la memoria, agregar y enviar el resultado a la memoria

para un total de 5 referencias de caché de datos.

El siguiente paso a partir de esto es una máquina de pila o un intérprete con un solo registro de la parte superior de la pila. El código anterior entonces hace:

  • Cargue X en el registro TOS vacío (si es una máquina de hardware), o
  • Presione el registro TOS en la memoria, cargue X en el registro TOS (si es un intérprete)
  • Empuje el registro TOS a la memoria, cargue 1 en el registro TOS
  • Saque el operando izquierdo de la memoria, agréguelo al registro TOS y déjelo allí

para un total de 5 referencias de caché de datos, en el peor de los casos. Generalmente, los intérpretes no rastrean el vacío, porque no tienen que hacerlo; cualquier cosa debajo del puntero de la pila es un valor no vacío, y el registro de caché de TOS siempre se mantiene activo. Los intérpretes típicos de Java no almacenan en búfer la parte superior de la pila de esta manera, sin embargo, porque el programa y la pila tienen una combinación de valores de datos cortos y amplios.

Si la máquina de pila cableada tiene N registros para almacenar en caché las palabras de la pila de memoria superior, entonces todos los derrames y recargas se evitan en este ejemplo y solo hay 1 ciclo de caché de datos, lo mismo que para una máquina de registro o acumulador.

En las máquinas de registro que utilizan compiladores de optimización, es muy común que las variables locales más utilizadas permanezcan en los registros en lugar de en las celdas de memoria del marco de pila. Esto elimina la mayoría de los ciclos de caché de datos para leer y escribir esos valores. El desarrollo de la "programación de la pila" para realizar análisis de variables en vivo y, por lo tanto, retener las variables clave en la pila durante períodos prolongados, ayuda a esta preocupación.

Por otro lado, las máquinas de registro deben derramar muchos de sus registros en la memoria a través de llamadas a procedimientos anidados. La decisión de qué registros derramar y cuándo se toma estáticamente en tiempo de compilación en lugar de en la profundidad dinámica de las llamadas. Esto puede generar más tráfico de caché de datos que en una implementación de máquina de pila avanzada.

Alto costo de factorizar subexpresiones comunes [ editar ]

En las máquinas de registro, una subexpresión común (una subexpresión que se usa varias veces con el mismo valor de resultado) se puede evaluar solo una vez y su resultado se puede guardar en un registro rápido. Las reutilizaciones posteriores no tienen costo de tiempo ni de código, solo una referencia de registro. Esta optimización acelera las expresiones simples (por ejemplo, la carga de la variable X o el puntero P), así como las expresiones complejas menos comunes.

En cambio, con las máquinas apiladoras, los resultados se pueden almacenar de dos formas. En primer lugar, los resultados se pueden almacenar utilizando una variable temporal en la memoria. El almacenamiento y las recuperaciones posteriores cuestan instrucciones adicionales y ciclos de caché de datos adicionales. Hacer esto es solo una ganancia si el cálculo de la subexpresión cuesta más en tiempo que la obtención de la memoria, que en la mayoría de las CPU de pila, casi siempre es el caso. Nunca vale la pena para variables simples y búsquedas de punteros, porque ya tienen el mismo costo de un ciclo de caché de datos por acceso. Solo vale la pena marginalmente para expresiones comoX+1. Estas expresiones más simples constituyen la mayoría de las expresiones redundantes y optimizables en programas escritos en lenguajes no concatenativos. Un compilador optimizador solo puede ganar en redundancias que el programador podría haber evitado en el código fuente.

La segunda forma deja un valor calculado en la pila de datos, duplicándolo según sea necesario. Esto usa operaciones para copiar entradas de pila. La pila debe tener una profundidad suficiente para las instrucciones de copia disponibles de la CPU. El código de pila escrito a mano a menudo utiliza este enfoque y alcanza velocidades como las de las máquinas de registro de uso general. [8] [12] [13] Desafortunadamente, los lenguajes de programación no utilizan ampliamente los algoritmos para una "programación de pila" óptima.

Orden de código rígido [ editar ]

En las máquinas modernas, el tiempo para obtener una variable de la caché de datos suele ser varias veces mayor que el tiempo necesario para las operaciones básicas de ALU. Un programa se ejecuta más rápido sin atascos si sus cargas de memoria pueden iniciarse varios ciclos antes de la instrucción que necesita esa variable. Las máquinas complejas pueden hacer esto con una canalización profunda y una "ejecución fuera de orden" que examina y ejecuta muchas instrucciones a la vez. Las máquinas de registro pueden incluso hacer esto con un hardware "en orden" mucho más simple, una canalización poco profunda y compiladores un poco más inteligentes. El paso de carga se convierte en una instrucción separada, y esa instrucción se programa estáticamente mucho antes en la secuencia de código. El compilador coloca pasos independientes en el medio.

La programación de los accesos a la memoria requiere registros de reserva explícitos. No es posible en máquinas apiladas sin exponer algún aspecto de la microarquitectura al programador. Para la expresión AB, el operando derecho debe evaluarse y presionarse inmediatamente antes del paso Menos. Sin permutación de pila o subprocesos múltiples de hardware, se puede poner relativamente poco código útil en el medio mientras se espera a que finalice la Carga B. Las máquinas de pila pueden solucionar el retraso de la memoria al tener una tubería de ejecución profunda fuera de orden que cubre muchas instrucciones a la vez, o más probablemente, pueden permutar la pila de modo que puedan trabajar en otras cargas de trabajo mientras la carga se completa, o Puede entrelazar la ejecución de diferentes subprocesos del programa, como en el sistema Unisys A9. [14] Sin embargo, las cargas computacionales cada vez más paralelas de hoy sugieren que esta podría no ser la desventaja que se ha dicho que es en el pasado.

Capaz de utilizar la ejecución fuera de orden [ editar ]

El algoritmo de Tomasulo encuentra el paralelismo a nivel de instrucción al emitir instrucciones a medida que sus datos están disponibles. Conceptualmente, las direcciones de las posiciones en una pila no son diferentes de los índices de registro de un archivo de registro. Esta vista permite la ejecución desordenada del algoritmo de Tomasulo para su uso con máquinas de pila.

La ejecución desordenada en máquinas apiladas parece reducir o evitar muchas dificultades teóricas y prácticas. [15] La investigación citada muestra que tal máquina de pila puede explotar el paralelismo a nivel de instrucción, y el hardware resultante debe almacenar datos en caché para las instrucciones. Estas máquinas omiten la mayoría de los accesos a la memoria de la pila. El resultado alcanza un rendimiento (instrucciones por reloj ) comparable al de las máquinas de registro RISC , con densidades de código mucho más altas (porque las direcciones de los operandos son implícitas).

El código compacto de una máquina de pila naturalmente se ajusta a más instrucciones en la caché y, por lo tanto, podría lograr una mejor eficiencia de la caché , reduciendo los costos de memoria o permitiendo sistemas de memoria más rápidos por un costo determinado. Además, la mayoría de las instrucciones de las máquinas de pila son muy simples, hechas de un solo campo de código de operación o un campo de operando. Por lo tanto, las máquinas de pila requieren muy pocos recursos electrónicos para decodificar cada instrucción.

Un problema que surgió en la investigación fue que se necesitan aproximadamente 1,88 instrucciones de máquina de pila para hacer el trabajo de la instrucción RISC de una máquina de registro. Por lo tanto, las máquinas apiladoras fuera de servicio de la competencia requieren aproximadamente el doble de recursos electrónicos para rastrear instrucciones ("estaciones de emisión"). Esto podría compensarse con ahorros en caché de instrucciones y circuitos de decodificación de memoria y de instrucciones.

Oculta una máquina de registro más rápida dentro [ editar ]

Algunas máquinas apiladas simples tienen un diseño de chip que se personaliza completamente hasta el nivel de registros individuales. El registro de direcciones de la parte superior de la pila y los N búferes de datos de la parte superior de la pila se construyen a partir de circuitos de registro individuales separados, con sumadores separados y conexiones ad hoc.

Sin embargo, la mayoría de las máquinas de pila se construyen a partir de componentes de circuito más grandes donde los N búferes de datos se almacenan juntos dentro de un archivo de registro y comparten buses de lectura / escritura. Las instrucciones de pila decodificadas se mapean en una o más acciones secuenciales en ese archivo de registro oculto. Las operaciones de cargas y ALU actúan sobre unos pocos registros superiores, y los derrames y rellenos implícitos actúan sobre los registros inferiores. El decodificador permite que el flujo de instrucciones sea compacto. Pero si, en cambio, el flujo de código tuviera campos de selección de registro explícitos que manipularan directamente el archivo de registro subyacente, el compilador podría hacer un mejor uso de todos los registros y el programa se ejecutaría más rápido.

Las máquinas apiladoras microprogramadas son un ejemplo de esto. El motor de microcódigo interno es una especie de máquina de registro similar a RISC o una máquina similar a VLIW que utiliza múltiples archivos de registro. Cuando se controla directamente mediante un microcódigo específico de la tarea, ese motor realiza mucho más trabajo por ciclo que cuando se controla indirectamente mediante un código de pila equivalente para esa misma tarea.

Los traductores de código objeto para HP 3000 y Tandem T / 16 son otro ejemplo. [16] [17]Tradujeron secuencias de código de pila en secuencias equivalentes de código RISC. Las optimizaciones 'locales' menores eliminaron gran parte de la sobrecarga de una arquitectura de pila. Se utilizaron registros de repuesto para descartar cálculos repetidos de direcciones. El código traducido aún conservaba mucha sobrecarga de emulación debido a la falta de coincidencia entre las máquinas originales y de destino. A pesar de esa carga, la eficiencia del ciclo del código traducido coincidió con la eficiencia del ciclo del código de pila original. Y cuando el código fuente se volvió a compilar directamente en la máquina de registro mediante la optimización de los compiladores, la eficiencia se duplicó. Esto muestra que la arquitectura de la pila y sus compiladores no optimizadores desperdiciaban más de la mitad de la potencia del hardware subyacente.

Los archivos de registro son buenas herramientas para la informática porque tienen un gran ancho de banda y una latencia muy baja, en comparación con las referencias de memoria a través de cachés de datos. En una máquina simple, el archivo de registro permite leer dos registros independientes y escribir un tercero, todo en un ciclo ALU con un ciclo o menos latencia. Mientras que la caché de datos correspondiente puede iniciar solo una lectura o una escritura (no ambas) por ciclo, y la lectura generalmente tiene una latencia de dos ciclos ALU. Eso es un tercio del rendimiento al doble de la demora de la tubería. En una máquina compleja como Athlonque completa dos o más instrucciones por ciclo, el archivo de registro permite la lectura de cuatro o más registros independientes y la escritura de otros dos, todo en un ciclo ALU con latencia de un ciclo. Mientras que la caché de datos de doble puerto correspondiente puede iniciar solo dos lecturas o escrituras por ciclo, con múltiples ciclos de latencia. Nuevamente, eso es un tercio del rendimiento de los registros. Es muy caro construir una caché con puertos adicionales.

Más instrucciones, intérpretes más lentos [ editar ]

Los intérpretes para máquinas de pila virtual suelen ser más lentos que los intérpretes para otros estilos de máquina virtual. [18] Esta ralentización es peor cuando se ejecuta en máquinas host con pipelines de ejecución profunda, como los chips x86 actuales.

Un programa tiene que ejecutar más instrucciones cuando se compila en una máquina de pila que cuando se compila en una máquina de registro o una máquina de memoria a memoria. Cada carga variable o constante requiere su propia instrucción de carga separada, en lugar de agruparse dentro de la instrucción que usa ese valor. Las instrucciones separadas pueden ser simples y de ejecución más rápida, pero el recuento total de instrucciones es aún mayor.

En algunos intérpretes, el intérprete debe ejecutar un salto de conmutación de N vías para decodificar el siguiente código de operación y pasar a sus pasos para ese código de operación en particular. Otro método para seleccionar códigos de operación es el código enhebrado . Los mecanismos de captación previa de la máquina host no pueden predecir y captar el objetivo de ese salto indexado o indirecto. Por lo tanto, la canalización de ejecución de la máquina host debe reiniciarse cada vez que el intérprete alojado decodifica otra instrucción virtual. Esto sucede con más frecuencia para las máquinas de pila virtual que para otros estilos de máquina virtual. [19]

La máquina virtual Dalvik de Android para Java utiliza un conjunto de instrucciones de registro virtual de 16 bits en lugar del código de pila habitual de 8 bits de Java, para minimizar el recuento de instrucciones y las paradas de despacho del código de operación. Las instrucciones aritméticas obtienen o almacenan directamente variables locales a través de campos de instrucción de 4 bits (o más grandes). La versión 5.0 de Lua reemplazó su máquina de pila virtual con una máquina de registro virtual más rápida. [20] [21]

Desde que la máquina virtual Java se hizo popular, los microprocesadores han empleado predictores de rama avanzados para saltos indirectos. [22] Este avance evita la mayoría de los reinicios de canalizaciones desde saltos de N vías y elimina gran parte de los costos de recuento de instrucciones que afectan a los intérpretes de pila.

Máquinas híbridas [ editar ]

(Estos no deben confundirse con las computadoras híbridas que combinan características digitales y analógicas, por ejemplo, una computadora digital que accede a la multiplicación analógica o la resolución de ecuaciones diferenciales mediante el mapeo de memoria y la conversión hacia y desde las entradas y salidas de un dispositivo analógico).

Las máquinas de pila pura son bastante ineficientes para los procedimientos que acceden a múltiples campos desde el mismo objeto. El código de la máquina de la pila debe recargar el puntero de objeto para cada cálculo de puntero + desplazamiento. Una solución común para esto es agregar algunas características de máquina de registro a la máquina de pila: un archivo de registro visible dedicado a mantener direcciones e instrucciones de estilo de registro para realizar cargas y cálculos simples de direcciones. Es poco común que los registros sean de propósito completamente general, porque entonces no hay una razón sólida para tener una pila de expresiones e instrucciones postfijas.

Otro híbrido común es comenzar con una arquitectura de máquina de registro y agregar otro modo de dirección de memoria que emule las operaciones push o pop de las máquinas de pila: 'memaddress = reg; reg + = instr.displ '. Esto fue utilizado por primera vez en diciembre 's PDP-11 minicomputadoras. Esta característica se implementó en las computadoras VAX y en los microprocesadores Motorola 6800 y M68000 . Esto permitió el uso de métodos de pila más simples en los primeros compiladores. También admitió de manera eficiente máquinas virtuales mediante intérpretes de pila o código enhebrado. Sin embargo, esta característica no ayudó a que el propio código de la máquina de registro se volviera tan compacto como el código de máquina de pila pura. Además, la velocidad de ejecución fue menor que cuando se compila bien en la arquitectura de registro. Es más rápido cambiar el puntero de la parte superior de la pila solo ocasionalmente (una vez por llamada o retorno) en lugar de subir y bajar constantemente a lo largo de cada declaración de programa, y ​​es incluso más rápido evitar las referencias a la memoria por completo.

Más recientemente, las llamadas máquinas de pila de segunda generación han adoptado una colección dedicada de registros para servir como registros de direcciones, descargando la tarea de direccionamiento de memoria de la pila de datos. Por ejemplo, MuP21 se basa en un registro llamado "A", mientras que los procesadores GreenArrays más recientes se basan en dos registros: A y B. [23]

La familia de microprocesadores Intel x86 tiene un conjunto de instrucciones de registro (acumulador) para la mayoría de las operaciones, pero usa instrucciones de pila para su aritmética de punto flotante x87 , Intel 8087 , que se remonta al coprocesador iAPX87 (8087) para el 8086 y el 8088. Eso es decir, no hay registros de punto flotante accesibles al programador, sino solo una pila profunda de 8 bits de ancho y 80 bits. El x87 depende en gran medida de la CPU x86 para obtener asistencia en la realización de sus operaciones.

Máquinas apiladoras comerciales [ editar ]

Ver también: Arquitectura informática de lenguaje de alto nivel

Ejemplos de conjuntos de instrucciones de pila ejecutados directamente en hardware incluyen

  • La arquitectura F18A del chip GA144 de 144 procesadores de GreenArrays, Inc. [4] [23] [24]
  • la arquitectura de grandes sistemas de Burroughs (desde 1961)
  • la Xerox diente de león introdujo 27 abril de 1981, se utiliza una arquitectura de máquina de pila para ahorrar memoria. [25] [26]
  • la máquina English Electric KDF9 . Entregado por primera vez en 1964, el KDF9 tenía una pila de 19 registros aritméticos de profundidad y una pila de 17 para las direcciones de retorno de subrutinas.
  • el miniordenador Collins Radio Collins Adaptive Processing System (CAPS, desde 1969) y el Microprocesador de Arquitectura Avanzada Rockwell Collins (AAMP, desde 1981). [27]
  • el UCSD Pascal p-machine (como el Pascal MicroEngine y muchos otros)
  • Serie MU5 e ICL 2900 . Máquinas híbridas de pila y acumulación. El registro del acumulador almacenó en búfer el valor de datos superior de la pila de memoria. Variantes de códigos de operación de carga y almacenamiento controlados cuando ese registro se derramaba en la pila de memoria o se recargaba desde allí.
  • HP 3000 (Clásico, no PA-RISC)
  • Computadoras en tándem T / 16. Como HP 3000, excepto que los compiladores, no el microcódigo, controlaban cuando la pila de registros se derramaba en la pila de memoria o se rellenaba desde la pila de memoria.
  • la Atmel Marc4 microcontrolador [28]
  • Varios "Forth chips" [29] como el RTX2000, el RTX2010 , el F21 [30] y el PSC1000 [31] [32]
  • La computadora Setun Ternary realizó ternario balanceado usando una pila.
  • El procesador 4stack de Bernd Paysan tiene cuatro pilas. [33]
  • La máquina apiladora Ignite de Patriot Scientific diseñada por Charles H. Moore tiene un punto de referencia de densidad funcional líder .
  • Microprocesador endurecido por radiación Saab Ericsson Space Thor [34]
  • Inmos transputers .
  • ZPU Una CPU físicamente pequeña diseñada para supervisar sistemas FPGA . [35]

Máquinas de pila virtual [ editar ]

Ejemplos de máquinas de pila virtual interpretadas en software:

  • el código interpretativo Whetstone ALGOL 60 , [36] en el que se basaron algunas características del Burroughs B6500
  • la máquina p UCSD Pascal ; que se parecía mucho a Burroughs
  • la máquina de código p Niklaus Wirth
  • Charla
  • el conjunto de instrucciones de la máquina virtual Java
  • el código de bytes de WebAssembly
  • el sistema de ejecución virtual (VES) para el conjunto de instrucciones Common Intermediate Language (CIL) de .NET Framework (ECMA 335)
  • el Forth lenguaje de programación, especialmente la máquina virtual integral
  • PostScript de Adobe
  • Lenguaje de programación para periquitos
  • Lenguaje de programación SwapDrop de Sun Microsystems para la identificación de tarjetas inteligentes Sun Ray
  • Máquina virtual ActionScript 2 de Adobe (AVM2)
  • EVM de Ethereum
  • el intérprete de código de bytes CPython
  • el intérprete de código de bytes Ruby YARV
  • la máquina virtual Rubinius
  • el bs (lenguaje de programación) en Unix usa una máquina de pila virtual para procesar comandos, después de la primera transposición de la forma del lenguaje de entrada proporcionada, a la notación de pulido inverso
  • la API C de Lua (lenguaje de programación)

Computadoras que usan pilas de llamadas y marcos de pila [ editar ]

La mayoría de las computadoras actuales (de cualquier estilo de conjunto de instrucciones) y la mayoría de los compiladores utilizan una gran pila de devolución de llamadas en la memoria para organizar las variables locales de corta duración y los enlaces de retorno para todos los procedimientos o funciones actualmente activos. Cada llamada anidada crea un nuevo marco de pila en la memoria, que persiste hasta que se completa esa llamada. Esta pila de devolución de llamadas puede ser administrada completamente por el hardware a través de registros de direcciones especializados y modos de direcciones especiales en las instrucciones. O puede ser simplemente un conjunto de convenciones seguidas por los compiladores, utilizando registros genéricos y modos de dirección de registro + desplazamiento. O puede ser algo intermedio.

Dado que esta técnica es ahora casi universal, incluso en máquinas de registro, no es útil referirse a todas estas máquinas como máquinas apiladoras. Ese término se reserva comúnmente para las máquinas que también usan una pila de expresiones e instrucciones aritméticas solo de pila para evaluar las partes de una sola declaración.

Las computadoras comúnmente brindan acceso directo y eficiente a las variables globales del programa y a las variables locales solo del procedimiento o función más interno actual, el marco de pila más alto. El direccionamiento 'de nivel superior' del contenido de los marcos de pila de los llamantes no suele ser necesario y no es compatible directamente con el hardware. Si es necesario, los compiladores admiten esto pasando punteros de marco como parámetros ocultos adicionales.

Algunas máquinas de pila de Burroughs admiten referencias de nivel superior directamente en el hardware, con modos de dirección especializados y un archivo de registro de 'visualización' especial que contiene las direcciones de marco de todos los ámbitos externos. Ninguna línea de computadora posterior ha hecho esto en hardware. Cuando Niklaus Wirth desarrolló el primer compilador Pascal para el CDC 6000 , descubrió que, en general, era más rápido pasar los punteros de cuadro como una cadena, en lugar de actualizar constantemente matrices completas de punteros de cuadro. Este método de software tampoco agrega gastos generales para lenguajes comunes como C, que carecen de referencias de nivel superior.

Las mismas máquinas de Burroughs también admitían el anidamiento de tareas o subprocesos. La tarea y su creador comparten los marcos de pila que existían en el momento de la creación de la tarea, pero no los marcos posteriores del creador ni los marcos propios de la tarea. Esto fue apoyado por una pila de cactus , cuyo diagrama de distribución se parecía al tronco y los brazos de un cactus Saguaro . Cada tarea tiene su propio segmento de memoria que contiene su pila y los marcos que posee. La base de esta pila está vinculada a la mitad de la pila de su creador. En máquinas con un espacio de direcciones plano convencional, la pila del creador y las pilas de tareas serían objetos de montón separados en un montón.

En algunos lenguajes de programación, los entornos de datos de alcance externo no siempre están anidados en el tiempo. Estos lenguajes organizan sus 'registros de activación' de procedimientos como objetos de montón separados en lugar de como marcos de pila adjuntos a una pila lineal.

En lenguajes simples como Forth que carecen de variables locales y nombres de parámetros, los marcos de pila no contendrían más que direcciones de rama de retorno y gastos generales de administración de marcos. Entonces, su pila de devoluciones contiene direcciones de retorno desnudas en lugar de marcos. La pila de devoluciones es independiente de la pila de valores de datos, para mejorar el flujo de configuración y devoluciones de llamadas.

Ver también [ editar ]

  • Lenguaje de programación orientado a pilas
  • Lenguaje de programación concatenativo
  • Comparación de máquinas virtuales de aplicaciones

Referencias [ editar ]

  1. ^ Barton, Robert S. (1961). "Un nuevo enfoque para el diseño funcional de una computadora digital" . IRE-AIEE-ACM '61 (occidental): artículos presentados en la conferencia de computación conjunta occidental IRE-AIEE-ACM del 9 al 11 de mayo de 1961 .
  2. ^ Barton, Robert S. (1987). "Un nuevo enfoque para el diseño funcional de una computadora digital" . IEEE Annals of the History of Computing .
  3. ^ Beard, Bob (otoño de 1997). "La computadora KDF9 - 30 años después" . RESURRECCIÓN informática .
  4. ^ a b "GreenArrays, Inc. - Documentos" . Greenarraychips.com . Consultado el 8 de octubre de 2017 .
  5. ^ Koopman, Philip (1994). "Una exploración preliminar de la generación de código de pila optimizada" (PDF) . Revista de aplicaciones e investigación Forth . 6 (3).
  6. ^ Bailey, Chris (2000). "Programación entre límites de operandos de pila: un estudio preliminar" (PDF) . Actas de la Conferencia Euroforth 2000 .
  7. ^ Shannon, Mark; Bailey C (2006). "Asignación de pila global: asignación de registros para máquinas de pila" (PDF) . Actas de la Conferencia Euroforth de 2006 .
  8. ^ a b "Stack Computers: la nueva ola - un libro en línea" . Ece.cmu.edu . Consultado el 8 de octubre de 2017 .
  9. ^ "Diseño e implementación de una máquina apiladora eficiente" (PDF) . Jopdesign.com . Consultado el 8 de octubre de 2017 .
  10. ^ Manual de la CPU 8051, Intel, 1980
  11. ^ "Arquitectura de la computadora: un enfoque cuantitativo", John L Hennessy, David A Patterson; Vea la discusión sobre máquinas apiladoras.
  12. ^ "Arquitectura de computadora de pila de segunda generación" (PDF) . Fpgacpu.ca . Consultado el 8 de octubre de 2017 .
  13. ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 18 de julio de 2011 . Consultado el 1 de noviembre de 2010 . Mantenimiento de CS1: copia archivada como título ( enlace )
  14. ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 21 de marzo de 2011 . Consultado el 29 de marzo de 2011 . Mantenimiento de CS1: copia archivada como título ( enlace )
  15. ^ Chatterji, Satrajit; Ravindran, Kaushik. "BOOST: Berkeley's Out of Order Stack Thingie" . Puerta de investigación . Kaushik Ravindran . Consultado el 16 de febrero de 2016 .
  16. ^ Bergh, Arndt; Keilman, Keith; Magenheimer, Daniel; Miller, James (diciembre de 1987). "Emulación HP3000 en equipos con arquitectura HP Precision" (PDF) . Revista de Hewlett-Packard : 87–89 . Consultado el 8 de octubre de 2017 .
  17. ^ Migración de una familia de computadoras CISC a RISC a través de la traducción de código de objeto, K. Andrews y D. Sand, Actas de ASPLOS-V, octubre de 1992
  18. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertle, M. Anton. " " Enfrentamiento de máquinas virtuales: apilar frente a registrar la máquina " " (PDF) . Usenix.org . Consultado el 8 de octubre de 2017 .
  19. ^ Davis, Brian; Beatty, Andrew; Casey, Kevin; Gregg, David; Waldron, John. " ' El caso de las máquinas de registro virtual ' " (PDF) . Scss.tcd.ie . Consultado el 8 de octubre de 2017 .
  20. ^ "La implementación de Lua 5.0" (PDF) . Lua.org . Consultado el 8 de octubre de 2017 .
  21. ^ "La máquina virtual de Lua 5.0" (PDF) . Inf.puc-rio.br . Consultado el 8 de octubre de 2017 .
  22. ^ "Predicción de rama y el desempeño de intérpretes - No confíe en el folclore" . Hal.inria.fr . Consultado el 8 de octubre de 2017 .
  23. ^ a b " " Conjunto de instrucciones de los núcleos F18A (llamado colorForth por razones históricas). " " . Colorforth.com . Archivado desde el original el 10 de marzo de 2016 . Consultado el 8 de octubre de 2017 .
  24. ^ " " GreenArrays, Inc. " " . Greenarraychips.com . Consultado el 8 de octubre de 2017 .
  25. ^ "Principios de funcionamiento del procesador Mesa" . Museo de la Computación DigiBarn . Xerox . Consultado el 23 de diciembre de 2019 .
  26. ^ "DigiBarn: El Xerox Star 8010" Diente de león " " . Museo de la Computación DigiBarn . Consultado el 23 de diciembre de 2019 .
  27. ^ "El primer procesador Java del mundo" , por David A. Greve y Matthew M. Wilding, Electronic Engineering Times , 12 de enero de 1998
  28. ^ [1]
  29. ^ "Forth chips" . Colorforth.com . Archivado desde el original el 15 de febrero de 2006 . Consultado el 8 de octubre de 2017 .
  30. ^ "Descripción general del microprocesador F21" . Ultratechnology.com . Consultado el 8 de octubre de 2017 .
  31. ^ "Wiki de ForthFreak" . GitHub.com . 25 de agosto de 2017 . Consultado el 8 de octubre de 2017 .
  32. ^ "Un chip Java disponible - ¡ahora! - Developer.com" . Developer.com . Consultado el 8 de octubre de 2017 .
  33. ^ "Procesador de 4 pilas" . bernd-paysan.de . Consultado el 8 de octubre de 2017 .
  34. ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 20 de agosto de 2011 . Consultado el 30 de marzo de 2011 . Mantenimiento de CS1: copia archivada como título ( enlace )
  35. ^ "ZPU - CPU de 32 bits más pequeña del mundo con una cadena de herramientas GCC: descripción general" . opencores.org . Consultado el 7 de febrero de 2015 .
  36. ^ Randell, Brian y Russell, Lawford John " Implementación de Algol 60 " Londres: Academic Press, 1964. ISBN 0-12-578150-4 . 

Enlaces externos [ editar ]

  • Stack Computers: el libro de la nueva ola de Philip J. Koopman, Jr. 1989
  • Homebrew CPU en una FPGA - máquina de pila homebrew usando FPGA
  • Mark 1 FORTH Computer : máquina apiladora casera que utiliza circuitos lógicos discretos
  • Mark 2 FORTH Computer - máquina apiladora de cerveza casera usando bitslice / PLD
  • Arquitectura informática de pila de segunda generación : tesis sobre la historia y el diseño de las máquinas de pila.