fbpx
Wikipedia

Máquina de pila

Agosto 24, 2021

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 instrucciones 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 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 acceder 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:

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 acceder 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 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 tiempo 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.

Véase también

Referencias

  1. The World's First Java Processor, by David A. Greve and Matthew M. Wilding, Electronic Engineering Times, Jan. 12, 1998,
  3. Forth chips el 15 de febrero de 2006 en Wayback Machine.
  4. F21 Microprocessor Overview
  5. A Java chip available — now!, by Rick Brian Slack
  6. 4stack Processor
  7. Harry Gunnarsson and Thomas Lundqvist (1995). Porting the GNU C Compiler to the Thor Microprocessor. Consultado el 4 de diciembre de 2008. 
  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.
  12. Grandes sistemas de Burroughs
  13. 8051 CPU Manual, Intel, 1980

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
  •   Datos: Q2740397

Agosto 24, 2021
máquina, pila, máquina, pila, modelo, computacional, cual, memoria, computadora, toma, forma, más, pilas, término, también, refiere, computador, real, implementando, simulando, máquina, pila, idealizada, adicionalmente, máquina, pila, también, puede, referirse. Una maquina de pila es un modelo computacional en el cual la memoria de la computadora toma la forma de una o mas pilas El termino tambien se refiere a un computador real implementando o simulando una maquina de pila idealizada Adicionalmente una maquina de pila tambien puede referirse a una maquina verdadera o simulada con un conjunto de instrucciones de 0 operandos En tal maquina la mayoria de las instrucciones implicitamente operan en valores en el tope de la pila y reemplazan esos valores por el resultado Tipicamente tales maquinas tambien tienen una instruccion load y una instruccion store que leen y escriben a posiciones arbitrarias de la RAM Como el resto de las instrucciones las instrucciones load y store no necesitan ningun operando en una maquina de pila tipica ellas siempre toman la direccion de la RAM que se quiere leer o escribir desde el tope de la pila La ventaja de las maquinas de pila conjunto de instrucciones de 0 operandos sobre las maquinas de acumulador conjunto de instrucciones de 1 operando y las maquinas 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 codigo mas alta que los programas equivalentes escritos para otros conjuntos de instrucciones Indice 1 Las pilas en teoria de automatas 2 Maquinas de pila practicas 3 Desempeno 4 Vease tambien 5 Referencias 6 Enlaces externosLas pilas en teoria de automatas EditarEn teoria de automatas una maquina de pila tiene un numero de pilas La entrada es el contenido inicial de la pila 1 todos los otras pilas comienzan vacios Cada estado de una maquina de pila es o un estado de lectura o un estado de la escritura y cada estado especifica un numero de pila desde el cual leer pop o hacia el cual escribir push Adicionalmente un estado de escritura especifica el simbolo a escribir y el siguiente estado a transicionar Un estado de lectura especifica para cada simbolo en el alfabeto a que estado trancisionaria si ese simbolo fuera leido adicionalmente tambien especifica a que estado transicionar si la pila esta vacia Una maquina de pila se detiene cuando sus transiciones entran en un estado de parado especial Una maquina de pila con 1 pila es un modelo computacional muy debil Por ejemplo puede ser demostrado que ninguna maquina de 1 pila puede reconocer el simple lenguaje 0n1n un numero de ceros seguido por el mismo numero de unos via argumentos de bombeo La potencia computacional de las maquinas de 1 pila es estrictamente mayor que la de un automata finito pero estrictamente menor que el del automata de pila determinista Por otro lado una maquina de pila con multiples pilas es equivalente a una maquina de Turing Por ejemplo una maquina de 2 pila puede emular a una maquina de Turing usando una pila para la porcion de la cinta a la izquierda de la posicion actual del cabezal de la maquina de Turing y el otra pila para la porcion a la derecha Maquinas de pila practicas EditarLas maquinas con un conjunto de instrucciones basado en pila pueden tener uno o mas pilas Algunas maquinas de pila son maquinas 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 ultimo para las direcciones de retorno Otras maquinas usan la misma pila para ambos Una maquina usando los registros del procesador para los operandos puede simular facilmente una maquina de pila Tal simulacion es llamada a veces una maquina de pila virtual La ventaja de un mas o menos conjunto de instrucciones basado en pila por hardware sobre una arquitectura basada en registros son instrucciones mas cortas puesto que tienen que ser especificadas menos direcciones de operando Este es lo mismo que una mejor densidad del codigo y programas compilados mas pequenos Las implementaciones comerciales de las maquinas de pila generalmente incluyen un pequeno conjunto de registros de proposito especial para tratar el encerramiento de contextos es decir los marcos frames de pila que no son el marco de la pila superior el ambito dinamico contra el lexico son dos maneras diferentes de usar y acceder el encerramiento de contextos Las maquinas de pila practicas no son asi identicas a las maquinas de pila de la teoria de automatas pero permiten que una CPU basada en pila sea enteramente conveniente para la computacion de propositos generales Ejemplos del uso comercial de una maquina 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 clasico 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 maquina de pila Ignite disenada por Charles H Moore mantiene el liderazgo en desempeno en densidad funcional El microprocesador Thor de Saab Ericsson Space 7 Maquinas virtuales interpretadas en software La p machine del UCSD Pascal que se parece mucho a Burroughs El conjunto de instrucciones de la maquina virtual Java El Virtual Execution System VES para el Common Intermediate Language CIL del ECMA 335 Microsoft NET environment El lenguaje de programacion Forth en particular la maquina virtual Forth El PostScript de Adobe Lenguaje de programacion Parakeet Lenguaje de programacion SwapDrop de Sun Microsystems para la identificacion de la tarjeta inteligente del Sun Ray Observe que la arquitectura de Burroughs combina una maquina 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 instruccion add trabaja para cualquier combinacion de operandos con numeros enteros y de punto flotante Requerir pocos opcodes significa que el conjunto de instrucciones completo pueda caber en opcodes mas pequenos reduciendo la anchura total de la instruccion Desempeno EditarLas maquinas de pila compiten contra las maquinas de registro convencionales por la cuota de mercado Ambas arquitecturas tienen fuerzas La discusion siguiente es para dar una idea de las ventajas relativas de las dos arquitecturas Las referencias convencionales dicen 8 que las maquinas de pila son lentas porque las pilas estan en memoria y por lo tanto son mas lentos de acceder que los registros Sin embargo esto es algo compensado por el mas pequeno tamano del codigo de una maquina de pila que es mas rapida al leer fetch y ejecutar Esto es confirmado por experimentos con optimizacion agresiva tanto de la arquitectura de la maquina como la de los compiladores 9 que demuestran que el codigo de la maquina de registro tiene 47 menos instrucciones virtuales y sin embargo es 25 mas grande que el codigo de la maquina de pila Cuando las pilas estan en memoria una maquina de registro corre cerca de 26 5 mas rapida que una maquina de pila en gran parte debido a la reutilizacion de las constantes en los registros Tambien se dice 10 que los registros proporcionan mas oportunidades para la ejecucion paralela durante la ejecucion superescalar Esto puede ser porque las maquinas de pila superscalares y los necesarios compiladores de optimizacion asociados no son un campo de investigacion muy activo o de desarrollo comercial En principio la velocidad de una computadora superscalar es constrenida por la lenta velocidad de acceso de memoria principal no por la notacion usada para tratar resultados intermedios Algunas maquinas de pila 11 12 tienen un cache que contiene partes de la pila en registros de alta velocidad para acelerar el acceso a las pilas y seguir conservando el rapido y pequeno tamano del codigo Sin embargo esto no es cierto para todas las maquinas de pila La latencia de tiempo real es decir el tiempo que transcurre desde un evento electronico hasta el inicio del codigo de interrupcion util puede ser menor en maquinas de pila porque los registros en una maquina de registro tienen que ser guardados y luego restaurados de modo que el codigo de la interrupcion no corrompa los calculos en el background Algunas maquinas de registro como el Intel 8051 13 tienen multiples conjuntos de registros El codigo de la interrupcion puede simplemente cambiar el indice del conjunto de registros para poder trabajar sin tocar los registros usados normalmente por los programas Desafortunadamente esta caracteristica no existe en todas las maquinas de registro El mas pequeno tamano del codigo de una maquina de pila puede reducir el tamano de la memoria y el costo de una computadora Pocos accesos de memoria pueden incrementar la velocidad de una maquina de registro comparada a una maquina de pila que tenga las pilas en memoria Reduciendo el tiempo de guardado y restauracion de registros una maquina de pila puede tener menos sobrecarga para responder a las interrupciones Vease tambien EditarLenguaje de programacion orientado a pila Grandes sistemas de Burroughs Forth lenguaje de programacion Maquina de acumulador Maquina de registro Pila Pila de llamadasReferencias Editar The World s First Java Processor by David A Greve and Matthew M Wilding Electronic Engineering Times Jan 12 1998 MARC4 4 Bit Architecture Forth chips Archivado el 15 de febrero de 2006 en Wayback Machine F21 Microprocessor Overview A Java chip available now by Rick Brian Slack 4stack Processor Harry Gunnarsson and Thomas Lundqvist 1995 Porting the GNU C Compiler to the Thor Microprocessor Consultado el 4 de diciembre de 2008 Computer Architecture a Quantitative Approach John L Henessy David Goldberg See the discussion of stack machines Virtual Machine Showdown Stack vs Register Machine Yunhe Shi David Gregg Andrew Beatty M Anton Ertle Hennessy ibid Sh Boom CPU description Charles Moore Grandes sistemas de Burroughs 8051 CPU Manual Intel 1980Enlaces externos EditarStack 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 Datos Q2740397Obtenido de https es wikipedia org w index php title Maquina de pila amp oldid 135050147, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos