Máquinas de Pilha - Máquina genérica
Máquinas com múltiplas pilhas e 0 operandos têm duas vantagens, inerentes à própria arquitectura, sobre os outros tipos de máquinas: endereçamento com 0 operandos leva a instruções pequenas e múltiplas pilhas permitem concorrência na chamadas de subrotinas e manipulação de dados. Estas características permitem programas pequenos, baixa complexidade do sistema e elevada performance.
Os programas de pequena dimensão são conseguidos não só pelo pequeno tamanho das instruções mas porque as máquinas de pilha encorajam o uso frequente de subrotinas para reduzir o tamanho do código. O pequeno tamanho dos programas reduz as necessidades de memória, número de componentes, exigências de consumo e pode levar ao aumento da velocidade do sistema permitindo o uso de memórias mais pequenas e rápidas, com um custo aceitável. Permitem uma maior performance em ambientes de memória virtual e necessitam de menos memória cache para atingir um mesmo nível de performance. Esta menor complexidade do sistema diminui o tamanho do chip, permitindo maior espaço para a memória e componentes específicos do sistema onde o processador se irá inserir.
Para avaliar a performance de um processador não podemos ter apenas em conta a velocidade de execução de instruções por unidade de tempo, mas também a velocidade com que são tratadas as interrupções, as mudanças de contexto e a degradação da performance devido a factores como os saltos condicionais e chamadas a procedimentos. Nas máquinas de pilha, o mesmo modo de endereçamento com 0 operandos e a frequente chamada a subrotinas que reduzem o tamanho do código e a complexidade do sistema, levam a uma melhoria na performance na execução dos programas.
Neste diagrama estão representados os componentes essenciais numa máquina com múltiplas pilhas e 0 operandos.
Esses componentes são:
Esta máquina tem apenas um único bus a ligar os recursos do sistema. Os processadores reais podem ter mais do que um caminho para os dados, permitindo paralelismo na obtenção de instruções e cálculos. Nesta máquina genérica o bus de dados apenas permite uma operação de escrita ou leitura por ciclo de relógio.
A pilha de dados é uma memória com um mecanismo interno para implementar uma pilha LIFO. A pilha de dados permite duas operações: PUSH e POP. Um PUSH reserva uma nova célula no topo da pilha e escreve o valor do bus de dados nessa célula. Um POP coloca o valor do topo da pilha no bus de dados, apaga a célula, expondo a célula seguinte da pilha para a próxima operação do processador.
Esta é uma pilha LIFO implementada da mesma forma que a anterior. A única diferença é que é usada para guardar endereços de retorno de subrotinas em vez de operandos de instruções.
A ALU efectua cálculos aritméticos e lógicos em pares de elementos. Um dos elementos deste par é o registo do topo da pilha, que guarda o elemento mais alto da pilha de dados usada pelo programador. Assim, o elemento de topo da pilha de dados é realmente o segundo elemento da pilha, pela forma como a pilha é vista pelo programador, enquanto que o elemento de topo da pilha para o programador é mantido num registo na ALU. Este esquema permite usar uma memória de uma entrada para a pilha de dados, possibilitando operações com os dois elementos de topo da pilha.
O PC guarda o endereço da próxima instrução a ser executada. Pode ser lido a partir do bus de dados para implementar saltos ou pode ser incrementado para obter, sequencialmente, a próxima instrução da memória do programa.
A memória do programa é constituída por um Registo de Endereço de Memória e por um bloco de memória de acesso aleatório. Para aceder à memória, é colocado no Registo de Endereço de Memória o endereço a ser lido ou escrito. Em seguida, no próximo ciclo de relógio, a memória do programa é lida ou escrita a partir do bus de dados.
As máquinas de pilha manipulam os dados usando operações em notação posfixa. Nestas operações os operandos surgem antes dos operadores. Por exemplo, uma expressão em notação infixa é representada da seguinte forma:
(12+45) * 98
Nesta expressão é necessário usar parêntesis para forçar que a adição seja efectuada antes da multiplicação. Mesmo em expressões sem parêntesis está implícita uma precedência de operadores. No exemplo anterior a multiplicação tinha sido efectuada antes da soma.
A expressão anterior, em notação posfixa, é representada da seguinte forma:
98 12 45 + *
Em notação posfixa, o operador actua sobre os mais recentes operandos e usa implicitamente uma pilha para avaliação das expressões. Os números 98, 12 e 45 são colocados num pilha. Então o operador + actua sobre os dois elementos de topo da pilha (45 e 12) obtendo o resultado 57, que é colocado na pilha em substituição destes dois elementos. De seguida, o operador * actua sobre os dois novos elementos de topo da pilha (57 e 98) colocando o valor 5586 na pilha.
Para perceber como as máquinas de pilha efectuam operações aritméticas e lógicas olhemos para o exemplo da soma de dois números.
Os elementos a somar (N1 e N2) encontram-se no topo da pilha. Estes valores são obtidos (POP) e somados, obtendo N3, que é colocado na pilha (PUSH). Sobre o ponto de vista da implementação, isto era conseguido obtendo o valor que estava no topo da pilha de dados, POP(PD), obtendo N2 e adicionando este valor ao Registo de Topo da Pilha, que contém o valor de N1. O resultado é colocado no Registo de Topo da Pilha, deixando N3 no topo da pilha como é vista pelo programador.
O elemento que está na pilha de dados, que é obtido por POP(PD), é na realidade o segundo elemento do topo da pilha de dados como é vista pelo programador, mas é o topo da pilha implementada em hardware. Esta operação POP(PD) é consistente com a noção de Registo de Topo da Pilha, como um registo visto pelo programador. Note-se que ao manter o Registo de Topo da Pilha como um buffer de 1 elemento da pilha, um POP de N2 e subsequente PUSH de N3 foram eliminados.
Um dos problemas associado com as máquinas de pilha puras é que elas são apenas capazes de aceder ao dois elementos de topo da pilha para operações aritméticas e lógicas. Assim, algumas instruções extra têm de ser usadas para preparar os operandos das operações a realizar. No entanto, algumas máquinas baseadas em registos também perdem um largo número de instruções em mudanças de registos para preparar os operandos.
Mesmo que todas as operações aritméticas e lógicas sejam efectuadas com
os elementos que se encontram na pilha, tem de existir alguma forma de escrever informação na pilha antes de se realizarem as operações. Esta
máquina de pilha usa um modelo simples de leitura e escrita da memória. Assim,
apenas existe uma única instrução de leitura e uma única instrução de
escrita.
Como as instruções não têm operandos, o endereço da memória é obtido da
pilha. Isto facilita o acesso a estruturas de dados, uma vez que que a pilha
pode ser usada para guardar um ponteiro que indexe um vector de elementos. Uma
vez que a memória tem de ser acedida uma vez para a instrução e outra para os
dados, estas instruções demoram dois ciclos a executar.
É necessário que exista uma forma de colocar um valor constante na pilha. Esta instrução requer uma palavra para especificar a operação e outra para indicar o valor a ser colocado no topo da pilha. Por esta razão demora dois ciclos a executar, um para a instrução e outro para o elemento de dados.
A execução de instruções numa máquina de pilha envolve uma típica sequência de obtenção de instruções, descodificação de instruções e execução das instruções.
O PC é o registo que mantém um ponteiro para a próxima instrução a ser executada. Depois de obter uma instrução, o PC é automaticamente incrementado para a próxima instrução em memória. No caso dum salto ou chamada a uma subrotina, o PC é gravado com o novo valor para efectuar o salto.
De forma a tomar decisões a máquina deve possuir algum método de salto condicional. Esta máquina usa um método muito simples. Um salto é tomado se o elemento de topo da pilha for igual a zero. Esta abordagem elimina a necessidade de código condicional, permitindo no entanto a implementação de todas as estruturas de controlo de fluxo.
Como existe uma pilha dedicada aos endereços de retorno, a chamada a
subrotinas requer simplesmente que se coloque o PC actual na pilha de endereços
de retorno e guardar o novo valor no PC. Nesta máquina genérica assume-se que
o endereço da subrotina é colocado como um campo da instrução e ignora-se o
método pelo qual o campo do endereço é extraído da instrução. As várias
implementações de máquinas de pilha oferecem um leque de métodos para
atingir este objectivo com bastante eficiência.
Para efectuar um retorno de uma subrotina basta obter o endereço do topo da
pilha de endereços de retorno e colocar este valor no PC. Uma vez que os dados
são mantidos na pilha de dados, a instrução de retorno não tem de manipular
ponteiros ou localizações de memória.
Instruções em hardware traduzem-se normalmente num desempenho superior. O
custo para esta melhoria da performance é uma crescente complexidade do sistema
no desenho dos circuitos de descodificação e um elevado risco de ter de
proceder a um total redesenho do controlo lógico se existir alguma alteração
no conjunto de instruções.
Nas máquinas de pilha o formato das instruções é extremamente simples e a
normal explosão combinatória de operandos e tipos está completamente ausente.
Assim o desenvolvimento em hardware de uma máquina de pilha é relativamente
simples.
Se um máquina de pilha tiver um comprimento de palavra de 16 bits ou superior,
o tamanho da palavra é enorme em relação aos poucos bits que são
necessários para especificar as operações possíveis. As máquinas de pilha
em hardware costumam normalmente aproveitar esta situação usando formatos de
instruções pré-descodificados, simplificando ainda mais o hardware de
controlo e aumentando a flexibilidade. Isto permite combinar várias
instruções independentes numa única instrução.
Apesar de 16 bits parecerem um desperdício, o uso de um tamanho fixo de
instrução simplifica o hardware de descodificação e permite que uma chamada
a uma subrotina seja codificada com o mesmo tamanho de palavra que as outras
instruções.
Com todos os benefícios das instruções em hardware nas máquinas de pilha,
poderia parecer que as instruções em microcódigo nunca seriam usadas. No
entanto, existem diversas vantagens em usar um esquema de implementação de
instruções em microcódigo.
A maior vantagem é a flexibilidade. Como a maioria das combinações de bits
numa implementação em hardware não são usadas, uma implementação em
microcódigo pode usar menos bits para especificar as mesmas instruções,
incluindo um conjunto de instruções optimizadas que efectuam uma sequência de
operações na pilha. Isto deixa em aberto a possibilidade de existirem opcodes
definidos pelo utilizador na arquitectura. Uma implementação em microcódigo
pode ter várias instruções complexas, impossíveis ou extremamente difíceis
de conseguir em hardware.
Um aspecto a ter em conta em aplicações de tempo real é como o processador consegue lidar com interrupções e mudanças de tarefa.
As interrupções são causadas por eventos excepcionais, como overflow da
pilha, ou por pedidos do serviço de I/O. Ambos requerem uma rápida resolução
sem perturbar o fluxo da tarefa corrente.
Interrupções overflow/underflow da pilha, são de longe o condição
excepcional mais frequente numa máquina de pilha. Ocorrem quando a capacidade
da memória da pilha em hardware é excedida pelo programa. Existem várias
respostas possíveis ao problema: ignorar o overflow e deixar o programa
estourar, parar o programa com um erro fatal de execução ou copiar uma
porção da pilha para a memória do programa para permitir que a execução do
programa continue. A última alternativa proporciona uma elevada flexibilidade
mas, em muitos ambientes, um erro de execução pode ser aceitável e mais
simples de executar.
I/O é uma interrupção potencialmente frequente que tem de ser tratada
rapidamente em tarefas de tempo real. Normalmente estas interrupções não
requerem muito processamento nem armazenamento temporário. Por esta razão as
máquinas de pilha tratam estas interrupções como chamadas a subrotinas
geradas pelo hardware.
Estas chamadas a subrotinas colocam valores na pilha, efectuam os seus cálculos
e em seguida retornam à execução do programa interrompido. A única
condição é que a interrupção não deixe "lixo" na pilha.
As interrupções são menos pesadas nas máquinas de pilha porque não existe a
necessidade de guardar registos uma vez que a pilha aloca automaticamente
espaço de armazenamento, não existem condições de salto a guardar uma vez
que estas são mantidas como dados na pilha e a maioria das máquinas de pilha
não tem pipeline, não existindo o custo de guardar a pipeline no momento da
interrupção.
As mudanças de tarefa ocorrem quando o processador troca entre programas
para dar a aparência de execução simultânea de programas. O estado do
programa que é parado numa mudança de tarefa tem de ser preservado para que
possa ser continuado mais tarde. O estado do programa que é começado tem de
ser correctamente colocado antes de se começar a sua execução.
A forma tradicional é usar um temporizador e trocar de tarefa a cada incremento
do temporizador, por vezes sujeito a prioridades e algoritmos de escalonamento.
Num processador simples esta situação pode levar a um enorme overhead para
gravar as pilhas para memória e voltar a ler a memória em cada mudança de
tarefa. Isto pode ser combatido com tarefas pequenas que usem pouco espaço na
pilha ou usar vários ponteiros para a pilha para várias tarefas dentro do
mesmo espaço de memória da pilha em hardware.