Random access machine

Random access machine
Page d'aide sur l'homonymie Pour les articles homonymes, voir RAM.
Page d'aide sur l'homonymie Ne doit pas être confondu avec Random Access Memory.

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.

Contenu soumis à la licence CC-BY-SA. Source : Article Random access machine de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Random access machine — In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of indirect addressing of its registers. Like the… …   Wikipedia

  • Random Access Machine — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Random Access Machine — Die Registermaschine (auch RAM für engl. random access machine) ist ein Rechnermodell der theoretischen Informatik, das einem realen Rechner (PC) sehr ähnlich ist. Das Modell geht auf eine Arbeit von John C. Shepherdson und Howard E. Sturgis aus… …   Deutsch Wikipedia

  • Parallel Random Access Machine — In computer science, Parallel Random Access Machine (PRAM) is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine (RAM). In the same way, that the RAM is… …   Wikipedia

  • Parallel random access machine — PRAM, pour Parallel Random Access Machine, est un modèle abstrait de machine destiné à concevoir des algorithmes pour machines parallèles de modèle MIMD, ou pour de plus rares cas de modèle SIMD. PRAM modélise une machine parallèle à une mémoire… …   Wikipédia en Français

  • Parallel Random Access Machine — Als Parallel Random Access Machine, kurz PRAM, bezeichnet man ein Maschinenmodell zur Analyse paralleler Algorithmen. Es handelt sich um eine Registermaschine, die um die Möglichkeit zur parallelen Verarbeitung von Befehlen erweitert wurde. Wie… …   Deutsch Wikipedia

  • Random access stored program machine — In theoretical computer science the Random Access Stored Program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.The RASP is a Random Access Machine (RAM) model that,… …   Wikipedia

  • Dynamic random-access memory — DRAM redirects here. For other uses, see Dram (disambiguation). Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube …   Wikipedia

  • Dynamic random access memory — (DRAM) is a type of random access memory that stores each bit of data in a separate capacitor within an integrated circuit. Since real capacitors leak charge, the information eventually fades unless the capacitor charge is refreshed periodically …   Wikipedia

  • Magnetoresistive random access memory — Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube Non volatile …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”