Una computadora con un conjunto de instrucciones ( OISC ), a veces llamada computadora con un conjunto de instrucciones reducido final ( URISC ), es una máquina abstracta que usa solo una instrucción, lo que evita la necesidad de un código de operación en lenguaje de máquina . [1] [2] [3] Con una elección acertada para la instrucción única y recursos infinitos dados, un OISC es capaz de ser una computadora universal de la misma manera que las computadoras tradicionales que tienen múltiples instrucciones. [2] : Se han recomendado 55 OISC como ayudas en la enseñanza de la arquitectura informática [1]: 327 [2] : 2 y se han utilizado como modelos computacionales en la investigación de la computación estructural. [3]
Si bien las CPU de 1 bit son obsoletas (y no eran OISC), la primera computadora con nanotubos de carbono es una computadora con un conjunto de instrucciones de 1 bit (y solo tiene 178 transistores). [ cita requerida ]
Arquitectura de la máquina
En un modelo completo de Turing , cada ubicación de memoria puede almacenar un número entero arbitrario y, según el modelo [ aclaración necesaria ] , puede haber arbitrariamente muchas ubicaciones. Las instrucciones mismas residen en la memoria como una secuencia de tales números enteros.
Existe una clase de computadoras universales con una sola instrucción basada en la manipulación de bits, como la copia o 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. [4]
Los OISC actualmente conocidos se pueden dividir aproximadamente en tres categorías amplias:
- Máquinas manipuladoras de bits
- Máquinas de arquitectura activadas por transporte
- Máquinas completas de Turing basadas en aritmética
Máquinas manipuladoras de bits
Las máquinas de manipulación de bits son la clase más simple.
FlipJump
La máquina FlipJump tiene 1 instrucción, a; b - voltea el bit a, luego salta a b. Este es el OISC más primitivo, pero sigue siendo útil. Puede realizar con éxito cálculos matemáticos / lógicos, ramificaciones, punteros y funciones de llamada con la ayuda de su biblioteca estándar.
BitBitJump
Una máquina copiadora de bits, [4] llamada BitBitJump, copia un bit en la 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 el código que se ejecutará posteriormente.
Computadora Toga
Otra máquina, llamada Toga Computer , invierte un poco y pasa la ejecución condicionalmente dependiendo del resultado de la inversión. La instrucción es única TOGA (a, b) que significa TOG GLE un Un nd rama en b si el resultado de la operación de conmutación es cierto.
Máquina copiadora de varios bits
Similar a BitBitJump, una máquina copiadora de varios 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 ] [ aclaración necesaria ]
Arquitectura activada por transporte
La arquitectura activada por transporte (TTA) es un diseño en el que la computación 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 usa una sola instrucción de copia de memoria a memoria, esto se hace activando puertos que realizan aritmética y saltos de puntero de instrucción cuando se escriben.
Máquinas completas de Turing basadas en aritmética
Las máquinas completas de Turing 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 existen varios OISC conocidos de esta clase, basados en diferentes operaciones aritméticas:
- Además (addleq, añadir y la rama si l ess que o eq ual a cero) [5]
- decremento (DJN, d ecrement y la rama ( j UMP) si n onzero) [6]
- incremento (P1eq, p lus 1 y la rama si eq ual a otro valor) [7]
- resta (subleq, sub tracto y la rama si l ess que o eq ual a cero) [8] [9]
- resta cuando sea posible (máquina aritmética) [ aclaración necesaria ] [10]
Tipos de instrucción
Las opciones comunes para la instrucción única son:
- Restar y bifurcar si es menor o igual a cero
- Restar y ramificar si es negativo
- Restar si es positivo rama else
- Restar inverso y omitir si se pide prestado
- Mover (utilizado como parte de una arquitectura activada por transporte)
- Restar y bifurcar si no es cero (SBNZ a, b, c, destino)
- Cryptoleq (cálculo heterogéneo cifrado y no cifrado)
Solo una de estas instrucciones se utiliza en una implementación determinada. Por 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 generalmente recibe el nombre de la instrucción que utiliza (por ejemplo, un SBN OISC, [2] : 41 el lenguaje SUBLEQ, [3] : 4, etc.). Cada una de las instrucciones anteriores se puede utilizar para construir un OISC completo de Turing.
Este artículo presenta solo instrucciones basadas en restas entre las que no se activan por transporte. Sin embargo, es posible construir máquinas completas de Turing usando una instrucción basada en otras operaciones aritméticas, por ejemplo, la suma. Por ejemplo, una variación conocida como DLN (Decremento y salto si no es cero) tiene solo dos operandos y usa el decremento como operación base. Para obtener más información, consulte Lenguajes derivados de Subleq [1] .
Restar y ramificar si no es igual a cero
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 pasa a la siguiente instrucción en secuencia). [3]
Restar y bifurcar si es menor o igual a cero
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 pasa 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) goto c
La bifurcación condicional se puede suprimir estableciendo el tercer operando igual a la dirección de la siguiente instrucción en 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 la memoria, y el segundo operando especifica la dirección de la rama:
Instrucción subleq2 a, b
Mem [a] = Mem [a] - ACCUM ACCUM = Mem [a] si (Mem [a] ≤ 0) goto b
Aunque esto usa solo dos (en lugar de tres) operandos por instrucción, en consecuencia, se necesitan más instrucciones para efectuar varias operaciones lógicas.
Instrucciones sintetizadas
Es posible sintetizar muchos tipos de instrucciones de orden superior utilizando solo el instrucción subleq . [3] : 9–10
Rama incondicional:
- JMP c
subleq Z , Z , c
La suma se puede realizar mediante resta repetida, sin ramificaciones condicionales; por ejemplo, las siguientes instrucciones dan como resultado el contenido en la ubicación un ser agregado al contenido en la ubicación b :
- AÑADIR a, b
subleq a , Z subleq Z , b subleq Z , Z
La primera instrucción resta el contenido en la ubicación a del contenido en la ubicación Z (que es 0) y almacena el resultado (que es el negativo del contenido en a ) en la ubicación Z . La segunda instrucción resta este resultado de b , almacenar 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 el contenido en la ubicación b siendo reemplazado por el contenido en la ubicación a , asumiendo nuevamente el contenido en la ubicación Z se mantiene como 0:
- MOV a, b
subleq b , b subleq a , Z subleq Z , b subleq Z , Z
Se puede construir cualquier prueba aritmética deseada. Por ejemplo, una condición de bifurcación si cero se puede ensamblar a partir de las siguientes instrucciones:
- BEQ b, c
subleq b , Z , L1 subleq Z , Z , OUT L1: subbleq Z , Z subleq Z , b , c OUT: ...
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 en un byte dado:
- No un
subleq2 tmp ; tmp = 0 (tmp = registro temporal) subleq2 tmp subleq2 one ; acc = -1 subleq2 a ; a '= a + 1 subleq2 Z ; Z = - a - 1 subleq2 tmp ; tmp = a + 1 subleq2 a ; a '= 0 subleq2 tmp ; cargue tmp en acc subleq2 a ; a '= - a - 1 (= ~ a) subleq2 Z ; establecer Z de nuevo a 0
Emulación
El siguiente programa (escrito en pseudocódigo ) emula la ejecución de un OISC basado en subleq:
int memory [], program_counter , a , b , c program_counter = 0 while ( program_counter > = 0 ) : a = memoria [ program_counter ] b = memoria [ program_counter + 1 ] c = memoria [ program_counter + 2 ] if ( a < 0 o b < 0 ) : program_counter = -1 else : memoria [ b ] = memoria [ b ] - memoria [ a ] if ( memoria [ b ] > 0 ) : program_counter + = 3 else : program_counter = c
Este programa asume que la memoria [] está indexada por enteros no negativos. En consecuencia, para un instrucción sublequna , b , c ), el programa interpreta a <0 , b <0 , o una rama ejecutada a c <0 como condición de parada. Intérpretes similares escritos en un lenguaje basado en subleq (es decir, auto-intérpretes , que pueden usar código auto-modificable según lo permita la naturaleza del instrucción subleq ) se pueden encontrar en los enlaces externos a continuación.
Compilacion
Hay un compilador llamado Higher Subleq escrito por Oleg Mazonka que compila un programa C simplificado en código de subbleq . [11]
Restar y ramificar si es negativo
La instrucción subneg (" restar y bifurcar si es negativo "), también llamada SBN , se define de manera similar a subbleq : [2] : 41,51–52
Instrucción subneg a, b, c
Mem [b] = Mem [b] - Mem [a] si (Mem [b] <0) goto c
La bifurcación condicional se puede suprimir estableciendo el tercer operando igual a la dirección de la siguiente instrucción en secuencia. Si no se escribe el tercer operando, esta supresión está implícita.
Instrucciones sintetizadas
Es posible sintetizar muchos tipos de instrucciones de orden superior utilizando solo el instrucción subneg . Para simplificar, aquí solo se muestra una instrucción sintetizada para ilustrar la diferencia entre subleq y subneg .
Rama incondicional: [2] : 88–89
- JMP c
POS subneg , Z , c
dónde Z y POS son ubicaciones previamente configuradas para contener 0 y un número entero positivo, respectivamente;
La ramificación incondicional está asegurada solo si Z inicialmente contiene 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, asumiendo que el contenido de Z debe mantenerse como 0.
subneg4
También es posible una variante con cuatro operandos: subneg4. La inversión de minuendo y sustraendo facilita la implementación en hardware. El resultado no destructivo simplifica las instrucciones sintéticas.
Instrucción (* sustraendo, minuendo, resultado y direcciones de salto *)subneg s, m, r, j
Mem [r] = Mem [m] - Mem [s] si (Mem [r] <0) goto j
Máquina aritmética
En un intento por hacer que la máquina de Turing sea más intuitiva, ZA Melzac considera la tarea de calcular con números positivos. La máquina tiene un ábaco infinito, un número infinito de contadores (guijarros, palos de conteo) inicialmente en una ubicación especial S. La máquina puede realizar una operación:
Tome de la ubicación X tantos contadores como haya en la ubicación Y y transfiéralos a la ubicación Z y continúe con la siguiente instrucción.
Si esta operación no es posible porque no hay suficientes contadores en Y, deje el ábaco como está y continúe con la instrucción T.
Se trata esencialmente de un subneg donde la prueba se realiza antes y no después de la resta, para mantener todos los números positivos e imitar a un operador humano que calcula en un ábaco del mundo real. Pseudocódigo:
Instrucción si (Mem [Y]goto T melzac X, Y, Z, T
Mem [Z] = Mem [Y] - Mem [X]
Después de dar algunos programas: multiplicación, gcd, calcular el n -ésimo número primo, representación en base b de un número arbitrario, ordenar en orden de magnitud, Melzac muestra explícitamente cómo simular una máquina de Turing arbitraria en su máquina aritmética.
Él menciona que se puede demostrar fácilmente usando los elementos de funciones recursivas que cada número calculable en la máquina aritmética es computable. Lambek [12] lo demostró en una máquina equivalente de dos instrucciones: X + (incremento X) y X− si no T (decremento X si no está vacío, de lo contrario salta a T).
Restar inverso y omitir si se pide prestado
En una instrucción de restar y omitir en reversa (RSSB), el acumulador se resta de la ubicación de la memoria y la siguiente instrucción se omite si hubo un préstamo (la ubicación de la memoria era más pequeña que el acumulador). El resultado se almacena tanto en el acumulador como en la ubicación de la 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 si (ACUM <0) pasa a PC + 2
Ejemplo
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 es claro RSSB x RSSB y # Cargar y en acc: no pedir prestado RSSB temp # Almacene -y en acc, temp: siempre tome prestado y omita RSSB temp # Omitió RSSB x # Almacene y en x, acc # En segundo lugar, realice la operación. RSSB temp # Se requieren tres instrucciones para borrar acc, temp RSSB temp RSSB temp RSSB z # Load 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 de la primera "RSSB temp" en esta rutina se tomó prestada, entonces se necesitarán cuatro instrucciones "RSSB temp" para que la rutina funcione. .
- [Nota 2] Si el valor almacenado en "z" es inicialmente un valor negativo, se omitirá el "RSSB x" final y, por lo tanto, la rutina no funcionará.
Arquitectura activada por transporte
Una arquitectura activada por transporte utiliza solo 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 [13]
Instrucción (también escrita a -> b )movx a, b
OP = GetOperation (Mem [ b ]) Mem [ b ]: = OP (Mem [ a ], Mem [ b ])
La operación realizada está definida por la celda de memoria de destino. Algunas celdas están especializadas además, otras en multiplicación, etc. Por lo tanto, las celdas de memoria no son un simple almacenamiento sino que están acopladas con una configuración de unidad aritmética lógica (ALU) 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 comercial de arquitectura activada por transporte llamado MAXQ, que oculta el aparente inconveniente de un OISC mediante el uso de un "mapa de transferencia" que representa todos los destinos posibles para las instrucciones de movimiento . [14]
Cryptoleq
Cryptoleq [15] es un lenguaje que consta de una instrucción del mismo nombre , es capaz de realizar cálculos de propósito general en programas encriptados y es un pariente cercano de Subleq. Cryptoleq trabaja en celdas continuas de memoria usando direccionamiento directo e indirecto, y realiza dos operaciones O 1 y O 2 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, byc son direccionados por el puntero de instrucción, IP, con el valor de direccionamiento IP a, IP + 1 punto ab e IP + 2 ac.
En las operaciones Cryptoleq, O 1 y O 2 se definen de la siguiente manera:
La principal diferencia con Subleq es que en Subleq, O 1 ( x, y ) simplemente resta y de x y O 2 ( 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 2 corresponde a la prueba Subleq si los valores no estaban 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, dado que el modelo es capaz de hacer multiplicaciones. La multiplicación en un dominio encriptado es 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 basado en la operación de O 2 :
dónde es el valor reencriptado de y yes cero cifrado. x es el valor cifrado de una variable, sea m , y es igual a .
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 Cryptoleq se basa en el criptosistema Paillier .
Ver también
- FRACTRAN
- Registrar máquina
- Tarpito de Turing
- Ordenador con conjunto de instrucciones cero
Referencias
- ↑ a b Mavaddat, F .; Parhami, B. (octubre de 1988). "URISC: la última computadora de conjunto de instrucciones reducidas" (PDF) . Int'l J. Educación en Ingeniería Eléctrica . Prensa de la Universidad de Manchester. 25 (4): 327–334. doi : 10.1177 / 002072098802500408 . S2CID 61797084 . Consultado el 4 de octubre de 2010 .Este documento considera "una máquina con una única instrucción de 3 direcciones como lo último en diseño RISC (URISC)". Sin dar un nombre a la instrucción, describe un SBN OISC y su lenguaje ensamblador asociado, enfatizando que se trata de una máquina universal (es decir, Turing-completa ) cuya simplicidad la hace ideal para uso en el aula.
- ^ a b c d e f g h Gilreath, William F .; Laplante, Phillip A. (2003). Arquitectura informática: una perspectiva minimalista . Springer Science + Business Media . ISBN 978-1-4020-7416-5. Archivado desde el original el 13 de junio de 2009.Destinado a investigadores, ingenieros de sistemas informáticos, teóricos computacionales y estudiantes, este libro proporciona un examen en profundidad de varios OISC, incluidos SBN y MOVE. Atribuye SBN a WL van der Poel (1956).
- ^ a b c d e f Nuremberg, Peter J .; Wiil, Uffe K .; Hicks, David L. (septiembre de 2003), "A Grand Unified Theory for Structural Computing" , Metainformatics: International Symposium, MIS 2003 , Graz, Austria: Springer Science + Business Media , págs. 1-16, ISBN 978-3-540-22010-7 Este trabajo de investigación se enfoca completamente en un SUBLEQ OISC y su lenguaje ensamblador asociado, usando el nombre SUBLEQ para "tanto la instrucción como cualquier lenguaje basado en él".
- ^ a b Oleg Mazonka, "Copia de bits: la máxima simplicidad computacional" , Complex Systems Journal 2011, Vol 19, N3, págs. 263-285
- ^ "Addleq" . Esolang Wiki . Consultado el 16 de septiembre de 2017 .
- ^ "DJN OISC" . Esolang Wiki . Consultado el 16 de septiembre de 2017 .
- ^ "P1eq" . Esolang Wiki . Consultado el 16 de septiembre de 2017 .
- ^ Mazonka, Oleg (octubre de 2009). "SUBLEQ" . Archivado desde el original el 29 de junio de 2017 . Consultado el 16 de septiembre de 2017 .
- ^ "Subleq" . Esolang Wiki . Consultado el 16 de septiembre de 2017 .
- ^ ZA Melzak (1961). "Un enfoque aritmético informal a la computabilidad y la computación" . Boletín matemático canadiense . 4 (3): 279-293. doi : 10.4153 / CMB-1961-031-9 .
- ^ Oleg Mazonka Una computadora multiprocesador simple basada en Subleq
- ^ J. Lambek (1961). "Cómo programar un ábaco infinito". Boletín matemático canadiense . 4 (3): 295-302. doi : 10.4153 / CMB-1961-032-6 .
- ^ Jones, Douglas W. (junio de 1988). "El último RISC" . ACM SIGARCH Computer Architecture News . Nueva York: ACM. 16 (3): 48–55. doi : 10.1145 / 48675.48683 . S2CID 9481528 . Consultado el 4 de octubre de 2010 . "Las arquitecturas informáticas con conjuntos de instrucciones reducidos han atraído un interés considerable desde 1980. La arquitectura RISC definitiva que se presenta aquí es una ilustración extrema pero simple de dicha arquitectura. Tiene solo una instrucción, mueve la memoria a la memoria, pero es útil".
- ^ Catsoulis, John (2005), Designing embedded hardware (2 ed.), O'Reilly Media , págs. 327–333, ISBN 978-0-596-00755-3
- ^ Mazonka, Oleg; Tsoutsos, Nektarios Georgios; Maniatakos, Michail (2016), "Cryptoleq: A Heterogeneous Abstract Machine for Encrypted and Unencrypted Computation", IEEE Transactions on Information Forensics and Security , 11 (9): 2123–2138, doi : 10.1109 / TIFS.2016.2569062 , S2CID 261387
enlaces externos
- Subleq en la wiki de lenguajes de programación esotéricos : intérpretes, compiladores, ejemplos y lenguajes derivados
- Reductio ad absurdum en YouTube por Christopher Domas
- Computadora subleq de laboratorio : implementación de FPGA usando VHDL
- The Retrocomputing Museum : 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 una 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 completas de Turing).
- Simulador SBN : simulador y diseño inspirados en la ayuda ilustrativa a la computación de CARDboard
- Computación de un bit a 60 hercios : intermedio entre una computadora y una máquina de estado
- La máquina NOR : información sobre la construcción de una CPU con una sola instrucción
- Cryptoleq - repositorio de recursos de Cryptoleq
- CAAMP - Arquitectura de computadora una perspectiva minimalista
- DawnOS : un sistema operativo para la arquitectura SUBLEQ
- Unileq : una variante de SUBLEQ que usa enteros sin signo