Stack machine (pt-BR)

Stack machine

Na ciência da computação, engenharia da computação e implementações de linguagens de programação, uma stack machine é um processador de computador ou uma máquina virtual cuja interação primária é mover valores temporários de curta duração para uma pilha push down e dela para fora. No caso de um processador de hardware, uma pilha de hardware é usada. O uso de uma pilha reduz significativamente o número necessário de registradores do processador. Stack machines estendem autômatos push-down com operações adicionais load/store ou múltiplas pilhas e, por tanto, são Turing-completas.

Design

A maioria ou todas as instruções de uma stack machine presumem que os operandos serão da pilha, e que os resultados serão colocados na pilha. A pilha contém facilmente mais de duas entradas ou mais de um resultado, portanto, um rico conjunto de operações pode ser calculado. Em código de stack machine (às vezes chamado de p-code), as instruções frequentemente terão apenas um opcode comandando uma operação, sem campos adicionais identificando uma constante, registrador ou célula de memória, conhecido como formato de endereço zero. Isso simplifica muito a decodificação de instruções. Ramificações, cargas imediatas e instruções de load/store requerem um campo de argumento, mas as stack machines costumam fazer com que os casos frequentes desses ainda se encaixem com o opcode em um grupo compacto de bits. A seleção de operandos de resultados anteriores é feita implicitamente a partir da ordenação das instruções. Alguns conjuntos de instruções de stack machines destinam-se à execução interpretativa de uma máquina virtual, em vez de direcionar o hardware diretamente.

Operandos constantes inteiros são enviados por instruções Push ou Load Immediate. A memória é frequentemente acessada por instruções separadas de Load ou Store contendo um endereço de memória ou calculando o endereço a partir de valores na pilha. Todas as stack machines práticas têm variantes dos opcodes load–store para acessar variáveis ​​locais e parâmetros formais sem cálculos de endereço explícitos. Isso pode ser por deslocamentos do endereço top-of-stack atual ou por deslocamentos de um registrador frame-base estável.O conjunto de instruções realiza a maioria das ações ALU com operações pós-fixadas (notação Polonesa reversa) que funcionam apenas na pilha de expressão, não em registradores de dados ou células de memória principal. Isso pode ser muito conveniente para a execução de linguagens de alto nível, porque a maioria das expressões aritméticas podem ser facilmente traduzidas para notação pós-fixada.Por exemplo, considere a expressão A*(B-C)+(D+E), escrita em notação Polonesa reversa como A B C - * D E + +. Compilar e rodar isso em uma stack machine imaginária simples tomaria a forma:

                # stack contents (leftmost = top = most recent):
push A          #           A
push B          #     B     A
push C          # C   B     A
subtract        #     B-C   A
multiply        #           A*(B-C)
push D          #     D     A*(B-C)
push E          # E   D     A*(B-C)
add             #     D+E   A*(B-C)
add             #           A*(B-C)+(D+E)

As operações aritméticas 'subtrair', 'multiplicar' e 'adicionar' atuam nos dois operandos superiores da pilha. O computador obtém ambos os operandos dos valores superiores (mais recentes) da pilha. O computador substitui esses dois valores pela diferença, soma ou produto calculado. Em outras palavras, os operandos da instrução são retirados (“popped”) da pilha e seu(s) resultado(s) são colocados (“pushed”) de volta na pilha, prontos para a próxima instrução.

As stack machines podem ter sua pilha de expressão e sua pilha de retorno de chamada (call-return stack) separadas ou como uma estrutura integrada. Se eles forem separados, as instruções da stack machine podem ser canalizadas com menos interações e menos complexidade de design, portanto, geralmente irá rodar mais rápido.

Otimização de código de pilha compilado é bem possível. Foi demonstrado que a otimização de back-end da saída do compilador melhora significativamente o código e, potencialmente, o desempenho, enquanto a otimização global dentro do próprio compilador alcança ganhos adicionais.

Armazenamento em pilha

Algumas stack machines têm uma pilha de tamanho limitado, implementada como um arquivo de registrador. A ULA irá acessá-lo com um índice. Um arquivo de registrador grande usa muitos transistores e, portanto, esse método só é adequado para sistemas pequenos. Algumas máquinas têm uma pilha de expressão na memória e uma pilha de registradores separada. Nesse caso, o software ou uma interrupção pode mover dados entre eles. Algumas máquinas têm uma pilha de tamanho ilimitado, implementada como uma matriz na RAM, que é armazenada em cache por alguns registradores de endereço "no topo da pilha" (top of stack) para reduzir o acesso à memória. Exceto por instruções “carregue da memória” (load from memory) explícitas, a ordem do uso de operandos é idêntica à ordem dos operandos na pilha de dados, então, pré-buscas perfeitas podem ser realizadas facilmente. Considere  X+1. Ele compila para Load X; Load 1; Add. Com uma pilha armazenada completamente em RAM, isso faz gravações e leituras implícitas da pilha na memória:

• Load X, push to memory
• Load 1, push to memory
• Pop 2 values from memory, add, and push result to memory

for a total of 5 data cache references. O próximo passo é uma stack machine ou intérprete com um único registrador no topo da pilha (top-of-stack). O código acima então faz:

• Load X into empty TOS register (if hardware machine) or Push TOS register to memory, Load X into TOS register (if interpreter)
• Push TOS register to memory, Load 1 into TOS register
• Pop left operand from memory, add to TOS register and leave it there

for a total of 5 data cache references, worst-case. Geralmente, os intérpretes não rastreiam o vazio, porque eles não precisam - qualquer coisa abaixo do ponteiro da pilha é um valor não vazio, e o registro de cache TOS é sempre mantido ativo. Os interpretadores Java típicos não armazenam em buffer o topo da pilha (top-of-stack) dessa maneira, porque o programa e a pilha possuem uma combinação de valores de dados curtos e amplos. Se a stack machine hardwired tem 2 ou mais registradores de topo de pilha, ou um arquivo de registrador, então todo o acesso à memória é evitado neste exemplo e há apenas 1 ciclo de cache de dados.

História e implementações

A descrição de tal método que exige apenas dois valores por vez para serem mantidos nos registradores, com um conjunto limitado de operandos predefinidos que podiam ser estendidos pela definição de outros operandos, funções e sub-rotinas, foi fornecida pela primeira vez na conferência por Robert S. Barton em 1961.

Stack machines comerciais

Veja também: High-level language computer architecture

Exemplos de conjuntos de instruções de pilha diretamente executados em hardware incluem

• A arquitetura F18A do chip 144-processor GA144 da GreenArrays, Inc.
• o computador Z$ por Konrad Zuse
• a arquitetura Burroughs large systems (desde 1961).
• o Xerox Dandelion introduzido em 27 de Abril de 1981, utilizava uma arquitetura stack machine para economizar memória
• a máquina English Electric KDF9. Primeiramente entregue em 1964, a KDF9 possuía uma pilha pushdown de profundidade 19 de registradores aritméticos, e uma pilha de profundidade 17 para endereços de retorno de subrotina
• o minicomputador Collins Adaptive Processing System (CAPS, desde 1969) da Collins Radio e o Advanced Architecture Microprocessor (AAMP, desde 1969) da Rockwell Collins
• a máquina-p UCSD Pascal (como a Pascal Microengine e vários outros) suportava um ambiente de programação de estudantes completo nos primeiros microprocessadores de 8-bits com conjuntos de instruções pobres e pouca RAM, compilando para uma stack machine virtual.
• Série MU5 e ICL 2900. Pilha híbrida e máquinas acumuladoras. O registrador do acumulador armazenou em buffer o valor de dados do topo da pilha de memória. Variantes de opcodes load e store controlados quando aquele registrador era derramado na pilha de memória ou recarregado de lá.
• HP 3000 (Clássico, não PA-RISC)
• Como o HP 3000, exceto que compiladores, não microcódigo, controlados quando a pilha de registradores transbordava para a pilha de memória ou era recarregada da pilha de memória.
• o microcontrolador Atmel MARC4.
• Diversos "Forth chips" como o RTX2000, RTX2010, F21 e o PSC1000
• O computador Setun Ternary executava o ternário balanceado usando uma pilha.
• O processador 4stack por Bernd Paysan tem quatro pilhas.
• A stack machine Ignite da Patriot Scientific, projetada por Charles H. Moore, possui uma referência em densidade funcional líder.
• Microprocessador endurecido por radiação Thor, da Saab Ericsson Space
• Transputadores Inmos.
• ZPU Uma CPU fisicamente pequena projetada para supervisionar sistemas FPGA.
• Algumas calculadoras manuais técnicas usam notação polonesa reversa em sua interface de teclado, em vez de ter teclas de parênteses. Esta é uma forma de stack machine. A tecla Mais depende de seus dois operandos já estarem nas posições superiores corretas da pilha visível ao usuário.

Stack machines virtuais

Exemplos de stack machines virtuais interpretadas em software:

• o código interpretativo Whetstone ALGOL 60, no qual algumas características do Burroughs B6500 foram baseadas
• o Burroughs B5000
• a p-machine UCSD Pascal; que se assemelhava muito ao Burroughs
• a máquina p-code Niklaus Wirth
• Smalltalk
• o conjunto de instruções da Java virtual machine
• o  bytecode WebAssembly
• o Virtual Execution System (VES) para o conjunto de instruções Common Intermediate Language (CIL) do .NET Framework (ECMA 335)
• a linguagem de programação Forth, especialmente a máquina virtual integral
• PostScript da Adobe
• linguagem de programação Parakeet
• Linguagem de programação SwapDrop da Sun Microsystems para identificação de smartcard Sun Ray
• ActionScript Virtual Machine 2 (AVM2) da Adobe
• EVM da Ethereum
• o interpretador bytecode CPython
• o interpretador bytecode  Ruby YARV
• a máquina virtual Rubinius
• a bs (linguagem de programação) no Unix usa uma stack machine virtual para processar comandos, após primeiro transpor a forma de linguagem de entrada fornecida, para a notação polonesa reversa
• a API C Lua (linguagem de programação)

Máquinas híbridas

(Eles não devem ser confundidos com computadores híbridos que combinam recursos digitais e analógicos, por exemplo, um computador digital que acessa multiplicação analógica ou resolução de equação diferencial por mapeamento de memória e conversão de e para as entradas e saídas de um dispositivo analógico.) As stack machines puras são bastante ineficientes para procedimentos que acessam vários campos do mesmo objeto. O código da stack machine deve recarregar o ponteiro do objeto para cada cálculo de ponteiro + deslocamento. Uma correção comum para isso é adicionar alguns recursos de máquina de registradores (register-machine) à stack machine: um arquivo de registradores visível dedicado a conter endereços e instruções estilo registrador para fazer loads e cálculos de endereço simples. É incomum que os registradores tenham um propósito totalmente geral, porque então não há uma razão forte para ter uma pilha de expressões e instruções pós-fixadas. Outro híbrido comum é começar com uma arquitetura de máquina de registrador e adicionar outro modo de endereço de memória que emula as operações push ou pop de stack machines: 'memaddress = reg; reg += instr.displ '. Isso foi usado pela primeira vez no minicomputador PDP-11 da DEC. Esse recurso foi levado adiante em computadores VAX e em microprocessadores Motorola 6800 e M68000. Isso permitiu o uso de métodos de pilha mais simples nos primeiros compiladores. Ele também oferecia suporte a máquinas virtuais de forma eficiente usando interpretadores de pilha ou threaded code. No entanto, esse recurso não ajudou o próprio código da máquina de registradores a se tornar tão compacto quanto o código de stack machine puro. Além disso, a velocidade de execução foi menor do que ao compilar bem para a arquitetura de registradores. É mais rápido alterar o ponteiro do topo da pilha (top-of-stack) apenas ocasionalmente (uma vez por chamada ou retorno) em vez de constantemente aumentá-lo e diminuí-lo em cada instrução do programa, e é ainda mais rápido evitar totalmente as referências à memória. Mais recentemente, as chamadas stack machines de segunda geração adotaram uma coleção dedicada de registradores para servir como registradores de endereço, descarregando a tarefa de endereçamento de memória da pilha de dados. Por exemplo, MuP21 depende de um registrador chamado "A", enquanto os processadores GreenArrays mais recentes contam com dois registradores: A e B. A família de microprocessadores Intel x86 tem um conjunto de instruções do tipo registrador (acumulador) para a maioria das operações, mas usa instruções de pilha para seu x87, aritmética de ponto flutuante Intel 8087, que remonta ao coprocessador iAPX87 (8087) para o 8086 e 8088. Ou seja, não há registradores de ponto flutuante programador-acessíveis, mas apenas uma pilha de 80 bits de largura e 8 de profundidade. O x87 depende muito da CPU do x86 para assistência na execução de suas operações.

Computadores que usam pilhas de chamadas (call stacks) e quadro de pilha (stack frames)

A maioria dos computadores atuais (de qualquer estilo de conjunto de instruções) e a maioria dos compiladores usam uma grande pilha de retorno de chamada na memória para organizar as variáveis ​​locais de curta duração e links de retorno para todos os procedimentos ou funções atualmente ativos. Cada chamada aninhada cria um novo quadro de pilha (stack frame) na memória, que persiste até que a chamada seja concluída. Essa pilha de retorno de chamada pode ser inteiramente gerenciada pelo hardware por meio de registradores de endereço especializados e modos de endereço especiais nas instruções. Ou pode ser meramente um conjunto de convenções seguidas pelos compiladores, usando registradores genéricos e modos de endereço registrador + deslocamento. Ou pode ser algo entre os dois. Uma vez que essa técnica agora é quase universal, mesmo em máquinas de registradores, não é útil referir-se a todas essas máquinas como stack machines. Esse termo é comumente reservado para máquinas que também usam uma pilha de expressões e instruções aritméticas stack-only para avaliar as partes de uma única instrução. Os computadores geralmente fornecem acesso direto e eficiente às variáveis ​​globais do programa e às variáveis ​​locais apenas do procedimento ou função mais interna atual, o quadro de pilha mais alto no topo. Endereçamento ‘up level' do conteúdo dos frames da pilha do chamador geralmente não é necessário e não é suportado diretamente pelo hardware. Se necessário, os compiladores suportam isso, passando ponteiros de quadro como parâmetros ocultos adicionais. Algumas stack machines Burroughs suportam up-level refs diretamente no hardware, com modos de endereço especializados e um arquivo de registrador especial de 'exibição' contendo os endereços de quadro de todos os escopos externos. Nenhuma linha de computador subsequente fez isso no hardware. Quando Niklaus Wirth desenvolveu o primeiro compilador Pascal para o CDC 6000, ele descobriu que era mais rápido no geral passar os ponteiros de quadro como uma cadeia, em vez de atualizar constantemente matrizes completas de ponteiros de quadro. Este método de software também não adiciona sobrecarga para linguagens comuns como C, que não possuem referências de up-level. As mesmas máquinas Burroughs também suportavam aninhamento de tarefas ou threads. A tarefa e seu criador compartilham os quadros de pilha que existiam no momento da criação da tarefa, mas não os frames subsequentes do criador nem os próprios frames da tarefa. Ele era sustentado por uma pilha de cactos, cujo diagrama de layout lembrava o tronco e os braços de um cacto Saguaro. Cada tarefa tinha seu próprio segmento de memória contendo sua pilha e os quadros que ela possuía. A base desta pilha está ligada ao meio da pilha de seu criador. Em máquinas com um espaço de endereço simples convencional, a pilha do criador e as pilhas de tarefas seriam objetos de heap separados em um heap. Em algumas linguagens de programação, os ambientes de dados de escopo externo nem sempre estão aninhados a tempo. Essas linguagens organizam seus 'registros de ativação' de procedimentos como objetos de heap separados, em vez de quadros de pilha anexados a uma pilha linear. Em linguagens simples como Forth, que carecem de variáveis ​​locais e nomenclatura de parâmetros, os quadros de pilha conteriam nada mais do que endereços de ramificação de retorno e overhead de gerenciamento de quadros. Portanto, sua pilha de retorno contém endereços de retorno vazios em vez de frames. A pilha de retorno é separada da pilha de valores de dados, para melhorar o fluxo de configuração de chamadas e retornos.

Comparação com máquinas de registro

As stack machines são frequentemente comparadas a máquinas de registro, que mantêm valores em uma matriz de registros. Máquinas de registro podem armazenar estruturas semelhantes a pilha neste array, mas uma máquina de registro tem instruções que contornam a interface de pilha. As máquinas de registro rotineiramente superam as stack machines, e as stack machines têm permanecido um jogador de nicho em sistemas de hardware. Mas as stack machines são frequentemente usadas na implementação de máquinas virtuais devido à sua simplicidade e facilidade de implementação.

Instruções

As stack machines têm maior densidade de código. Em contraste com as instruções de stack machine comuns, que podem caber facilmente em 6 bits ou menos, as máquinas de registro requerem dois ou três campos de número de registro por instrução ALU para selecionar operandos; as máquinas de registro mais densas têm em média cerca de 16 bits por instrução mais os operandos. As máquinas de registro também usam um campo de deslocamento mais amplo para opcodes (código de operação) de carregar-armazenar. O código compacto de uma stack machine acomoda naturalmente mais instruções no cache e, portanto, pode obter melhor eficiência do cache, reduzindo os custos de memória ou permitindo sistemas de memória mais rápidos por um determinado custo. Além disso, a maioria das instruções de pilha-máquina são muito simples, feita de apenas um campo de opcode ou um campo de operando. Assim, as stack machines requerem muito pouco recursos eletrônicos para decodificar cada instrução.

Um programa precisa executar mais instruções quando compilado em uma stack machine do que quando compilado em uma máquina de registro ou de memória para memória. Cada carga ou constante variável requer sua própria instrução Load separada, em vez de ser agrupada dentro da instrução que usa aquele valor. As instruções separadas podem ser simples e de execução mais rápida, mas a contagem total de instruções ainda é maior.

A maioria dos intérpretes de registro especificam seus registros por número. Mas os registros de uma máquina host não podem ser acessados ​​em um array indexado, então um array de memória é alocado para registradores virtuais. Portanto, as instruções de um interpretador de registradores devem usar memória para passar os dados gerados para a próxima instrução. Isso força os intérpretes de registro a serem muito mais lentos em microprocessadores feitos com uma regra de processo fina (ou seja, transistores mais rápidos sem melhorar a velocidade do circuito, como o Haswell x86). Isso requer vários relógios para acesso à memória, mas apenas um relógio para acesso ao registro. No caso de uma stack machine com um circuito de encaminhamento de dados em vez de um arquivo de registro, os intérpretes de pilha podem alocar os registros da máquina host para os vários operandos do topo da pilha em vez da memória da máquina host

Em uma stack machine, os operandos usados ​​nas instruções estão sempre em um deslocamento conhecido (definido no ponteiro da pilha), a partir de um local fixo (a parte inferior da pilha, que em um design de hardware pode sempre estar no local de memória zero), evitando que o precioso armazenamento em cache ou na CPU seja usado para armazenar tantos endereços de memória ou números de índice. Isso pode preservar esses registros e cache para uso em computação sem fluxo.

Valores temporários / locais

Alguns na indústria acreditam que as stack machines executam mais ciclos de cache de dados para valores temporários e variáveis ​​locais do que as máquinas de registro.

Em stack machines, os valores temporários geralmente são derramados na memória, enquanto em máquinas com muitos registros esses temps geralmente permanecem nos registros. (No entanto, esses valores geralmente precisam ser derramados em "quadros de ativação" no final da definição de um procedimento, bloco básico ou, pelo menos, em um buffer de memória durante o processamento de interrupção). Os valores derramados na memória adicionam mais ciclos de cache. Esse efeito de propagação depende do número de registros ocultos usados ​​para armazenar os valores do topo da pilha, da frequência das chamadas de procedimento aninhado e das taxas de processamento de interrupção do computador host.

Em máquinas de registro que usam compiladores de otimização, é muito comum que as variáveis ​​locais mais usadas permaneçam em registros em vez de em células de memória de quadro de pilha. Isso elimina a maioria dos ciclos de cache de dados para leitura e gravação desses valores. O desenvolvimento de "escalonamento de pilha" para realizar análises de variáveis ​​vivas e, assim, reter variáveis-chave na pilha por longos períodos, ajuda nessa preocupação. Por outro lado, as máquinas de registradores devem transferir muitos de seus registradores para a memória por meio de chamadas de procedimento aninhadas. A decisão de quais registros registrar e quando, é feita estaticamente no tempo de compilação, e não na profundidade dinâmica das chamadas. Isso pode levar a mais tráfego de cache de dados do que em uma implementação avançada de stack machine.

Subexpressões comuns

Em máquinas de registro, uma subexpressão comum (uma subexpressão que é usada várias vezes com o mesmo valor de resultado) pode ser avaliada apenas uma vez e seu resultado salvo em um registro rápido. As reutilizações subsequentes não têm custo de tempo ou código, apenas uma referência de registro. Essa otimização acelera expressões simples (por exemplo, carregar a variável X ou o ponteiro P), bem como expressões complexas menos comuns. Com stack machines, em contraste, os resultados podem ser armazenados de duas formas. Em primeiro lugar, os resultados podem ser armazenados usando uma variável temporária na memória. O armazenamento e as recuperações subsequentes custam instruções adicionais e ciclos de cache de dados adicionais. Fazer isso é só uma vitória se o cálculo da subexpressão custar mais tempo do que buscar na memória, o que na maioria das CPUs da pilha, quase sempre é o caso. Nunca vale a pena para variáveis ​​simples e buscas de ponteiro, porque elas já têm o mesmo custo de um ciclo de cache de dados por acesso. É apenas marginalmente útil para expressões como X + 1. Essas expressões mais simples constituem a maioria das expressões redundantes e otimizáveis ​​em programas escritos em linguagens não concatenativas. Um compilador otimizado só pode vencer redundâncias que o programador poderia ter evitado no código-fonte.

A segunda forma deixa um valor calculado na pilha de dados, duplicando-o conforme é necessário. Isso usa operações para copiar entradas de pilha. A pilha deve ter profundidade suficiente para as instruções de cópia disponíveis da CPU. O código de pilha escrito à mão geralmente usa essa abordagem e atinge velocidades como máquinas de registro de uso geral. Infelizmente, algoritmos para "escalonamento de pilha" ideal não são amplamente usados ​​por linguagens de programação.

Pipelining

Em máquinas modernas, o tempo para buscar uma variável no cache de dados costuma ser várias vezes maior do que o tempo necessário para as operações básicas da ALU. Um programa é executado mais rápido sem travamentos se a carga de sua memória puder ser iniciada vários ciclos antes da instrução que precisa dessa variável. Máquinas complexas podem fazer isso com um pipeline profundo e "execução fora de ordem" que examina e executa muitas instruções ao mesmo tempo. As máquinas de registro podem até fazer isso com um hardware "em ordem" muito mais simples, um pipeline raso e compiladores um pouco mais inteligentes. A etapa de carregamento se torna uma instrução separada e essa instrução é programada estaticamente muito antes na sequência de código. O compilador coloca etapas independentes no meio.

O agendamento de acessos à memória requer registros sobressalentes explícitos. Não é possível em stack machines sem expor algum aspecto da microarquitetura ao programador. Para a expressão A B -, B deve ser avaliado e pressionado imediatamente antes da “etapa Menos”. Sem permutação de pilha ou multithreading (capacidade de uma unidade de processamento central de fornecer vários threads de execução simultaneamente) de hardware, relativamente pouco código útil pode ser colocado no meio enquanto espera o Load B terminar. As stack machines podem contornar o atraso de memória por ter um pipeline de execução profundamente fora de ordem cobrindo muitas instruções ao mesmo tempo ou, mais provavelmente, podem permutar a pilha de modo que possam trabalhar em outras cargas de trabalho enquanto a carga é concluída, ou eles podem entrelaçar a execução de diferentes threads de programa, como no sistema Unisys A9. As cargas computacionais cada vez mais paralelas de hoje sugerem, no entanto, essa pode não ser a desvantagem que foi feita no passado. As stack machines podem omitir o estágio de busca de operando de uma máquina de registro. Por exemplo, no microprocessador Java Optimized Processor (JOP), os 2 principais operandos da pilha entram diretamente em um circuito de encaminhamento de dados que é mais rápido do que o arquivo de registro.

Execução fora de ordem

O algoritmo Tomasulo encontra o paralelismo em nível de instrução emitindo instruções conforme seus dados se tornam disponíveis. Conceitualmente, os endereços das posições em uma pilha não são diferentes dos índices de registro de um arquivo de registro. Esta visualização permite a execução fora de ordem do algoritmo Tomasulo a ser usado com stack machines. A execução fora de ordem em stack machines parece reduzir ou evitar muitas dificuldades teóricas e práticas. A pesquisa citada mostra que tal stack machine pode explorar o paralelismo em nível de instrução, e o hardware resultante deve armazenar dados em cache para as instruções. Essas máquinas evitam efetivamente a maioria dos acessos à memória para a pilha. O resultado alcança uma taxa de transferência (instruções por clock) comparável às máquinas de registro RISC, com densidades de código muito mais altas (porque os endereços de operando estão implícitos).

Um problema levantado na pesquisa foi que são necessárias cerca de 1.88 instruções de stack machine para fazer o trabalho de uma instrução RISC de máquina de registro. Portanto, as stack machines fora de ordem da concorrência requerem cerca de duas vezes mais recursos eletrônicos para rastrear as instruções ("estações de emissão"). Isso pode ser compensado pela economia no cache de instruções e na memória e nos circuitos de decodificação de instruções.

Esconde uma máquina de registro mais rápida dentro

Algumas stack machines simples têm um design de chip totalmente personalizado até o nível de registros individuais. O registro de endereço no topo da pilha e o topo N de buffers de dados são construídos a partir de circuitos de registro individuais separados, com somadores separados e conexões ad hoc.

No entanto, a maioria das stack machines são construídas a partir de componentes de circuitos maiores, onde os N buffers de dados são armazenados juntos em um arquivo de registro e compartilham barramentos de leitura / gravação. As instruções de pilha decodificadas são mapeadas em uma ou mais ações sequenciais naquele arquivo de registro oculto. Loads e as operações da ALU atuam em alguns registradores superiores, e os derramamentos e preenchimentos implícitos atuam nos registradores inferiores. O decodificador permite que o fluxo de instruções seja compacto. Mas se o fluxo de código, em vez disso, tivesse campos de seleção de registro explícitos que manipulavam diretamente o arquivo de registro subjacente, o compilador poderia fazer melhor uso de todos os registros e o programa seria executado mais rápido. As stack machines microprogramadas são um exemplo disso. O mecanismo de microcódigo interno é algum tipo de máquina de registro semelhante a RISC ou uma máquina semelhante a VLIW (Very Long Instruction Word, arquitetura de CPU que executa um grupo de instruções ao mesmo tempo) usando vários arquivos de registro. Quando controlado diretamente por microcódigo específico de tarefa, esse mecanismo obtém muito mais trabalho concluído por ciclo do que quando controlado indiretamente por código de pilha equivalente para a mesma tarefa. Os tradutores de código-objeto para HP 3000 e Tandem T / 16 são outro exemplo. Eles traduziram sequências de código de pilha em sequências equivalentes de código RISC. Pequenas otimizações 'locais' removeram muito da sobrecarga de uma arquitetura de pilha. Registradores sobressalentes foram usados ​​para fatorar cálculos de endereço repetidos. O código traduzido ainda retinha bastante sobrecarga de emulação da incompatibilidade entre as máquinas original e de destino. Apesar dessa carga, a eficiência do ciclo do código traduzido correspondeu à eficiência do ciclo do código da pilha original. E quando o código-fonte foi recompilado diretamente na máquina de registro por meio da otimização de compiladores, a eficiência dobrou. Isso mostra que a arquitetura da pilha e seus compiladores não otimizados estavam desperdiçando mais da metade da capacidade do hardware subjacente.

Os arquivos de registro são boas ferramentas para computação porque têm alta largura de banda e latência muito baixa, em comparação com referências de memória por meio de caches de dados. Em uma máquina simples, o arquivo de registro permite a leitura de dois registros independentes e a escrita de um terceiro, tudo em um ciclo de ALU com um ciclo ou menos latência. Enquanto o cache de dados correspondente pode iniciar apenas uma leitura ou uma gravação (não ambas) por ciclo, a leitura normalmente tem uma latência de dois ciclos ALU. Isso é um terço da taxa de transferência com o dobro do atraso do pipeline. Em uma máquina complexa como o Athlon que completa duas ou mais instruções por ciclo, o arquivo de registro permite a leitura de quatro ou mais registros independentes e a escrita de outros dois, tudo em um ciclo ALU com latência de um ciclo. Enquanto o cache de dados de porta dupla correspondente pode iniciar apenas duas leituras ou gravações por ciclo, com vários ciclos de latência. Novamente, isso é um terço da taxa de transferência dos registros. É muito caro construir um cache com portas adicionais. Como uma pilha é um componente da maioria dos programas de software, mesmo quando o software usado não é estritamente uma stack machine, uma stack machine de hardware pode imitar mais de perto o funcionamento interno de seus programas. Os registros do processador têm um alto custo térmico e uma stack machine pode alegar maior eficiência energética.

Interrupções

Responder a uma interrupção envolve salvar os registradores em uma pilha e, em seguida, ramificar para o código do manipulador de interrupção. Frequentemente, as stack machines respondem mais rapidamente às interrupções, porque a maioria dos parâmetros já está em uma pilha e não há necessidade de colocá-los lá. Algumas máquinas de registro lidam com isso tendo vários arquivos de registro que podem ser trocados instantaneamente, mas isso aumenta os custos e atrasa o arquivo de registro.

Intérpretes

Os intérpretes para stack machines virtuais são mais fáceis de construir do que os intérpretes para máquinas de registro; a lógica para lidar com os modos de endereço de memória está em apenas um lugar, em vez de repetida em muitas instruções. As stack machines também tendem a ter menos variações de um opcode; um opcode generalizado irá lidar com casos frequentes e casos obscuros de referências de memória ou configuração de chamada de função. (Mas a densidade do código geralmente é melhorada com a adição de formulários curtos e longos para a mesma operação.) Os intérpretes para stack machines virtual são frequentemente mais lentos do que os intérpretes para outros estilos de máquina virtual. Essa desaceleração é pior durante a execução em máquinas host com pipelines de execução profunda, como os atuais chips x86. Em alguns intérpretes, o intérprete deve executar um salto de switch N-way para decodificar o próximo opcode e ramificar para suas etapas para aquele opcode específico. Outro método para selecionar opcodes é o código encadeado. Os mecanismos de pré-busca da máquina host são incapazes de prever e buscar o destino daquele salto indexado ou indireto. Portanto, o pipeline de execução da máquina host deve reiniciar cada vez que o interpretador hospedado decodificar outra instrução virtual. Isso acontece com mais frequência para stack machines virtual do que para outros estilos de máquina virtual.

Um exemplo é a linguagem de programação Java. Sua máquina virtual canônica é especificada como uma stack machine de 8 bits. No entanto, a máquina virtual Dalvik para Java usada em smartphones Android é uma máquina de registro virtual de 16 bits - uma escolha feita por razões de eficiência. As instruções aritméticas buscam ou armazenam diretamente as variáveis ​​locais por meio de campos de instrução de 4 bits (ou maiores). Da mesma forma, a versão 5.0 de Lua substituiu sua stack machine virtual por uma máquina de registro virtual mais rápida. Desde que a máquina virtual Java se tornou popular, os microprocessadores empregaram preditores de ramificação avançados para saltos indiretos. Esse avanço evita a maioria das reinicializações de pipeline de saltos de N-way e elimina muitos dos custos de contagem de instruções que afetam os interpretadores de pilha.

Veja também

• Stack-oriented programming language
• Concatenative programming language
• Comparison of application virtual machines
• SECD machine
• Accumulator machine
• Belt machine
• Random-access machine

Referências

1. Beard, Bob (Autumn 1997). "The KDF9 Computer - 30 Years On". Computer RESURRECTION.
2. Koopman, Philip (1994). "A Preliminary Exploration of Optimized Stack Code Generation" (PDF). Journal of Forth Applications and Research. 6 (3).
3. Bailey, Chris (2000). "Inter-Boundary Scheduling of Stack Operands: A preliminary Study" (PDF). Proceedings of Euroforth 2000 Conference.
4. Shannon, Mark; Bailey C (2006). "Global Stack Allocation : Register Allocation for Stack Machines" (PDF). Proceedings of Euroforth Conference 2006.
5. Barton, Robert S. (1961). "A new approach to the functional design of a digital computer". IRE-AIEE-ACM '61 (Western): Papers presented at the May 9–11, 1961, western joint IRE-AIEE-ACM computer conference.
6. Barton, Robert S. (1987). "A new approach to the functional design of a digital computer". IEEE Annals of the History of Computing.
7. "GreenArrays, Inc. - Documents". Greenarraychips.com. Retrieved 8 October 2017.
8. ""Instruction set of the F18A cores (named colorForth for historical reasons)."". Colorforth.com. Archived from the original on 2016-03-10. Retrieved 8 October 2017.
9. ""GreenArrays, Inc."". Greenarraychips.com. Retrieved 8 October 2017.
10. http://fpgacpu.ca/publications/Second-Generation_Stack_Computer_Architecture.pdf
11. "Mesa Processor Principles of Operation". DigiBarn Computer Museum. Xerox. Retrieved 23 December 2019.
12. "DigiBarn: The Xerox Star 8010 "Dandelion"". DigiBarn Computer Museum. Retrieved 23 December 2019.
13. "The World's First Java Processor", by David A. Greve and Matthew M. Wilding, Electronic Engineering Times, January 12, 1998,
14. [1]
15. "Forth chips". Colorforth.com. Archived from the original on 15 February 2006. Retrieved 8 October 2017.
16. "F21 Microprocessor Overview". Ultratechnology.com. Retrieved 8 October 2017.
17. "ForthFreak wiki". GitHub.com. 25 August 2017. Retrieved 8 October 2017.
18. "A Java chip available -- now! - Developer.com". Developer.com. Retrieved 8 October 2017.
19. "4stack Processor". bernd-paysan.de. Retrieved 8 October 2017.
20. "Archived copy" (PDF). Archived from the original (PDF) on 2011-08-20. Retrieved 2011-03-30.
21. "ZPU - the world's smallest 32-bit CPU with a GCC tool-chain: Overview". opencores.org. Retrieved 7 February 2015.
22. Randell, Brian and Russell, Lawford John "Algol 60 Implementation" London: Academic Press, 1964. ISBN 0-12-578150-4.
23. Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005). "Virtual machine showdown: stack versus registers". Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments - VEE '05: 153. doi:10.1145/1064979.1065001.
24. Hyde, Randall (2004). Write Great Code, Vol. 2: Thinking Low-Level, Writing High-Level. No Starch Press. p. 391. ISBN 978-1-59327-065-0. Retrieved 30 June 2021.
25. "Computer Architecture: A Quantitative Approach", John L Hennessy, David A Patterson; See the discussion of stack machines.
26. "Stack Computers: the new wave -- an on-line book". Ece.cmu.edu. Retrieved 8 October 2017.
27. "Second-Generation Stack Computer Architecture" (PDF). Fpgacpu.ca. Retrieved 8 October 2017.
28. "Archived copy" (PDF). Archived from the original (PDF) on 2011-07-18. Retrieved 2010-11-01.
29. "Archived copy" (PDF). Archived from the original (PDF) on 2011-03-21. Retrieved 2011-03-29.
30. "Design and Implementation of an Efficient Stack Machine" (PDF). Jopdesign.com. Retrieved 8 October 2017.
31. Chatterji, Satrajit; Ravindran, Kaushik. "BOOST: Berkeley's Out of Order Stack Thingie". Research Gate. Kaushik Ravindran. Retrieved 16 February 2016.
32. Bergh, Arndt; Keilman, Keith; Magenheimer, Daniel; Miller, James (December 1987). "HP3000 Emulation on HP Precision Architecture Computers" (PDF). Hewlett-Packard Journal: 87–89. Retrieved 8 October 2017.
33. Migrating a CISC Computer Family onto RISC via Object Code Translation, K. Andrews and D. Sand, Proceedings of ASPLOS-V, October, 1992
34. 8051 CPU Manual, Intel, 1980
35. Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertle, M. Anton. ""Virtual Machine Showdown: Stack vs. Register Machine"" (PDF). Usenix.org. Retrieved 8 October 2017.
36. Davis, Brian; Beatty, Andrew; Casey, Kevin; Gregg, David; Waldron, John. "'The Case for Virtual Register Machines'" (PDF). Scss.tcd.ie. Retrieved 8 October 2017.
37. Bornstein, Dan (2008-05-29). "Presentation of Dalvik VM Internals" (PDF). p. 22. Retrieved 2010-08-16.
38. "The Implementation of Lua 5.0" (PDF). Lua.org. Retrieved 8 October 2017.
39. "The Virtual Machine of Lua 5.0" (PDF). Inf.puc-rio.br. Retrieved 8 October 2017.
40. "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore". Hal.inria.fr. Retrieved 8 October 2017.

This article "Stack machine (pt-BR)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Stack machine (pt-BR). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---