Remarque : Le premier exercice du sujet zéro évoque fortement le jeu robosomes.
RISC
Le premier microprocesseur (CPU) commercialisé fut le Intel 4004 bientôt suivi par le Intel 8008. Ce dernier comprenait 48 instructions ce qui le classe dans la catégorie « complex instruction set computer » (en abrégé, CISC), le nombre d’instructions de la plupart des microprocesseurs ayant eu tendance à croître au cours du temps, pour améliorer la puissance de calcul.
Dans le monde de l’informatique embarquée (y compris les consoles de jeu) et des serveurs informatique, la tendance s’est amorcée dans les années 1980 vers le reduced instruction set computer (en abrégé, RISC). En particulier, Acorn Computers se lance rapidement dans le Acorn RISC Machines à base de processeurs RISC, et de fait l’architecture ARM est encore très présente, notamment dans les smartphones...
Noter que le RISC-V avec ses 63 instructions ne semble pas plus réduit que le vieux Intel 8008 aux 48 instructions. La réduction du jeu d’instructions est la conséquence de l’architecture du processeur. Marvin Minsky avait réussi avec les machines à registre à descendre à deux instructions (incrémentation et décrémentation avec branchement) seulement.
Mais à l’extrême, dès la fin des années 1980, Farhad Mavaddat et Behrooz Parhami ont imaginé un processeur n’ayant qu’une seule instruction ! En voici la description :
Un ordinateur à jeu d’instruction unique (OISC en anglais) a ceci de fascinant qu’il ne comprend qu’une seule instruction, ce qui rend sa programmation quelque peu monotone. David Naccache a trouvé des applications cryptographiques à ce genre de machine. Un exemple important est celui où l’unique instruction consiste à
- lire en mémoire les nombres A, B et C pointés par le pointeur de programme (en P, P+1 et P+2)
- arrêter le calcul si un des entiers A, B et C est négatif
- sinon,
- soustraire (SUBtract) A à B
- si le résultat de la soustraction est négatif ou nul (Less or EQual) forcer le contenu de P à C, sinon incrémenter P
On montre que ce langage de programmation est Turing-complet. Par exemple on peut simuler les opérations des machines à registre avec une machine subleq pour prouver ce fait. C’est essentiellement l’objet de l’exercice « langages de programmation » du sujet zéro.
Dans cet article, on va faire un peu l’inverse, en simulant en JavaScript un OISC qui sera programmé dans des pages html. Un clic sur une copie d’écran d’une de ces pages html permet de manipuler en ligne l’OISC considéré.
L’exemple du sujet zéro est celui-ci :
Et voici le corrigé, en respectant les numéros des questions :
Question 21) Décrire les étapes de l’exécution du programme suivant et donner le contenu de la mémoire à l’issue de cette exécution :
Question 22) Écrire en Python une fonction OISC(memoire, P) qui permet de simuler un tel ordinateur, en considérant que l’on n’utilise jamais que les 1000 premières cellules de la mémoire. Elle prend deux paramètres :
-
memoireest une liste de 1000 éléments, qui représente l’état initial de la mémoire. -
Pest la valeur du pointeur d’instruction.
La fonction modifie la mémoire en appliquant les règles et renvoie une liste qui représente l’état de cette mémoire en fin d’exécution (quand cette exécution se termine).
Cette question est laissée en exercice, sauf le début qui devrait ressembler à ceci :
def OISC(memoire, P):
...
return memoireQuestion 23) Écrire un programme sous la forme ci-dessus, tel que si la cellule 0 contient le nombre x et la cellule 1 le nombre y au début de l’exécution, alors la cellule 0 contient x - y à la fin de l’exécution.
Question 24) Écrire un programme, tel que si la cellule 0 contient le nombre x et la cellule 1 le nombre y au début de l’exécution, alors la cellule 0 contient x + y à la fin de l’exécution.
Corrigé
Le principe est qu’additionner 1 revient à soustraire -1 :
Question 25 Écrire un programme tel que si la cellule 0 contient le nombre x et la cellule 1 le nombre y au début de l’exécution, alors la cellule 0 contient le nombre y et la cellule 1 contient le nombre x à la fin de l’exécution.
Corrigé
Algorithme (avec deux cellules a et b initialement nulles) :
- soustraire x à b,
- soustraire y à a,
- vider x et y (les soustraire à eux-mêmes),
- soustraire a à x,
- soustraire b à y.
Question 26) Écrire un programme, tel que si la cellule 0 contient le nombre x et la cellule 1 le nombre y au début de l’exécution, alors la cellule 0 contient max(x, y) à la fin de l’exécution.
Corrigé
Algorithme :
- on commence par mettre -x et -y dans des cellules initialement vides,
- on soustrait y à x :
- si le résultat est positif, c’est que le maximum est x, il est déjà en place, on termine alors ;
- sinon, c’est que le maximum est y, on vide alors la cellule 0 puis on lui soustrait -y.
Question 27) Écrire un programme tel que, si la cellule 0 contient le nombre x et la cellule 1 le nombre y au début de l’exécution, alors la cellule 0 contient x×y à la fin de l’exécution. On suppose que x et y sont tous deux strictement positifs.
Corrigé
L’algorithme a été vu dans l’article sur les machines à registre : la multiplication est une addition itérée, donc
- on soustrait 1 à y tant que c’est possible,
- on soustrait également -x à une cellule valent initialement 0
- quand y est devenu négatif, la cellule en question vaut x×y
Le programme en subleq est aussi dans ce document :
Question 29) Cet ordinateur peut-il faire tous les calculs que peut faire un ordinateur classique ? Expliquer.
Cet ordinateur est capable de simuler
- une boucle while
- l’addition, la soustraction, la multiplication
- la comparaison
Il est donc Turing-complet, comme le sont les machines de Post qui sont d’ailleurs simulables en subleq.
Commentaires