- Random access machine
-
Pour les articles homonymes, voir RAM.La machine RAM, pour Random Access Machine, est un modèle abstrait d'ordinateur destiné à étudier des algorithmes.
Il s'agit au départ d'un modèle théorique d'ordinateur, avec de nombreuses simplifications. Cette machine RAM est néanmoins assez proche des ordinateurs actuels sur certains points.
Sommaire
Ordinateur
Notre ordinateur est une machine qui ne 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 chaine de "caractère" 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 donc la numération binaire.
Architecture d'une machine RAM
La machine RAM est un ordinateur composée :
- 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 inscrite 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/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 mit 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. RAM étant l'abréviation de Random Acces 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.
A 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 registres 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, voir 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, une machine RAM en est à l'instruction numéro 5. Si cette instruction est une instruction de rupture de séquence, la machine RAM passera alors directement à l'instruction numéro 60; plutôt que d'automatiquement passer à 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ée-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 cours ! Les premiers ordinateurs n'étaient pas des machines dotées d'une mémoire RAM, et fonctionnaient avec des mémoires bien différentes.
Wikimedia Foundation. 2010.
