Máquina de empilhar - Stack machine

Em ciência da computação , engenharia da computação e implementações de linguagem de programação , uma máquina de pilha é um processador de computador ou uma máquina virtual na qual a interação primária está movendo valores temporários de curta duração de e para uma pilha push-down . 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 registros do processador . As máquinas de pilha estendem o autômato push-down com operações adicionais de carga / armazenamento ou múltiplas pilhas e, portanto, são Turing-completas .

Projeto

A maioria ou todas as instruções de máquina de pilha assumem que os operandos virão da pilha e 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 máquina de pilha (às vezes chamado de código-p ), as instruções freqüentemente terão apenas um opcode comandando uma operação, sem campos adicionais que identifiquem uma constante, registro 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 carga / armazenamento requerem um campo de argumento, mas as máquinas de pilha 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 ordenando as instruções. Alguns conjuntos de instruções de máquina de pilha 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 Pushou Load Immediate. A memória é freqüentemente acessada por instruções separadas Loadou Storecontendo um endereço de memória ou calculando o endereço a partir de valores na pilha. Todas as máquinas de pilha 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 atual do topo da pilha ou por deslocamentos de um registro base de quadro 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 executar linguagens de alto nível, porque a maioria das expressões aritméticas pode ser facilmente traduzida em notação pós-fixada.

Árvore de sintaxe binária para a expressão A * ( B - C ) + ( D + E )

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 executar isso em uma máquina de pilha 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 os dois 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" da pilha e seus resultados são "colocados" de volta na pilha, prontos para a próxima instrução.

As máquinas de pilha podem ter sua pilha de expressão e sua pilha de retorno de chamada separadas ou como uma estrutura integrada. Se eles forem separados, as instruções da máquina de pilha podem ser canalizadas com menos interações e menos complexidade de design, portanto, geralmente será executado mais rápido.

A otimização do código de pilha compilado é perfeitamente 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 de pilha

Algumas máquinas de pilha têm uma pilha de tamanho limitado, implementada como um arquivo de registro. A ALU acessará isso com um índice. Um arquivo de registro 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 registro 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 registros de endereço "no topo da pilha" para reduzir o acesso à memória. Exceto para instruções explícitas de "carregar da memória", a ordem de uso do operando é idêntica à ordem dos operandos na pilha de dados, portanto, uma pré-busca excelente pode ser realizada facilmente.

Considere X+1. Compila para Load X; Load 1; Add. Com uma pilha armazenada completamente na RAM, isso faz gravações e leituras implícitas da pilha na memória:

  • Carregue o X, empurre para a memória
  • Carregue 1, empurre para a memória
  • Extraia 2 valores da memória, adicione e envie o resultado para a memória

para um total de 5 referências de cache de dados.

A próxima etapa é uma máquina de pilha ou intérprete com um único registro no topo da pilha. O código acima faz:

  • Carregar X no registro TOS vazio (se máquina de hardware) ou Empurrar registro TOS para a memória, carregar X no registro TOS (se intérprete)
  • Empurre o registro TOS para a memória, carregue 1 no registro TOS
  • Retire o operando esquerdo da memória, adicione ao registro TOS e deixe-o lá

para um total de 5 referências de cache de dados, pior caso. 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 do TOS é sempre mantido ativo. Os interpretadores Java típicos não armazenam o topo da pilha dessa maneira, entretanto, porque o programa e a pilha possuem uma combinação de valores de dados curtos e amplos.

Se a máquina de pilha com fio tiver 2 ou mais registros da pilha superior ou um arquivo de registro, todo o acesso à memória será evitado neste exemplo e haverá 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 registros, com um conjunto limitado de operandos predefinidos que podem 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.

Empilhadoras comerciais

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

  • A arquitetura F18A do chip GA144 com 144 processadores da GreenArrays, Inc.
  • o computador Z4 por Konrad Zuse .
  • a arquitetura de grandes sistemas Burroughs (desde 1961)
  • o Xerox Dandelion lançado em 27 de abril de 1981, utilizava uma arquitetura de máquina em pilha para economizar memória.
  • a máquina elétrica inglesa KDF9 . Entregue pela primeira vez em 1964, o KDF9 tinha uma pilha pushdown de 19 profundidades de registros aritméticos e uma pilha de 17 profundidades para endereços de retorno de sub-rotina
  • o minicomputador Collins Radio Collins Adaptive Processing System (CAPS, desde 1969) e Rockwell Collins Advanced Architecture Microprocessor (AAMP, desde 1981).
  • o UCSD Pascal p-machine (como o Pascal MicroEngine e muitos outros) suportava um ambiente completo de programação do aluno nos primeiros microprocessadores de 8 bits com conjuntos de instruções pobres e pouca RAM, compilando em uma máquina de pilha virtual.
  • Série MU5 e ICL 2900 . Pilha híbrida e máquinas acumuladoras. O registro do acumulador armazenou em buffer o valor de dados do topo da pilha de memória. Variantes de carregar e armazenar opcodes controlados quando aquele registro foi derramado na pilha de memória ou recarregado de lá.
  • HP 3000 (Classic, não PA-RISC)
  • Computadores Tandem T / 16. Como o HP 3000, exceto pelos compiladores, não microcódigo, controlados quando a pilha de registros transbordava para a pilha de memória ou era recarregada da pilha de memória.
  • o microcontrolador Atmel MARC4
  • Vários "Forth chips" como o RTX2000, o RTX2010 , o F21 e o PSC1000
  • O computador Ternário Setun realizou o ternário balanceado usando uma pilha.
  • O processador de 4 pilhas de Bernd Paysan tem quatro pilhas.
  • A máquina de pilha Ignite da Patriot Scientific, projetada por Charles H. Moore, é uma referência de densidade funcional líder .
  • Microprocessador endurecido por radiação Saab Ericsson Space Thor
  • INMOS transputers .
  • 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 máquina de pilha. A tecla Mais depende de seus dois operandos já estarem nas posições superiores corretas da pilha visível ao usuário.

Máquinas virtuais de pilha

Exemplos de máquinas de pilha virtuais interpretadas em software:

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 soluçã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 máquinas de pilha pura são bastante ineficientes para procedimentos que acessam vários campos do mesmo objeto. O código de máquina da pilha deve recarregar o ponteiro do objeto para cada ponteiro + cálculo de deslocamento. Uma correção comum para isso é adicionar alguns recursos de máquina de registro à máquina de pilha: um arquivo de registro visível dedicado a endereços de retenção e instruções de estilo de registro para fazer cargas e cálculos de endereço simples. É incomum que os registradores tenham um propósito totalmente geral, porque então não há 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 registro e adicionar outro modo de endereço de memória que emula as operações push ou pop de máquinas de pilha: 'memaddress = reg; reg + = instr.displ '. Isso foi usado pela primeira vez em dezembro de PDP-11 minicomputador. 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 oferece suporte a máquinas virtuais de forma eficiente usando interpretadores de pilha ou código encadeado . No entanto, esse recurso não ajudou o próprio código da máquina de registro a se tornar tão compacto quanto o código de máquina de pilha puro. Além disso, a velocidade de execução foi menor do que ao compilar bem para a arquitetura de registro. É mais rápido alterar o ponteiro do topo da pilha 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 máquinas de pilha 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 de estilo de registro (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 8086 e 8088. Isso ou seja, não há registradores de ponto flutuante acessíveis ao programador, mas apenas uma pilha de 80 bits de largura e 8 de profundidade. O x87 depende muito da CPU x86 para assistência na execução de suas operações.

Computadores que usam pilhas de chamadas e frames de pilha

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 retornar links para todos os procedimentos ou funções atualmente ativos. Cada chamada aninhada cria um novo quadro de pilha 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 apenas um conjunto de convenções seguidas pelos compiladores, usando registradores genéricos e modos de endereço de registro + deslocamento. Ou pode ser algo intermediário.

Como essa técnica agora é quase universal, mesmo em máquinas de registro, não é útil referir-se a todas essas máquinas como máquinas de pilha. Esse termo é comumente reservado para máquinas que também usam uma pilha de expressões e instruções aritméticas apenas de pilha 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. O endereçamento de 'nível superior' 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 máquinas da pilha Burroughs suportam refs de nível superior diretamente no hardware, com modos de endereço especializados e um arquivo de registro 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 nível superior.

As mesmas máquinas Burroughs também suportavam aninhamento de tarefas ou threads. A tarefa e seu criador compartilham os frames da 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 possui. 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 no tempo. Essas linguagens organizam seus procedimentos de 'registros de ativação' como objetos 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 sobrecarga de gerenciamento de quadros. Portanto, sua pilha de retorno contém endereços de retorno vazios em vez de quadros. 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 máquinas de pilha são freqüentemente comparadas a máquinas de registro , que armazenam valores em uma série 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 máquinas de pilha, e as máquinas de pilha permaneceram um participante de nicho em sistemas de hardware. Mas as máquinas de pilha são frequentemente usadas na implementação de máquinas virtuais devido à sua simplicidade e facilidade de implementação.

Instruções

As máquinas de pilha têm maior densidade de código . Em contraste com as instruções de máquina de pilha 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 carregar-armazenar. O código compacto de uma máquina de pilha encaixa naturalmente mais instruções no cache e, portanto, pode alcançar 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 é muito simples, feita de apenas um campo de opcode ou um campo de operando. Assim, as máquinas-pilha requerem muito poucos recursos eletrônicos para decodificar cada instrução.

Um programa tem que executar mais instruções quando compilado para uma máquina de pilha do que quando compilado para uma máquina de registro ou máquina 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 máquina de pilha 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 máquina de pilha, 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 máquinas de pilha executam mais ciclos de cache de dados para valores temporários e variáveis ​​locais do que as máquinas de registro.

Em máquinas de pilha, 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 máquina de pilha.

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 as máquinas de pilha, em contraste, os resultados podem ser armazenados de duas maneiras. 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 é apenas 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 máquinas de pilha sem expor algum aspecto da microarquitetura ao programador. Para a expressão AB -, B deve ser avaliado e pressionado imediatamente antes da etapa Menos. Sem permutação de pilha ou multithreading de hardware, relativamente pouco código útil pode ser colocado no meio enquanto espera o Load B terminar. As máquinas de pilha 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 pode 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 máquinas de pilha 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 máquinas de pilha.

A execução fora de ordem em máquinas de pilha parece reduzir ou evitar muitas dificuldades teóricas e práticas. A pesquisa citada mostra que tal máquina de pilha 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 da máquina de pilha para fazer o trabalho de uma instrução RISC da máquina de registro. Portanto, as máquinas de pilha fora de ordem da concorrência requerem cerca de duas vezes mais recursos eletrônicos para rastrear 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 máquinas de pilha 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 os N buffers de dados no topo da pilha 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 máquinas de pilha é construída a partir de componentes de circuito 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 ALU ops atuam em alguns registradores superiores, e spills 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 máquinas de pilha 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 usando vários arquivos de registro. Quando controlado diretamente por microcódigo de tarefa específica, 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 grande 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, e 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.

Uma vez que uma pilha é um componente da maioria dos programas de software, mesmo quando o software usado não é estritamente uma máquina de pilha, uma máquina de pilha 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 máquina de pilha 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. Freqüentemente, as máquinas de pilha 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 retarda o arquivo de registro.

Intérpretes

Os intérpretes para máquinas de pilha 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 máquinas de pilha 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 de máquinas de pilha virtual costumam ser mais lentos do que os intérpretes de 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 máquinas de pilha 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 máquina de pilha 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 máquina de pilha 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

Referências

links externos