Ordinateur à un jeu d'instructions - One-instruction set computer

Un ordinateur à jeu d'instructions unique ( OISC ), parfois appelé ordinateur à jeu d'instructions ultime réduit ( URISC ), est une machine abstraite qui n'utilise qu'une seule instruction, ce qui évite le besoin d'un code opération en langage machine . Avec un choix judicieux pour l'instruction unique et des ressources infinies étant donné, un OISC est capable d'être un ordinateur universel de la même manière que les ordinateurs traditionnels qui ont plusieurs instructions. Les OISC ont été recommandés comme aides à l'enseignement de l'architecture informatique et ont été utilisés comme modèles informatiques dans la recherche en informatique structurelle.

Alors que les processeurs 1 bit sont par ailleurs obsolètes (et n'étaient pas des OISC), le premier ordinateur à nanotubes de carbone est un ordinateur à jeu d'instructions 1 bit (et ne possède que 178 transistors).

Architecture des machines

Dans un modèle Turing-complet , chaque emplacement de mémoire peut stocker un entier arbitraire et, selon le modèle, il peut y avoir arbitrairement de nombreux emplacements. Les instructions elles-mêmes résident en mémoire sous la forme d'une séquence de tels nombres entiers.

Il existe une classe d' ordinateurs universels avec une seule instruction basée sur la manipulation de bits telle que la copie de bits ou l' inversion de bits . Étant donné que leur modèle de mémoire est fini, tout comme la structure de mémoire utilisée dans les ordinateurs réels, ces machines de manipulation de bits sont équivalentes à de vrais ordinateurs plutôt qu'à des machines de Turing.

Les OISC actuellement connus peuvent être grossièrement divisés en trois grandes catégories :

• Machines à manipuler les bits
• Machines à architecture déclenchée par le transport
• Machines complètes de Turing basées sur l'arithmétique

Machines à manipuler les bits

Les machines à manipuler les bits sont la classe la plus simple.

FlipJump

La machine FlipJump a 1 instruction, a;b - retourne le bit a, puis saute à b. C'est l'OISC le plus primitif, mais il est toujours utile. Il peut effectuer avec succès des calculs mathématiques/logiques, des branchements, des pointeurs et des fonctions d'appel à l'aide de sa bibliothèque standard.

BitBitJump

Une machine à copier des bits, appelée BitBitJump, copie un bit en mémoire et passe l'exécution inconditionnellement à l'adresse spécifiée par l'un des opérandes de l'instruction. Ce processus s'avère être capable de calcul universel (c'est-à-dire être capable d'exécuter n'importe quel algorithme et d'interpréter n'importe quelle autre machine universelle) car copier des bits peut modifier conditionnellement le code qui sera ensuite exécuté.

ordinateur Toge

Une autre machine, appelée Toga Computer , inverse un peu et passe l'exécution conditionnellement en fonction du résultat de l'inversion. L'instruction unique est TOGA(a,b) qui signifie TOG gle a A et se branche sur b si le résultat de l'opération de basculement est vrai.

Machine à copier multi-bits

Semblable à BitBitJump, une machine de copie multi-bits copie plusieurs bits en même temps. Le problème de l' universalité de calcul est résolu dans ce cas en gardant en mémoire des tables de saut prédéfinies.

Architecture déclenchée par le transport

L'architecture déclenchée par le transport (TTA) est une conception dans laquelle le calcul est un effet secondaire du transport de données. Habituellement, certains registres de mémoire (ports de déclenchement) dans l'espace d'adressage commun effectuent une opération assignée lorsque l'instruction les référence. Par exemple, dans un OISC utilisant une seule instruction de copie mémoire à mémoire, cela se fait en déclenchant des ports qui effectuent des sauts arithmétiques et de pointeur d'instruction lors de l'écriture.

Machines complètes de Turing basées sur l'arithmétique

Les machines complètes de Turing basées sur l'arithmétique utilisent une opération arithmétique et un saut conditionnel. Comme les deux ordinateurs universels précédents, cette classe est également Turing-complet. L'instruction opère sur des entiers qui peuvent également être des adresses en mémoire.

Actuellement, il existe plusieurs OISC connus de cette classe, basés sur différentes opérations arithmétiques :

• addition (addleq, ajouter et branche si l ess que ou eq uel à zéro)
• décrémentation (DJN, D Ecrement et la branche ( J UMP) si N onzero)
• incrément (P1eq, P lus 1 et de la branche si eq uel à une autre valeur)
• soustraction (subleq, sous des voies et de la branche si l ess que ou eq uel à zéro)
• soustraction positive si possible, sinon branche (machine arithmétique)

Types d'instructions

Les choix courants pour l'instruction unique sont :

• Soustraire et brancher si inférieur ou égal à zéro
• Soustraire et brancher si négatif
• Soustraire si positif sinon branche
• Inverser la soustraction et sauter si emprunter
• Déplacer (utilisé dans le cadre d'une architecture déclenchée par le transport)
• Soustraire et brancher si non nul (SBNZ a, b, c, destination)
• Cryptoleq (calcul hétérogène crypté et non crypté)

Une seule de ces instructions est utilisée dans une implémentation donnée. Par conséquent, il n'y a pas besoin d'un opcode pour identifier quelle instruction exécuter ; le choix de l'instruction est inhérent à la conception de la machine, et un OISC est généralement nommé d'après l'instruction qu'il utilise (par exemple, un SBN OISC, le langage SUBLEQ, etc.). Chacune des instructions ci-dessus peut être utilisée pour construire un OISC complet de Turing.

Cet article présente uniquement les instructions basées sur la soustraction parmi celles qui ne sont pas déclenchées par le transport. Cependant, il est possible de construire des machines complètes de Turing en utilisant une instruction basée sur d'autres opérations arithmétiques, par exemple l'addition. Par exemple, une variante connue sous le nom de DLN (Décrément et saut sinon zéro) n'a que deux opérandes et utilise la décrémentation comme opération de base. Pour plus d'informations, voir Langages dérivés Subleq [1] .

Soustraire et brancher s'il n'est pas égal à zéro

L' SBNZ a, b, c, d instruction (" soustraire et branchement si différent de zéro ") soustrait le contenu à l'adresse a du contenu à l'adresse b , stocke le résultat à l'adresse c , puis, si le résultat n'est pas 0 , transfère le contrôle à l'adresse d ( si le résultat est égal à zéro, l'exécution passe à l'instruction suivante dans la séquence).

Soustraire et brancher si inférieur ou égal à zéro

L' instruction subleq (" soustraire et branchement si inférieur ou égal à zéro ") soustrait le contenu à l'adresse a du contenu à l'adresse b , stocke le résultat à l'adresse b , puis, si le résultat n'est pas positif , transfère le contrôle à adresse c (si le résultat est positif, l'exécution passe à l'instruction suivante dans la séquence). Pseudocode :

Instruction subleq a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] ≤ 0)
        goto c

Le branchement conditionnel peut être supprimé en définissant le troisième opérande égal à l'adresse de l'instruction suivante dans la séquence. Si le troisième opérande n'est pas écrit, cette suppression est implicite.

Une variante est également possible avec deux opérandes et un accumulateur interne , où l'accumulateur est soustrait de l'emplacement mémoire spécifié par le premier opérande. Le résultat est stocké à la fois dans l'accumulateur et dans l'emplacement mémoire, et le deuxième opérande spécifie l'adresse de la branche :

Instruction subleq2 a, b
    Mem[a] = Mem[a] - ACCUM
    ACCUM = Mem[a]
    if (Mem[a] ≤ 0)
        goto b

Bien que cela n'utilise que deux (au lieu de trois) opérandes par instruction, davantage d'instructions sont alors nécessaires pour effectuer diverses opérations logiques.

Instructions synthétisées

Il est possible de synthétiser de nombreux types d'instructions d'ordre supérieur en utilisant uniquement l' instruction subleq .

Branche inconditionnelle :

JMP c

  subleq Z, Z, c

L'addition peut être effectuée par soustraction répétée, sans branchement conditionnel ; par exemple, les instructions suivantes résultent de la teneur à l' emplacement d' un être ajoutés au contenu à l' emplacement b :

AJOUTER a, b

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

La première instruction soustrait le contenu à l'emplacement a du contenu à l'emplacement Z (qui est 0) et stocke le résultat (qui est le négatif du contenu à a ) à l'emplacement Z . La deuxième instruction soustrait ce résultat de b , stockant dans b cette différence (qui est maintenant la somme des contenus originellement en a et b ) ; la troisième instruction restitue la valeur 0 à Z .

Une instruction de copie peut être implémentée de manière similaire ; Par exemple, les instructions suivantes entraînent le remplacement du contenu de l'emplacement b par le contenu de l'emplacement a , en supposant à nouveau que le contenu de l'emplacement Z est maintenu à 0 :

MOV a, b

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

Tout test arithmétique souhaité peut être construit. Par exemple, une condition de branchement si zéro peut être assemblée à partir des instructions suivantes :

BEQ b, c

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

Subleq2 peut également être utilisé pour synthétiser des instructions d'ordre supérieur, bien qu'il nécessite généralement plus d'opérations pour une tâche donnée. Par exemple, pas moins de 10 instructions subleq2 sont nécessaires pour inverser tous les bits d'un octet donné :

PAS un

  subleq2 tmp          ; tmp = 0 (tmp = temporary register)
  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          ; load tmp into acc
  subleq2 a            ; a' = - a - 1 ( = ~a )
  subleq2 Z            ; set Z back to 0

Émulation

Le programme suivant (écrit en pseudocode ) émule l'exécution d'un OISC basé sur subleq :

 int 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 += 3
         else:
             program_counter = c

Ce programme suppose que memory[] est indexé par des entiers non négatifs . Par conséquent, pour une instruction subleq ( a , b , c ), le programme interprète a < 0 , b < 0 , ou un branchement exécuté vers c < 0 comme une condition d'arrêt. Des interprètes similaires écrits dans un langage basé sur subleq (c'est -à- dire des auto-interprètes , qui peuvent utiliser un code auto-modifiant comme le permet la nature de l' instruction subleq ) peuvent être trouvés dans les liens externes ci-dessous.

Compilation

Il existe un compilateur appelé Higher Subleq écrit par Oleg Mazonka qui compile un programme C simplifié en code subleq .

Soustraire et brancher si négatif

L' instruction subneg (" soustraire et branchement si négatif "), également appelée SBN , est définie de la même manière que subleq :

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

Le branchement conditionnel peut être supprimé en définissant le troisième opérande égal à l'adresse de l'instruction suivante dans la séquence. Si le troisième opérande n'est pas écrit, cette suppression est implicite.

Instructions synthétisées

Il est possible de synthétiser de nombreux types d'instructions d'ordre supérieur en utilisant uniquement l' instruction subneg . Pour plus de simplicité, une seule instruction synthétisée est montrée ici pour illustrer la différence entre subleq et subneg .

Branche inconditionnelle :

JMP c

  subneg POS, Z, c

où Z et POS sont des emplacements précédemment définis pour contenir 0 et un entier positif, respectivement ;

Le branchement inconditionnel n'est assuré que si Z contient initialement 0 (ou une valeur inférieure à l'entier stocké dans POS ). Une instruction de suivi est requise pour effacer Z après le branchement, en supposant que le contenu de Z doit être maintenu à 0.

subneg4

Une variante est également possible avec quatre opérandes – subneg4. L'inversion du minuend et du subtrahend facilite la mise en œuvre dans le matériel. Le résultat non destructif simplifie les instructions synthétiques.

Instruction subneg s, m, r, j
    (* subtrahend, minuend, result and jump addresses *)
    Mem[r] = Mem[m] - Mem[s]
    if (Mem[r] < 0)
        goto j

Machine arithmétique

Dans une tentative de rendre la machine de Turing plus intuitive, ZA Melzac envisage la tâche de calculer avec des nombres positifs. La machine possède un abaque infini, un nombre infini de jetons (cailloux, bâtons de comptage) initialement à un emplacement spécial S. La machine est capable de faire une opération :

Prenez à l'emplacement X autant de compteurs qu'il y en a dans l'emplacement Y et transférez-les à l'emplacement Z et passez à l'instruction suivante.

Si cette opération n'est pas possible car il n'y a pas assez de compteurs en Y, alors laissez le boulier tel quel et passez à l'instruction T.

Il s'agit essentiellement d'un sous-négatif où le test est effectué avant plutôt qu'après la soustraction, afin de garder tous les nombres positifs et d'imiter un opérateur humain calculant sur un boulier du monde réel. Pseudocode :

Instruction melzac X, Y, Z, T
    if (Mem[Y] < Mem[X])
        goto T
    Mem[Z] = Mem[Y] - Mem[X]

Après avoir donné quelques programmes : multiplication, pgcd, calcul du n- ième nombre premier, représentation en base b d'un nombre arbitraire, tri par ordre de grandeur, Melzac montre explicitement comment simuler une machine de Turing quelconque sur sa machine arithmétique.

Il mentionne qu'il peut facilement être montré en utilisant les éléments de fonctions récursives que tout nombre calculable sur la machine arithmétique est calculable. La preuve en a été donnée par Lambek sur une machine équivalente à deux instructions : X+ (incrémenter X) et X− sinon T (décrémenter X s'il n'est pas vide, sinon sauter à T).

Inverser la soustraction et sauter si emprunter

Dans une instruction de soustraction inverse et de saut si emprunt (RSSB), l' accumulateur est soustrait de l'emplacement mémoire et l'instruction suivante est sautée s'il y avait un emprunt (l'emplacement mémoire était plus petit que l'accumulateur). Le résultat est stocké à la fois dans l'accumulateur et dans l'emplacement mémoire. Le compteur de programme est mappé à l'emplacement mémoire 0. L'accumulateur est mappé à l'emplacement mémoire 1.

Instruction rssb x
    ACCUM = Mem[x] - ACCUM
    Mem[x] = ACCUM
    if (ACCUM < 0)
        goto PC + 2

Exemple

Pour définir x à la valeur de y moins z :

# First, move z to the destination location x.
  RSSB temp # Three instructions required to clear acc, temp [See Note 1]
  RSSB temp
  RSSB temp
  RSSB x    # Two instructions clear acc, x, since acc is already clear
  RSSB x
  RSSB y    # Load y into acc: no borrow
  RSSB temp # Store -y into acc, temp: always borrow and skip
  RSSB temp # Skipped
  RSSB x    # Store y into x, acc
# Second, perform the operation.
  RSSB temp # Three instructions required to clear acc, temp
  RSSB temp
  RSSB temp
  RSSB z    # Load z
  RSSB x    # x = y - z [See Note 2]

• [Note 1] Si la valeur stockée dans "temp" est initialement une valeur négative et l'instruction qui s'est exécutée juste avant le premier "RSSB temp" dans cette routine empruntée, alors quatre instructions "RSSB temp" seront nécessaires pour que la routine fonctionne .
• [Note 2] Si la valeur stockée à "z" est initialement une valeur négative, le "RSSB x" final sera ignoré et donc la routine ne fonctionnera pas.

Architecture déclenchée par le transport

Une architecture déclenchée par le transport utilise uniquement l' instruction de déplacement , c'est pourquoi elle s'appelait à l'origine une « machine de déplacement ». Cette instruction déplace le contenu d'un emplacement mémoire vers un autre emplacement mémoire en se combinant avec le contenu actuel du nouvel emplacement :

Instruction movx a, b (also written a -> b)
    OP = GetOperation(Mem[b])
    Mem[b] := OP(Mem[a], Mem[b])

L'opération effectuée est définie par la cellule mémoire destinataire. Certaines cellules sont spécialisées en plus, d'autres en multiplication, etc. Ainsi, les cellules mémoires ne sont pas de simples stockages mais couplées à une unité arithmétique et logique (ALU) configurée pour effectuer une seule sorte d'opération avec la valeur courante de la cellule. Certaines des cellules sont des instructions de flux de contrôle pour modifier l'exécution du programme avec des sauts, une exécution conditionnelle , des sous - routines , if-then-else , for-loop , etc...

Un microcontrôleur commercial à architecture déclenchée par transport a été produit, appelé MAXQ, qui masque l'inconvénient apparent d'un OISC en utilisant une « carte de transfert » qui représente toutes les destinations possibles pour les instructions de déplacement .

Cryptoleq

Processeur Cryptoleq fabriqué à NYU Abu Dhabi

Cryptoleq est un langage composé d'une instruction éponyme , capable d'effectuer des calculs à usage général sur des programmes cryptés et est un proche parent de Subleq. Cryptoleq travaille sur des cellules de mémoire continues en adressage direct et indirect, et effectue deux opérations O ₁ et O ₂ sur trois valeurs A, B et C :

Instruction cryptoleq a, b, c
    Mem[b] = O1(Mem[a], Mem[b])
    if O2(Mem[b]) ≤ 0
        IP = c
    else
        IP = IP + 3

où a, b et c sont adressés par le pointeur d'instruction, IP, avec la valeur d'adressage IP a, IP + 1 pointe vers b et IP + 2 vers c.

Dans Cryptoleq, les opérations O ₁ et O ₂ sont définies comme suit :

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

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

La principale différence avec Subleq est que dans Subleq, O ₁ ( x,y ) soustrait simplement y de x et O ₂ ( x ) est égal à x . Cryptoleq est également homomorphe à Subleq, l'inversion modulaire et la multiplication sont homomorphes à la soustraction et l'opération de O ₂ correspond au test Subleq si les valeurs étaient en clair. Un programme écrit en Subleq peut s'exécuter sur une machine Cryptoleq, ce qui signifie une rétrocompatibilité. Cryptoleq cependant, implémente des calculs entièrement homomorphes et puisque le modèle est capable de faire des multiplications. La multiplication sur un domaine chiffré est assistée par une fonction unique G qui est supposée difficile à rétro-concevoir et permet le rechiffrement d'une valeur basée sur l' opération O ₂ :

${\displaystyle G(x,y)={\begin{cases}{\tilde {0}},&{\text{if }}O_{2}({\bar {x}}){\text{ } }\leq 0\\{\tilde {y}},&{\text{autrement}}\end{cases}}}$

où est la valeur rechiffrée de y et est chiffré zéro. x est la valeur chiffrée d'une variable, qu'il s'agisse de m , et est égal à . ${\displaystyle {\tilde {y}}}$${\displaystyle {\tilde {0}}}$${\displaystyle {\bar {x}}}$${\style d'affichage Nm+1}$

L'algorithme de multiplication est basé sur l'addition et la soustraction, utilise la fonction G et n'a pas de sauts conditionnels ni de branches. Le cryptage Cryptoleq est basé sur le cryptosystème Paillier .

Voir également

• FRACTRAN
• Enregistrer la machine
• Bâche de Turing
• Ordinateur à jeu d'instructions zéro

Les références

Liens externes

• Subleq sur le wiki des langages de programmation ésotériques – interprètes, compilateurs, exemples et langages dérivés
• Reductio ad absurdum sur YouTube par Christopher Domas
• Ordinateur de laboratoire subleq - Implémentation FPGA en utilisant VHDL
• The Retrocomputing Museum – émulateur SBN et exemples de programmes
• Ordinateur de laboratoire SBN - mis en œuvre avec des circuits intégrés de la série 7400
• RSSB sur le wiki des langages de programmation ésotériques – interprètes et exemples
• Implémentation OISC 32 bits du Dr Dobb - architecture déclenchée par le transport (TTA) sur un FPGA à l' aide de Verilog
• Introduction à l'architecture MAXQ - comprend un diagramme de carte de transfert
• Emulateur OISC – version graphique
• TrapCC (les MMU Intel x86 récents sont en fait des OISC complets de Turing.)
• Simulateur SBN - simulateur et conception inspirés de l' aide illustrative au calcul de CARDboard
• Calcul à un bit à 60 Hertz - intermédiaire entre un ordinateur et une machine à états
• La machine NOR  - informations sur la construction d'un processeur avec une seule instruction
• Cryptoleq  – Référentiel de ressources Cryptoleq
• ACCHA  – L'architecture informatique Une perspective minimaliste
• DawnOS – un système d'exploitation pour l'architecture SUBLEQ
• Unileq - une variante de SUBLEQ utilisant des entiers non signés