Algorithmique ii - La machine RAM

Vous trouverez ici une brève description d'un modèle de machine de type ram et un simulateur qui vous permettra de tester vos propres programmes. Cliquez sur ce lien pour récupérer le mémento en pdf.

Description physique de la machine

La machine ram, acronyme de Random Access Machine (qu'il faut traduire par Machine à ad­res­sa­ge direct) ou encore Register Adressable Memory, est un modèle abstrait de calcul introduit dans les années 60. Ce modèle avait pour objectif de fournir un outil d'étude des algorithmes plus proche des ordinateurs que ne l'étaient les modèles abstraits déjà proposés comme les fonctions récursives, le λ-calcul ou encore la machine de Turing. Même si l'écriture d'algorithmes sur la machine ram reste fastidieuse, son langage de pro­gram­ma­tion s'apparente aux langages d'assemblage beau­coup plus fa­mi­liers des informaticiens.

Description schématique d'une machine RAM.

Cette machine est constituée de 4 éléments principaux :

  1. Une bande d'entrée qui contient des entiers relatifs bornés. Elle est accessible uniquement en lecture de manière séquentielle ;
  2. Une bande de sortie qui contient des entiers relatifs bornés. Elle accessible uniquement en écriture de manière séquentielle ;
  3. Une mémoire indexée qui contient des entiers relatifs bornés. Elle est accessible directement à l'aide d'une adresse rangée dans un registre particulier appelé registre de sélection mémoire ;
  4. Un programme, i.e. une séquence d'instructions qui sont des couples (opérateur, opérande) exécutées de manière séquentielle.

Son fonctionnement est rudimentaire. On charge au préalable les instructions du programme dans le bloc programme (ce chargement est bien entendu virtuel, il s'agit d'un modèle abstrait) et on saisit (toujours virtuellement) les données à traiter sur la bande d'entrée. Ces données sont encodées sous formes d'entiers bornés suivant un schéma d'encodage arbitraire. La borne pour ces entiers et le schéma d'encodage, comme celui de décodage, sont arbitraires. Les instructions \(I_k\) du programme sont décodées séquentiellement, pour cela, un registre particulier de la machine appelé compteur ordinal (co sur le schéma ci-dessus qui joue le rôle de l'indice \(k\)) contient précisément l'adresse du registre contenant l'instruction à décoder, initialement 0. Après qu'une instruction a été décodée, le compteur ordinal est incrémenté d'une unité pour passer à l'instruction suivante du programme sauf si l'instruction est une rupture de séquence, auquel cas son rôle est justement de modifier la valeur du compteur ordinal. La machine arrête le cycle de décodage dès que l'instruction STOP a été exé­cu­tée. Les données à traiter peuvent être chargées dans la mémoire à l'aide de l'instruction de lecture READ et les résultats des calculs sont renvoyés à l'utilisateur sur la bande de sortie à l'aide de l'ins­truc­tion d'écriture WRITE.

Jeu d'instructions

Les instructions peuvent être regroupées selon leur nature en 4 groupes distincts :

  1. Entrées/sorties;
  2. Mémoire, adressage;
  3. Opérations arithmétiques;
  4. Ruptures de séquence.

Pour la compréhension du jeu d'instruction et du fonctionnement de cette machine, nous notons \(E\) (resp. \(S\)) le registre qui contient l'adresse de la prochaine cellule de la bande d'entrée (resp. sortie) à lire (resp. écrire). Nous utilisons la notation classique \(R[n]\) pour désigner le contenu du \(n\)-ème registre de la mémoire \(R\) et nous ferons de même pour la bande d'entrée et de sortie. Le registre \(R[0]\) qui joue un rôle central dans le fonctionnement de la machine ram, il est appelé accumulateur et est noté acc :

Les lectures et écritures étant séquentielles, cela signifie qu'un fois une valeur lue sur la bande d'entrée avec l'instruction READ (resp. WRITE), la prochaine lecture (resp. écriture) se fera sur la cellule suivante sans retour possible. Dans la table ci-dessous l'interprétation d'une instruction est écrite sous une forme algorithmique très commune juste à côté de l'instruction.

Entrées-sorties

READ ACC ← E[i++] Lecture: lit un entier sur la bande d'entrée et le range dans l'acc.
WRITE S[j++] ← ACC Écriture: écrit le contenu de l'acc sur la bande de sortie.

Mémoire, adressage

LOAD #n ACC ← n Absolu: charge la valeur n dans l'acc.
LOAD n ACC ← R[n] Direct: charge le contenu du registre n dans l'acc.
LOAD @n ACC ← R[R[n]] Indirect: charge le contenu du registre R[n] dans l'acc.
STORE n R[n] ← ACC Direct: range le contenu de l'acc dans le registre n.
STORE @n R[R[n]] ← ACC Indirect: range le contenu de l'acc dans le registre R[n].

Opérations arithmétiques

DEC n R[n] ← R[n] - 1 Décrément: décrémente le contenu du registre n.
DEC @n R[n] ← R[R[n]] - 1 Décrément ind.: décrémente le contenu du registre R[n].
INC n R[n] ← R[n] + 1 Incrément: incrémente le contenu du registre n.
INC @n R[n] ← R[R[n]] + 1 Incrément ind.: incrémente le contenu du registre R[n].
ADD #n ACC ← ACC + n Addition abs.: Ajoute la valeur n à l'acc.
ADD n ACC ← ACC + R[n] Addition dir.: Ajoute le contenu du registre n à l'acc.
ADD @n ACC ← ACC + R[R[n]] Addition indir.: Ajoute le contenu du registre R[n] à l'acc.
SUB #n ACC ← ACC - n Soustraction abs.: Soustrait la valeur n à l'acc.
SUB n ACC ← ACC - R[n] Soustraction dir.: Soustrait le contenu du registre n à l'acc.
SUB @n ACC ← ACC - R[R[n]] Soustraction indir.: Soustrait le contenu du registre R[n] à l'acc.
MUL #n ACC ← ACC × n Produit abs.: Multiplie la valeur n à l'acc.
MUL n ACC ← ACC × R[n] Produit dir.: Multiplie le contenu du registre n à l'acc.
MUL @n ACC ← ACC × R[R[n]] Produit indir.: Multiplie le contenu du registre R[n] à l'acc.
DIV #n ACC ← ACC / n Quotient abs.: Quotiente l'acc par n.
DIV n ACC ← ACC / R[n] Quotient dir.: Quotiente l'acc par le contenu du registre n.
DIV @n ACC ← ACC / R[R[n]] Quotient indir.: Quotiente l'acc par le contenu du registre R[n].
MOD #n ACC ← ACC / n Modulo abs.: Réduit l'acc modulo n.
MOD n ACC ← ACC / R[n] Modulo dir.: Réduit l'acc modulo le contenu du registre n.
MOD @n ACC ← ACC / R[R[n]] Modulo indir.: Réduit l'acc modulo le contenu du registre R[n].

Ruptures de séquence

JUMP n CO ← n Saute à l'instruction n.
JUMZ n IF (ACC = 0) CO ← n Saute à l'instruction n si acc = 0.
JUML n IF (ACC < 0) CO ← n Saute à l'instruction n si acc < 0.
JUMG n IF (ACC > 0) CO ← n Saute à l'instruction n si acc > 0.
STOP Arrêt du programme.

Modèle abstrait

La description schématique de cette machine ne doit pas masquer le fait qu'il s'agit bien d'un modèle abstrait, on peut parfaitement le définir dans le langage de la théorie des ensembles. Une machine est caractérisée par une base \(B\) limitant la taille des entiers sur la bande d'entrée et dans la mémoire, et son programme. Il y a \(31\) opérations distinctes au total et elles opérent sur des entiers, un programme est donc une séquence de couples \((op,x)\) de \([0,30]\times{\mathbf Z}\). On peut résumer cette machine ram à la définition suivante :

Une machine ram est un couple \((B,P)\) où

On peut également décrire le fonctionnement d'une machine ram à travers ses configurations. Une configuration est un sexuplet \((E,i,S,j,co,R)\) où \(i\), \(j\) et \(co\) sont des entiers naturels, \(E\), \(S\) et \(R\) sont des suites à valeur dans un intervalle \([a,b]\) de cardinal \(B\). La configuration initiale de la machine est fixée à \(C_0:=(x,0,0^\infty,0,0^\infty)\) où \(x\) désigne la suite codant les données à traiter et \(0^\infty\) la suite identiquement nulle. On peut alors définir une fonction de transition \(\delta:\mathcal C\rightarrow\mathcal C\) de l'ensemble des configurations dans lui-même et qui décrit comment l'on passe d'une configuration à la suivante après le décodage d'une instruction. L'exécution du programme consiste à itérer la fonction \(\delta\) pour obtenir la suite des configurations \(C_n:=\delta^n(C_0)\).

Cette suite est convergente si l'al­go­ri­thme s'arrête, autrement dit cette suite est constante à partir d'un certain rang. Si \(e=e_0,e_1,\ldots,e_{n-1}\) désigne une entrée et \(A\) un programme de la machine ram qui s'arrête pour l'entrée \(e\), on note ce rang \begin{equation} \eta(e)=\min\{N\in{\mathbf N}\mid \forall n > N,\ C_n=C_N\} \end{equation} Il s'agit tout simplement du nombre total d'instructions décodées par la machine ram pour traiter l'entrée \(e\) et s'arrêter. Ce modèle nous permet à présent de définir précisément ce qu'est un al­go­ri­thme.

On appelle algorithme un programme de la machine ram qui s'arrête.

Exemples

Ce premier algorithme que vous pouvez charger sur le simulateur, calcule la partie entière de la moyenne arithmétique des valeurs en entrée. Par convention la valeur nulle sert de marqueur pour la fin des données à lire sur la bande d'entrée. Le registre \(R_1\) contiendra le nombre de valeurs non-nulles lues, le registre \(R_2\) la somme des valeurs non-nulles lues.

LOAD #0     ; ACC ← 0
STORE 1     ; R[1] ← ACC   
STORE 2     ; R[2] ← ACC   
READ        ; ACC ← ENTREE[i++]
JUMZ 9      ; SI ACC = 0 SAUTER A L'INSTRUCTION #8
ADD 2       ; ACC ← ACC + R[2]
STORE 2     ; R[2] ← ACC
INC 1       ; R[1] ← R[1] + 1
JUMP 3      ; SAUTER A L'INSTRUCTION #2
LOAD 2      ; ACC ← R[2]
DIV 1       ; ACC ← ACC / R[1]
WRITE       ; SORTIE[j++] ← ACC
STOP        ; ARRET
Les instructions #0, #1 et #2 initialisent les registres \(R_1\leftarrow 0\) et \(R_2\leftarrow 0\). Les instructions #3 à #8 constituent la boucle de lecture et additionnent les valeurs non-nulles de la bande d'entrée dans le registre \(R_2\).

L'algorithme suivant cherche la plus grande valeur parmi celles qui sont fournies en entrée. Par con­ven­tion la valeur nulle sert de marqueur pour la fin des données à lire sur la bande d'entrée. Le registre \(R_1\) sert à mémoriser la plus grande valeur courante et le registre \(R_2\) permet de conserver la dernière valeur lue. On suppose que la liste contient au moins une valeur, il y a donc au moins deux cellules de la bande d'entrée qui sont utilisées.

READ        ; ACC ← ENTREE[i++]
STORE 1     ; R[1] ← ACC
READ        ; ACC ← ENTREE[i++]
JUMZ 11     ; SI ACC = 0 SAUTER A L'INSTRUCTION #11
STORE 2     ; R[2] ← ACC
LOAD 1      ; ACC ← R[1]
SUB 2       ; ACC ← ACC - R[2]
JUMG 2      ; SI (R[2] - R[1] > 0) SAUTER A L'INSTRUCTION #2
LOAD 2      ; ACC ← R[2]
STORE 1     ; R[1] ← ACC
JUMP 2      ; SAUTER A L'INSTRUCTION #2
LOAD 1      ; ACC ← R[1]
WRITE       ; SORTIE[j++] ← ACC
STOP        ; ARRET

Ce troisième algorithme prend en entrée une liste de valeurs et fait remonter la plus grande à la fin de la liste. La valeur 0 sert encore une fois de balise de fin de lecture. Le principe général est simple, on compare les valeurs contiguës deux-à-deux dans l'ordre de lecture de la liste en les permutant si nécessaire, ainsi à la fin du parcours la plus grande valeur est en fin de liste. Par exemple, si la bande d'entrée contient les valeurs \(3,1,6,2,5,1,0\), la bande de sortie contiendra la séquence \(1,3,2,5,1,6\). Il s'agit du principe sous-jacent du tri à bulles.

Dans un premier temps, l'algorithme lit les toutes les valeurs de la bande d'entrée et range les \(n\) valeurs non-nulles dans des registres consécutifs de la mémoire à partir du registre \(R_5\). Dans un deuxième temps, l'algorithme fait les \(n-1\) comparaisons \(R_i\leq R_{i+1}\) pour \(i\in[5,n+3]\) et permute le contenu des registres si nécessaire. Dans un troisième et dernier temps, l'algorithme écrit les valeurs contenus dans les registres mémoire \(R_5\) à \(R_{n+4}\) sur la bande de sortie.

Les registres \(R_0\) (accumulateur) et \(R_1\) serviront pour les calculs et les registres 2 à 4 seront utilisés pour:

Phase de lecture : les ins­truc­tions #0 à #3 initialisent les registres \(R_2\leftarrow 0\) et \(R_4\leftarrow 5\). Les ins­truc­tions #2 à #9 constituent la boucle de lecture des valeurs de la bande d'entrée, le registre \(R_2\) est incrémenté pour déterminer combien de valeurs non-nulles auront été lues. L'ins­truc­tion #5 teste si la valeur lue est nulle et détourne le programme à l'ins­truc­tion #10 qui débute la phase 2.

Phase d'écriture : les ins­truc­tions #31 à #35 réinitialisent les registres \(R_2\leftarrow n\) et \(R_4\leftarrow 5\). Les ins­truc­tions #36 à #42 constituent la boucle d'écriture de la mémoire vers la bande de sortie.

Phase de calcul : l'ins­truc­tion #16 teste s'il y a encore des comparaisons à faire entre les registres \(R_{i}\) et \(R_{i+1}\). Dans ce cas, on soustrait les valeurs des deux registres et l'ins­truc­tion #19 teste s'il y a lieu de faire la permutation (rôle des ins­truc­tions #21 à #26). Sinon on passe à la phase d'écriture.

LOAD #0     ; ACC ← 0
STORE 2     ; R[2] ← ACC
LOAD #5     ; ACC ← 5
STORE 4     ; R[4] ← ACC
READ        ; ACC ← ENTREE[i++]
JUMZ 10     ; SI ACC = 0 SAUTER A L'INSTRUCTION #10
STORE @4    ; R[R[4]] ← ACC
INC 4       ; R[4] ← R[4] + 1
INC 2       ; R[2] ← R[2] + 1
JUMP 4      ; SAUTER A L'INSTRUCTION #4
DEC 2       ; R[2] ← R[2] - 1
LOAD #5     ; ACC ← 5
STORE 3     ; R[3] ← ACC
STORE 4     ; R[4] ← ACC
INC 4       ; R[4] ← R[4] + 1
LOAD 2      ; ACC ← R[2]
JUMZ 31     ; SI ACC = 0 SAUTER A L'INSTRUCTION #31
LOAD @4     ; ACC ← R[R[4]]
SUB @3      ; ACC ← ACC - R[R[3]]
JUML 21     ; SI ACC < 0 SAUTER A L'INSTRUCTION #21
JUMP 27     ; SAUTER A L'INSTRUCTION #27
LOAD @4     ; ACC ← R[R[4]]
STORE 1     ; R[1] ← ACC
LOAD @3     ; ACC ← R[R[3]]
STORE @4    ; R[R[4]] ← ACC
LOAD 1      ; ACC ← R[1]
STORE @3    ; R[R[3]] ← ACC
INC 3       ; R[3] ← R[3] + 1
INC 4       ; R[4] ← R[4] + 1
DEC 2       ; R[2] ← R[2] - 1
JUMP 15     ; SAUTER A L'INSTRUCTION #15
LOAD 4      ; ACC ← R[4]
SUB #5      ; ACC ← ACC - 5
STORE 2     ; R[2] ← ACC
LOAD #5     ; ACC ← 5
STORE 4     ; R[4] ← ACC
LOAD 2      ; ACC ← R[2]
JUMZ 43     ; SI ACC = 0 SAUTER A L'INSTRUCTION #43
LOAD @4     ; ACC ← R[R[4]]
WRITE       ; S[j++] ← ACC
INC 4       ; R[4] ← R[4] + 1
DEC 2       ; R[2] ← R[2] - 1
JUMP 36     ; SAUTER A L'INSTRUCTION #36
STOP        ; ARRET

Travaux pratiques

Le simulateur javascript vous permet d'étudier le comportement de la machine avec vos pro­gram­mes. L'intervalle des valeurs autorisées est fixé à \([-256,255]\). Vous écrirez vos programmes dans un fichier texte avec votre éditeur préféré en codant une ins­truc­tion par ligne. Tout ce qui suit le symbole ; est ignoré, donc commentez impérativement vos programmes !

Écrivez un algorithme sur la machine ram qui additionne tous les nombres de la bande d'entrée et qui écrit le résultat sur la bande de sortie. La sommation doit s'arrêter dès qu'une valeur nulle est lue sur la bande d'entrée.

Modifiez l'algorithme précédent de manière à afficher également le nombre de termes qui auront été additionnés (à l'exception de la première valeur nulle rencontrée lors de la lecture de la bande d'entrée).

Écrivez un algorithme qui calcule la factorielle du premier nombre de la bande d'entrée. Quel est la valeur entière la plus grande que votre algorithme est capable de traiter ? Modifier votre algorithme pour qu'il ne traite que les valeurs possibles. Peut-on réellement considérer que cet algorithme calcule la factorielle?
Écrivez un algorithme qui calcule la plus petite valeur présente sur la bande d'entrée ainsi que son ordre (sa position sur la bande d'entrée). La valeur nulle sera utilisée pour indiquer la fin de la lecture.
Écrivez l'algorithme du TriSélection sur la machine ram. On supposera que les valeurs à trier sont toutes positives, la première valeur négative rencontrée indique la fin de la liste à trier. Estimez la complexité de cet algorithme.