Médiation : activité mémoire cache

Cache-cache avec la RAM

Les documents disponibles sur cette page ainsi que le contenu de la page sont mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International .
Merci aux personnes m'ayant aidée à développer cette activité, en particulier les membres du groupe InfoSansOrdi, et les enseignant.e.s de l'APMEP lors des journées de Dijon en 2019.

Notions abordées :

Cette activité présente un peu d'architecture des ordinateurs, deux types de mémoire vive (la mémoire cache et la RAM) et comment un processeur doit jongler avec les deux.

Public :

Contrairement à ce que pourrait laisser croire le paragraphe précédent, cette activité n'est pas résevée aux élèves du secondaire ou plus. On peut très bien en faire une déclinaison pour les plus jeunes, et le matériel s'y prête.

Cette activité a été testée avec des publics du CE1 au supérieur. Il suffit d'adapter son discours, de prendre son temps, et peut-être d'aller un peu moins loin avec les plus petits.

Matériel :

Pour réaliser cette activité, quelle que soit la version ci-dessous que vous choisissez il vous faut les deux premiers éléments, puis choisir une des deux options proposées :

imprimer (en couleurs !) la roue mise à disposition dans la section lien, en 4 exemplaires pour avoir 4 processeurs en parallèle.
des programmes permettant chacun de reconstituer un morceau de l'image,
version économique :
1. des feutres à pointe large(ou crayons de couleurs mais moins bien car moins couvrants), 4 pour chacune des 12-1=11 couleurs de la roue (pas besoin du blanc)
2. des feuilles de papier quadrillé (petits ou grands carreaux au choix suivant la résolution que vous souhaitez)
3. un support montrant 3 emplacements pour 3 feutres. On peut percer trois trous assez gros dans une planche de bois épaisse où on glisse les feutres, ou bien dessiner le contour de trois feutres sur un support papier
version plus chère (mais les briques c'est rigolo)
1. Un stock considérable de briques de couleur de taille 2x2, personnellement j'en ai une centaine de chaque couleur et 12 couleurs différentes (celles de la roue)
2. trois gobelets par processeur, dans ma version il y en a 4 donc 12 gobelets
3. une plaque sur laquelle on peut fixer les briques. Dans l'exemple des photos j'ai une plaque de 32 picots de large de sorte que je peux y fixer 16 briques 2*2 en largeur. Je coupe cette plaque en 4 carrés de 16 sur 16 picots.

Découper pour chaque roue les trois éléments. Les superposer et passer une attache parisienne dans le point de la partie en V puis au centre de la roue colorée puis dans le point de la roue blanche. Rabattre et coller au dos de la grande roue blanche, de part et d'autre de la valeur "+0", les deux branches du V qui dépassent. On a ainsi une roue dans laquelle les deux morceaux blancs sont solidaires, et la roue colorée est entre les deux et peur tourner par rapport aux autres.

Principe :

Nombre de participants : minimum 3 (un processeur, un bus et une RAM) et maximum une bonne vingtaine (voir en fin de cette section pour plus de précisions).

Pour commencer l'activité il faut donner à chaque processeur (entre 1 et 4 suivant le nombre de participants et le degré de parallélisme que vous voulez atteindre) une roue, un des programmes (4 dans l'exemple donné en lien), ses emplacements de cache (3 gobelets ou support à crayons) et de quoi dessiner (plaque pour les briques ou papier quadrillé de la taille de l'image à réaliser). On installe la RAM avec le stock de briques ou de feutres, loin des processeurs (l'idée est que le temps d'accès à la RAM est nettement plus long que pour le cache).

Calcul des couleurs : chaque processeur va lire son programme et utiliser la roue pour en déduire la couleur du prochain pixel (carré colorié ou brique de couleur) de son image. Les programmes sont écrits comme suit : le premier nombre sur une ligne est la couleur du premier pixel de cette ligne. Dans le premier programme donné en lien (celui du haut à gauche) le premier pixel est de couleur 1 c'est à dire blanc. Ensuite pour chacun des autres pixels de la ligne on donne le décalage entre l'ancienne couleur et la nouvelle. Ainsi +0 indique qu'on conserve la même couleur, +1 qu'on passe à la suivante et ainsi de suite. Sur l'exemple on a donc un premier pixel blanc suivi de 4 autres blancs (on a quatre fois "+0") puis on passe à la couleur 1+4 = 5 soit rouge, et on ajoute encore deux autres pixels rouges (+0). Attention, le décalage est calculé à chaque fois par rapport à la couleur qu'on vient d'utiliser. Il est donc utile de tourner la roue pour mettre à chaque fois la couleur actuelle en face du "+0" ce qui facilite le calcul du décalage.

Gestion du cache : pour dessiner ce qu'indique le programme, un processeur a besoin des couleurs demandées (briques ou feutres). Problème : il n'a localement qu'une petite mémoire à disposition : le cache, et n'a donc de la place que pour stocker 3 couleurs différentes, et ces couleurs (feutres ou briques) sont au départ dans la RAM, qui est loin. A chaque fois qu'il a besoin d'une couleur qu'il n'a pas localement, il doit la demander à son bus, et s'il a déjà trois couleurs devant lui, il doit en rendre une (mais laquelle ??? bonne question, voir extensions).

Et on illustre quoi ? L'ordinateur a différents types de mémoires, plus ou moins proches du processeur, plus ou moins rapides et plus ou moins grandes. La règle générale est que plus la mémoire est proche du processeur, plus elle est rapide, mais également plus elle est chère et plus elle est petite. Du coup il faut jongler entre ce qui est stocké dans la mémoire rapide mais petite, et ce qui est stocké plus loin.

Et si on a beaucoup de participants ? Cette activité est présentée avec une personne jouant le rôle du processeur, mais en classe entière et surtout avec des petits il est intéressant de faire participer plus d'enfants à la fois. On peut donc conserver une personne pour la RAM (c'est important qu'il y ait des embouteillages de temps en temps), mais choisir entre un bus pour tout le monde et un bus par processeur, et répartir le travail du processeur entre plusieurs personnes. Le processeur effectue plusieurs tâches :

lire le programme,
en déduire la couleur à utiliser en s'aidant de la roue,
voir si on a a la couleur sinon donner un gobelet (ou un feutre si on en a déjà trois) au bus pour qu'il rapporte la nouvelle couleur,
prendre la bonne couleur (une brique ou un feutre) à l'emplacement où elle/il se trouve,
et enfin fixer la brique ou colorier la case de la bonne couleur.

On peut donc avoir jusque 5 personnes pour jouer le rôle d'un processeur. Avec 4 processeurs en parallèle et un bus par processeur on a 6 * 4 + 1 RAM = 25 personnes occupées en même temps. C'est peut-être un peu beaucoup mais on peut facilement en occuper une dizaine avant de tourner pour faire passer un autre groupe.

Extensions :

une extension naturelle de la version simple est de réfléchir à quelle ressource effacer (rendre à la RAM dans notre cas) pour libérer de la place pour la nouvelle. Comme on n'est pas sensé avoir toute la visibilité sur la suite, on a plusieurs possibilités
1. le processeur prend un peu d'avance pour voir la prochaine couleur pendant qu'il attend le retour du bus,
2. le processeur décide de rendre la couleur qui est inutilisée depuis le plus longtemps,
3. le processeur rend la couleur qui a été le moins souvent utilisée dans les 10, 20 ou 30 précédents pixels.
Ces stratégies ressemblent à ce qui peut se faire dans un vrai processeur.
si votre processeur prend trop d'avance et lit tout le programme pour savoir à l'avance ce dont il aura besoin jusqu'à la fin, on peut mettre un cache sur le programme qui ne permet de voir que la ligne en cours et la suivante par exemple. Quand on a fini une ligne, on glisse le cache d'une ligne vers le bas et on ne voit donc pas tout à la fois.

Liens :

L'activité est récente (début 2019), pas encore de vidéo tournée pour le moment.
Je mets à votre disposition le modèle de roue des couleurs à imprimer pour réaliser vous même l'activité.
Pas encore de fiche d'activité, mais c'est en projet.
Une version des programmes à donner aux processeurs pour faire l'activité. La première colonne est grisée pour bien montrer que la façon de l'interpréter (le code de la couleur utilisée) est différente de celle des autres colonnes (le décalage avec la couleur précédente).

Photos :

A gauche, un aperçu du matériel avec deux des plaques, le programme écrit à la main sur un morceau de papier, un des trois emplacements de la mémoire cache (le mug rouge), la roue dans sa première version et un sac à briques de la RAM. A droite la RAM en action : elle (à gauche) remplit un gobelet donné par le bus (qui attend à droite). Photo prise lors d'un atelier APMEP à Grenoble.

première version du matériel (sans roue améliorée)