Vous trouverez ici une description d'un modèle de calcul abstrait, appelé machine ram. Cliquez sur ce lien pour récupérer le mémento en pdf.
Introduction
Historiquement, les recherches menées autour du concept de calcul ont engendré de nombreux modèles abstraits pour en cerner les contours. Voici les plus importants :
La machine ram, acronyme de Random Access Machine — qu'il est préférable de traduire par Machine à adressage direct ou Register Adressable Memory —, a été introduit pour fournir un outil d'étude des algorithmes plus proche des ordinateurs que ne l'étaient les autres modèles de calcul. C'est un modèle de ce type qui est présenté dans ce cours.
Description schématique de la machine
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. La description schématique de cette machine est présentée ci-dessous.
Les 4 éléments constitutifs de ce modèle sont :
Le fonctionnement de la machine est rudimentaire. On charge*le chargement du programme et la saisie des données sont bien entendu virtuel sur ce modèle abstrait au préalable les instructions du programme dans le bloc programme et on saisit* les données à traiter sur la bande d'entrée. Ces données sont encodées sous formes d'entiers naturels suivant un schéma d'encodage et de décodage arbitraires.
Les instructions \(P_{\color{red}k}\) du programme sont décodées séquentiellement dans l'ordre défini par le compteur ordinal co qui contient l'adresse \(\color{red}k\) de l'instruction à décoder. Initialement co\(\;=\,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, qui rompt le déroulement séquentiel des instructions en fixant arbitrairement l'adresse de la prochaine instruction dans le compteur ordinal. C'est le mécanisme qui permet, entre autres, au programmeur de réaliser des boucles. 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.
Jeu d'instructions
Le modèle présenté ici est moins spartiate que le modèle abstrait originel, il autorise des valeurs positives ou négatives, a un jeu d'opérateurs arithmétiques plus riche ainsi que des instructions de rupture de séquence plus étendu. Il permet de se familiariser plus facilement avec le concept de modèle de calcul abstrait.
Les instructions peuvent être regroupées en 4 groupes distincts selon leur nature :
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 \(x,\) \(y\) et \(R\) et les écritures conventionnelles \(S_i\) ou S[i] selon que l'on se trouve dans un cadre mathématique ou algorithmique, pour désigner le contenu d'une telle structure à la position \(i\).
L'accumulateur, c'est-à-dire le registre \(R_0,\) joue un rôle central dans le fonctionnement de la machine ram.
Les lectures et écritures étant séquentielles, cela signifie qu'un fois une valeur lue sur la bande d'entrée (READ) ou écrite sur la bande de sortie (WRITE), la prochaine opération de lecture ou d'é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é. Par souci de concision, les instructions en tête de groupe sur fond gris servent de modèles pour celles sur fond noir qui suivent et dont seule la première déclinaison est donnée. Par exemple la décrémentation DEC n a pour autre déclinaison DEC @n.
Entrées/Sorties
READ | ACC ← x[i++] | copie une valeur de la bande d'entrée dans acc. |
WRITE | y[i++] ← ACC | copie le contenu de acc sur la bande de sortie. |
Gestion mémoire
Chargement de l'accumulateur [load]
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. |
Rangement dans les registres [store]
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]\). |
Incréments et opérations arithmétiques
Incrémentation/Décrémentation [inc|dec]
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]\). |
DEC n | R[n] ← R[n] - 1 | décrémente le contenu du registre d'adresse \(n\). |
Opérations arithmétiques [add|sub|mul|div|mod]
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. |
MUL #n | ACC ← ACC × n | multiplie la valeur \(n\) à acc. |
DIV #n | ACC ← ACC / n | quotiente acc par la valeur \(n\). |
MOD #n | ACC ← ACC % n | réduit acc modulo la valeur \(n.\) |
Ruptures de séquence
Inconditionnelles [jump|stop|nop]
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|juml|jumg]
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. |
JUMG n | IF (ACC > 0) CO ← n | saut à l'instruction \(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
Définition
La description quasi matérielle de cette machine ne doit pas masquer le fait qu'il s'agit bien d'un modèle formel de la théorie des ensembles.Dans cette théorie, une machine est confondue avec son programme, à savoir une séquence d'instructions \((P_k)_{i\in\ab{0}{r}}\) qui régissent son comportement pour toute instance \(x\) en entrée. Il y a \(36\) opérations distinctes au total si l'on intègre les différents types d'adressage des instructions concernées, absolu et indirect. On peut donc les coder avec un nombre entier dans l'intervalle \(\ab{0}{35}\). Ces instructions opèrent sur des nombres entiers signés* Dans le modèle originel c'est \(\N,\) ce qui ne limite en rien les capacités de cette machine, bien entendu., donc des éléments de \(\Z\).
Configuration d'une machine
On peut également décrire formalement le fonctionnement d'une machine ram à travers ses configurations. Une configuration est une sorte de photographie de l'état de la machine, i.e. un septuplet \((x,i,y,j,c,s,R)\) oùLa configuration initiale de la machine est fixée à \begin{equation} \label{eq:confinit} C_0:=(x,0,0^\infty,0,0,0,0^\infty) \end{equation} où \(x=(x_0,x_1,\ldots,x_{n-1})\) est l'instance à calculer et \(0^\infty\) la suite identiquement nulle. On définit alors la fonction de transition \(\delta:{\mathscr C}\rightarrow{\mathscr C}\) de l'ensemble des configurations dans lui-même qui code le passage d'une configuration à la suivante après le décodage d'une instruction. L'exécution pas à pas du programme consiste à itérer la fonction \(\delta\). La suite des configurations \((C_t)_{t\in\N}\) du programme à l'instant \(t\) définie par \(C_t:=\delta^t(C_0)\) est appelée trace du programme.
Autrement dit, la machine s'arrête si elle ne change plus de configuration. On peut à présent définir formellement ce qu'est un algorithme :
Le temps de calcul \(\tau(x)\) est donc égal au nombre total d'instructions décodées par la machine ram pour traiter l'entrée \(x\) et s'arrêter. L'espace de calcul \(\epsilon(x)\) est égal au nombre total de registres mémoire \(R_k\) utilisés durant l'exécution du programme pour traiter \(x\). Ces deux nombres apparaissent à gauche dans le simulateur.
Exemples
Moyenne arithmétique
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 ; ARRET
Les 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\).
Recherche du maximum
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
Remontée du maximum
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 !
Le fichier à charger doit contenir une instruction du programme par ligne. Chaque instruction peut éventuellement être accompagnée d'un commentaire qui commence par le caractère ;. La bande d'entrée peut être initialisée par la même occasion, si la première ligne du fichier commence par le caractère > suivi d'une liste d'entiers séparés par un espace. Par exemple > -1 12 3 0 1 rangera les entiers \(-1,\) \(12,\) \(3,\) \(0\) et \(1\) dans les \(5\) premières cellules de 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).