5.1

5.1 Projetando Máquinas de Registradores

Para projetar uma máquina de registradores, devemos projetar seus caminhos de dados (registradores e operações) e o controlador que sequencia essas operações. Para ilustrar o projeto de uma máquina de registradores simples, vamos examinar o Algoritmo de Euclides, que é usado para calcular o máximo divisor comum (MDC) de dois inteiros. Como vimos na seção anterior, o Algoritmo de Euclides pode ser executado por um processo iterativo, conforme especificado pela seguinte função:

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

Uma máquina para executar este algoritmo deve acompanhar dois números, $a$ e $b$, então vamos assumir que esses números são armazenados em dois registradores com esses nomes. As operações básicas necessárias são testar se o conteúdo do registrador b é zero e calcular o resto do conteúdo do registrador a dividido pelo conteúdo do registrador b.

A operação de resto é um processo complexo, mas vamos assumir por enquanto que temos um dispositivo primitivo que calcula restos. Em cada ciclo do algoritmo MDC, o conteúdo do registrador a deve ser substituído pelo conteúdo do registrador b, e o conteúdo de b deve ser substituído pelo resto do conteúdo antigo de a dividido pelo conteúdo antigo de b. Seria conveniente se essas substituições pudessem ser feitas simultaneamente, mas em nosso modelo de máquinas de registradores vamos assumir que apenas um registrador pode receber um novo valor a cada passo. Para realizar as substituições, nossa máquina usará um terceiro registrador "temporário", que chamaremos de t. (Primeiro o resto será colocado em t, depois o conteúdo de b será colocado em a, e finalmente o resto armazenado em t será colocado em b.)

Podemos ilustrar os registradores e operações necessários para esta máquina usando o diagrama de caminho de dados mostrado na Figura 5.1. Neste diagrama, os registradores (a, b e t) são representados por retângulos. Cada forma de atribuir um valor a um registrador é indicada por uma seta com um botão—desenhado como $\otimes$—atrás da cabeça, apontando da fonte de dados para o registrador. Quando pressionado, o botão permite que o valor na fonte "flua" para o registrador designado. O rótulo ao lado de cada botão é o nome que usaremos para nos referir ao botão. Os nomes são arbitrários e podem ser escolhidos para ter valor mnemônico (por exemplo, a<-b denota pressionar o botão que atribui o conteúdo do registrador b ao registrador a). A fonte de dados para um registrador pode ser outro registrador (como na atribuição a<-b), um resultado de operação (como na atribuição t<-r), ou uma constante (um valor embutido que não pode ser alterado, representado em um diagrama de caminho de dados por um triângulo contendo a constante).

Uma operação que calcula um valor a partir de constantes e do conteúdo de registradores é representada em um diagrama de caminho de dados por um trapézio contendo um nome para a operação. Por exemplo, a caixa marcada rem na Figura 5.1 representa uma operação que calcula o resto do conteúdo dos registradores a e b aos quais está conectada. Setas (sem botões) apontam dos registradores de entrada e constantes para a caixa, e setas conectam o valor de saída da operação aos registradores. Um teste é representado por um círculo contendo um nome para o teste. Por exemplo, nossa máquina MDC tem uma operação que testa se o conteúdo do registrador b é zero. Um teste também tem setas de seus registradores de entrada e constantes, mas não tem setas de saída; seu valor é usado pelo controlador em vez dos caminhos de dados. No geral, o diagrama de caminho de dados mostra os registradores e operações que são necessários para a máquina e como eles devem ser conectados. Se visualizarmos as setas como fios e os botões $\otimes$ como interruptores, o diagrama de caminho de dados é muito parecido com o diagrama de fiação de uma máquina que poderia ser construída a partir de componentes elétricos.

Figura 5.1: Caminhos de dados para uma máquina MDC.

Para que os caminhos de dados realmente calculem MDCs, os botões devem ser pressionados na sequência correta. Descreveremos essa sequência em termos de um diagrama de controlador, conforme ilustrado na Figura 5.2. Os elementos do diagrama de controlador indicam como os componentes do caminho de dados devem ser operados. As caixas retangulares no diagrama de controlador identificam os botões do caminho de dados a serem pressionados, e as setas descrevem o sequenciamento de um passo para o próximo. O diamante no diagrama representa uma decisão. Uma das duas setas de sequenciamento será seguida, dependendo do valor do teste do caminho de dados identificado no diamante. Podemos interpretar o controlador em termos de uma analogia física: pense no diagrama como um labirinto no qual uma bola de gude está rolando. Quando a bola de gude rola para dentro de uma caixa, ela pressiona o botão do caminho de dados que é nomeado pela caixa. Quando a bola de gude rola para dentro de um nó de decisão (como o teste para b $= 0$), ela sai do nó pelo caminho determinado pelo resultado do teste indicado. Tomados em conjunto, os caminhos de dados e o controlador descrevem completamente uma máquina para calcular MDCs. Iniciamos o controlador (a bola de gude rolando) no lugar marcado start, depois de colocar números nos registradores a e b. Quando o controlador atinge done, encontraremos o valor do MDC no registrador a.

Figura 5.2: Controlador para uma máquina MDC.

Exercício 5.1

Projete uma máquina de registradores para calcular fatoriais usando o algoritmo iterativo especificado pela seguinte função. Desenhe diagramas de caminho de dados e controlador para esta máquina.

function factorial(n) {
    function iter(product, counter) {
        return counter > n
               ? product
               : iter(counter * product,
                      counter + 1);
   }
   return iter(1, 1);
}

Solução:

(Solução do usuário GitHub escolmebartlebooth)

Em factorial(n), a função iter(product, counter) é inicializada com os argumentos (1, 1) e executa até counter > n, momento em que o produto é retornado. Diferentemente de gcd(a, b), a máquina de registradores não precisa de um registrador temporário, assumindo que a ordem correta de atribuição de registradores seja seguida.

Para o caminho de dados, vemos três registradores: product, counter e n. Existem duas operações: multiply e plus com duas atribuições. Existe um teste: greater than.

Para o controlador, começamos preenchendo os três registradores com o fatorial desejado n e o valor 1 (inicializando product e counter). A função iter executa e testa se counter > n. Se counter <= n, então product é atualizado para product * counter, seguido por counter sendo atualizado para counter + 1 e o processo é repetido até counter > n. Uma vez que counter é > n, o produto é factorial(n) e pode ser retornado.