Uma CPU em miniatura: o Little Man Computer

O programa ocupa as mesmas cem caixas de correio que os números com que trabalha. Ao avançar passo a passo, vês cada movimento do ciclo de busca, descodificação e execução: as leituras a azul, as escritas a âmbar e a próxima instrução com um contorno roxo.

Exemplo resolvido — Uma CPU em miniatura: o Little Man Computer

Instruções executadas	65
F: buscas de instruções, 1 leitura por busca	65
R: leituras de operandos por LDA, ADD e SUB	30
W: escritas por STA	16
Total de acessos às caixas	111
Percentagem de acessos para ler o programa	58,6%
Saída	42
Como terminou a execução	em HLT

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Uma CPU em miniatura: o Little Man Computer

O ciclo de busca, descodificação e execução é a sequência que um processador segue para cada instrução. Na busca, copia PC para MAR, lê a caixa indicada para MDR, copia esse valor para CIR e soma 1 a PC. Na descodificação, separa a instrução numa operação (o algarismo das centenas) e num endereço (os dois últimos algarismos). As exceções são 901, 902 e 000: códigos completos de INP, OUT e HLT, que não indicam nenhuma caixa. Na execução, realiza a operação, que pode exigir a leitura ou a escrita de outra caixa através de MAR e MDR.

O que significa cada símbolo

PC: contador de programa: o endereço da próxima instrução a ir buscar
MAR: registo de endereços de memória: o endereço da caixa que vai ser lida ou escrita
MDR: registo de dados de memória: o valor acabado de ler ou prestes a ser escrito
CIR: registo da instrução corrente: a instrução em execução
ACC: acumulador: onde ADD, SUB e LDA colocam o resultado

Pressupõe: O Little Man Computer de Stuart Madnick (MIT, 1965) não define o que acontece quando SUB produz um valor negativo ou ADD ultrapassa 999. Nesta máquina, o acumulador admite valores de −999 a 999, pelo que BRP verifica o sinal. Um resultado fora desse intervalo provoca um transbordo e interrompe a execução, em vez de dar a volta ao intervalo. Os simuladores escolares diferem neste ponto. Um programa cujo acumulador se mantenha entre 0 e 999 executa-se da mesma forma em todos eles.

A máquina não distingue um número de uma instrução 🖖

Carrega em Dados como código. O programa contém LDA n e OUT para apresentar 105 uma vez, mas quem o escreveu esqueceu-se de HLT. PC avança então para a caixa 02, onde está guardado o valor 105, e a máquina lê-o como qualquer outra instrução: 105 corresponde a ADD 05, e a caixa 05 contém 20. A linha DAT seguinte contém 902, que corresponde a OUT, pelo que aparece 125 na saída. A seguir vem 0, que corresponde a HLT. Nada numa caixa indica se o seu conteúdo é uma instrução ou um número. Se PC apontar para ela, o conteúdo é uma instrução; se LDA, ADD ou SUB indicar o seu endereço, é um dado. A primeira instrução leu este 105 como número, e a terceira executou-o. É esta a ideia de programa armazenado, posta em prática pela primeira vez no Manchester Baby, em junho de 1948.

Para ler o elemento seguinte da lista, este programa reescreve-se 🖖

Carrega em Somar uma lista e observa a caixa 00. Começa com 517, ou seja, LDA 17, que carrega o primeiro número da lista. Uma instrução do LMC inclui o próprio endereço, e a máquina não dispõe de um registo de onde a instrução possa obter esse endereço. Por isso, não há forma de dizer «a caixa a seguir à que acabei de ler». Escrever LDA 17, ADD 18, ADD 19 e assim por diante serve para esta lista, mas deixa de servir se ela crescer. Para somar com um único ciclo, seja qual for a contagem, o programa carrega a sua primeira instrução como número, soma-lhe 1 e volta a guardá-la. 517 passa a 518, que corresponde a LDA 18. As 5 passagens pelo ciclo escrevem na caixa 00 por 5 vezes. A última versão, LDA 22, nunca é executada, porque a contagem chega a zero antes disso. Os processadores reais podem obter um endereço a partir de um registo precisamente para percorrer uma lista sem alterar o próprio programa.

A maior parte das leituras da máquina serve para ler o próprio programa 🖖

Antes de fazer seja o que for, cada instrução custa 1 leitura de uma caixa: a busca. LDA, ADD e SUB leem mais 1 caixa; STA escreve em 1 caixa; os desvios, INP e OUT não acedem a nenhuma outra. Assim, em Multiplicar por adições, 6 × 7 exige 65 buscas, 30 leituras de operandos e 16 escritas. A leitura das instruções representa 58,6 % de todo o tráfego entre o processador e a memória. Considerando todos os pares de entradas cujo produto é, no máximo, 999, essa percentagem fica entre 57,2 % e 69,2 %. O programa e os dados percorrem o mesmo caminho até à mesma memória, um de cada vez. Na conferência que proferiu ao receber o Prémio Turing de 1977, John Backus chamou a esse caminho o gargalo de von Neumann.

Problema resolvido na íntegra

Porque é que 2 × 99 custa 801 instruções e 99 × 2 custa 25 4 passos
Seleciona 2 × 99, devagar e depois altera os valores de entrada para 99, 2. O resultado é 198 em ambos os casos. Conta as instruções executadas em cada caso, determina a fórmula e indica quanto custa, na ordem mais desfavorável, calcular um produto que caiba numa caixa de correio.

Abrir este problema na ferramenta
1. Antes do ciclo, há 2 INP e 2 STA: 4 instruções. O corpo do ciclo executa LDA b, BRZ, SUB one, STA b, LDA total, ADD a, STA total, BRA loop: 8 instruções por cada unidade de b.
  
  $INP, STA, INP, STA : 4 LDA, BRZ, SUB, STA, LDA, ADD, STA, BRA : 8$
2. Quando b chega a zero, o ciclo executa apenas LDA b e BRZ. Depois, LDA total, OUT e HLT terminam o programa: mais 5 instruções. O custo de uma execução é, portanto, 4 + 8b + 5 = 8b + 9. O valor de a nem sequer aparece na fórmula.
  
  $LDA, BRZ, LDA, OUT, HLT : 5 C (b) = 4 + 8 b + 5 = 8 b + 9$
3. Com b = 99, o custo é 8 × 99 + 9 = 801; com b = 2, é 25. A tabela de resultados apresenta 801 para a primeira ordem e 25 para a segunda.
  
  $C (99) = 8 \times 99 + 9 = 801 C (2) = 8 \times 2 + 9 = 25$
4. O maior produto que cabe numa caixa é 999. Com as entradas 1, 999, o ciclo repete-se 999 vezes: 8 001 instruções. Com 999, 1, executa-se uma vez: 17.
  
  $C (999) = 8001 C (1) = 173 1^{2} = 961 \leq 999 < 1024 = 3 2^{2}$
Resposta

8b + 9 instruções, sendo b a segunda entrada. Para obter o mesmo 999, uma ordem custa 8 001 instruções e a outra 17, cerca de 470 vezes menos. Se o programa começasse por comparar as entradas e usasse a menor para controlar o ciclo, o custo nunca ultrapassaria 8 × 31 + 9, acrescido do custo da comparação: num produto até 999, o menor fator é, no máximo, 31.

$C = 8 b + 9, min (a, b) \leq 31 \Rightarrow C \leq 8 \times 31 + 9 = 257$

Percurso de aprendizagem

Como um computador executa um programa

Referências (4)

Where the third insight's phrase comes from: the connecting tube between CPU and store, named the von Neumann bottleneck, and the remark that much of its traffic is not data but the names of data: John Backus, "Can programming be liberated from the von Neumann style? A functional style and its algebra of programs." Communications of the ACM 21(8), 613–641, August 1978. The 1977 ACM Turing Award Lecture.
The date the first insight gives for the stored-program idea first running: The University of Manchester, "How a 70-year-old 'Baby' changed the face of modern computing." News, 21 June 2018.
The machine itself: Madnick's 1965 design, the instruction codes, and the fact the page's assumes rests on, that a negative or over-999 result is left undefined: "Little man computer." Wikipedia, read 14 October 2026.
A school simulator's instruction table, with BRP described as branching when the accumulator is zero or positive, the sign convention this page follows: 101computing.net, "LMC Simulator."

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.