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.

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 0ⁿ1ⁿ (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
  • La p-machine del UCSD Pascal (que se parece mucho a Burroughs)
  • El conjunto de instrucciones de la máquina virtual Java
  • El Virtual Execution System (VES) para el Common Intermediate Language (CIL) del ECMA 335 (Microsoft .NET environment)
  • El lenguaje de programación Forth, en particular la máquina virtual Forth
  • El PostScript de Adobe.
  • Lenguaje de programación Parakeet.
  • Lenguaje de programación SwapDrop de Sun Microsystems para la identificación de la tarjeta inteligente del Sun Ray.

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

• Lenguaje de programación orientado a pila
• Grandes sistemas de Burroughs
• Forth (lenguaje de programación)
• Máquina de acumulador
• Máquina de registro
• Pila
• Pila de llamadas

Enlaces externos

• Stack Computers: the new wave book by Philip J. Koopman, Jr. 1989
• Homebrew CPU in an FPGA — homebrew stack machine using FPGA
• Mark 1 FORTH Computer — homebrew stack machine using discrete logical circuits
• Mark 2 FORTH Computer — homebrew stack machine using bitslice/PLD
• The Case for Virtual Register Machines, Brian Davis, Andrew Beatty, Kevin Casey, David Gregg and John Waldron