Random access machine

En informatique théorique, la machine RAM, pour Random Access Machine, est un modèle abstrait d'ordinateur destiné à étudier des algorithmes.

Ordinateur

Notre ordinateur est^{[Interprétation personnelle ?]} une machine qui ne fait qu'effectuer des calculs sur des nombres, codés sous la forme d'une suite de symboles. Ces calculs vont donc transformer une suite de symboles en une autre. Les suites de symboles manipulées sont appelées des données, tandis que les calculs qui transforment une chaîne de « caractères » en une autre sont appelées des instructions.

Un ordinateur, quel qu'il soit, ne fait qu'exécuter une suite d'instructions dans un ordre bien précis sur des données. La suite d'instructions à exécuter s'appelle un programme.

Dans nos ordinateurs actuels, ces symboles sont des 0 ou des 1 : notre ordinateur utilise la numération binaire.

Architecture d'une machine RAM

La machine RAM est un ordinateur composé :

• d'une unité de calcul, qui va effectuer des instructions ;
• une mémoire, à savoir quelque chose capable de retenir des données, pour pouvoir les stocker et les récupérer. Cette mémoire est découpée en deux sous-mémoires :
  • une mémoire programme, qui stocke les instructions du programme à effectuer dans l'ordre dans lequel elles doivent être calculées ;
  • une mémoire de travail, qui stocke les données (variables) que va manipuler le programme ;
• de registres, de petites mémoires ultra-rapides capables de stocker temporairement une donnée ;
• d'une bande de sortie, un morceau de papier sur lequel notre machine RAM va écrire le résultat du programme exécuté ;
• une bande d'entrée sur laquelle est inscrit l'ensemble des données initiales nécessaires à l'exécution du programme, qui va être lue par notre machine RAM ;
• et d'un bus de communication qui va permettre la transmission de données ou d'instructions entre les différents composants de la machine.

Mémoire RAM

La mémoire d'un ordinateur sert à stocker le programme à exécuter et ses données. On peut accéder à la mémoire de deux façons :

• en écriture : on stocke une donnée dans la mémoire ;
• en lecture : on récupère une donnée/instruction de la mémoire.

La mémoire de la machine RAM possède quelques particularités.

Cette mémoire est découpée en cases mémoires. Chacune de ces cases mémoire peut stocker un nombre, sous la forme d'une suite de symboles.

Notre machine RAM a besoin de pouvoir sélectionner une case mémoire parmi toutes les autres afin d'accéder à son contenu et uniquement à son contenu. Pour cela, on attribue à chaque case mémoire un identifiant, nommé son adresse mémoire. Cette adresse est un nombre, attribué de façon unique à une case mémoire : deux cases mémoires auront deux adresses mémoires différentes. On dit que la mémoire est adressable. On peut donc accéder à une donnée dans la mémoire sans avoir besoin de lire toutes les données précédentes (accès séquentiel).

Enfin, il faut savoir que le temps mis pour lire (récupérer) ou écrire (modifier) le contenu d'une case mémoire est le même pour toutes les cases mémoires. Il n'y en a pas une plus lente que l'autre.

La mémoire est donc :

• découpée en cases mémoires ;
• adressable ;
• à temps d'accès constant quelle que soit la case mémoire sélectionnée.

Une mémoire de ce type est appelée en électronique une mémoire RAM (Random Access Memory).

Registres

Un registre est une petite mémoire interne à un processeur qui va permettre de stocker un nombre, représenté sous la forme d'une suite de symboles. Dans les ordinateurs actuels ces registres stockent des suites de 0 et de 1, nos ordinateurs utilisant la représentation binaire. Cette suite de symbole représente un « nombre ».

Notre machine RAM possède donc des registres. Parmi ces registres, certains ont une utilité particulière.

Le compteur d'instruction

Pour rappel, un ordinateur doit effectuer une suite d'instructions dans un ordre bien précis. En prenant un programme ayant un nombre fini n d'instructions, on peut donc numéroter chaque instruction du programme par un nombre bien précis, de 1 à n. La dernière instruction étant une instruction STOP, qui arrête le fonctionnement de la machine RAM.

Le compteur d'instruction stocke ce nombre attribué à chaque instruction.

À la fin de chaque instruction, ce compteur est automatiquement augmenté de 1 (on dit aussi incrémenté) : cela permet de passer à l'instruction suivante.

Dans nos ordinateurs actuels il y a de légères différences :

• les instructions sont toujours stockées dans la mémoire, mais elles ne sont pas numérotées. Le compteur d'instruction stocke alors l'adresse de l'instruction en mémoire ;
• les instructions peuvent prendre plusieurs cases mémoire. Le compteur n'est donc pas augmenté de 1 à chaque fois, mais d'un nombre représentant le nombre de cases mémoires occupées par l'instruction.

L'accumulateur

Ce registre peut contenir une copie d'une donnée présente dans la mémoire RAM. C'est sur la donnée présente dans cet accumulateur que le processeur va effectuer des instructions. Mais le processeur peut aussi aller chercher des données supplémentaires en RAM, en plus de la donnée présente dans l'accumulateur.

Instructions

On l'a vu, notre machine RAM a un processeur qui exécute des instructions. Ces instructions peuvent être des additions, des multiplications, par exemple, mais qui peuvent aussi faire des choses un peu plus utiles. Parmi ces instructions, on peut citer certaines instructions présentes chez toutes les machines RAM :

   * LOAD
   * STORE
   * JUMP
   *…

Instructions arithmétiques

Ces instructions font simplement des calculs sur des nombres. On peut citer par exemple :

   * addition,
   * multiplication,
   * division,
   * modulo,
   * soustraction,
   * racine carrée,
   * cosinus,
   *…

Les instructions logiques

Elles travaillent sur des bits.

   * ET,
   * OU,
   * XOR,
   * NON.

Instructions LOAD et STORE

LOAD permet de copier une donnée présente en mémoire dans un registre.

STORE permet de copier une donnée contenue dans un registre dans la mémoire RAM.

Instructions de rupture de séquence

Ces instructions sont appelées des branchements.

Elles permettent de sauter directement à une instruction autre que l'instruction immédiatement suivante et poursuivre l'exécution à partir de cette instruction. Cela permet au programme de passer directement à une instruction située plus loin dans le déroulement normal du programme, voire de revenir à une instruction antérieure.

Pour ce faire, elles modifient le contenu du registre pointeur d'instruction, et y place l'adresse de l'instruction à laquelle on veut sauter.

Les branchements permettent de ne pas respecter d'ordre d'exécution des instructions.

Par exemple, supposons qu'une machine RAM en soit à l'instruction numéro 5. Si cette instruction est une instruction de rupture de séquence, alors la machine RAM passera directement, par exemple, à l'instruction numéro 60 au lieu de l'instruction 6.

Les instructions de test

Ces instructions permettent de vérifier si une proposition est valide ou pas.

Les plus courantes sont :

   * Test d'égalité : vérifie si deux nombres sont égaux.
   * Test de supériorité : teste si un nombre est supérieur à un autre.
   * Test d'infériorité : teste si un nombre est inférieur à un autre.
   * Test de différence : teste si deux nombres a et b sont différents.

Ces instructions se marient très bien avec les instructions de rupture de séquence, comme on le verra plus tard.

Instructions READ et WRITE

Ces instructions permettent d'écrire une donnée sur les bandes d'entrées (pour READ) et de sortie (pour WRITE). Cela permet de représenter de manière ultra-simplifiée la communication avec les entrées-sorties.

Dans la réalité, la communication avec une entrée ou une sortie est bien plus compliquée qu'une simple instruction !

Différences et ressemblances avec un ordinateur actuel

La machine RAM ressemble beaucoup aux ordinateurs actuels, mais s'en différencie par certains points.

Les ordinateurs actuels, tout comme les machines RAM, possèdent les ressemblances suivantes avec la machine RAM :

• la présence de registres ;
• la mémoire de travail est une mémoire RAM.

Dans un ordinateur, rien n'empêche d'utiliser une mémoire dont le temps d'accès est très dépendant de l'emplacement de la donnée dans la mémoire, comme un disque dur. Mais tous les ordinateurs actuels utilisent une mémoire RAM, pour des raisons techniques.

Mais il existe des différences avec un ordinateur réel. Dans la machine RAM, les entrées-sorties sont modélisées par des bandes sur lesquelles on écrit un nombre en binaire.

Nonobstant ces différences, nos ordinateurs actuels sont le plus souvent des machines RAM améliorées sur certains points, auxquelles on a rajouté quelques subtilités, comme une pile ou un cache. Ce sont donc des machines RAM. Mais il existe des ordinateurs qui ne sont pas des machines RAM améliorées, ni même des machines RAM tout court ! Les premiers ordinateurs n'étaient pas des machines dotées d'une mémoire RAM, et fonctionnaient avec des mémoires bien différentes.

Articles connexes

• Parallel random access machine
• Simulateur de machine RAM