La machine RAM

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 :

  1. \(\lambda\)-calcul. Alonzo Church, "Set of Postulates for the Foundation of Logic", 1932. Cet article pose les bases du \(\lambda\)-calcul à la base des langages fonctionnels modernes comme Ocaml par exemple.
  2. Machine de Turing : Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", 1936. Cet article fondateur définit le modèle qui porte aujourd'hui le nom de l'auteur et dans lequel il explore les limites de la calculabilité.
  3. Fonctions récursives. Alonzo Church, "An Unsolvable Problem of Elementary Number Theory", 1936. Cet article introduit la notion de fonction récursive. C'est l'un des piliers de la théorie de[6~ la calculabilité.
  4. Machines de Post : Emil Post, "Finite Combinatory Processes – Formulation 1", 1936. Cet article propose un modèle de calcul équivalent à celui d'Alan Turing.
  5. Automates finis : Stephen Kleene, "Representation of Events in Nerve Nets and Finite Automata", 1956. L'auteur démontre que tout langage reconnu par un automate fini peut être décrit par une expression régulière, établissant ainsi un lien fondamental entre ces deux concepts. Ce résultat, connu sous le nom de théorème de Kleene, est une pierre angulaire de la théorie des langages en informatique.
  6. Automates à pile : Noam Chomsky, "Three Models for the Description of Language", 1956. L'auteur établit un lien entre les automates à pile et les grammaires hors-contexte. Il a eu une influence majeure en théorie des langages.
  7. Machine RAM : John C. Shepherdson et Howard E. Sturgis, "Computability of Recursive Functions", 1963. Les auteurs montrent que ce modèle est équivalent au modèle de la machine de Turing. Sa structure étant bien plus proche des architectures réelles des ordinateurs, elle est plus adaptée à l'étude de la complexité algorithmique.
  8. Machines à registres : Marvin Minsky, "Computation: Finite and Infinite Machines", 1967. Cet ouvrage explore les machines à registres comme une alternative aux machines de Turing.

La machine ram, acronyme de Random Access Machine — qu'il est préférable de traduire par Machine à ad­res­sa­ge 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 pro­gram­ma­tion s'apparente aux langages d'assemblage beau­coup plus fa­mi­liers des informaticiens. La description schématique de cette machine est présentée ci-dessous.

◁
⇱
▷
⭮
0
0
0
Aucun programme
◁
⇱
▷
△
⇱
▽
►
◼
1
⭮
−
+

HEX
DEC
Schéma de la machine RAM. le simulateur.

Les 4 éléments constitutifs de ce modèle sont :

  1. Une BANDE D'ENTRÉE divisée en cellules contenant des entiers \(x_i\) codant une instance \(\color{yellow}x\). La machine n'accède aux valeurs \(x_i\) des cellules qu'en lecture et séquentiellement ;
  2. Une BANDE DE SORTIE divisée en cellules contenant des entiers \(y_j\) codant le résultat \(\color{#44F}y\) du calcul. La machine n'accède aux valeurs \(y_j\) des cellules qu'en écriture et séquentiellement ;
  3. Un PROGRAMME \(P,\) i.e. une séquence d'instructions \((P_k)_{k\in\ab{0}{t}}\) codées par des couples \((code, adr)\) et indexées par le compteur ordinal CO contenant la valeur \(k\) de l'instruction \(P_k\) à exécuter.
  4. Une MÉMOIRE \(R\) composée de registres \(R_q\) contenant des entiers, accessibles directement via leurs adresses \(q\) rangées dans le registre de sélection mémoire SM. Le premier registre \(R_0\) en haut de la mémoire joue le rôle d'accumulateur ACC.

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é­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.

Dans cette architecture, dite de type Harvard, le stockage du programme se fait dans une zone séparée de celle qui contient les données, il ne peut donc pas être modifié lors de son exécution. Dans une architecture de type Von Neumann, où le code programme est placé dans la même mémoire que celle des données (machines RAST), celui-ci peut donc être modifié par sa propre exécution. On montre que les deux modèles sont équivalents.

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 :

  1. Entrées/sorties ;
  2. Gestion 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 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.

  1. Toute instruction de lecture ou d'écriture opère sur ce registre, il est le passage obligé de la bande d'entrée vers la mémoire ou réciproquement de la mémoire vers la bande de sortie ;
  2. Les opérations de rupture de séquence conditionnelles dépendent du con­te­nu de ce registre ;
  3. L'accumulateur est toujours l'opérande gauche de toute opération arithmétique, et le résultat du calcul écrase son con­te­nu.

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 con­te­nu 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 con­te­nu du registre d'ad­res­se \(n\) dans acc.
LOAD @n ACC ← R[R[n]] copie le con­te­nu du registre d'ad­res­se \(R[n]\) dans acc.

Rangement dans les registres [store]

STORE n R[n] ← ACC copie le con­te­nu de acc dans le registre d'ad­res­se \(n\).
STORE @n R[R[n]] ← ACC copie le con­te­nu de acc dans le registre d'ad­res­se \(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 con­te­nu du registre d'ad­res­se \(n\).
INC @n R[R[n]] ← R[R[n]] + 1 incrémente le con­te­nu du registre d'ad­res­se \(R[n]\).
DEC n R[n] ← R[n] - 1 décrémente le con­te­nu du registre d'ad­res­se \(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 con­te­nu du registre d'ad­res­se \(n\) à acc.
ADD @n ACC ← ACC + R[R[n]] ajoute le con­te­nu du registre d'ad­res­se \(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 ad­res­ses 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 ma­chi­ne, bien entendu., donc des éléments de \(\Z\).

Une machine RAM est une séquence \((P_i)_{i\in \ab{0}{k}}\) d'instructions, c'est-à-dire de couples \((o,a)\) de \(\ab{0}{35}\times{\Z},\) où \(o\) est le code opération et \(a\) l'opérande. La séquence \((P_i)_{i\in \ab{0}{k}}\) est appelée programme de la machine ram.
Il est inutile d'inclure la bande d'entrée, la bande de sortie, la mémoire ou les registres spéciaux dans la description abstraite du modèle. Le programme peut être considéré comme une application \(\pi:\Z^{(\Z)}\,\rg\,\Z^{(\Z)}\) qui transforme une séquence d'entiers relatifs (la bande d'entrée) en une séquence d'entiers relatifs (la bande de sortie). En pratique, et en particulier avec le simulateur, nous considérons nécessairement des valeurs bornées.

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.

On dit qu'une machine ram s'arrête pour l'entrée \(x\) si la trace de son programme \((C_n)_{n\in\N}\) converge, i.e. si elle est constante à partir d'un certain rang : \begin{equation} \exists R\in\N\ \ \forall k\in\N\quad (k\geqslant R)\then (C_k=C_R). \end{equation}

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 al­go­ri­thme :

On appelle algorithme un programme de la machine ram qui s'arrête.
On appelle temps de calcul d'un algorithme pour une entrée \(x\) le nombre \begin{equation} \label{eq:taux} \tau(x)=\min\{R\in{\N}\such \forall t \gt R\ \ C_t=C_R\}. \end{equation} On appelle espace de calcul d'un algorithme pour une entrée \(x\) le nombre \begin{equation} \epsilon(x)=\#\{s_t\such t\in\N\}. \end{equation} où \(s_t\) est la valeur du registre de sélection mémoire à l'instant \(t\).

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 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

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:

  1. Lecture des \(n+1\) valeurs (la dernière est la balise négative) sur la bande d'entrée. Elles sont rangées du registre \(R_6\) au registre \(R_{6+n})\) par adressage indirect à l'aide du registre \(R_4\) initialisé à 6.
  2. Comparaisons \(R_{i+1} - R_{i} \geq 0,\) i.e. R[R[5]] - R[R[4]] et permutation des valeurs si nécessaire via le registre \(R_1\). Les indices \(i\) et \(i+1\) de deux valeurs contiguës sont rangés respectivement dans les registres \(R_4\) et \(R_5\). On s'assure que \(R_{i+1}\) n'est pas négatif pour continuer la boucle (instruction #17).
  3. Écriture des valeurs à partir de l'ins­truc­tion #28, toujours à l'aide du registre \(R_4\) pour l'adressage indirect. 

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 vous permet d'étudier le comportement de la machine ram avec vos pro­gram­mes. 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 ins­truc­tion par ligne. Commentez impérativement vos programmes, le codage ram ne se lit pas comme un roman~: tout ce qui suit le symbole ; est ignoré.

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.

Échauffement

É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?

Le tri sélection

Écrivez un algorithme qui calcule la plus petite valeur non nulle sur la bande d'entrée ainsi que sa position sur la bande d'entrée. La valeur nulle indique la fin de la lecture.
Écrivez l'algorithme du TriSélection par la recherche du minimum 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.