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 à adressage 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 programmation s'apparente aux langages d'assemblage beaucoup plus familiers des informaticiens.
Cette machine est constituée de 4 éléments principaux :
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 \(P_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écuté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'instruction d'écriture WRITE.
NB. Dans cette architecture, dite de type Harvard, le stockage du programme se fait dans une zone séparée de celle qui sontient les données et ne peut donc être modifié lors de son exécution. Dans une architecture dite de type Von Neumann (machines rast), où le code programme est placé dans la même mémoire que celle des données (au début en général), celui-ci peut donc être modifié par sa propre exécution. Les deux modèles sont équivalents.Jeu d'instructions
Les instructions peuvent être regroupées selon leur nature en 4 groupes distincts :
Pour la compréhension du jeu d'instruction et du fonctionnement de cette machine, nous décrivons symboliquement la bande d'entrée, la bande de sortie et la mémoire respectivement par les listes \(E\), \(S\) et \(R\) et l'écriture conventionnelle \(L[i]\) pour désigner le contenu d'une telle structure à la position \(i\).
Le registre \(R_0\) joue un rôle central dans le fonctionnement de la machine ram, il est appelé accumulateur et est également 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 les tables ci-dessous l'interprétation d'une instruction est écrite sous une forme algorithmique très commune juste à côté.
Entrées-sorties
READ | ACC ← E[i++] | copie une valeur de la bande d'entrée dans acc. |
WRITE | S[i++] ← ACC | copie le contenu de acc sur la bande de sortie. |
Gestion mémoire, adressage
Chargement
LOAD #n | ACC ← n | charge la valeur n dans acc. |
LOAD n | ACC ← R[n] | copie le contenu du registre d'adresse \(n\) dans acc. |
LOAD @n | ACC ← R[R[n]] | copie le contenu du registre d'adresse \(R[n]\) dans acc. |
Stockage
STORE n | R[n] ← ACC | copie le contenu de acc dans le registre d'adresse \(n\). |
STORE @n | R[R[n]] ← ACC | copie le contenu de acc dans le registre d'adresse \(R[n]\). |
Opérations arithmétiques
Décrémentation / Incrémentation
DEC n | R[n] ← R[n] - 1 | décrémente le contenu du registre d'adresse \(n\). |
DEC @n | R[R[n]] ← R[R[n]] - 1 | décrémente le contenu du registre d'adresse \(R[n]\). |
INC n | R[n] ← R[n] + 1 | incrémente le contenu du registre d'adresse \(n\). |
INC @n | R[R[n]] ← R[R[n]] + 1 | incrémente le contenu du registre d'adresse \(R[n]\). |
Opérations arithmétiques
ADD #n | ACC ← ACC + n | ajoute la valeur \(n\) à acc. |
ADD n | ACC ← ACC + R[n] | ajoute le contenu du registre d'adresse \(n\) à acc. |
ADD @n | ACC ← ACC + R[R[n]] | ajoute le contenu du registre d'adresse \(R[n]\) à acc. |
SUB #n | ACC ← ACC - n | soustrait la valeur \(n\) à acc. |
SUB n | ACC ← ACC - R[n] | soustrait le contenu du registre d'adresse \(n\) à acc. |
SUB @n | ACC ← ACC - R[R[n]] | soustrait le contenu du registre d'adresse \(R[n]\) à acc. |
MUL #n | ACC ← ACC × n | multiplie la valeur \(n\) à acc. |
MUL n | ACC ← ACC × R[n] | multiplie le contenu du registre d'adresse \(n\) à acc. |
MUL @n | ACC ← ACC × R[R[n]] | multiplie le contenu du registre d'adresse \(R[n]\) à acc. |
DIV #n | ACC ← ACC / n | quotiente acc par la valeur \(n\). |
DIV n | ACC ← ACC / R[n] | quotiente acc par le contenu du registre d'adresse \(n\). |
DIV @n | ACC ← ACC / R[R[n]] | quotiente acc par le contenu du registre d'adresse \(R[n]\). |
MOD #n | ACC ← ACC % n | réduit acc modulo la valeur \(n.\) |
MOD n | ACC ← ACC % R[n] | réduit acc modulo le contenu du registre d'adresse \(n\). |
MOD @n | ACC ← ACC % R[R[n]] | réduit acc modulo le contenu du registre d'adresse \(R[n]\). |
Ruptures de séquence
Inconditionnelles
JUMP n | CO ← n | saut à l'instruction \(n\). |
JUMP @n | CO ← R[n] | saut à l'instruction \(R[n]\). |
STOP | arrêt du programme. | |
NOP | Instruction nulle. Ne fait rien. |
Conditionnelles
JUMZ n | IF (ACC = 0) CO ← n | saut à l'instruction \(n\) si acc=0. |
JUMZ @n | IF (ACC = 0) CO ← R[n] | saut à l'instruction \(R[n]\) si acc=0. |
JUML n | IF (ACC < 0) CO ← n | saut à l'instruction \(n\) si acc<0. |
JUML @n | IF (ACC < 0) CO ← R[n] | saut à l'instruction \(R[n]\) si acc<0. |
JUMG n | IF (ACC > 0) CO ← n | saut à l'instruction \(n\) si acc>0. |
JUMG @n | IF (ACC > 0) CO ← R[n] | saut à l'instruction \(R[n]\) si acc>0. |
L'instruction NOP qui ne fait rien (no operation) permet, par exemple, en l'intercalant entre certaines instructions du code, de recaler correctement les instructions de saut en cas de modification du code sans avoir à changer les adresses de saut.
Modèle abstrait
La description quasi physique 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. Dans ce cadre abstrait, une machine est identifiée et caractérisée par son programme, à savoir la séquence d'instructions qui détermine son comportement pour une entrée donnée. Ici nous considérons le modèle borné, c'est-à-dire celui dans lequel les entiers manipulés sont bornés. Comme il y a \(36\) opérations distinctes au total ‐ en intégrant les différents types d'adressage pour les instructions concernées, absolu et indirect ‐ et elles opérent sur des entiers relatifs pour plus de souplesse. Un programme est donc une séquence de couples \((op,x)\) de \(\ab{0}{35}\times{\Z}\). On peut à présent résumer cette machine ram à la définition suivante :
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'algorithme s'arrête, autrement dit cette suite est constante à partir d'un certain rang. Si \(x=x_0,x_1,\ldots,x_{n-1}\) désigne une entrée et \(P\) un programme de la machine ram qui s'arrête pour l'entrée \(x\), on note ce rang \begin{equation} \eta(x)=\min\{N\in{\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 \(x\) et s'arrêter. Ce modèle nous permet à présent de définir précisément ce qu'est un algorithme.
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\) contient le nombre de valeurs non-nulles lues et 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 #9 ADD 2 ; ACC ← ACC + R[2] STORE 2 ; R[2] ← ACC INC 1 ; R[1] ← R[1] + 1 JUMP 3 ; SAUTER A L'INSTRUCTION #3 LOAD 2 ; ACC ← R[2] DIV 1 ; ACC ← ACC / R[1] WRITE ; SORTIE[j++] ← ACC STOP ; ARRETLes instructions #0, #1 et #2 initialisent acc et les registres \(R_1\) et \(R_2\) à \(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 convention 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. Une valeur négative sert 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.
L'algorithme procède en trois étapes:
LOAD #6 ; ACC ← 6 (IDX DU 1ER REGISTRE DE L) STORE 4 ; R[4] ← ACC (1ER IDX DE L DANS R[5]) READ ; ACC ← e[i++] (LECTURE DE LA LISTE) STORE @4 ; R[R[4]] ← ACC (R[IDX] ← L[i] POUR IDX = i + 6) INC 4 ; R[4] ← R[4] + 1 (IDX ← IDX + 1) JUMG 2 ; SI ACC > 0 POURSUIVRE LECTURE DE L JUMZ 2 ; SI ACC = 0 POURSUIVRE LECTURE DE L LOAD 4 ; ON VA TESTER SI |L| < 2 SUB #8 ; ON SOUSTRAIT 8 JUML 28 ; SI |L| < 2 => AFFICHER LA LISTE LOAD #5 ; ACC ← 5 PREINITIALISATION STORE 4 ; R[4] ← 5 DE R[4] LOAD #6 ; ACC ← 6 PREINITIALISATION STORE 5 ; R[5] ← 6 DE R[5] INC 4 ; R[4]++ i ← i + 1 INC 5 ; R[5]++ i + 1 ← i + 2 LOAD @5 ; ACC ← R[5] JUML 28 ; L[i] < 0 => FIN LISTE => ECRITURE SUB @4 ; ACC ← L[i+1] - L[i] JUMG 14 ; SI L[i+1] - L[i] > 0 => i++ JUMZ 14 ; SI L[i+1] - L[i] = 0 => i++ LOAD @4 ; SINON ACC ← L[i] STORE 1 ; R[1] ← L[i] LOAD @5 ; ACC ← L[i+1] STORE @4 ; L[i] ← L[i+1] LOAD 1 ; ACC ← R[1] STORE @5 ; L[i+1] ← L[i] ECHANGE L[i] ↔ L[i+1] TERMINE JUMP 14 ; ON PASSE AU SUIVANT LOAD #6 ; ACC ← 6 (ON CHARGE L'INDEX DU DEBUT DE LA LISTE) STORE 4 ; R[4] ← 6 (ON LE RANGE DANS R[4] = IDX) LOAD @4 ; ACC ← R[R[4]] (ON CHARGE R[IDX]) JUML 35 ; SI ACC < 0 => FIN DE LISTE ON ARRETE WRITE ; SINON ON ECRIT INC 4 ; IDX ← IDX + 1 (ELEMENT SUIVANT DE LA LISTE) JUMP 30 ; ON RECOMMENCE STOP ; FIN DU PROGRAMME
Travaux pratiques
Le simulateur javascript vous permet d'étudier le comportement de la machine avec vos programmes. L'intervalle des valeurs autorisées est fixé à \([-16383,16384]\). Vous écrirez vos programmes dans un fichier texte avec votre éditeur préféré en codant une instruction par ligne. Tout ce qui suit le symbole ; est ignoré, donc commentez impérativement vos programmes !
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).