Máquina de pila


Máquina de pila

Una máquina de pila es un modelo computacional en el cual la memoria de la computadora toma la forma de una o más pilas. El término también se refiere a un computador real implementando o simulando una máquina de pila idealizada.

Adicionalmente, una máquina de pila también puede referirse a una máquina verdadera o simulada con un conjunto de instrucción de "0 operandos". En tal máquina, la mayoría de las instrucciones implícitamente operan en valores en el tope de la pila y reemplazan esos valores por el resultado. Típicamente tales máquinas también tienen una instrucción "load" y una instrucción "store" que leen y escriben a posiciones arbitrarias de la RAM. (Como el resto de las instrucciones, las instrucciones "load" y "store" no necesitan ningún operando en una máquina de pila típica - ellas siempre toman la dirección de la RAM que se quiere leer o escribir desde el tope de la pila).

La ventaja de las máquinas de pila ("conjunto de instrucciones de 0 operandos") sobre las máquinas de acumulador ("conjunto de instrucciones de 1 operando") y las máquinas de registro ("conjunto de instrucciones de 2 operandos" o un "conjunto de instrucciones de 3 operandos") es que los programas escritos para un conjunto de instrucciones de "0 operandos" generalmente tienen una densidad de código más alta que los programas equivalentes escritos para otros conjuntos de instrucciones.

Contenido

Las pilas en teoría de autómatas

En teoría de autómatas, una máquina de pila tiene un número de pilas. La entrada es el contenido inicial de la pila 1; todos los otras pilas comienzan vacíos. Cada estado de una máquina de pila es, o un estado de lectura o un estado de la escritura; y cada estado especifica un número de pila desde el cual leer (pop), o hacia el cual escribir (push). Adicionalmente, un estado de escritura especifica el símbolo a escribir, y el siguiente estado a transicionar. Un estado de lectura especifica, para cada símbolo en el alfabeto, a qué estado trancisionaría si ese símbolo fuera leído; adicionalmente, también especifica a qué estado transicionar si la pila está vacía. Una máquina de pila se detiene cuando sus transiciones entran en un estado de parado especial.

Una máquina de pila con 1 pila es un modelo computacional muy débil. Por ejemplo, puede ser demostrado que ninguna máquina de 1 pila puede reconocer el simple lenguaje 0n1n (un número de ceros seguido por el mismo número de unos), vía argumentos de bombeo. La potencia computacional de las máquinas de 1 pila es estrictamente mayor que la de un autómata finito, pero estrictamente menor que el del autómata de pila determinista.

Por otro lado, una máquina de pila con múltiples pilas es equivalente a una máquina de Turing. Por ejemplo, una máquina de 2 pila puede emular a una máquina de Turing usando una pila para la porción de la cinta a la izquierda de la posición actual del cabezal de la máquina de Turing y el otra pila para la porción a la derecha.

Máquinas de pila prácticas

Las máquinas con un conjunto de instrucciones basado en pila pueden tener uno o más pilas. Algunas máquinas de pila son máquinas 2 pilas, con los dos pilas usualmente siendo un pila de datos y un pila de retorno, el primero para las operaciones en datos y el último para las direcciones de retorno. Otras máquinas usan la misma pila para ambos.

Una máquina usando los registros del procesador para los operandos puede simular fácilmente una máquina de pila. Tal simulación es llamada a veces una máquina de pila virtual. La ventaja de un (más o menos) conjunto de instrucciones basado en pila (por hardware) sobre una arquitectura basada en registros, son instrucciones más cortas, puesto que tienen que ser especificadas menos direcciones de operando. Éste es lo mismo que una mejor densidad del código y programas compilados más pequeños.

Las implementaciones comerciales de las máquinas de pila generalmente incluyen un pequeño conjunto de registros de propósito especial para tratar el encerramiento de contextos, es decir los marcos (frames) de pila que no son el marco de la pila superior (el ámbito dinámico contra el léxico son dos maneras diferentes de usar y accesar el encerramiento de contextos). Las máquinas de pila prácticas no son así idénticas a las máquinas de pila de la teoría de autómatas pero permiten que una CPU basada en pila sea enteramente conveniente para la computación de propósitos generales.

Ejemplos del uso comercial de una máquina de pila incluyen:

  • arquitecturas de conjunto de instrucciones ejecutadas directamente en hardware
    • La arquitectura de los grandes sistemas de Burroughs (desde 1961)
    • El microcomputador Collins Adaptive Processing System de Collins Radio (CAPS, desde 1969) y el Advanced Architecture Microprocessor de Rockwell Collins (AAMP, desde 1981).[1]
    • La p-machine del UCSD Pascal (como el Pascal MicroEngine y muchos otros)
    • El T/16 de Tandem Computers
    • El HP 3000 de Hewlett Packard (el clásico, no el PA-RISC)
    • El microcontrolador MARC4 de Atmel[2]
    • Varios "chips Forth",[3] por ejemplo el RTX2000, el RTX2010, el Sh-Boom, el F21[4] y el PSC1000[5]
    • El procesador 4stack de Bernd Paysan tiene cuatro pilas.[6]
    • La máquina de pila "Ignite" diseñada por Charles H. Moore mantiene el liderazgo en desempeño en densidad funcional.
    • El microprocesador Thor de Saab Ericsson Space[7]
  • Máquinas virtuales interpretadas en software

Observe que la arquitectura de Burroughs combina una máquina de pila con la memoria etiquetada (tagged memory) (algunos bits en cada palabra de la memoria se usan para describir el tipo de datos de los operandos). La memoria etiquetada requiere pocos opcodes, ej., una sola instrucción "add" trabaja para cualquier combinación de operandos con números enteros y de punto flotante. Requerir pocos opcodes significa que el conjunto de instrucciones completo pueda caber en opcodes más pequeños, reduciendo la anchura total de la instrucción.

Desempeño

Las máquinas de pila compiten contra las máquinas de registro convencionales por la cuota de mercado. Ambas arquitecturas tienen fuerzas. La discusión siguiente es para dar una idea de las ventajas relativas de las dos arquitecturas.

Las referencias convencionales dicen[8] que las máquinas de pila son lentas porque las pilas están en memoria, y por lo tanto son más lentos de accesar que los registros. Sin embargo, esto es algo compensado por el más pequeño tamaño del código de una máquina de pila, que es más rápida al leer (fetch) y ejecutar. Esto es confirmado por experimentos con optimización agresiva tanto de la arquitectura de la máquina como la de los compiladores[9] que demuestran que el código de la máquina de registro tiene 47% menos instrucciones virtuales, y sin embargo, es 25% más grande que el código de la máquina de pila. Cuando las pilas están en memoria, una máquina de registro corre cerca de 26.5% más rápida que una máquina de pila, en gran parte debido a la reutilización de las constantes en los registros.

También se dice[10] que los registros proporcionan más oportunidades para la ejecución paralela durante la ejecución superescalar. Esto puede ser porque las máquinas de pila superscalares y los necesarios compiladores de optimización asociados no son un campo de investigación muy activo o de desarrollo comercial. En principio, la velocidad de una computadora superscalar es constreñida por la lenta velocidad de acceso de de memoria principal, no por la notación usada para tratar resultados intermedios.

Algunas máquinas de pila[11] [12] tienen un caché que contiene partes de la pila en registros de alta velocidad para acelerar el acceso a las pilas y seguir conservando el rápido y pequeño tamaño del código. Sin embargo, esto no es cierto para todas las máquinas de pila.

La latencia de tiempor real, es decir, el tiempo que transcurre desde un evento electrónico hasta el inicio del código de interrupción útil, puede ser menor en máquinas de pila porque los registros en una máquina de registro tienen que ser guardados y luego restaurados, de modo que el código de la interrupción no corrompa los cálculos en el background. Algunas máquinas de registro, como el Intel 8051[13] tienen múltiples conjuntos de registros. El código de la interrupción puede simplemente cambiar el índice del conjunto de registros para poder trabajar sin tocar los registros usados normalmente por los programas. Desafortunadamente, esta característica no existe en todas las máquinas de registro.

El más pequeño tamaño del código de una máquina de pila puede reducir el tamaño de la memoria y el costo de una computadora. Pocos accesos de memoria pueden incrementar la velocidad de una máquina de registro, comparada a una máquina de pila (que tenga las pilas en memoria). Reduciendo el tiempo de guardado y restauración de registros, una máquina de pila puede tener menos sobrecarga para responder a las interrupciones.

Referencias

  1. The World's First Java Processor, by David A. Greve and Matthew M. Wilding, Electronic Engineering Times, Jan. 12, 1998,
  2. MARC4 4-Bit Architecture
  3. Forth chips
  4. F21 Microprocessor Overview
  5. A Java chip available — now!, by Rick Brian Slack
  6. 4stack Processor
  7. Plantilla:Cite manual
  8. "Computer Architecture, a Quantitative Approach", John L. Henessy, David Goldberg; See the discussion of stack machines.
  9. Virtual Machine Showdown: Stack vs. Register Machine, Yunhe Shi, David Gregg, Andrew Beatty, M. Anton Ertle
  10. Hennessy, ibid.
  11. Sh'Boom CPU description, Charles Moore
  12. Grandes sistemas de Burroughs
  13. 8051 CPU Manual, Intel, 1980

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Máquina virtual Parrot — ? Información general Última versión estable 3.6.0 Pájaros del Caribe 19 de julio de 2011 Género Máquina virtual …   Wikipedia Español

  • Máquina virtual Java — Una Máquina virtual Java (en inglés Java Virtual Machine, JVM) es un máquina virtual de proceso nativo, es decir, ejecutable en una plataforma específica, capaz de interpretar y ejecutar instrucciones expresadas en un código binario especial (el… …   Wikipedia Español

  • Pila de llamadas — Estructura de la pila de llamadas. En la figura se ve una pila, creciendo de abajo hacia arriba. La subrutina DrawSquare es llamada y se crea un stack frame para ella (en azul). Luego, DrawSquare llama a la subrutina DrawLine, la cual tiene su… …   Wikipedia Español

  • Pila de combustible — Saltar a navegación, búsqueda Pila de hidrógeno. La celda en sí es la estructura cúbica del centro de la imagen. Una pila de combustible, también llamada célula o celda de combustible es un dispositivo electroquímico de conversión de energía… …   Wikipedia Español

  • Pila (informática) — Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta… …   Wikipedia Español

  • Máquina de Turing — Para otros usos de este término, véase Turing (desambiguación). Una máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este …   Wikipedia Español

  • Registro de pila — Saltar a navegación, búsqueda Un registro de pila es un registro de un CPU de computadora cuyo propósito es mantener la pista de la posición actual de la pila de llamadas. En una máquina de arquitectura basada en acumulador, éste puede ser un… …   Wikipedia Español

  • Lenguaje de programación orientado a pila — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Autómata con pila — Saltar a navegación, búsqueda Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al …   Wikipedia Español

  • Grandes sistemas de Burroughs — Los grandes sistemas de Burroughs fueron los más grandes de tres series de computadores mainframes de Burroughs Corporation. Fundada en los años 1880, Burroughs era la más vieja entidad continuamente operando en el área de la computación, pero… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.