# Fonctionnement d'un ordinateur/La hiérarchie mémoire

Sur la plupart des systèmes embarqués ou des tous premiers ordinateurs, on n'a que deux mémoires : une mémoire RAM et une mémoire ROM, comme indiqué dans le chapitre précédent. Mais ces systèmes sont très simples et peuvent se permettre d'implémenter l'architecture de base sans devoir y ajouter quoi que ce soit. Ce n'est pas le cas sur les ordinateurs plus puissants.
Un ordinateur moderne ne contient pas qu'une seule mémoire, mais plusieurs. Entre le disque dur, la mémoire RAM, les différentes mémoires cache, et autres, il y a de quoi se perdre. Et de plus, toutes ces mémoires ont des caractéristiques, voire des fonctionnements totalement différents. Certaines mémoires seront très rapides, d'autres auront une grande capacité mémoire (elles pourront conserver beaucoup de données), certaines s'effacent quand on coupe le courant et d'autres non.
La raison à cela est que plus une mémoire peut contenir de données, plus elle est lente. On doit faire le choix entre une mémoire de faible capacité et très performante, ou une mémoire très performante mais très petite. Les cas intermédiaires, avec une capacité et des performances intermédiaires, existent aussi. Le fait est que si l'on souhaitait utiliser une seule grosse mémoire dans notre ordinateur, celle-ci serait trop lente et l'ordinateur serait inutilisable. Pour résoudre ce problème, il suffit d'utiliser plusieurs mémoires de taille et de vitesse différentes, qu'on utilise suivant les besoins. Des mémoires très rapides de faible capacité seconderont des mémoires lentes de capacité importante.
Finalement, l'architecture d'un ordinateur moderne diffère de l'architecture de base par la présence d'une grande quantité de mémoires, organisées sous la forme d'une hiérarchie qui va des mémoires très rapides mais très petites à des mémoires de forte capacité très lentes. Le reste de l’architecture ne change pas trop par rapport à l'architecture de base : on a toujours un processeur, des entrées-sorties, un bus de communication, et tout ce qui s'en suit. Les mémoires d'un ordinateur moderne sont les suivantes :
| Type de mémoire | Temps d'accès | Capacité | Relation avec la mémoire primaire/secondaire |
| Registres | 1 nanosecondes | Entre 1 et 512 bits | Mémoire incorporée dans le processeur |
| Caches | 10 - 100 nanosecondes | Kibi- ou mébi-octets | Mémoire incorporée dans le processeur, sauf pour d'anciens processeurs |
| Mémoire RAM | 1 microsecondes | Gibioctets | Mémoire primaire |
| Mémoires de masse (Disque dur, disque SSD, autres) | 1 millisecondes | Dizaines à centaines de gibioctets | Mémoire secondaire |
Précisons cependant que le compromis capacité-performance n'est pertinent que quand on compare des mémoires avec des capacités très différentes, avec au moins un ordre de grandeur de différence. Entre un ordinateur avec 16 gibioctets de RAM et un autre avec 64 gibioctets, les différences de performances sont marginales. Par contre, la différence entre un cache de quelques mébioctets et une RAM de plusieurs gibioctets, la différence est très importante. Ce qui fait que l'ensemble des mémoires de l'ordinateur est organisé en plusieurs niveaux, avec des registres ultra-rapides, des caches intermédiaires, une mémoire RAM un peu lente, et des mémoires de masse très lentes.

## La distinction entre mémoire primaire et secondaire

La première amélioration de l'architecture de base consiste à rajouter un niveau de mémoire. Il n'y a alors que deux niveaux de mémoire : les mémoires primaires directement accessibles par le processeur, et la mémoire secondaire accessible comme les autres périphériques. La mémoire primaire, correspond aux mémoire RAM et ROM de l'ordinateur, dans laquelle se trouvent les programmes en cours d’exécution et les données qu'ils manipulent. Les mémoires secondaires correspondent aux disques durs, disques SSD, clés USB et autres. Ce sont des périphériques connectés sur la carte mère ou via un connecteur externe.
Les mémoires secondaires sont généralement confondues avec les mémoires de masse, des mémoires de grande capacité qui servent à stocker de grosses quantités de données. De plus, elles conservent des données qui ne doivent pas être effacés et sont donc des mémoire de stockage permanent (on dit qu'il s'agit de mémoires non-volatiles). Concrètement, elles conservent leurs données mêmes quand l'ordinateur est éteint et ce pendant plusieurs années, voir décennies. Les disques durs, mais aussi les CD/DVD et autres clés USB sont des mémoires de masse.
Du fait de leur grande capacité, les mémoires de masse sont très lentes. Leur lenteur pachydermique fait qu'elles n'ont pas besoin de communiquer directement avec le processeur, ce qui fait qu'il est plus pratique d'en faire de véritables périphériques, plutôt que de les souder/connecter sur la carte mère. C'est la raison pour laquelle mémoires de masse et mémoires secondaires sont souvent confondues.
Les mémoires de masse se classent en plusieurs types : les mémoires secondaires proprement dit, les mémoires tertiaires et les mémoires quaternaires. Toutes sont traitées comme des périphériques par le processeur, la différence étant dans l’accessibilité.
* Une mémoire secondaire a beau être un périphérique, elle est située dans l'ordinateur, connectée à la carte mère. Elle s'allume et s'éteint en même temps que l'ordinateur et est accessible tant que l'ordinateur est allumé. Les disques durs et disques SSD sont dans ce cas.
* Une mémoire tertiaire est un véritable périphérique, dans le sens où on peut l'enlever ou l'insérer dans un connecteur externe à loisir. Par exemple, les clés USB, les CD/DVD ou les disquettes sont dans ce cas. Une mémoire tertiaire est donc rendue accessible par une manipulation humaine, qui connecte la mémoire à l'ordinateur. Le système d'exploitation doit alors effectuer une opération de montage (connexion du périphérique à l’ordinateur) ou de démontage (retrait du périphérique).
* Quant aux mémoires quaternaires, elles sont accessibles via le réseau, comme les disques durs montés en cloud.

### Les technologies de fabrication des mémoires secondaires sont à part

Les mémoires de masse sont par nature des mémoires non-volatiles, à savoir qui ne s'effacent pas quand on coupe l'alimentation électrique, à l'opposé des mémoires RAM qui elles s'effacent quand on coupe le courant. Et ce fait nous dit quelque chose de très important : les mémoires de masse ne sont pas fabriquées de la même manière que les mémoires volatiles.
Les mémoires volatiles sont presque toutes électroniques, à quelques exceptions qui appartiennent à l'histoire de l'informatique. Elles sont fabriquées avec des transistors, que ce soit des transistors CMOS ou bipolaire. Et quand on cesse de l'alimenter en courant, les transistors repasse en état inactif, de repos, qui est soit fermé ou ouvert. Ils ne mémorisent pas l'état qu'ils avaient avant qu'on coupe le courant. On ne peut donc pas fabriquer de mémoire non-volatile avec des transistors ! Et ce genre de chose vaut pour les ancêtres du transistors, comme les thrysistors, les triodes, les tubes à vide et autres : ils permettaient de fabriquer des mémoires volatiles, mais rien d'autres.
    Les mémoires ROM ne sont pas concernées par ce problème vu que ce sont de simples circuits combinatoires, qui n'ont pas besoin d'avoir de capacité de mémorisation proprement dit. Elles sont donc non-volatiles, mais le fait qu'on ne puisse pas modifier leur contenu rend la solution aisée.
Aussi, pour fabriquer des mémoires de masse, on doit utiliser des technologies différentes, on ne peut pas utiliser de transistors CMOS ou bipolaire normaux. Et le moins qu'on puisse dire est que les technologies des mémoires de masse sont très nombreuses, absolument tous les supports de mémorisation possibles ont été essayés et commercialisés. L'évolution des technologies de fabrication est difficile à résumer pour les mémoires de masse. Mais dans les grandes lignes, on peut distinguer quatre grandes technologies.
La solution la plus ancienne était d'utiliser un support papier, avec les cartes perforées. Mais cette solution a rapidement été remplacée par l'usage de d'un support de mémorisation magnétique, à savoir que chaque bit était attribué à un petit morceau de matériau magnétique. Le matériau magnétique peut être magnétisé dans deux sens N-S ou S-N, ce qui permet d'encoder un bit. C'est ainsi que sont nées les toutes premières mémoire de masse magnétique : les bandes magnétiques (similaires à celles utilisées dans les cassettes audio), les tambours magnétiques, les mémoires à tore de ferrite, et quelques autres. Par la suite, sont apparues les disquettes et les disques durs.
Par la suite, les CD-ROM, puis les DVD sont apparus sur le marchés. Ils sont regroupés sous le terme de mémoires optiques, car leur fonctionnement utilise les propriétés optiques du support de mémorisation, on les lit en faisant passer un laser très fin dessus. Ils n'ont cependant pas remplacé les disques durs, leur usage était tout autre. En effet, les mémoires optiques ne peuvent pas être effacées et réécrites. Sauf dans le cas des CD/DVD réincriptibles, mais on ne peut les effacer qu'un nombre limité de fois, mettons une dizaine. De plus, il faut les effacer intégralement avant de réécrire complétement leur contenu. Cette limitation fait qu'ils n'étaient pas utilisés pour mémoriser le système d'exploitation ou les programmes installés.
Toutes ces mémoires sont totalement obsolètes de nos jours, à l'exception des disques durs magnétiques. Et encore ces derniers tendent à disparaitre. Les mémoires de masse actuelles sont toutes... électroniques ! J'ai dit plus haut qu'il n'était pas possible de fabriquer des mémoires de masse/secondaires avec des transistors CMOS, je n'ai pas mentit. Les mémoires électronique actuelle sont des mémoires FLASH, qui sont fabriquées avec des transistors CMOS à grille flottante. Leur fonctionnement est différent des transistors CMOS normaux, ils ont une capacité de mémorisation que les transistors CMOS normaux n'ont pas. Par contre, leur procédé de fabrication est différent, ils ne sont pas fabriqués dans les mêmes usines que les transistors CMOS normaux.

### Le démarrage de l'ordinateur à partir d'une mémoire secondaire

L'ajout de deux niveaux de mémoire pose quelques problèmes pour le démarrage de l'ordinateur : comment charger les programmes depuis un périphérique ?
Les tout premiers ordinateurs pouvaient démarrer directement depuis un périphérique. Ils étaient conçus pour cela, directement au niveau de leurs circuits. Ils pouvaient automatiquement lire un programme depuis une carte perforée ou une mémoire magnétique, et le copier en mémoire RAM. Par exemple, l'IBM 1401 lisait les 80 premiers caractères d'une carte perforée et les copiait en mémoire, avant de démarrer le programme copié. Si un programme faisait plus de 80 caractères, les 80 premiers caractères contenaient un programme spécialisé, appelé le chargeur d’amorçage, qui s'occupait de charger le reste. Sur l'ordinateur Burroughs B1700, le démarrage exécutait automatiquement le programme stocké sur une cassette audio, instruction par instruction.
Les processeurs "récents" ne savent pas démarrer directement depuis un périphérique. À la place, ils contiennent une mémoire ROM utilisée pour le démarrage, qui contient un programme qui charge les programmes depuis le disque dur. Rappelons que la mémoire ROM est accessible directement par le processeur.
Sur les premiers ordinateurs avec une mémoire secondaire, le programme à exécuter était en mémoire ROM et la mémoire secondaire ne servait que de stockage pour les données. Le système d'exploitation était dans la mémoire ROM, ce qui fait que l'ordinateur pouvait démarrer même sans mémoire secondaire. La mémoire secondaire était utilisée pour stocker données comme programmes à exécuter. Les programmes à utiliser étaient placés sur des disquettes, des cassettes audio, ou tout autre support de stockage. Les premiers ordinateurs personnels, comme les Amiga, Atari et Commodore, étaient de ce type.
Par la suite, le système d'exploitation aussi a été déporté sur la mémoire secondaire, à savoir qu'il est installé sur le disque dur, voire un SSD. Un cas d'utilisation familier est celui de votre ordinateur personnel. Le système d'exploitation et les logiciels que vous utilisez au quotidien sont mémorisés sur le disque dur. Mais vu qu'aucun ordinateur ne démarre directement depuis le disque dur ou une clé USB, il y a forcément une mémoire ROM dans un ordinateur moderne, qui n'est autre que le BIOS sur les ordinateurs anciens, l'UEFI sur les ordinateurs récents. Elle est utilisée lors du démarrage de l'ordinateur pour le configurer à l'allumage et démarrer son système d'exploitation. La ROM en question ne sert donc qu'au démarrage de l'ordinateur, avant que le système d'exploitation prenne la relève. L'avantage, c'est qu'on peut modifier le contenu du disque dû assez facilement, tandis que ce n'est pas vraiment facile de modifier le contenu d'une ROM (et encore, quand c'est possible). On peut ainsi facilement installer ou supprimer des programmes, en rajouter, en modifier, les mettre à jour sans que cela ne pose problème.
Le fait de mettre les programmes et le système d'exploitation sur des mémoires secondaire a quelques conséquences. La principale est que le système d'exploitation et les autres logiciels sont copiés en mémoire RAM à chaque fois que vous les lancez. Impossible de faire autrement pour les exécuter. Les systèmes de ce genre sont donc des architectures de type Von Neumann ou de type Harvard modifiée, qui permettent au processeur d’exécuter du code depuis la RAM. Vu que le programme s’exécute en mémoire RAM, l'ordinateur n'a aucun moyen de séparer données et instructions, ce qui amène son lot de problèmes, comme nous l'avons dit au chapitre précédent.

## L'ajout des mémoires caches et des local stores

La hiérarchie mémoire d'un ordinateur moderne est une variante de la hiérarchie à deux niveaux de la section précédente (primaire et secondaire) à laquelle on a rajouté une ou plusieurs mémoires intermédiaires. Le niveau intermédiaire entre les registres et la mémoire principale regroupe deux types distincts de mémoires : les mémoires caches et les local stores. Les premiers sont des mémoires qui ne sont pas adressables et fonctionnent très différemment des mémoires RAM et ROM normales. Leur fonctionnement sera expliqué rapidement dans la section suivante, et détaillé dans un chapitre à part. A l'opposé, les local store sont des mémoires RAM adressables, très semblables à la mémoire principale, mais avec une plus fiable capacité et une vitesse plus importante.
Le rajout de ces niveaux supplémentaires est une question de performance. Les processeurs anciens pouvaient se passer de mémoires caches. Mais au fil du temps, les processeurs ont gagné en performances plus rapidement que la mémoire RAM et les processeurs ont incorporé des mémoires caches pour compenser la différence de vitesse entre processeur et mémoire RAM. Les caches sont beaucoup plus utilisés que les local store, ces derniers étant absent des processeurs commerciaux modernes, sauf peut-être dans quelques CPU dédiés aux applications embarquées. Ils sont présents dans les cartes graphiques modernes, l'ont été dans le CPU de la console Playstation 3, mais guère plus. A l'inverse, tous les processeurs disposent d'une ou plusieurs mémoires cache depuis au moins les années 90.

### Les mémoires caches

Dans la majorité des cas, la mémoire intercalée entre les registres et la mémoire RAM/ROM est ce qu'on appelle une mémoire cache. Aussi bizarre que cela puisse paraître, elle n'est jamais adressable ! Le contenu du cache est géré par un circuit spécialisé et le programmeur ne peut pas gérer directement le cache. Le cache contient une copie de certaines données présentes en RAM et cette copie est accessible bien plus rapidement, le cache étant beaucoup plus rapide que la RAM. Tout accès mémoire provenant du processeur est intercepté par le cache, qui vérifie si une copie de la donnée demandée est présente ou non dans le cache. Si c'est le cas, on accède à la copie le cache : on a un succès de cache (cache hit). Sinon, c'est un défaut de cache (cache miss) : on est obligé d’accéder à la RAM et/ou de charger la donnée de la RAM dans le cache.
Le fonctionnement interne d'un cache sera expliqué dans le chapitre dédié aux mémoires caches. Pour le moment, tout ce qu'on peut dire est que la majorité des processeurs utilise des caches dit partiellement associatifs. Ils contiennent en leur sein une ou plusieurs mémoire RAM de petite taille, qui sont entourées par des circuits qui font fonctionner le tout comme un cache. Un cache est donc plus complexe qu'une RAM normale, du fait des circuit en plus. Il est plus gourmand en transistors, en consommation énergétique, etc.
Plus haut, on a vu que les mémoires secondaires ne sont pas fabriqués avec les mêmes technologies que les mémoires volatiles/RAM. Il en est de même avec les mémoires caches, ce qui explique la différence de performance entre RAM et cache. Les caches sont plus rapides, non seulement car ils sont plus petits, mais aussi car ils ne sont pas fabriqués comme des mémoires RAM. Les mémoires RAM actuelles sont des mémoires dites DRAM, alors que les caches sont fabriqués avec des mémoires dites SRAM. La différence sera expliquée dans quelques chapitres, retenez simplement que les procédés de fabrication sont différents. La SRAM est rapide, mais a une faible capacité, la DRAM est lente et de forte capacité. La raison est que 1 bit de SRAM prend beaucoup de place et utilise beaucoup de circuits, alors que les DRAM sont plus économes en circuits et en espace.
Les caches peuvent ou non être intégrés au processeur. Il a existé des caches séparés du processeur, connectés sur la carte mère. Un exemple était le cache du processeur Pentium 2, qui avait son propre "socket". Mais de nos jours, les caches sont incorporés au processeur, pour des raisons de performance. Les caches devant être très rapides, avec des temps d'accès proches de la nanoseconde, il fallait réduire drastiquement la distance entre le processeur et ces mémoires. Cela n'a l'air de rien, mais l'électricité met quelques dizaines ou centaines de nanosecondes pour parcourir les connexions entre le processeur et le cache, si le cache est en dehors du processeur. En intégrant les caches dans le processeur, on s'assure que le temps d'accès est minimal, la mémoire étant la plus proche possible des circuits de calcul.

### Les local store et les caches RAM-configurables

Sur certains processeurs, les mémoires caches sont remplacées par des mémoires RAM appelées des local stores. Ce sont des mémoires RAM, identiques à la mémoire RAM principale, mais qui sont plus petites et plus rapides. Contrairement aux mémoires caches, il s'agit de mémoires adressables, ce qui fait qu'elles ne sont plus gérées automatiquement par le processeur : c'est le programme en cours d'exécution qui prend en charge les transferts de données entre local store et mémoire RAM.
Les local stores sont plus économes en circuits et consomment moins d'énergie que les caches à taille équivalente. En effet, ils n'ont pas besoin de circuits compliqués pour gérer automatiquement les échanges avec la RAM, contrairement aux caches. Ils sont adressables, ce qui est assez simple à implémenter avec un décodeur et des registres. Côté inconvénients, ces local stores peuvent entraîner des problèmes de compatibilité : un programme conçu pour fonctionner avec des local stores ne fonctionnera pas sur un ordinateur qui en est dépourvu.
Il faut noter que certains caches peuvent être configurés pour fonctionner comme des local store. En effet, une mémoire cache est souvent fabriquée en prenant une ou plusieurs mémoires SRAM adressables et en ajoutant des circuits autour. Mais il est possible d'utiliser les mémoires SRAM adressables telles quelles, en les adressant directement. Il s'agit de la technique du 'cache RAM-configurable.
L'usage de cache RAM-configurable est fréquent sur les cartes graphiques récentes. Elles incorporent un ou plusieurs processeurs multicœurs, dont le cache L1 de données est un cache RAM-configurable. Les CPU commerciaux incorporent aussi des caches de ce type, bien que cela ne soit utilisé que lors du démarrage de l'ordinateur. Au démarrage, le BIOS n'a pas immédiatement accès à la mémoire RAM principale, qui demande d'être configurée du fait de technicalités des mémoires DDR. Aussi, le BIOS utilise alors le cache du processeur comme une mémoire RAM. Les registres de configuration du CPU sont configurés de manière à ce que le cache soit utilisé comme local store. Du code s'exécute, vérifie la présence de mémoire RAM, configure le contrôleur DDR, fait quelques manipulations, puis met le cache à l'état normal.

### Les principes de localité spatiale et temporelle

Utiliser au mieux la hiérarchie mémoire demande placer les données accédées souvent, ou qui ont de bonnes chances d'être accédées dans le futur, dans la mémoire la plus rapide possible. Le tout est de faire en sorte de placer les données intelligemment, et les répartir correctement dans cette hiérarchie des mémoires. Ce placement se base sur deux principes qu'on appelle les principes de localité spatiale et temporelle :
* un programme a tendance à réutiliser les instructions et données accédées dans le passé : c'est la localité temporelle ;
* et un programme qui s'exécute sur un processeur a tendance à utiliser des instructions et des données consécutives, qui sont proches, c'est la localité spatiale.
Pour donner un exemple, les instructions d'un programme sont placées en mémoire dans l’ordre dans lequel on les exécute : la prochaine instruction à exécuter est souvent placée juste après l'instruction en cours (sauf avec les branchements). La localité spatiale est donc respectée tant qu'on a pas de branchements qui renvoient assez loin dans la mémoire (appels de sous-programmes). De même, les boucles (des fonctionnalités des langages de programmation qui permettent d’exécuter en boucle un morceau de code tant qu'une condition est remplie) sont un bon exemple de localité temporelle. Les instructions de la boucle sont exécutées plusieurs fois de suite et doivent être lues depuis la mémoire à chaque fois.
On peut exploiter ces deux principes pour placer les données dans la bonne mémoire. Par exemple, si on a accédé à une donnée récemment, il vaut mieux la copier dans une mémoire plus rapide, histoire d'y accéder rapidement les prochaines fois : on profite de la localité temporelle. On peut aussi profiter de la localité spatiale : si on accède à une donnée, autant précharger aussi les données juste à côté, au cas où elles seraient accédées. Ce placement des données dans la bonne mémoire peut être géré par le matériel de notre ordinateur, mais aussi par le programmeur.
De nos jours, le temps que passe le processeur à attendre la mémoire principale devient de plus en plus un problème au fil du temps, et gérer correctement la hiérarchie mémoire est une nécessité, particulièrement sur les processeurs multi-cœurs. Il faut dire que la différence de vitesse entre processeur et mémoire est très importante : alors qu'une simple addition ou multiplication va prendre entre 1 et 5 cycles d'horloge, une lecture en mémoire RAM fera plus dans les 400-1000 cycles d'horloge. Les processeurs modernes utilisent des techniques avancées pour masquer ce temps de latence, qui reviennent à exécuter des instructions pendant ce temps d'attente, mais elles ont leurs limites.
Bien évidement, optimiser au maximum la conception de la mémoire et de ses circuits dédiés améliorera légèrement la situation, mais n'en attendez pas des miracles. Il faut dire qu'il n'y a pas vraiment de solution facile à implémenter. Par exemple, changer la taille d'une mémoire pour contenir plus de données aura un effet désastreux sur son temps d'accès qui peut se traduire par une baisse de performance. Par exemple, les processeurs Nehalem d'Intel ont vus leurs performances dans les jeux vidéos baisser de 2 à 3 % malgré de nombreuses améliorations architecturales très évoluées : la latence du cache L1 avait augmentée de 2 cycles d'horloge, réduisant à néant de nombreux efforts d'optimisations architecturales.
Une bonne utilisation de la hiérarchie mémoire repose en réalité sur le programmeur qui doit prendre en compte les principes de localités vus plus haut dès la conception de ses programmes. La façon dont est conçue un programme joue énormément sur sa localité spatiale et temporelle. Un programmeur peut parfaitement tenir compte du cache lorsqu'il programme, et ce aussi bien au niveau :
* de son algorithme : on peut citer l'existence des algorithmes cache oblivious ;
* du choix de ses structures de données : un tableau est une structure de donnée respectant le principe de localité spatiale, tandis qu'une liste chaînée ou un arbre n'en sont pas (bien qu'on puisse les implémenter de façon à limiter la casse);
* ou de son code source : par exemple, le sens de parcours d'un tableau multidimensionnel peut faire une grosse différence.
Cela permet des gains très intéressants pouvant se mesurer avec des nombres à deux ou trois chiffres. Je vous recommande, si vous êtes programmeur, de vous renseigner le plus possible sur les optimisations de code ou algorithmiques qui concernent le cache : il vous suffira de chercher sur Google. Quoi qu’il en soit, il est quasiment impossible de prétendre concevoir des programmes optimisés sans tenir compte de la hiérarchie mémoire. Et cette contrainte va se faire de plus en plus forte quand on devra passer aux architectures multicœurs.