source: trunk/IPs/systemC/processor/Morpheo/Documentation/Source/Documents/document-cache-specification/fr/02_overview_partial.tex @ 81

\Section{Vue d'ensemble du cache - Modèle simplifié}\label{overview_partial}

\printgraphonly{CACHE_overview_basic}{.8}

Dans un premier temps, nous allons montrer un modèle qui satisfait les cas de requêtes courantes : read hit, write hit, read miss et write miss, sur des adresses non conflictuelles.

Afin de réaliser un cache non bloquant, nous avons séparé l'interface des requêtes (à gauche sur les schémas), de l'interface des réponses (à droite sur les schémas). Ces interfaces sont eux même décomposées en deux parties : ceux impliquant le processeur (en haut sur les schémas) et ceux impliquant le bus (en bas sur les schémas). Le cache est donc découpés en 4 sections différentes : 
\begin{enumerate}
\item {\bf SECTION\_DCACHE\_REQ :} Les requêtes émisent par le processeur.
\item {\bf SECTION\_DCACHE\_RSP :} Les réponses à retourner au processeur.
\item {\bf SECTION\_VCI\_REQ    :} Les requêtes à émettre au bus.
\item {\bf SECTION\_VCI\_RSP    :} Les réponses retournées par le bus.
\end{enumerate}

Chaque partie est controlée par un automate et la communication entre deux sections ce fait par l'intermédiaire de files d'attentes (de type FIFO). Les ressources partagées sont les bancs mémoires contennant les lignes de caches ainsi que les informations sur les requêtes en cours de traitements.

Nous allons maintenant voir les différents blocs internes :
\begin{itemize}
\item Quatre automates : 
  \begin{description}
  \item[FSM\_DCACHE\_REQ :] Cette automate gère la section {\bf SECTION\_DCACHE\_REQ}. Il gère l'écriture dans la QUEUE\_READ\_HIT, l'écriture dans la QUEUE\_REQ, l'allocation d'une entrée dans la RAM\_INFO et la lecture de RAM\_TAG et RAM\_DATA et enfin gère un porte d'écriture dans RAM\_DATA. 

Pour chaque requête venant du processeur, l'adresse est envoyée au bloc RAM\_TAG. Ce dernier indique si la ligne contenant l'adresse demandée est dans le cache et, dans le cas d'un cache non direct map, retourne le numéro de banc contenant l'adresse. Si la requête est une lecture, alors avec le numéro de banc et le numéro de ligne, le cache va lire dans RAM\_DATA la donnée désirée. 

Si la requête est une écriture qui fait un succès, alors la donnée est écrite dans le bloc RAM\_DATA.

Quelque soit le type de la requête, si cette dernière est acceptée par la section {\bf SECTION\_DCACHE\_REQ}, nous allons allouer une entrée dans le bloc RAM\_INFO. Un identifiant sera retourné lors de l'allocation. Pendant l'allocation, nous allons également stocker dans le bloc RAM\_INFO toute les informations concernant la requête : type, adresse, donnée ... L'identifiant permettra d'accéder à ces informations dans les différentes sections du cache.

L'automate ne peut plus accepter de requêtes si l'une des RAM est occupée ou si la file de destination est pleine (la file de destination dépends de la requête).
  \item[FSM\_DCACHE\_RSP :] Cette automate gère la section {\bf SECTION\_DCACHE\_RSP}. Il gère la lecture du bloc QUEUE\_READ\_HIT, la lecture de QUEUE\_RSP, la désallocation d'une entrée dans la RAM\_INFO et la mise à jour des blocs RAM\_TAG et RAM\_DATA.

La plupart des requêtes envoyées par le processeur, par l'intermédiaire de l'interface DCACHE\_REQ, ont besoin qu'une réponse soit retourné au processeur. Ceci se fait par l'intermédiaire de l'interface DCACHE\_RSP. Les réponses peuvent provenir de deux files d'attentes : soit QUEUE\_READ\_HIT dans le cas d'une lecture avec succès, soit ,pour tout les autres cas, QUEUE\_RSP. 

Les informations étant stockées dans le bloc RAM\_INFO, les files d'attente contiennent un identifiant permettant d'adresser ce bloc. Lors d'une transaction réponse avec le processeur, le bloc RAM\_INFO va désallouer l'entrée concernée par la réponse. 

Les requêtes provenant de la file QUEUE\_RSP vont modifier le cache : soit en écrivant une ligne complète (read - miss) soit en écrivant une donnée (write - miss). Les requêtes provenant de la file QUEUE\_READ\_HIT vont modifier le bit de validité contenant dans le bloc RAM\_TAG (par exemple : invalidate et flush).

L'automate ne peut plus envoyer de réponses au processeur si l'une des RAM est occupée ou les files d'attente sont vides.
  \item[FSM\_VCI\_REQ    :] Cette automate gère la section {\bf SECTION\_VCI\_REQ}. Il contrôle la consommation d'une requête dans la file QUEUE\_REQ, la lecture de l'information de la requête dans le bloc RAM\_INFO et l'envoye des requêtes sur l'interface VCI\_REQ.

Toutes les requêtes d'écriture (car politique {\it write through}) et les échecs de lectures transitent par cette section. Les requêtes d'écritures et les accès mémoires non cachés vont provoquer l'envoye d'un paquet requête sur le bus (la section {\bf SECTION\_VCI\_RSP} devra recevoir un paquet réponse). Une lecture cachée va provoquer l'envoye de (NB\_WORD * SIZE\_WORD) / SIZE\_WORD\_VCI paquets requêtes. (SIZE\_WORD\_VCI représente la largeur d'une donnée transitant sur VCI. De plus il faut que SIZE\_WORD soit multiple de SIZE\_WORD\_VCI)

\printgraphonly{CACHE_bloc_COUNTER}{.8}

Comme le montre le graphe \ref{CACHE_bloc_COUNTER}, l'adresse envoyée est la concaténation entre un compteur et l'adresse de la requête (plus précisement c'est le Tag et l'Index de l'adresse qui est nécessaire).
La consommation d'une entrée dans la file QUEUE\_REQ ce fait lorsque l'intégralité des paquets sont envoyés.

L'automate ne peut plus envoyer de requête au bus VCI si la RAM\_INFO est occupée et/ou si la file d'attente QUEUE\_REQ est vide.
  \item[FSM\_VCI\_RSP    :] Cette automate gère la section {\bf SECTION\_VCI\_RSP}. Il contrôle la réception des réponses par le bus VCI et les stocke dans la file QUEUE\_RSP.

Chaque paquet requête VCI provoque la réception d'un paquet de réponse. Seul les échecs de lecture cachée vont avoir plus d'un paquet réponse. La ligne en cours de réception est stockée dans un tampon. Une fois le paquet de fin reçu, le contenu du tampon ou la réponse sera stocké dans la file QUEUE\_RSP. 

L'automate ne peux plus accepter de réponse VCI si QUEUE\_RSP est plein.
  \end{description}
\item Trois files d'attentes :
  \begin{description}
  \item[QUEUE\_READ\_HIT :] Toute requête provenant du processeur et qui n'accède pas au bus VCI passe par cette file. Elle contient les requêtes de lectures cachés ayant fait un succès. 

Les informations sont stockés dans le bloc RAM\_INFO, cette file ne contient qu'un index permettant d'adresser le bloc RAM\_INFO.
  \item[QUEUE\_REQ       :] Toutes les requêtes qui ne sont pas stocké dans la file QUEUE\_READ\_HIT sont alors stockés dans la QUEUE\_REQ. Il s'agit des écritures ou des lectures ayant fait un MISS ou réalisant un accès non cacheable. 

Cette file est à la frontière entre les sections {\bf SECTION\_DCACHE\_REQ} et {\bf SECTION\_VCI\_REQ}.
  \item[QUEUE\_RSP       :] Chaque paquet requête émit sur l'interface VCI\_REQ provoque l'émission par la cible d'un paquet réponse. Une fois que la réponse entière est revenu au cache, elle est stockée dans la file QUEUE\_RSP. A la différence des deux autres files d'attente, elle ne contient pas qu'une adresse vers une entrée du bloc RAM\_INFO. Chaque entrée contient une ligne de cache provenant d'un échec de de lecture, ainsi que le code d'erreur envoyé par la cible. 

L'automate {\bf FSM\_DCACHE\_RSP} donne la priorité au réponse car le processeur à effectué depuis plusieurs cycle l'accès et attend une éventuelle réponse. Cette file n'a pas besoin d'avoir beaucoup d'entrées.
  \end{description}
\item Trois blocs mémoires : 
  \begin{description}
  \item[RAM\_DATA :] Cette ram contient toute les données du cache. Elle est décomposé en autant de banc que le degré d'associativité du cache (ASSOC). Pour indexer une ligne particulière, il faut donc le numéro de la ligne (l'index) et le numéro de banc. Chaque ligne contient plusieurs mots. Un mot particulier est adressé par le déplacement contenu dans l'adresse (l'offset). Enfin un mot est composé de plusieurs octects, qui est l'unité la plus petit que peut modifier le processeur.

 Cette ram possède un port d'écriture : il est accédé lors de la section {\bf SECTION\_DCACHE\_RSP} et va écrire, dans le cas d'un échec de lecture, une ligne complète dans la RAM\_DATA. Ce port est accèder lors de la section {\bf SECTION\_DCACHE\_RSP}.  La section {\bf SECTION\_DCACHE\_REQ} va soit lire un mot dans le cas d'un read-hit, soit écrire un mot dans le cas d'un write-hit. Pour cela, il y a un port pour réaliser ces deux accès.
  \item[RAM\_TAG  :] Ce bloc mémoire contient les informations du contrôle du cache. Pour chaque ligne du cache contenus dans RAM\_DATA, nous sauvegardons deux informations : un bit de validité, qui indique si la ligne correspondante contient des données valide ou non, et un champ Tag qui contient l'étiquette de la ligne de cache. 

Le bloc RAM\_TAG possède 2 ports : le premier est un port de lecture contrôlé par la section {\bf SECTION\_DCACHE\_REQ}. Une requête provenant du  processeur accède aux informations de la ligne de cache, le bloc RAM\_TAG va lire simultanément tous les tag de chaque banc et indiquer si l'accès réalise un succès. Si c'est le cas, il fournit le numéro de banc le réalisant. Le deuxième port est un port d'écriture accèdé lors de la section {\bf SECTION\_DCACHE\_RSP}. Après avoir choisit une victime (donc un numéro de banc pour la ligne de cache), nous allons enregistrer dans cette mémoire son étiquette et placer le bit de validité à 1.
  \item[RAM\_INFO :] Ce bloc contient toute les informations des requêtes en cours de traitement (requêtes pendantes). Nous avons centralisé toutes les informations des requêtes dans une seule mémoire. Ceci permet de ne pas dupliquer les informations. Le nombre d'entrée de cette mémoire représente le nombre maximales de requêtes pendantes. 

    Il y a 3 ports à cette mémoire : le premier est utilisé lors de la section {\bf SECTION\_DCACHE\_REQ} qui consiste à demander au bloc RAM\_INFO d'allouer une case et enregistrer les informations fournit par la requête. La requête provenant du processeur ne peux pas être accepter si aucune entrée n'est disponible. Le deuxième port est utilisé par la section {\bf SECTION\_VCI\_REQ} pour récuper les informations de la requête pour envoyer un paquet de requête : l'adresse, la commande, la donnée à écrire ainsi qu'un masque concernant les octects de la donnée. L'identifiant du paquet VCI sera le numéro d'entrée de la RAM\_INFO. Un paquet réponse revoye l'identifiant contenu dans le paquet requête. Ceci permet à la section {\bf SECTION\_DCACHE\_RSP} d'accèder au bloc RAM\_INFO pour récuperer les informations afin de constituer la réponse pour le processeur : identifiant de requête, erreur, ... Si la réponse est envoyée avec succès au processeur, le bloc RAM\_INFO va désallouer l'entrée utilisé lors de cette section.
  \end{description}
\end{itemize}

\subSection{Chemin des requêtes}
Dans cette section, nous allons voir le chemin des requêtes en fonction de leur type et de leur succès ou échec dans le cache.

\begin{description}
\item[Read - cached - Hit  :] Une requête de lecture provenant du processeur va accèder au bloc RAM\_TAG afin de définir si le cache fait un hit sur cette accès. En cas de cache associatif, le bloc RAM\_TAG va également retourner le numéro de banc dans lequel la ligne est stockée. Dans le même temps, la requête va demander une allocation d'une entrée dans le bloc RAM\_INFO, et y stocker les informations de requêtes ainsi que la donnée lut.

L'identifiant retournée par le bloc RAM\_INFO est enregistré dans la file d'attente QUEUE\_READ\_HIT. Cette file est de type First In First Out. Une fois que la requête arrive en tête de file, alors elle sera traité par la section {\bf SECTION\_DCACHE\_RSP}. L'automate FSM\_DCACHE\_RSP donne la priorité à la file QUEUE\_RSP. La requête sera selectionnée une fois que la file QUEUE\_RSP est vide. Ensuite avec le numéro d'identifiant, nous adressons le bloc RAM\_INFO afin de lire les donnée utile pour une réponse : donnée à lire, identifiant de requête ...

La requête de lecture est terminé dès que le processeur renvoie accepte la requête de réponses.

\item[Read - cached - Miss :] Lors de l'accès au bloc RAM\_TAG, ce dernier indique que la ligne contenant l'adresse demandé n'est pas dans le cache. Dans ce cas nous avons un échec de lecture. Les informations concernant la requête est enregistré dans une ligne nouvellement alloué du bloc RAM\_INFO. L'identifiant retournée par ce bloc est enregistré dans la file d'attente QUEUE\_REQ. C'est également un file de type FIFO. 

Une fois que la requête arrive en tête de cette file, l'automate FSM\_VCI\_REQ va lire les informations à partir de RAM\_INFO. Avec ces informations l'automate va provoquer (NB\_WORD * SIZE\_WORD) / SIZE\_WORD\_VCI paquets requêtes. Les adresses des paquêts sont les adresses de la ligne de cache. Suivant la norme VCI seul le dernier paquet aura le champ EOP (End Of Packet) à 1.

Une fois tous les paquets de requêtes envoyés, l'entrée contenue dans la file QUEUE\_REQ est supprimée. 

La section {\bf SECTION\_VCI\_RSP} attend les paquets réponses. A réception de la première réponse, nous allons remplir un buffer qui va contenir la ligne demandée. Suivant la norme VCI, les réponses sont atomiques, c'est à dire que lors de la réception d'une réponse, nous ne pouvons pas recevoir un paquet d'une autre réponse. Une fois le dernier paquet de réponse, nous enregistrons la ligne ainsi que le code d'erreur dans la file d'attente QUEUE\_RSP. 

La section {\bf SECTION\_DCACHE\_RSP} va lire l'entrée de la file QUEUE\_RSP. Comme l'identifiant de requête VCI sert aussi d'adresse pour le bloc RAM\_INFO, nous pouvons récupérer les informations de la requêtes mémoire. Si la requête n'a pas fait d'erreur, le cache sera mise à jour : choix d'un banc victime, écriture de la ligne dans le bloc RAM\_DATA et écriture de l'étiquette dans RAM\_TAG. Le bit de validité de la ligne est placé à 1.

Dans tous les cas, la requête est envoyé sur le port DCACHE\_RSP du processeur. Dès que la réponse est accepté par le processeur, l'entrée contenue dans la file QUEUE\_RSP est supprimée.
\item[Read - uncached : ] Un accès en lecture non caché est identique à un accès en lecture caché réalisant un échec d'accès au cache. Néanmoins il y a 2 changements :
\begin{itemize}
\item Le premier est que SIZE\_WORD / SIZE\_WORD\_VCI paquets requête sera émis sur l'interconnect VCI. Ils ne contiendront que l'adresse désirée. Il y a un nombre équivalent de paquets réponses attendus.
\item Le cache ne sera pas mise à jour, c'est à dire pas d'écriture dans les blocs RAM\_DATA et RAM\_TAG.
\end{itemize}

{\it {\bf Remarque :} Nous faisons l'hypothèse qu'une requête non cachable ne peut jamais être dans le cache. C'est à dire que si l'adresse cible ne peut changer de status en cours d'éxecution et que c'est toute la ligne qui la contient qui est cachable ou non. Si cette hypothèse n'est plus vrai, alors lors de l'émission de la requête, il faut que le cache invalide l'entrée la contenant.}

\item[Write - cached - Hit  :] Lors d'une requête d'écriture caché, nous accèdons au bloc RAM\_TAG. Ce dernier indique que la ligne contenant l'adresse demandé est dans le cache : c'est donc un succès. La ligne contenant l'adresse envoyée par le processeur doit être mise à jour. Pour cela, la requête accède au bloc RAM\_DATA et écrit la donnée envoye par le processeur.

De plus les informations concernant la requête est enregistré dans une ligne nouvellement alloué du bloc RAM\_INFO. L'identifiant retournée par ce bloc est enregistré dans la file d'attente QUEUE\_REQ.

Une fois que la requête arrive en tête de cette file, l'automate FSM\_VCI\_REQ va lire les informations à partir de RAM\_INFO. Avec ces informations l'automate va envoyer (SIZE\_WORD) / SIZE\_WORD\_VCI paquets requêtes avec les données à écrire. Suivant la norme VCI seul le dernier paquet aura le champ EOP (End Of Packet) à 1.

Une fois tous les paquets de requêtes envoyés, l'entrée contenue dans la file QUEUE\_REQ est supprimée. 

La section {\bf SECTION\_VCI\_RSP} attend les paquets réponses. Seul les codes d'erreurs sont récupérés car l'écriture ne récupére aucune information.  Une fois le dernier paquet de réponse, nous enregistrons le code d'erreur dans la file d'attente QUEUE\_RSP. 

La section {\bf SECTION\_DCACHE\_RSP} va lire l'entrée de la file QUEUE\_RSP. Comme l'identifiant de requête VCI sert aussi d'adresse pour le bloc RAM\_INFO, nous pouvons récupérer les informations de la requêtes mémoire. Si la requête a un code d'erreur non nul, alors une réponses sera envoyer au processeur. Sinon aucune réponse n'est envoyée au processeur lors d'une écriture. Ensuite l'entrée contenue dans la file QUEUE\_RSP est supprimée.
\item[Write - cached - Miss :] Un échec d'écriture est équivalent à une réussite d'écriture mais sans mise à jour du cache.
\item[Write - uncached : ] Un accès en écriture non caché est équivalent à un accès en écriture caché réalisant un défaut de cache.
\item[Prefetch :] La pré lecture (prefetch) est une technique qui consiste à anticipé l'accès à une adresse en pré-chargeant une ligne de chace. Comme cette ligne ne sera pas forcément utile, il ne faut pas qu'elle modifie le cache. La ligne est en général stocké dans un petit cache. Ce cache de pré lecture est accèdé en parralèle à l'accès au cache, ou après un MISS. Lors d'un hit dans le cache de prélecture, la ligne sera placée dans le cache. La décision de préchargé une ligne peut être aussi bien logiciel que matériel. La présence d'un type {\it PREFETCH} indique que le processeur (et le logiciel tournant sur le processeur) peut envoyer des directives de préchargements. 

Dans l'implémentation de ce cache, nous n'avons pas inclue de mécanisme de pré-lecture. Pour cela, ces accès mémoires sont ignorées. Nous ne fournissons pas de réponses à ces requêtes.
\item[Lock  :] Le verrouillage de lignes est une technique qui permet d'enlever une ligne de la politique d'évincement du cache. Le programmeur qui a une vision global de l'application peut avoir une variable très utilisé. Dans ce cas, il envoie une directive de verrouillage de ligne et possède la donnée dans le cache. Ce mecanisme peut ressembler au mot clé {\bf register} en C qui une directive pour le compilateur de tenter de placer la variable dans un registre du processeur.

Le verrouillage ce fait jusqu'à une demande d'invalidation ou de flush de la ligne. C'est au cache de ne pas verrouiller l'intégralité d'un ensemble de ligne. C'est à dire que le cache doit au moins avoir pour chaque index, une ligne non verrouiller. Ceci impose que le cache soit au moins semi associatif. Dans un cas de conflit (c'est à dire lors d'une demande de verrouillage de la dernier ligne disponible d'un sensemble), le cache doit choisir une victime parmit les lignes verrouiller. 

Dans l'implémentation de ce cache, nous n'avons pas inclue de mécanisme de verrouillage de ligne. Ces accès mémoires sont ignorés.  Nous ne fournissons pas de réponses à ces requêtes.
\item[Invalidate :] Un accès mémoire de type {\it invalidation} est une directive qui va de supprimer la ligne correspondante dans le cache. L'invalidation ne va pas annuler les requêtes pendantes sur cette adresse. Mais à la fin de l'execution de cet accès mémoire, il ne doit avoir aucune instruction pendante sur l'ensemble de cette ligne de cache.

D'après les hypothèse donnée en introduction de cette section, comme nous n'avons pas d'accès conflictuel. Si la ligne est dans le cache, la section {\bf SECTION\_DCACHE\_REQ} va placer le bit valide contenu dans le bloc RAM\_TAG. Sinon, cet requête n'aura aucun effet sur le cache.

Le cache ne fournit pas de réponses à ces requêtes.

\item[Flush :] Un accès de type {\it flush} consiste à rendre cohérent les caches locaux ainsi que la mémoire principal. Toute les modifications de la ligne contenant l'adresse fournit par la requête doit être envoyé à la mémoire principale. A la fin de l'execution de cette instruction, toute les écritures sur la ligne de cache ciblée doit être terminée.

Pour notre implémentation de cache, celui-ci est write through. Il y a une cohérence entre le contenu du cache et le contenu de la mémoire. De plus, d'après les hypothèse donnée en introduction de cette section, comme nous n'avons pas d'accès conflictuel. Dans ce cas, cette commande est ignorée.

\item[Synchronization :] Ce type spécial est intégralement géré par l'automate {\it FSM\_DCACHE\_REQ}. Après la réception de cette requête, le cache ne va accepter plus aucune requête provenant du processeur jusqu'a ce qu'il n'y ait plus aucune requête en cours de traitement. La condition de reprise du cache est que le bloc RAM\_INFO soit vide. Une fois la RAM\_INFO vide, alors toutes les lectures (succès ou échec) ont été retournée au processeur. De plus chaque requête d'écriture envoyé sur l'interconnect VCI retourne une réponse. Ce n'est qu'une fois la réponse VCI parvenue au cache que l'entrée dans le bloc RAM\_INFO peut être désalloué. Ceci garantie qu'il n'y a aucune requête (aussi bien de lecture que d'écriture) en cours d'éxecution.

\end{description}