Modélisation à partir d'une liste

La mémoire centrale d'un ordinateur peut être vue comme un grand tableau pour lequel l'adresse mémoire correspond à l'indice, ou la position, d'un élément dans ce tableau.

En Python, une telle mémoire RAM peut être modélisée à l'aide d'une simple liste : une mémoire de taille N sera une liste à N éléments.

1. Écrivez la fonction init_ram_list(taille) qui prend en paramètre la taille de la mémoire et retourne une liste de taille N où tous les éléments sont nuls.

   Voici un exemple de ce que vous devriez obtenir :

   >>> RAM = init_ram_list(2)
   >>> print(RAM)
   [0, 0]
   
   >>> RAM = init_ram_list(16)
   >>> print(RAM)
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   

2. Pour la simulation de cette mémoire, il sera peut-être nécessaire d'utiliser une mémoire dans laquelle des valeurs auront été placées au hasard.

   Écrivez la fonction fill_ram_random(ram, N) qui prend en paramètre la liste représentant la mémoire RAM et un nombre entier N, qui place au hasard N valeurs entières (tirées au hasard entre 1 et 255) dans cette mémoire.

   Voici un exemple de ce que vous pourriez obtenir :

   >>> RAM = init_ram_list(16)
   >>> print(RAM)
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   
   >>> RAM = fill_ram_random(RAM, 5)
   >>>  print(RAM)
   [0, 0, 0, 0, 225, 0, 0, 0, 105, 179, 0, 0, 247, 136, 0, 0]
   

3. Pour mieux pouvoir débugger, les valeurs que l'on place en mémoire sont rarement tirées au hasard mais sont sont choisies pour être identifiable et traçable. Par exemple, on peut placer la valeur 48879 qui en hexadécimal donne 0xbeef si on travaille sur 2 octets.

   Écrivez la fonction fill_ram_place(ram, N) qui prend comme paramètre la mémoire RAM et un nombre entier N, et qui place au hasard N nombres dont la valeur dépend de leur position : si un nombre doit être placé à l'adresse x, la valeur à mettre sera x.

   Voici un exemple de ce que vous pourriez obtenir :

   >>> RAM = init_ram_list(16)
   >>>  print(RAM)
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   
   >>> RAM = fill_ram_place(RAM, 5)
   >>> print(RAM)
   [0, 0, 0, 0, 4, 0, 0, 0, 8, 9, 0, 0, 12, 13, 0, 0]
   

4. Écrivez la fonction get_value_list(ram, adresse) qui prend comme paramètre la mémoire RAM et une adresse, et qui retourne la valeur en mémoire placée à l'adresse donnée.

   Voici un exemple de ce que vous pourriez obtenir :

   >>> print(RAM)
   [0, 0, 0, 0, 4, 0, 0, 0, 8, 9, 0, 0, 12, 13, 0, 0]
   
   >>> get_value_list(RAM, 3)
   0
   
   >>> get_value_list(RAM, 4)
   4
   

Modélisation à partir d'un dictionnaire

La modélisation précédente a l'avantage d'être simple et suivre la réalité matérielle de la mémoire RAM : toute la mémoire disponible doit physiquement exister. Toutefois, dans le cadre de cette simulation, une telle modélisation fait utiliser une grande quantité de la vrai mémoire de votre ordinateur, principalement pour conserver une liste presque vide (qui ne contient presque que des 0).

Une modélisation plus économe consiste à utiliser le type dictionnaire de Python à la place d'une liste.

Le fonctionnement d'un dictionnaire est semblable à un tiroir dans lequel vous rangez des dossiers. Au lieu de les classer par position comme dans le cas de liste, vous les classés selon une étiquette que vous mettez au dossier. Par cette étiquette vous pouvez retrouver un dossier, le modifier, etc. De plus vous pouvez ajouter un dossier directement dans le tiroir, sans avoir à le mettre dans une position particulière qui ne changera plus.

Plus concrètement, un dictionnaire est un ensemble de couples clé-valeur, la clé jouant le rôle de l'étiquette pour retrouver la valeur. L'idée des dictionnaires est d'utiliser de place mémoire uniquement pour les valeurs présentes et de pouvoir retrouver les valeurs par un nom plus parlant que de se rappeler exactement l'ordre de placement dans une liste.

Par exemple, si une personne possède un nom, un prénom et un âge, et que nous utilisons une liste pour la décrire, nous aurions les manipulations suivantes :

# on déclare une liste pour décrire une personne
jd = ['John', 'Doh', 18]

# on veut afficher son prenom
print('prenom: ' + jd[0])

# on veut changer son âge
jd[2] = 19

Pour gérer ce genre d'information avec une liste, vous êtes obligés de bien vous rappeler à quoi correspond chaque indice : 0 est le prénom, etc.

La même chose mais en utilisant un dictionnaire :

# on déclare une dictionnaire pour décrire une personne
jd = {'nom': 'Doh', 'age': 18, 'prenom': 'John}

# on veut afficher son prenom
print('prenom: ' + jd['prenom'])  # on utilise l'étiquette 'prenom'

# on veut charger son âge
jd['age'] = 19  # on utilise l'étiquette 'age'

Il n'est plus nécessaire de se souvenir de l'indice d'une valeur, il suffit de connaître son étiquette. La position dans la déclaration du dictionnaire n'a aucune importance. Les principaux types que l'on peut utiliser comme étiquette sont les entiers et les chaînes de caractères (types non-mutables).

1. Écrivez la fonction init_ram_dict(taille) qui prend en paramètre la taille de la mémoire et retourne un dictionnaire contenant uniquement un élément dont la clé est 'taille' initialisée à N. Le dictionnaire ne contiendra pas d'autres éléments sinon cela reviendrait à utiliser une liste.

   Voici un exemple de ce que vous devriez obtenir :

   >>> RAM = init_ram_dict(2)
   >>> print(RAM)
   {'taille': 2}
   
   >>> RAM = init_ram_dict(16)
   >>> print(RAM)
   {'taille': 16}
   

2. Écrivez la fonction fill_ram_random_dict(ram, N) qui prend en paramètre le dictionnaire représentant la mémoire RAM et un nombre entier N, puis qui retourne un dictionnaire qui contient N valeurs entières (tirées au hasard entre 1 et 255) à une place tirée au hasard. Cependant cette fois, comme la RAM est modélisée par un dictionnaire, seules les valeurs non nulles seront conservées dans le dictionnaire et la clé sera l'adresse de la valeur. Les adresses seront toujours indicées à partir de 0.

   Voici un exemple de ce que vous pourriez obtenir :

   >>> RAM = init_ram_dict(16)
   >>> print(RAM)
   {'taille': 16}
   
   >>> RAM = fill_ram_random_dict(RAM, 5)
   >>> print(RAM)
   {'taille': 16, 8: 105, 4: 225, 13: 136, 12: 247, 9: 179}
   

3. Écrivez la fonction fill_ram_place_dict(ram, N) qui prend comme paramètre le dictionnaire représentant la mémoire RAM et un nombre entier N, et qui place au hasard N nombres dont la valeur dépend de leur position : si un nombre doit être placé à l'adresse x, la valeur à mettre sera x. Cette fois aussi, seules les valeurs non nulles seront conservées dans le dictionnaire et la clé sera l'adresse de la valeur.

   Voici un exemple de ce que vous pourriez obtenir :

   >>> RAM = fill_ram_place_dict(RAM, 5)
   >>> print(RAM)
   {'taille': 16, 4: 4, 8: 8, 9: 9, 12: 12, 13: 13}
   

4. Toutefois cette modélisation présente un problème : comment récupérer la valeur d'une adresse qui n'est pas dans le dictionnaire ?

   >>> print(RAM)
   {'taille': 16, 4: 4, 8: 8, 9: 9, 12: 12, 13: 13}
   
   >>> RAM[8]  # la valeur 8 existe dans le dictionnaire
   8
   
   >>> RAM[1]  # la valeur 1 n'existe pas dans le dictionnaire
   KeyError: 1
   

   Or, nous aimerions obtenir dans ce cas la valeur 0. Il existe une méthode sur les dictionnaires qui permet de retourner une valeur par défaut si elle n'existe pas dans le dictionnaire. Retrouvez la en utilisant la commande help().

   Écrivez la fonction get_value_dict(ram, adresse) qui prend comme paramètre la mémoire RAM et une adresse, et qui retourne la valeur en mémoire placée à l'adresse donnée, avec une RAM modélisée par un dictionnaire .

   Voici un exemple de ce que vous pourriez obtenir :

   >>> print(RAM)
   {'taille': 16, 4: 4, 8: 8, 9: 9, 12: 12, 13: 13}
   
   >>> get_value_dict(RAM, 3)
   0
   
   >>> get_value_dict(RAM, 4)
   4
   
   >>> get_value_dict(RAM, 30)
   Erreur: adresse invalide
   

La mémoire associative

Une mémoire associative est interrogée avec un mot et répond en indiquant si le mot y est présent. Pour cela, chaque case de la mémoire associative est comparée avec le mot question pour donner une réponse booléenne, c'est-à-dire un vecteur formé des réponses qui indique, le cas échéant, l'indice de la première des cases contenants le mot, si elle existe.

1. En supposant que la mémoire associative soit modélisée par une simple liste de taille fixe N quelconque (en pratique une puissance de deux), écrivez la fonction is_in(mem_asso, mot) qui prend en paramètre la mémoire associative et le mot recherché, et qui retourne un tuple formé de trois valeurs :

   • le mot 'HIT' si le mot est dans la mémoire, 'MISS' s'il n'y est pas ;
   • le vecteur de comparaison (liste de booléens) ;
   • l'indice en mémoire contenant le mot (ou None s'il n'y est pas).

   Vérifiez le bon fonctionnement de votre fonction sur les exemples ci-dessous :

   >>> M = [4, 1, 2, 0]  # mémoire associative de taille 4
   >>> is_in(M, 3)
   ('MISS', [False, False, False, False], None)
   
   >>> is_in(M, 1)
   ('HIT', [False, True, False, False], 1)
   
   >>> is_in(M, 0)
   ('HIT', [False, False, False, True], 3)
   

La mémoire classique

La mémoire classique qui compose la mémoire cache peut être vue comme la RAM : un tableau avec à chaque indice un élément contenant une valeur et potentiellement des informations de gestion.

Nous allons modéliser la mémoire classique par une liste de taille N (taille identique à la mémoire associative définie précédemment), et les éléments de cette liste seront des dictionnaires avec les clés suivantes :

• ok : un booléen indiquant si la donnée est valide ;
• data : la donnée mémorisée.

Le booléen ok (dit bit de validité) est utile principalement dans deux cas :

• à l'initialisation de la mémoire : car elle contient des valeurs aléatoire ;
• au vidage de la mémoire : car on n'efface pas les données (c'est impossible), on les invalide.

1. Écrivez la fonction get_value(mem, idx) qui prend en paramètre la mémoire classique et l'indice de l'élément voulu, puis qui retourne le dictionnaire associé mais avec la clé data à None si l'entrée n'est pas valide.

   Vérifiez le bon fonctionnement de votre fonction sur des exemples comme ceux-ci :

   >>> # exemple d'une mémoire classique de taille 4
   >>> M = [{'ok': True, 'data': 0x44}, {'ok': False, 'data': 0xFF},
            {'ok': True, 'data': 0x22}, {'ok': True, 'data': 0x99}]
   >>> get_value(M, 3)
   {'ok': True, 'data': 153}
   
   >>> get_value(M, 1)
   {'ok': False, 'data': None}
   

Combinaison des deux mémoires

La mémoire cache full associative combine les deux types de mémoire précédentes : elle est interrogée avec une adresse mémoire demandée par le processeur et si cette adresse est présente dans le cache et que son entrée est valide, elle retourne la valeur stockée dans la mémoire classique associée.

1. Écrivez la fonction in_cache(mem_asso, mem_class, adresse) qui prend en paramètres les deux types de mémoires précédentes (associative et classique), ainsi que l'adresse recherchée. En retour, cette fonction retourne le tuple composé :

   • du mot 'HIT' si la valeur est présente en cache et valide, ou 'MISS' sinon ;
   • de la valeur stockée dans la mémoire classique associée ou None.

   Vous utiliserez évidemment les deux fonctions définie précédemment (is_in() et get_value()). Vous testerez également votre fonction sur les exemples ci-dessous :

   # exemple avec une taille 4
   >>> mem_associative = [4, 1, 2, 0]
   >>> mem_classique = [{'ok': True, 'data': 0x44}, {'ok': False, 'data': 0xFF},
                        {'ok': True, 'data': 0x22}, {'ok': True, 'data': 0x00}]
   >>> in_cache(mem_associative, mem_classique, 3)
   ('MISS', None)
   
   >>> in_cache(mem_associative, mem_classique, 1)
   ('MISS', None)
   
   >>> in_cache(mem_associative, mem_classique, 2)
   ('HIT', 34)
   

Gestion des synonymes dans la cache direct-mapped

La méthode du placement calculé a l'inconvénient de son avantage : plusieurs adresse donnent le même indice. Dans l'exemple ci-dessus, il n'y a que 4 emplacements et les adresses 3 et 7 se projettent au même indice : 3. Il faut gérer ce problème des synonymes pour ne renvoyer que la bonne valeur et non pas celle correspondant à une autre adresse stockée antérieurement.

Pour cela, il faut ajouter dans la mémoire cache une information supplémentaire qui permettra de distinguer les synonymes. Cette information sera le tag issu de la décomposition de l'adresse en tag-indice (cf. le cache direct-mapped).

1. Écrivez la fonction in_cache_direct_mapped_fixed(mem_class, adresse) intègrant cette gestion des synonymes et qui prend en paramètre la mémoire classique du cache et une adresse à rechercher, puis qui retourne un tuple formé :

   • du mot 'HIT' si l'adresse est présente en cache et valide, ou le mot 'MISS' ;
   • de la valeur présente ou None si elle n'est pas présente en cache.

   Vous testerez votre fonction sur les exemples ci-dessous :

   >>> mem_direct_mapped = [{'ok': True, 'data': 0x00, 'tag': 0x0},
                            {'ok': False, 'data': 0xFF, 'tag': 0x1},
                            {'ok': True, 'data': 0x22, 'tag': 0x0},
                            {'ok': True, 'data': 0x77, 'tag': 0x1}]
   
   >>> in_cache_direct_mapped_fixed(mem_direct_mapped, 0)
   ('HIT', 0)
   
   >>> in_cache_direct_mapped_fixed(mem_direct_mapped, 7)
   ('HIT', 119)
   
   >>> in_cache_direct_mapped_fixed(mem_direct_mapped, 1)
   ('MISS', None)
   
   >>> in_cache_direct_mapped_fixed(mem_direct_mapped, 3)
   ('MISS', None)
   

Politique de remplacement dans le cache full associative

L'interrogation du cache est sa fonction première. Mais pour qu'il soit utile il faut qu'il contienne les valeurs recherchées. La taille du cache étant bien inférieure à celle de la RAM, il nécessaire que le cache change son contenu au fur et à mesure de l'exécution du programme. Il est ainsi nécessaire de mettre en place des politiques de remplacement des valeurs du cache.

Mémoires full associative avec politique de remplacement

Vous allez maintenant mettre en place le fonctionnement complet d'une mémoire cache full associative avec les trois politiques de remplacement traitées ci-avant. Pour cela, vous allez utiliser les fonctions définies précédemment pour écrire :

• la fonction full_associative_random(mem_asso, mem_class, valeur) : qui utilise la politique aléatoire ;
• la fonction full_associative_fifo(mem_asso, mem_class, valeur, fifo) : qui utilise la politique FIFO ;
• la fonction full_associative_lru(mem_asso, mem_class, valeur, pile) : qui utilise la politique LRU.

Pour simuler plus en avant le comportement du cache dans une structure plus complète d'une hiérarchie de mémoire, vous devez aussi définir la mémoire centrale RAM qui contient les valeurs recherchées. Vous modéliserez la RAM par un dictionnaire avec comme clé l'adresse et comme donnée la valeur associée. Par exemple :

RAM = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7}

Les trois fonctions que vous devez écrire auront le même comportement externe :

• elles prendront en paramètre une valeur question (adresse à rechercher)
• elles retourneront soit le tuple ('HIT', valeur en cache), soit ('MISS', None) ;

Par contre, le comportement interne sera différent :

• si la valeur est en cache, selon la politique il faut mettre à jour les informations de gestion du cache (cas LRU ;
• si la valeur n'est pas en cache, alors le cache va récupérer directement la valeur depuis la RAM et la stoker, en appliquant si besoin la politique de remplacement adéquate.

Normalement, le cache ne fait pas de demande à la RAM : le cpu fait la demande en parallèle au cache et à la RAM. Si le cache n'a pas la valeur, il intercepte la réponse de la RAM pour la stocker dans le cache. Le temps d'accès à la donnée sera au plus le temps d'accès à la RAM.

Vous testerez votre fonction sur les exemples ci-dessous (illustration avec le cas de la politique aléatoire) :

>>> RAM = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7}
>>> mem_associative = [4, 1, 2, 0]
>>> mem_classique = [{'ok': True, 'data': 4}, {'ok': False, 'data': 0xFF},
                     {'ok': True, 'data': 2}, {'ok': True, 'data': 0}]
>>> full_associative_random(mem_associative, mem_classique, 2)
('HIT', 2)

>>> full_associative_random(mem_associative, mem_classique, 1)
('MISS', None)

>>> full_associative_random(mem_associative, mem_classique, 1)
('HIT', 1)

Évaluation des performances

Pour comparer les différentes politiques de remplacement du cache vous allez compter le nombre de MISS sur une même séquence de demandes, avec un cache dans le même état, selon chacune des trois politiques : aléatoire, FIFO, LRU.

Vous partirez pour chaque politique d'une situation initiale où le cache est totalement vide et de taille 4. Puis, avec la RAM proposée ci-après, vous comparerez le nombre de 'MISS' pour chacune des séquences de demandes suivantes :

• séquence 1 : [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 3, 2, 4, 0, 1, 3, 2, 2, 4, 0, 2, 4, 3, 1],
• séquence 2 : [0, 1, 2, 3, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 1, 0, 3, 3, 3, 3, 4, 4, 4, 0, 1, 2, 7, 1, 2, 0, 3],
• séquence 3 : [0, 1, 2, 3, 0, 1, 2, 3, 0, 0, 1, 4, 1, 0, 3, 0, 4, 1, 2, 3, 4, 1, 2, 3, 4, 4, 4, 3, 2, 0, 1, 7, 4, 2, 4, 3].

RAM = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7}

Cache set associative

Ce type de cache est un compromis entre la flexibilité du cache full associative et la rapidité et facilité de recherche du cache direct-mapped. L'idée et d'introduire une associativité horizontale dans un cache direct-mapped, comme s'il y avait plusieurs caches direct-mapped en parallèle. Ainsi, à un même indice de cache va correspondre un ensemble de valeurs dont le calcul de position donne la même valeur, chacune se distinguant par son tag.

L'introduction de cette associativité horizontale amène la nécéssité de définir une politique de remplacement sur ces valeurs horizontales, et cela pour chaque indice du cache.

1. Écrivez la fonction set_associative(mem, pile_lru, adresse) qui prend en paramètre une adresse question et qui retourne soit :

   • le tuple formé du mot 'HIT' et de la valeur à trouver,
   • le tuple formé du mot 'MISS' et de la valeur None, avec une politique de remplacement LRU.

   Vous testerez votre fonction sur les exemples ci-dessous :

   >>> RAM = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7}
   >>> mem_set_associative = [[{'ok': True, 'data': 0, 'tag': 0}, None],
                              [{'ok': False, 'data': 0xFF, 'tag': 1},
                               {'ok': True, 'data': 5, 'tag': 1}],
                              [{'ok': True, 'data': 2, 'tag': 0}, None],
                              [{'ok': True, 'data': 3, 'tag': 0},
                               {'ok': True, 'data': 7, 'tag': 1}]]
   >>> pile_lru = [[0, None],
                   [0, 1],
                   [0, None],
                   [1, 0]]
   >>> set_associative(mem_set_associative, pile_lru, 2)
   ('HIT', 2)