Máquina de uma instrução

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Wikitext.svg
Esta página ou seção precisa ser wikificada (desde novembro de 2014).
Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas.
Searchtool.svg
Esta página foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa (desde novembro de 2014). Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a consistência e o rigor deste artigo.

OISC do inglês "One instruction set computer", é uma máquina que possui apenas uma instrução, o que elimina a possibilidade de ter uma linguagem de máquina, ou seja,opcode. OISC pode ser comparada tanto um computador universal quanto uma máquina tradicional que trabalha com mais de uma instrução, então sendo assim pode realizar as mesmas tarefas do que uma máquina padrão. Existe uma classe de computadores universais com uma instrução baseada na manipulacão de bits. O modelo de memória OISC possui a mesma estrutura de memória usada em computadores tradicionais. Máquinas e aparelhos de manipulacão de bits são equivalentes aos computadores tradicionais.[1][2]

O objetivo da implementação de OISC foi inicialmente para ajudar na arquitetura de um computador de ensino e também utilizada como modelo computacional na pesquisa de computação estrutural.[1][2]

Arquitetura de Máquina[editar | editar código-fonte]

Atualmente OISCs são conhecidas por serem basicamente divididas em três grandes categorias:

  • Transport Triggered Architecture Machines.
  • Bit Manipulating Machines.
  • Arithmetic Based Turing-Complete Machines.

Transport Triggered Architecture Machines (TTA) tem como consequência a computação para transporte de dados. Normalmente alguns registros de memória com espaço de endereçamento em comum, executam uma operação quando a instrução faz referência a eles. Por exemplo, utilizando uma cópia de instruções de memória para memória em uma OISC, isto é feito pelas portas de troca de estado, que executam o cálculo e o ponteiro da instrução desvia para onde será escrito.

Bit Manipulating Machines é a parte mais simples, a cópia é chamada de BitBitJump, copia de um bit da memória e passa a execução incondicional para o endereço especificado por um dos operandos da instrução. Este processo pode ser considerado com computação universal(sendo capaz de executar qualquer algoritmo e de interpretar qualquer outra máquina universal). A cópia condicional de bits pode modificar o código que será posteriormente executado. Uma outra máquina, chamada de computador Toga, inverte o bit e passa a execução condicionalmente, dependendo do resultado da inversão.Ainda uma outra máquina que opera bits, semelhante ao BitBitJump, copia vários bits ao mesmo tempo. Neste caso o problema da universalidade computacional é resolvido, mantendo tabelas de pulos predefinidos na memória.

Arithmetic Based Turing-Complete Machines, esta usa uma operação aritmética e um pulo condicional, diferente das duas categorias anteriores, que são classificadas como comuputadores universais, esta é universal e também de Turing-Compete, cujo tem o mesmo poder de processamento de uma Máquina de Turing em sua representação abstrata. A instrução opera sobre número inteiros, que também podem ser endereços na memória. Atualmente existem várias OISCs conhecidas nesta categoria, com base em diferentes operações aritméticas como, adição (Addleq), decremento (DJN), incremento (Pleq) e subtração (Subleq). Esta é a mais antiga, mais popular e sem dúvida a mais eficiente.

Tipos de Instruções[editar | editar código-fonte]

Opções mais utilizadas para uma única instrução:

  • Subtrai e desvia se for menor ou igual a zero.
  • Subtrai e desvia se for negativo.
  • Subtrai e inverte, pula se pegar emprestado.
  • Mover(Usado na arquitetura de transporte disparado).
  • Subtrai e desvia se não for zero(SBNZ, a,b,c, destino).

Apenas uma destas instruções é utilizada em uma determinada implementação, sendo assim não há a necessidade de se ter um opcode para identificar qual instrução irá executar. A escolha da instrução não tem nenhuma influência com relação ao projeto da máquina, uma OISC é normalmente chamada após usar uma instrução, por exemplo(na OISC SBN,[1] SUBLEQ,[2] etc...) Cada uma das instruções acima pode ser utilizada para construir uma Máquina de Turing OISC.

Este artigo apresenta apenas instruções baseadas em subtração, as que não são de transporte disparado não fazem parte. No entanto é possível construir uma Máquina de Turing utilizando uma instrução com base em outras operações aritméticas, como a adição. Por exemplo, uma variação conhecida como DLN (Diminuir e pular se não for igual a zero) tem apenas dois operandos e usa decremento como operação de base.

Subtrai e desvia se não for igual a zero[editar | editar código-fonte]

A instrução SBNZ a, b, c, d, subtrai o conteúdo de um endereço a partir do conteúdo que está no endereço b e armazena o resultado no endereço c, em seguida de o resultado não for igual a zero, o controle transfere para resolver d e se o resultado for igual a zero a execução prossegue para a próxima instrução que está na sequência.[2]

Subtrai e desvia se for menor ou igual a zero[editar | editar código-fonte]

Subleq, subtrai o conteúdo que está no endereço a, do conteúdo que está no endereço b e armazena o resultado no endereço b e em seguida se o resultado não for positivo, o controle transfere para o endereço c, se for positivo a execução prossegue para próxima instrução que está na sequência.

Pseudocódigo:

    Subleq a, b, c;
    Mem[b] = Mem[b] - Mem [a];
    If (Mem[b] ≤ 0) goto c;

O desvio condicional, usa apenas dois operandos por instrução, mas para efetuar algumas outras operações lógicas, são necessárias mais instruções.

Instruções Sintetizadas[editar | editar código-fonte]

É possível sintetizar muitas instruções de ordem superior usando apenas a instrução subleq.[2] :9-10

Desvio Incondicional:

    JMP c == subleq Z, Z, c

A adição pode ser realizada, com uma ou mais subtrações, sem o uso do desvio condicional. As seguintes instruções informadas abaixo resultam no conteúdo que está no endereço a que é adicionado ao conteúdo que está no endereço b.

    ADD a, b == subleq a, Z
             == subleq Z, b
             == subleq Z, Z

A primeira instrução subtrai o conteúdo do endereço a do conteúdo que está no endereço Z (que é zero) e armazena o resultado no endereço Z. A segunda instrução subtrai este resultado de b e armazena em b, este resultado agora é a soma dos conteúdos originais de a e b. A terceira instrução repõe o valor zero em Z.

Uma instrução que faz a cópia pode ser implementada de forma semelhante, as próximas instruções informadas abaixo, resultam no conteúdo do endereço b que será substituído pelo que está no endereço a, novamente assumindo que o conteúdo do endereço Z é zero.

    MOV a, b == subleq b, b
             == subleq a, Z
             == subleq Z, b
             == subleq Z, Z

Intrução com condição de desvio se for zero.

    BEQ b, c == subleq b, Z, L1
             == subleq Z, Z, OUT
             L1 subleq Z, Z
                subleq Z, b, c
            OUT:...

Subleq2, pode ser usado para sintetizar instruções mais complexas, mesmo que precise de mais operações para uma dada tarefa. No máximo dez instruções subleq2 para que se possa inverter todos os bits em um byte.

    NOT a == subleq2 tmp; tmp = 0 (tmp = temporary register)
             subleq2 tmp
             subleq2 minus_one; acc = -1
             subleq2 a; a' = a + 1
             subleq2 Z; Z  = Z - 1
             subleq2 tmp; tmp = a + 1
             subleq2 a; a' = 0
             subleq2 tmp; load tmp into acc
             subleq2 a; a'  = -a -1 (= ~a)
             subleq2 Z; set Z back to 0

Emulação[editar | editar código-fonte]

O programa a seguir escrito em Pseudocódigo emula a execução de subleq em OISC:

integer memory, program_counter a, b, c,
program_counter = 0
while (program counter >= 0):
   a = memory [program_counter]
   b = memory [program_counter + 1]
   c = memory[program_counter + 2]
   if (a < 0 or b < 0):
        program_counter = -1
   else:
       memory[b] = memory[b] - memory[a]
       if (memory[b] > 0):
           program_counter = program_counter + 3
       else:
           program_counter = c

Este programa, assume que a memória é indexada por números inteiros e positivos. Consequentemente para uma instrução subleq (a, b, c) o programa interpreta a< 0, b< 0, ou executa um desvio para c< 0 como uma condição de parada. Intérpretes similares escritos em uma linguagem baseada em subleq, ou seja, auto-intérpretes, que podem utilizar códigos auto-modificados conforme o permitido pela natureza da instrução.

Compilação[editar | editar código-fonte]

Há um compilador chamado Higher Subleq escrito por Oleg Mazonka que compila um programa simplificado em C em um código Subleq.[3]

Subtrai e desvia se for negativo[editar | editar código-fonte]

A intrução subneg também chamada de SBN é definida de forma semelhante a subleq:[1] :41,51-52

           subneg a, b, c; Mem[b] = Mem[b] - Mem[a];
                           if (Mem[b] < 0) goto c

O desvio condicional pode ser suprimido ou configurado como o terceiro operando igual ao endereço da próxima instrução. Se o terceiro operando não está escrito, a supressão está implícita.

Intruções Sintetizadas[editar | editar código-fonte]

É possível sintetizar vários tipos de instruções de ordem superior, usando apenas a instrução subneg. Para simplificar, uma situação é mostrada abaixo para ilustrar a diferença entre subleq e subneg.

Desvio Incondicional:[1] :88-89

    JMP c ==    subneg POS, Z, c

...

c: subneg Z, Z

Onde, Z e POS são posições previamente definidas para conter zero e um número inteiro positivo, respectivamente:

O desvio condicional só é garantido se o Z contém inicialmente o número zero, ou um valor menor e inteiro armazenado em POS. Uma instrução de acompanhamento é necessária para limpar Z depois do desvio, assumindo que o conteúdo de Z deve ser mantido como zero.

Subtrai e inverte, pula se pegar emprestado[editar | editar código-fonte]

O acumulador é subtraído da posição de memória, e a próxima instrução é ignorada se a posição de memória for menor do que o acumulador, o resultado é armazenado em ambos, no acumulador e no endereço de memória. O Program Counter é mapeado para endereço de memória 0. O acumulador é mapeado para endereço de memmória 1.[1]

Exemplo[editar | editar código-fonte]

Para definir o valor de x, y menos z:

  1. Em primeiro lugar, move Z para endereço de destino x
    RSSB temp # Três instruções necessárias para limpar o acc, temporário
    RSSB temp
    RSSB temp
    RSSB x    # Duas instruções limpam acc, x, desde que acc já esteja limpo
    RSSB x
    RSSB y    # Coloca y no acc: não emprestar
    RSSB temp # Guarda - y em acc, temp: sempre pedir emprestado e pular
    RSSB temp # Pulados
    RSSB x    # Guarda y em x, acc
  1. Em segundo lugar executa a operação
    RSSB temp # Três instruções necessárias para limpar o acc, temporário
    RSSB temp
    RSSB temp
    RSSB z    # Carrega z
    RSSB x    # x = y - z

Transport Triggered Architecture Machines[editar | editar código-fonte]

Transport Triggered Architecture Machines, utiliza apenas mover instrução, foi originalmente chamado de "movimento de máquina". Esta instrução move o conteúdo de um endereço de memória para outro endereço de memória.[1] :42[4]

    move a to b;
    Mem[b]:= Mem [a]
    As vezes escrito como:
    ab;
    Mem[b]:= Mem[a]

A aritmética é realizada através de uma Unidade lógica e aritmética que possui memória mapeada e pulos são realizados com "Program Counter"

Processador capaz de executar instruções subleq[editar | editar código-fonte]

-Bibliotecas para programas escritos em Assembly, SUBLEQ e um programa para demontração destes. -Intérprete subleq escrito em C. -Intérprete Jsubleq escrito em javascript.

CPU[editar | editar código-fonte]

[5]

A versão atual do Logisim[6] é necessária para simular a CPU. Instruções de simulação são apresentadas abaixo:

Há três "bus" principais na CPU:

  A bus: contém o endereço da localização da memória atual.
  B bus: contém a saída da ALU.
  D bus: contém os dados lidos da memória.

A CPU tem seis sinais de controle:

  MAR: registro de endereços da memória devem ser atualizados com o valor do barramento D no fim deste clico.
  PC: Program counter deve ser atualizado no final deste ciclo.
  JMP: o PC deve ser carregado com o valor do barramento D no fim deste ciclo se a flag LEQ estiver sido definida pela ALU, senão o PC é incrementado se JMP ou LEQ forem falsos.
  RD: o valor do MAR deve ser carregado para o A bus se a RD for falsa ele é carregado com o valor do PC.
  WR: o valor do B bus  deve ser armazenado na memória no final do ciclo e o valor da flag LEQ deverá ser atualizada.
  A: os sinais de que o operando A está atualmente em D bus, então o registro de A deve ser atualizado no final deste ciclo.

Estes sinais são controlados por um programa com cinco micro-instruções que funciona num ciclo contínuo. Os sinais habilitados por cada uma destas micro-instruções são:

  1. MAR,PC: carrega Mem[PC](endereço de um operando) em MAR e incrementa PC.
  2. RD, A: carrega Mem[MAR] no registrador A.
  3. MAR, PC: carrega Mem[PC](endereço do operando B) em MAR e incrementa o PC.
  4.RD, WR: carrega Mem[MAR]para B bus e em seguida escreve o valor do B bus (o valor do D bus menos o valor do registrador A) em MEm[MAR].
  5. PC, JMP: se o flag LEQ está definido(o resultado B-A for menor ou igual a zero) em seguida define o PC para Mem[PC](o operando C) ou seja, salta para C senão incrementa o PC.

Input/Output é realizada através de memória mapeada I/O como o driver de I/O mapeado para o endereço 0xffffffff (-1). Se o sinal de A está ativado então lê a partir do endereço e retorna a negação do próximo carácter de entrada. Se o sinal de A não for habilitado então o valor de 0xffffffff é retornado. Escreve neste endereço e imprime o carácter obtido realizando um NOT bit a bit no valor do B bus. Este comportamento permite que as seguintes intruções de I/O sejam realizadas:

  • (-1) X: adiciona o carácter de entrada para X(X -= - input)
  • X (-1): saída do carácter em X (subtrai o X de 0xffffffff e em seguida realiza um NOT X, e resulta o valor original de X).

Pula para o endereço 0xffffffff (-1) desativa o sinal de clock e trava a cpu.

Simulação

Simulando a CPU:

 1. Abra cpu.circ[7] no Logisim.[6]
 2. Aumentar a velocidade da simulação: Marcar frequência 1024 Hz.
 3. Carregar o programa: para executar o programa demo, certifique-se de ter executado no diretório o projeto raiz, clique no elemento identificado com RAM> Load>...Image.../Image.hex
 4. Iniciar a simulação: simule> marcar ativado
 5. Certifique que está utilizando uma ferramenta de mão e selecione o componente "input" usando a ferramenta.
 6. Interagir com o programa como faria com aplicativo baseado em console.
 7. Se a linha do clock ficar azul, significa que o programa foi interrompido.
 8. Para parar a máquina, desmarque a opção> simule> marcar ativado e em seguida pressione o botão "reset" rotulado como "R".
 9. Repita a etapa 3 se for necessário.

Bibliotecas/DEMO[editar | editar código-fonte]

Bibliotecas escritas em assembly SUBLEQ, como sqasm[8] estão disponíveis.

Oferecem várias funções comuns:

  • getint (lê um número inteiro de entrada).
  • gets (lê uma string de entrada).
  • putint (escreve um inteiro de saída).
  • puts (escreve uma sequência de caracteres de saída).

Vários procedimentos também estão disponíveis:

  • bubblesort(ordena uma sequência de carácteres).
  • calc(realiza uma determinada operação em dois inteiros).
  • factorial(calcula o fatorial de um número inteiro positivo).
  • primes(gera e imprime uma lista de números primos).

Referências

  1. a b c d e f g Gilreath, William F.; Laplante, Phillip A. (2003). Computer Architecture: A Minimalist Perspective. [S.l.: s.n.] ISBN 978-1-4020-7416-5  Intended for researchers, computer system engineers, computational theorists and students, this book provides an in-depth examination of various OISCs, including SBN and MOVE. It attributes SBN to W. L. van der Poel (1956).
  2. a b c d e Nürnberg, Peter J.; Wiil, Uffe K.; Hicks, David L. (setembro de 2003), «A Grand Unified Theory for Structural Computing», Metainformatics: International Symposium, MIS 2003, ISBN 978-3-540-22010-7, Graz, Austria, pp. 1–16  This research paper focusses entirely on a SUBLEQ OISC and its associated assembly language, using the name SUBLEQ for "both the instruction and any language based upon it".
  3. Oleg Mazonka A Simple Multi-Processor Computer Based on Subleq
  4. Jones, Douglas W. (junho de 1988). «The Ultimate RISC». New York: ACM. ACM SIGARCH Computer Architecture News. 16 (3): 48–55. doi:10.1145/48675.48683. Consultado em 4 de outubro de 2010  "Reduced instruction set computer architectures have attracted considerable interest since 1980. The ultimate RISC architecture presented here is an extreme yet simple illustration of such an architecture. It has only one instruction, move memory to memory, yet it is useful."
  5. [1] https://raw.githubusercontent.com/davidar/subleq/master/logisim/cpu.png
  6. a b [2] http://cburch.com/logisim/
  7. [https://github.com/davidar/subleq/blob/master/logisim/cpu.circ [https://github.com/davidar/subleq/blob/master/logisim/cpu.circ
  8. [3] http://mazonka.com/subleq/

Ver também[editar | editar código-fonte]