Chapitre 4 - Les mémoires associatives - ARCH2 - 2CP - S1 PDF

# Résumé - Chapitre 4: Les mémoires associatives - Module ARCH2 - 2CP – S1 ## Les mémoires associatives ### Problématique - Dans une mémoire conventionnelle (RAM classique), il faut connaitre l'adresse de l'information. Si celle-ci est inconnue, le seul moyen de retrouver l'information est d'eff...

# Résumé - Chapitre 4: Les mémoires associatives - Module ARCH2 - 2CP – S1 ## Les mémoires associatives ### Problématique - Dans une mémoire conventionnelle (RAM classique), il faut connaitre l'adresse de l'information. Si celle-ci est inconnue, le seul moyen de retrouver l'information est d'effectuer une recherche séquentielle sur tous les mots de la mémoire. - Cependant, dans une telle mémoire, plusieurs problèmes se posent: - L'opération de recherche est très couteuse. - Le temps de parcours élevé des RAM de grandes capacités. - Il n y'a aucune garantie que l'information existe en mémoire. ### Solution - Une solution plus rapide consiste à rechercher en parallèle tous les mots mémoires dont le champ « groupe » est égal à « 5 ». Ceci est possible uniquement dans une mémoire associative (MA). - Les RAM répond à la question « Quelle est l'information qui se trouve à l'adresse A ? », par ailleurs dans une MA on tente plutôt à répondre à « Y a-t-il un mot mémoire contenant l'information I ? ». - L'information I qui sert de critère de sélection est comparée en parallèle au champ qui lui correspond dans chaque mot de la mémoire ; d'où le nom « mémoire adressable par contenu ». ### Description d'une mémoire associative - Une mémoire associative contient : - Un bloc mémoire constitué de l'ensemble des mots de la mémoire associative. - Un registre clé (C) de même format (taille) que le mot mémoire, il recevra l'information qui sert de critère de recherche (par exemple : 05, 01, 21). - Un registre masque (M) de même format (taille) que le mot mémoire, il permet de préciser le champ sur lequel portera la recherche (par exemple : nombre de filles, groupe). A chaque bit du registre « C » correspond un bit du registre « M » (1 : sélectionné, 0 : masqué). - Un registre de sortie (S) de même format (taille) que le mot mémoire, il permet de récupérer le résultat de la lecture uniquement. - Un registre indicateur (I) composé d'autant de bits que de mots mémoire. - Un circuit de sélection formé des logiques de recherche, de lecture et d'écriture. ### Exemple - Par exemple, supposons que les informations suivantes sont rangées en mémoire : - **Groupe** | **Nombre de filles** | **Nombre de garçons** ----|---|---| - 5 | 12 | 18 - 1 | 13 | 16 - 3 | 10 | 21 - 2 | 15 | 13 - 4 | 14 | 14 - Comment peut-on répondre aux questions : - Quel est le nombre de garçons du groupe 05 ? - Quel est le nombre de filles du groupe 01 ? - Quel est le groupe qui contient 21 garçons ? ## Opérations sur une mémoire associative - Dans une mémoire associative, les opérations de lecture et d'écriture doivent être précédées d'une opération de recherche. ### Opération de recherche - **Principe** : - Au début, tous les bits du registre indicateur (I) sont mis à « 1 » par la commande SET. - L'information (critère de recherche) est placée dans le registre clé (C). Les bits du registre masque (M) correspondant au champ du critère de recherche sont aussi positionnés à « 1 ». - Ainsi, seuls les bits du registre clé dont le bit masque est a 1 participent à la comparaison. - Au cours de la recherche, chaque bit non-masqué du registre clé est comparé en parallèle à tous les bits de même position du bloc mémoire. Si le bit « i » (non masqué) du registre clé et le bit « i » du mot mémoire de rang (ligne) « j » sont différents, le jème bit du registre I est remis à « 0 ». - A la fin de la recherche, les seuls bits du registre I qui sont toujours à « 1 » sont ceux répondant au critère de sélection. On parle alors de « répondeur ». Un signal S/N (Some/None) indique, s'il est à « 1 », qu'il existe au moins un répondeur (information trouvée). - **Par exemple** : dans une MA de 3 mots de 3 bits chacun, on cherche l'information « 110 » (constituée d'un seul champ). - Critère de recherche: 1 1 0 - Masque (mise à 1): 1 1 1 - Indicateurs (mise à 1): 1 1 1 - Bloc mémoire 3x3: - j=1: 1 0 1 1 - j=2: 1 1 1 1 - j=3: 1 1 0 1 - i=1 i=2 i=3 ### Exemple - La MA suivante contient des noms de personnes ainsi que leur tailles. On désire connaitre les noms de personnes dont la taille est de 1.70m. - **Étapes de résolution du problème:** 1. Positionner tous les bits du registre I à '1' en activant la commande SET. 2. Placer l'information dans le champ taille du registre C (1.70 dans le champ taille). 3. Positionner à « 1 » les bits correspondant au champ taille dans le registre M et les bits des autres champs à « 0 » (00000...0111...1). 4. Activer la commande de recherche. - **Résultats:** 1. **C** | **M** | **I** ---|---:|---: ---|XXXX 170 | SET - BATTA | 170 | 1 - CHABANE | 180 | 1 - HAMOU | 165 | 1 - BACHI | 172 | 1 - KACIM | 178 | 1 - S 2. **C** | **M** | **I** ---|---:|---: ---|XXXX 170 | SET - BATTA | 170 | 1 - CHABANE | 180 | 1 - HAMOU | 165 | 1 - BACHI | 172 | 1 - KACIM | 178 | 1 - S 3. **C** | **M** | **I** ---|---:|---: ---|XXXX 170 | SET - 00...00 1...1 - BATTA | 170 | 1 - CHABANE | 180 | 1 - HAMOU | 165 | 1 - BACHI | 172 | 1 - KACIM | 178 | 1 - S 4. **C** | **M** | **I** ---|---:|---: ---|XXXX 170 | Recherche - 00...00 1...1 - BATTA | 170 | 1 - CHABANE | 180 | 1 - HAMOU | 165 | 1 - BACHI | 172 | 1 - KACIM | 178 | 1 - S 5. **C** | **M** | **I** ---|---:|---: ---|XXXX 170 | - 00...00 1...1 - BATTA | 170 | 0 - CHABANE | 180 | 0 - HAMOU | 165 | 0 - BACHI | 172 | 0 - KACIM | 178 | 0 - S ### Circuit de recherche - Relation entre les registres C (clé) et M (masque) - **C**: correspond à la valeur (bit) recherchée. - **M**: correspond à valider la recherche si M=1 (bit non-masqué). Sinon (M=0), le bit est masqué donc ce n'est pas la peine de rechercher. ## Fonctionnement général - **La commande RAZ sert à conserver ou mettre à « 0 » les bits du registre I lors de la comparaison.** - RAZ₁ = 1 : remise à 0 du jème bit de l'indicateur I. - RAZ₁ = 0 : conservation du jème bit de l'indicateur I. - **RAZ₁ = ∑RAZ₁ = ∑(R. Qij - Lò + R. Qij · L₁) avec :** - n = la taille d'un mot mémoire ; - j∈ [[1,m]] ; m = nombre de mots (lignes) de la MA ; ## Opération de lecture - **Principe:** - Dans une mémoire associative, la lecture est effectuée sur tout mot dont le bit correspondant dans le registre indicateur est à « 1 ». - Pour réaliser une lecture sélective, il est donc nécessaire de faire procéder la lecture par une recherche pour positionner les bits indicateurs des mots que l'on ne désire pas sélectionner à « 0 » et garder à « 1 » les bits correspondant aux mots que l'on veut lire. - L'information lue est récupérée dans le registre de sortie (S). - **Remarque:** plusieurs informations peuvent répondre aux mêmes critères. ### Organisation des cellules pour la lecture - **Lecture**: - ... - i+1 L₁ B₁ R₁ I₁ M₁ - ... - i+1 L₂ B₂ R₂ I₂ M₂ - ... - i+1 L₃ B₃ R₃ I₃ M₃ - ... - Vers le registre de Sortie - Registre I ## Opération d'écriture - **Principe:** - L'écriture est aussi effectuée sur tout mot dont le bit correspondant dans le registre indicateur est à « 1 ». - L'information à écrire est rangée dans le registre clé et les bits du registre masque correspondant aux champs que l'on désire écrire sont positionnés à « 1 ». L'écriture porte sur les cellules mémoire dont : le bit correspondant dans le registre M est à « 1 » & le bit correspondant au mot dans le registre I est à « 1 » aussi. - On peut donc écrire un « 0 » ou un « 1 » dans n'importe quel bit d'un mot qui répond à la recherche. - **Remarque**: plusieurs informations peuvent répondre aux mêmes critères. ### Organisation des cellules pour l'écriture - **Commande d'écriture**: - ... - i+1+1 L₁ L₁ J₁ B₁ D₁+1 R₁ I₁ M₁ K₁ M₁ - ... - i+1+1 L₂ L₂ J₂ B₂ D₁+1 R₂ I₂ M₂ K₂ M₂ - ... - i+1+1 L₃ L₃ J₃ B₃ D₁+1 R₃ I₃ M₃ K₃ M₃ - ... - Registre I ## Réinitialisation de la mémoire à 0 - **Cette opération se fait en deux étapes :** 1. Positionner tous les bits du registre I à '1' en activant la commande SET. 2. On positionne tous les bits de la clé à « 0 » et tous les bits du masque à « 1 » et on lance l'opération d'écriture. ### Remarques : - **Les bascules dans une MA sont des bascules JK et on a :** - JBM = E.LI - KB BM = EL Ij (avec : E = commande d'écriture) - **Si plusieurs informations répondent à la même clé de recherche (nombre de répondeur ≥ 2), on aura en sortie le résultat du ‘OU' logique entre toutes les informations sélectionnées (indicateur I₁=1), ainsi : Si = ∑-1L.IjQj (avec: L = commande de lecture ; i ∈ [[1, n − 1]]).** - **L'opération de réinitialisation n'est pas sélective, on écrasera tous les mots de la mémoire.** ## Sélection du premier répondeur - **Suite à une opération de recherche, plusieurs mots peuvent répondre (i.e. : plusieurs bits du registre I sont à « 1 »). Dans ce cas, la lecture délivre dans le registre de sortie le résultat du ‘OU” entre les mots sélectionnés. Si on désire traiter un seul mot, le résultat de la lecture est erroné.** - **De même, l'opération d'écriture présente un inconvénient en cas de réinitialisation (écrasement de tous les mots).** - **On doit donc pouvoir sélectionner un répondeur à la fois.** ### Comment garantir la sélection des répondeurs un par un? - **Pour cela, on ajoute une commande de Sélection/Inhibition qui force tous les indicateurs à « 0 » à l'exception de celui du premier répondeur. Le traitement désiré peut alors être effectué sur ce répondeur.** - **Une bascule BT est associée à chaque mot. Lorsqu'elle est à « 1 », le bit correspondant dans le registre indicateur est forcé à « 0 ». La bascule est positionnée à « 1 » dès que son répondeur est traité.** - **Plusieurs opérations de recherche sont nécessaires pour sélectionner successivement les autres répondeurs. L'enchainement des opérations est le suivant :** 1. **Positionnement des bascules BT de tous les mots à « 0 ».** 2. **Sélection/Inhibition (S/I) mise à "0" S/I ← 0.** 3. **Positionnement des registres C (clé) et M (masque).** 4. **Commande SET (positionnement des indicateurs à « 1 »).** 5. **Activation de la commande de recherche.** 6. **Si S/N = 0 (pas de répondeur ou fin de traitement), aller à 11.** 7. **Sinon : S/I ← 1 (premier répondeur sélectionné), lecture du répondeur et positionnement des indicateurs des autres mots à « 0 ».** 8. **Traitement du répondeur et positionnement de sa bascule BT; à « 1 ».** 9. **Commande SET (positionnement des indicateurs à « 1 » de nouveau) et S/I ← 0.** 10. **Aller à 4.** 11. **Fin de l'opération.** ### **Algorithme** - Reset, S/I← 0 - C.Champ ← info - Masque.Champ ← ‘1', '0' ailleurs - SET - Recherche - Si S/N = 0, aller à : Fin - S/I← 1 - Lecture, BT; ← 1 - S/I←0 - Aller à (4) - Fin ### **Répondeur déjà traité :** - BT₁ = 1 et I₁ = 0 ### **Remarque :** - **Il ne faut pas oublier de remettre S/I à « 0 » au début et après le traitement de chaque répondeur. En effet, si on laisse S/I à « 1 » au début de l'algorithme ou avant la boucle, dès l'activation de la commande SET, le premier bit indicateur à « 1 » va forcer tous les autres à « 0 », qu'ils soient répondeurs ou non.** ## SPOILER - **Les mémoires associatives sont utilisées dans les mémoires caches (chapitre suivant) !!**