Computadora con un solo conjunto de instrucciones

Una computadora con un conjunto de instrucciones único ( OISC ), a veces denominada computadora con un conjunto de instrucciones reducido definitivo ( URISC ), es una máquina abstracta que utiliza solo una instrucción, lo que obvia la necesidad de un código de operación en lenguaje de máquina . ^{[1] [2] [3]} Con una elección juiciosa de la instrucción única y dados arbitrariamente muchos recursos, una OISC es capaz de ser una computadora universal de la misma manera que las computadoras tradicionales que tienen múltiples instrucciones. ^{[2] : 55} Las OISC se han recomendado como ayudas en la enseñanza de la arquitectura de computadoras ^{[1] : 327  [2] : 2} y se han utilizado como modelos computacionales en la investigación de computación estructural. ^[3] La primera computadora con nanotubos de carbono es una computadora con un conjunto de instrucciones único de 1 bit (y tiene solo 178 transistores). ^[4]

En un modelo Turing-completo , cada posición de memoria puede almacenar un número entero arbitrario y, según el modelo ^{[ aclaración necesaria ]}  , puede haber una cantidad arbitraria de posiciones. Las instrucciones en sí residen en la memoria como una secuencia de dichos números enteros.

Existe una clase de computadoras universales con una única instrucción basada en la manipulación de bits, como la copia o la inversión de bits . Dado que su modelo de memoria es finito, al igual que la estructura de memoria utilizada en las computadoras reales, esas máquinas de manipulación de bits son equivalentes a las computadoras reales en lugar de a las máquinas de Turing. ^[5]

Los OISC conocidos actualmente se pueden dividir en tres grandes categorías:

• Máquinas manipuladoras de bits
• Máquinas de arquitectura de transporte activadas
• Máquinas completas de Turing basadas en aritmética

Las máquinas manipuladoras de bits son la clase más simple.

La máquina FlipJump tiene una instrucción, a;b: cambia el bit a y luego salta a b. Es la OISC más primitiva, pero sigue siendo útil. Puede realizar cálculos matemáticos y lógicos, ramificaciones, punteros y llamadas a funciones con la ayuda de su biblioteca estándar.

Una máquina copiadora de bits, ^[5] denominada BitBitJump, copia un bit en memoria y pasa la ejecución incondicionalmente a la dirección especificada por uno de los operandos de la instrucción. Este proceso resulta ser capaz de computación universal (es decir, poder ejecutar cualquier algoritmo e interpretar cualquier otra máquina universal) porque la copia de bits puede modificar condicionalmente la dirección de copia que se ejecutará posteriormente.

Otra máquina, llamada Toga Computer, invierte un bit y pasa la ejecución condicionalmente dependiendo del resultado de la inversión. La única instrucción es TOGA(a,b) que significa TOG gle a y pasa a b si el resultado de la operación de cambio es verdadero.

De manera similar a BitBitJump, una máquina de copia de múltiples bits copia varios bits al mismo tiempo. El problema de la universalidad computacional se resuelve en este caso manteniendo tablas de salto predefinidas en la memoria. ^{[ Aclaración necesaria ]}

La arquitectura activada por transporte (TTA) es un diseño en el que el cálculo es un efecto secundario del transporte de datos. Por lo general, algunos registros de memoria (puertos de activación) dentro del espacio de direcciones común realizan una operación asignada cuando la instrucción hace referencia a ellos. Por ejemplo, en un OISC que utiliza una única instrucción de copia de memoria a memoria, esto se hace activando puertos que realizan operaciones aritméticas y saltos de puntero de instrucción cuando se escribe en ellos.

Las máquinas Turing-completas basadas en aritmética utilizan una operación aritmética y un salto condicional. Al igual que las dos computadoras universales anteriores, esta clase también es Turing-completa. La instrucción opera con números enteros que también pueden ser direcciones en la memoria.

Actualmente se conocen varios OISC de esta clase, basados ​​en diferentes operaciones aritméticas:

• adición (addleq, add y ramifica si es menor o igual a cero) ^[6]
• decremento (DJN, Decremento y rama ( Salto ) si no es cero) ^[7]
• incremento (P1eq, P lus 1 y ramificación si es igual a otro valor) ^[8]
• Resta (subleq, resta y ramifica si es menor o igual a cero) ^{[9] [10]}
• resta positiva cuando sea posible, de lo contrario ramificación (máquina aritmética) ^[11]

Las opciones comunes para la instrucción única son:

• Restar y ramificar si es menor o igual a cero
• Restar y ramificar si es negativo
• Restar si es positivo, de lo contrario, ramificación
• Resta inversa y omite si tomas prestado
• Mover (utilizado como parte de una arquitectura activada por transporte) ^[12]

• Restar y ramificar si no es cero (SBNZ a, b, c, destino)
• Cryptoleq (computación heterogénea cifrada y no cifrada)

Solo se utiliza una de estas instrucciones en una implementación determinada. Por lo tanto, no es necesario un código de operación para identificar qué instrucción ejecutar; la elección de la instrucción es inherente al diseño de la máquina, y un OISC normalmente recibe el nombre de la instrucción que utiliza (por ejemplo, un OISC SBN, ^{[2] : 41} el lenguaje SUBLEQ, ^{[3] : 4} etc.). Cada una de las instrucciones anteriores se puede utilizar para construir un OISC Turing-completo.

En este artículo se presentan únicamente instrucciones basadas en la resta entre aquellas que no se activan mediante transporte. Sin embargo, es posible construir máquinas completas de Turing utilizando una instrucción basada en otras operaciones aritméticas, por ejemplo, la suma. Por ejemplo, una variación conocida como DLN (Decrement and jump if not zero) tiene solo dos operandos y utiliza el decremento como operación base. Para obtener más información, consulte Lenguajes derivados de Subleq [1].

La SBNZ a, b, c, d instrucción (" restar y bifurcar si no es igual a cero ") resta el contenido en la dirección a del contenido en la dirección b , almacena el resultado en la dirección c y luego, si el resultado no es 0 , transfiere el control a la dirección d (si el resultado es igual a cero, la ejecución procede a la siguiente instrucción en secuencia). ^[3]

La instrucción subleq (" restar y bifurcar si es menor o igual a cero ") resta el contenido en la dirección a del contenido en la dirección b , almacena el resultado en la dirección b y, luego, si el resultado no es positivo , transfiere el control a la dirección c (si el resultado es positivo, la ejecución procede a la siguiente instrucción en secuencia). ^{[3] : 4–7} Pseudocódigo :

Instrucción subleq a, b, c
    Mem[b] = Mem[b] - Mem[a]
    si (Mem[b] ≤ 0)
         ir a c

La bifurcación condicional se puede suprimir estableciendo el tercer operando igual a la dirección de la siguiente instrucción en la secuencia. Si no se escribe el tercer operando, esta supresión está implícita.

También es posible una variante con dos operandos y un acumulador interno , donde el acumulador se resta de la ubicación de memoria especificada por el primer operando. El resultado se almacena tanto en el acumulador como en la ubicación de memoria, y el segundo operando especifica la dirección de la bifurcación:

Instrucción subleq2 a, b
    Mem[a] = Mem[a] - ACCUM
    ACUMULACIÓN = Mem[a]
    si (Mem[a] ≤ 0)
         ir a b

Aunque esto utiliza sólo dos (en lugar de tres) operandos por instrucción, se necesitan más instrucciones para efectuar varias operaciones lógicas.

Es posible sintetizar muchos tipos de instrucciones de orden superior utilizando únicamente la instrucción subleq . ^{[3] : 9–10}

Rama incondicional:

JMP c

  subleqZ , Z , c​   

La adición se puede realizar mediante resta repetida, sin ramificación condicional; por ejemplo, las siguientes instrucciones dan como resultado que el contenido en la ubicación a se agregue al contenido en la ubicación b :

Añade a, b

  subleq a , Z subleq Z , b subleq Z , Z  
    
    

La primera instrucción resta el contenido en la posición a del contenido en la posición Z (que es 0) y almacena el resultado (que es el negativo del contenido en a ) en la posición Z . La segunda instrucción resta este resultado de b , almacenando en b esta diferencia (que ahora es la suma de los contenidos originalmente en a y b ); la tercera instrucción restaura el valor 0 a Z .

Una instrucción de copia se puede implementar de manera similar; por ejemplo, las siguientes instrucciones dan como resultado que el contenido en la ubicación b sea reemplazado por el contenido en la ubicación a , asumiendo nuevamente que el contenido en la ubicación Z se mantiene como 0:

Movimiento a, b

  subleq b , b subleq a , Z subleq Z , b subleq Z , Z  
    
    
    

Se puede crear cualquier prueba aritmética que se desee. Por ejemplo, se puede crear una condición de bifurcación si es cero a partir de las siguientes instrucciones:

Ecuación básica b, c

  subleq b , Z , L1 subleq Z , Z , SALIDA L1: subleq Z , Z subleq Z , b , c SALIDA: ...   
     

    
     

  

Subleq2 también se puede utilizar para sintetizar instrucciones de orden superior, aunque generalmente requiere más operaciones para una tarea determinada. Por ejemplo, se requieren no menos de 10 instrucciones subleq2 para invertir todos los bits de un byte determinado:

NO es un

  subleq2 tmp ; tmp = 0 (tmp = registro temporal) subleq2 tmp subleq2 uno ; acc = -1 subleq2 a ; a' = a + 1 subleq2 Z ; Z = - a - 1 subleq2 tmp ; tmp = a + 1 subleq2 a ; a' = 0 subleq2 tmp ; cargar tmp en acc subleq2 a ; a' = - a - 1 ( = ~a ) subleq2 Z ; restablecer Z a 0           
   
             
               
               
             
               
             
               
               

El siguiente programa (escrito en pseudocódigo ) emula la ejecución de un OISC basado en subleq :

 int memoria [], contador_de_programa , a , b , c contador_de_programa = 0 while ( contador_de_programa >= 0 ) : a = memoria [ contador_de_programa ] b = memoria [ contador_de_programa + 1 ] c = memoria [ contador_de_programa + 2 ] if ( a < 0 o b < 0 ) : contador_de_programa = -1 else : memoria [ b ] = memoria [ b ] - memoria [ a ] ​​if ( memoria [ b ] > 0 ) : contador_de_programa += 3 else : contador_de_programa = c     
   
    
       
       
       
            
           
     
             
            
               
         
               

Este programa supone que memory[] está indexado por números enteros no negativos . En consecuencia, para una instrucción subleq ( a , b , c ), el programa interpreta a < 0 , b < 0 o una bifurcación ejecutada a c < 0 como una condición de detención. Se pueden encontrar intérpretes similares escritos en un lenguaje basado en subleq (es decir, intérpretes automáticos , que pueden usar código automodificable según lo permita la naturaleza de la instrucción subleq ) en los enlaces externos a continuación.

Se ha implementado un sistema operativo de 64 bits con capacidad SMP de propósito general llamado Dawn OS en una máquina Subleq emulada. El sistema operativo contiene un compilador tipo C. Algunas áreas de memoria en la máquina virtual se utilizan para periféricos como el teclado, el ratón, los discos duros, la tarjeta de red, etc. Las aplicaciones básicas escritas para él incluyen un reproductor multimedia, una herramienta de pintura, un lector de documentos y una calculadora científica. ^[13]

Yoel Matveyev ha construido un ordenador Subleq de 32 bits con una pantalla gráfica y un teclado llamado Izhora como un gran patrón de automatización celular . ^{[14] [15]}

Existe un compilador llamado Higher Subleq escrito por Oleg Mazonka que compila un programa C simplificado en código subleq . ^[16]

Alternativamente, existe una implementación de Forth auto hospedada escrita por Richard James Howe que se ejecuta sobre una máquina virtual Subleq y es capaz de realizar una programación interactiva de la máquina Subleq ^[17].

La instrucción subneg (" restar y ramificar si es negativo "), también llamada SBN , se define de manera similar a subleq : ^{[2] : 41, 51–52}

Instrucción subneg a, b, c
    Mem[b] = Mem[b] - Mem[a]
    si (Mem[b] < 0)
         ir a c

La bifurcación condicional se puede suprimir estableciendo el tercer operando igual a la dirección de la siguiente instrucción en la secuencia. Si no se escribe el tercer operando, esta supresión está implícita.

Es posible sintetizar muchos tipos de instrucciones de orden superior utilizando únicamente la instrucción subneg . Para simplificar, aquí se muestra únicamente una instrucción sintetizada para ilustrar la diferencia entre subleq y subneg .

Rama incondicional: ^{[2] : 88–89}

JMP c

  subneg POS , Z , c   

donde Z y POS son ubicaciones previamente configuradas para contener 0 y un entero positivo, respectivamente;

La ramificación incondicional se garantiza solo si Z contiene inicialmente 0 (o un valor menor que el entero almacenado en POS ). Se requiere una instrucción de seguimiento para borrar Z después de la ramificación, suponiendo que el contenido de Z debe mantenerse como 0.

También es posible una variante con cuatro operandos: subneg4. La inversión del minuendo y el sustraendo facilita la implementación en hardware. El resultado no destructivo simplifica las instrucciones sintéticas.

Instrucción  (*direcciones de sustraendo, minuendo, resultado y salto*)subneg s, m, r, j
    
    Mem[r] = Mem[m] - Mem[s]
    si (Mem[r] < 0)
         ir a j

En un intento de hacer que la máquina de Turing sea más intuitiva, ZA Melzak se planteó la tarea de calcular con números positivos. La máquina tiene un ábaco infinito, una cantidad infinita de fichas (piedras, palitos de recuento) inicialmente en una posición especial S. La máquina es capaz de realizar una operación:

Toma de la ubicación X tantas fichas como haya en la ubicación Y y transfiérelas a la ubicación Z y procede a la instrucción y.

Si esta operación no es posible porque no hay suficientes fichas en X, entonces deje el ábaco como está y proceda a la instrucción n. ^[18]

Para mantener todos los números positivos e imitar a un operador humano que calcula en un ábaco del mundo real, la prueba se realiza antes de cualquier resta. Pseudocódigo:

Instrucción  if (Mem[X] < Mem[Y])
         goto nmelzak X, Y, Z, n, y
    
    Memoria[X] -= Memoria[Y]
    Memoria[Z] += Memoria[Y]
    Ve a y

Después de dar algunos programas: multiplicación, mcd, cálculo del n -ésimo número primo, representación en base b de un número arbitrario, ordenación por magnitud, Melzak muestra explícitamente cómo simular una máquina de Turing arbitraria en su máquina aritmética.

MUL p, q

multiplicar: 
melzak P , ONE , S , stop ; Mueve 1 contador de P a S. Si no es posible, muévete a stop. melzak S , Q , ANS , multiplicar , multiplicar ; Mueve q contadores de S a ANS. Muévete a la primera instrucción. stop:                      
         

donde la ubicación de memoria P es p , Q es q , UNO es 1, ANS es inicialmente 0 y al final pq , y S es un número grande.

Menciona que se puede demostrar fácilmente utilizando los elementos de funciones recursivas que todo número calculable en la máquina aritmética es computable. Lambek ^[19] dio una prueba de esto en una máquina equivalente de dos instrucciones: X+ (incrementar X) y X− en caso contrario T (decrementar X si no está vacío, en caso contrario saltar a T).

En una instrucción de resta inversa y omisión si se toma prestado (RSSB), el acumulador se resta de la ubicación de memoria y se omite la siguiente instrucción si hubo un préstamo (la ubicación de memoria era más pequeña que el acumulador). El resultado se almacena tanto en el acumulador como en la ubicación de memoria. El contador de programa se asigna a la ubicación de memoria 0. El acumulador se asigna a la ubicación de memoria 1. ^[2]

Instrucción rssb x
    ACUM = Mem[x] - ACUM
    Mem[x] = ACUM
    si (ACCUM < 0)
         ir a PC + 2

Para establecer x en el valor de y menos z:

# Primero, mueva z a la ubicación de destino x. 
RSSB temp # Se requieren tres instrucciones para borrar acc, temp [Ver Nota 1] RSSB temp RSSB temp RSSB x # Dos instrucciones borran acc, x, ya que acc ya está borrado RSSB x RSSB y # Cargar y en acc: no tomar prestado RSSB temp # Almacenar -y en acc, temp: siempre tomar prestado y omitir RSSB temp # Omitido RSSB x # Almacenar y en x, acc # Segundo, realizar la operación. RSSB temp # Se requieren tres instrucciones para borrar acc, temp RSSB temp RSSB temp RSSB z # Cargar z RSSB x # x = y - z [Ver Nota 2]    
   
   
       
   
       
    
    
       

    
   
   
       
       

• [Nota 1] Si el valor almacenado en "temp" es inicialmente un valor negativo y la instrucción que se ejecutó justo antes del primer "RSSB temp" en esta rutina tomó prestado, entonces se requerirán cuatro instrucciones "RSSB temp" para que la rutina funcione.
• [Nota 2] Si el valor almacenado en "z" es inicialmente un valor negativo, entonces se omitirá el "RSSB x" final y, por lo tanto, la rutina no funcionará.

Una arquitectura activada por transporte utiliza únicamente la instrucción de movimiento , por lo que originalmente se la llamó "máquina de movimiento". Esta instrucción mueve el contenido de una ubicación de memoria a otra ubicación de memoria combinándose con el contenido actual de la nueva ubicación: ^{[2] : 42  [20]}

Instrucción  (también escrita a -> b )movx a, b
    OP = ObtenerOperación(Mem[ b ])
    Memoria[ b ] := OP(Mem[ a ], Memoria[ b ])

La operación que se realiza está definida por la celda de memoria de destino. Algunas celdas están especializadas en la suma, otras en la multiplicación, etc. Por lo tanto, las celdas de memoria no son simples almacenes, sino que están acopladas a una unidad lógica aritmética (ALU) configurada para realizar solo un tipo de operación con el valor actual de la celda. Algunas de las celdas son instrucciones de flujo de control para alterar la ejecución del programa con saltos, ejecución condicional , subrutinas , if-then-else , for-loop , etc.

Se ha producido un microcontrolador con arquitectura activada por transporte comercial llamado MAXQ, que oculta el aparente inconveniente de un OISC al utilizar un "mapa de transferencia" que representa todos los destinos posibles para las instrucciones de movimiento . ^[21]

Cryptoleq ^[22] es un lenguaje similar a Subleq. Consta de una instrucción homónima y es capaz de realizar cálculos de propósito general en programas cifrados. Cryptoleq trabaja en celdas continuas de memoria utilizando direccionamiento directo e indirecto, y realiza dos operaciones O ₁ y O ₂ en tres valores A, B y C:

Instrucción  
    Mem[b] = O 1 (Mem[a], Mem[b])
     si O 2 (Mem[b]) ≤ 0cryptoleq a, b, c
        IP = c
    demás
        IP = IP + 3

donde a, b y c son direccionados por el puntero de instrucción, IP, con el valor de IP direccionando a, IP + 1 apunta a b e IP + 2 a c.

En Cryptoleq las operaciones O ₁ y O ₂ se definen de la siguiente manera:

${\displaystyle {\begin{array}{lcl}O_{1}(x,y)&=&x^{-1}y\,{\bmod {\,}}N^{2}\end{array} }}$

${\displaystyle {\begin{array}{lcl}O_{2}(x)&=&\left\lfloor {\frac {x-1}{N}}\right\rfloor \end{array}}}$

La principal diferencia con Subleq es que en Subleq, O ₁ ( x,y ) simplemente resta y de x y O ₂ ( x ) es igual a x . Cryptoleq también es homomórfico a Subleq, la inversión modular y la multiplicación son homomórficas a la resta y la operación de O ₂ corresponde a la prueba de Subleq si los valores no estuvieran encriptados. Un programa escrito en Subleq puede ejecutarse en una máquina Cryptoleq, lo que significa compatibilidad con versiones anteriores. Sin embargo, Cryptoleq implementa cálculos completamente homomórficos y es capaz de realizar multiplicaciones. La multiplicación en un dominio encriptado está asistida por una función única G que se supone que es difícil de aplicar ingeniería inversa y permite volver a encriptar un valor en función de la operación O ₂ :

${\displaystyle G(x,y)={\begin{cases}{\tilde {0}},&{\text{si }}O_{2}({\bar {x}}){\text{ }}\leq 0\\{\tilde {y}},&{\text{en caso contrario}}\end{cases}}}$

donde es el valor reencriptado de y y es cero encriptado. x es el valor encriptado de una variable, sea m , e igual a ⁠ ⁠ . ${\displaystyle {\tilde {y}}}$${\displaystyle {\tilde {0}}}$${\estilo de visualización {\bar {x}}}$${\estilo de visualización Nm+1}$

El algoritmo de multiplicación se basa en la suma y la resta, utiliza la función G y no tiene saltos ni ramificaciones condicionales. El cifrado de Cryptoleq se basa en el criptosistema Paillier .

• Fractrano
• Axiomas mínimos para el álgebra de Boole
• Registrar máquina
• Alquitrán de Turing
• Computadora con conjunto de instrucciones reducido
• Conjunto complejo de instrucciones para computadoras
• Computadora con conjunto de instrucciones cero

• Subleq en la wiki de lenguajes de programación esotéricos: intérpretes, compiladores, ejemplos y lenguajes derivados
• Reducción al absurdo en YouTube de Christopher Domas
• Implementación de un ordenador subleq de laboratorio mediante FPGA utilizando VHDL
• Museo de la Retrocomputación: emulador SBN y programas de muestra
• Computadora SBN de laboratorio: implementada con circuitos integrados de la serie 7400
• RSSB en la wiki de lenguajes de programación esotéricos: intérpretes y ejemplos
• Implementación de OISC de 32 bits del Dr. Dobb: arquitectura activada por transporte (TTA) en un FPGA con Verilog
• Introducción a la arquitectura MAXQ: incluye diagrama de mapa de transferencia
• Emulador OISC – versión gráfica
• TrapCC (las MMU Intel x86 recientes son en realidad OISC Turing-completos).
• Izhora – El ordenador Subleq de Yoel Matveyev, construido como un sistema de automatización celular
• Simulador SBN – Simulador y diseño inspirados en CARDboard Ayuda ilustrativa para el cálculo
• Computación de un bit a 60 hercios: intermedio entre una computadora y una máquina de estados
• La máquina NOR: información sobre cómo construir una CPU con una sola instrucción
• SUBLEQ eFORTH Un intérprete Forth completo que se ejecuta en SUBLEQ OISC.
• Cryptoleq – Repositorio de recursos de Cryptoleq
• CAAMP – Arquitectura de Computadores: Una Perspectiva Minimalista
• SICO – Single Instruction COmputer: una variante de SUBLEQ que utiliza números enteros sin signo