Ordinateur à jeu d'instruction unique
# Ordinateur à jeu d'instruction unique

Un ordinateur à un jeu d'instruction unique (one-instruction set computer, OISC), parfois appelé processeur à jeu d'instructions réduit ultime (ultimate reduced instruction set computer URISC), est une machine abstraite qui n'utilise qu'une seule instruction – évitant le besoin d'un code opération en langage machine. Avec un choix judicieux pour l'instruction unique et des ressources infinies, 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.

## Architecture des machines

Dans un modèle Turing-complet, chaque emplacement 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 une seule 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 pouvoir exécuter n'importe quel algorithme et interpréter n'importe quelle autre machine universelle) car copier des bits peut modifier conditionnellement le code qui sera ensuite exécuté.

**l'ordinateur TOGA**

Une autre machine, appelée (en)Toga Computer , inverse un bit 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 embranche sur b ((en) TOGgle a And branch to 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 des tables de saut prédéfinies dans la mémoire.

### 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, add and branch if less than or equal to zero)
* décrémentation (DJN, Decrement and branch (Jump) if Nonzero)
* incrément (P1eq, Plus 1 and branch if equal to another value)
* soustraction (subleq, subtract and branch if less than or equal to $zero)^,$
* soustraction lorsque cela est possible (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 code opération 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 Turing-complet.

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 ((en) Decrement and jump if not zero, 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 de Subleq .

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

L'instruction SBNZ a, b, c, d ((en) "subtract and branch if not equal to zero" " soustraire et brancher s'il n'est pas égal à 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 ((en) "subtract and branch if less than or equal to zero" " soustraire et brancher 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 à l'adresse c (si le résultat est positif, l'exécution passe à l'instruction suivante dans la séquence).

### Soustraire et brancher si négatif

Les subneg ((en) "subtract and branch if negative" " soustraire et branchement si négatif "), également appelée SBN, est défini de la même manière que subleq (cette fois, strictement négatif)

### 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 endroit 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 subneg 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.

### Inverser la soustraction et sauter si emprunter

Dans une instruction de soustraction inverse et de saut si emprunt ((en) reverse subtract and skip if borrow 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.

### Architecture déclenchée par le transport

Une architecture déclenchée par le transport utilise uniquement l'instruction de déplacement move, 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.

### Cryptoleq

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_1$ et $O_2$ sur trois valeurs A, B et C :

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_1$ et $O_2$ sont définies comme suit :

    ${\begin{array}{lcl}O_{1}(x,y)&=&x_{N^{2}}^{-1}y\,{\bmod {\,}}N^{2}\end{array}}$
    ${\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_1(x,y)$ soustrait simplement y de x et $O_2(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_2$ 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 crypté est assistée par une fonction unique G qui est supposée difficile à rétroconcevoir et permet le recryptage d'une valeur basée sur l'opération $O_2$

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

où ${\tilde {y}}$ est la valeur recryptée de y et ${\tilde {0}}$ est chiffré zéro. x est la valeur chiffrée d'une variable, soit m, et ${\bar {x}}$ équivaut à 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
* Machine à registres illimités
* Turing tarpit
* (en)en:Zero_instruction_set_computer

## Les références

* 1 2 William F. Gilreath et Laplante, Phillip A., Computer Architecture: A Minimalist Perspective, Springer Science+Business Media, 2003 (ISBN 978-1-4020-7416-5, lire en ligne [archive du 13 juin 2009]) 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).
* ↑ F. Mavaddat et Parhami, B., « URISC: The Ultimate Reduced Instruction Set Computer », Manchester University Press, vol. 25, $n^o$ 4,‎ octobre 1988, p. 327–334 (DOI 10.1177/002072098802500408, S2CID 61797084, lire en ligne, consulté le 4 octobre 2010) This paper considers "a machine with a single 3-address instruction as the ultimate in RISC design (URISC)". Without giving a name to the instruction, it describes a SBN OISC and its associated assembly language, emphasising that this is a universal (i.e., Turing-complete) machine whose simplicity makes it ideal for classroom use.
* 1 2 Oleg Mazonka, "Bit Copying: The Ultimate Computational Simplicity", Complex Systems Journal 2011, vol. 19, N3, pp. 263–285
* ↑ « Addleq », Esolang Wiki (consulté le 16 septembre 2017)
* ↑ « DJN OISC », Esolang Wiki (consulté le 16 septembre 2017)
* ↑ « P1eq », Esolang Wiki (consulté le 16 septembre 2017)
* ↑ Mazonka, « SUBLEQ » [archive du 29 juin 2017], octobre 2009 (consulté le 16 septembre 2017)
* ↑ « Subleq », Esolang Wiki (consulté le 16 septembre 2017)
* ↑ Z. A. Melzak, « An informal arithmetical approach to computability and computation », Bulletin canadien de mathématiques, vol. 4, $n^o$ 3,‎ 1961, p. 279–293 (DOI 10.4153/CMB-1961-031-9)
