source: trunk/IPs/systemC/processor/Morpheo/Documentation/Source/Documents/document-cache-specification/fr/04_overview_full.tex @ 45

\Section{Vue d'ensemble du cache - Modèle complet}\label{overview_full}
Cette section à pour but de montrer les modifications par rapport au modèle de base.

\printgraphonly{CACHE_overview}{.8}

\subSection{Solution retenue}

Dans cette section, nous allons montrer la solution retenue. Il s'agit de l'intégration dans la modèle de base vue dans la section \ref{overview_partial} des solutions données au problème vus dans la section \ref{problem}.

Le problème principal est la gestion par le cache de la consistance mémoire. Nous allons implémenté la solution consistant à vérrouiller les lignes de cache. Comme nous verrouillons au niveau des lignes de cache, nous avons besoin que la section {\bf SECTION\_DCACHE\_REQ} réalise le choix de la victime.

La solution abordé dans la section précédente prévoit un bit de verrouillage qui est positionné à un lorsque une requête va être émise sur le bus, et positionné à 0 lors que la réponse reviens du bus. Tous requête qui accède à cette ligne de cache n'est pas accepter. De plus nous pouvons noter lors de la selection d'une victime, le cache n'accepte pas la requête si la victime est vérrouillé.

Le tableau suivant résume pour tous les cas possibles, ce que la théorie autorise, et ce que notre algorithme actuelle autorise.

\begin{tabular}{l|cc}
Cas                                                                       & théorie & algo actuel \\
\hline
2 lectures                     adressant la même adresse                  & oui & non \\ 
2 lectures                     adressant la même ligne de cache           & oui & non \\
2 lectures                     adressant deux lignes de cache différentes & oui & oui \\
2 écritures                    adressant la même adresse                  & non & non \\
2 écritures                    adressant la même ligne de cache           & oui & non \\
2 écritures                    adressant deux lignes de cache différentes & oui & oui \\
1 lecture  suivit d'1 écriture adressant la même adresse                  & non & non \\
1 lecture  suivit d'1 écriture adressant la même ligne de cache           & oui & non \\
1 lecture  suivit d'1 écriture adressant deux lignes de cache différentes & oui & oui \\
1 écriture suivit d'1 lecture  adressant la même adresse                  & non & non \\
1 écriture suivit d'1 lecture  adressant la même ligne de cache           & oui & non \\
1 écriture suivit d'1 lecture  adressant deux lignes de cache différentes & oui & oui \\
\end{tabular}

La solution actuelle est très restrictive. Ceci est du au fait que quant le cache verrouille une ligne de cache, il ne sait pas si c'est un échec de lecture ou une écriture qui est la cause du verrouillage.

Pour cela, nous modifions l'algorithme en ne proposant pas un bit de verrouillage mais deux bits de verrouillage :
\begin{description}
\item[Lock\_by\_read  : ] la ligne de cache à été verrouiller par une lecture. (Un échec de lecture de cette ligne de cache est en cours de traitement).
\item[Lock\_by\_write : ] la ligne de cache à été verrouiller par une écriture. (Une écriture d'un mot de cette ligne de cache est en cours de traitement).
\end{description}

En terme d'implémentation, nous avons ajouter un banc de registre RAM\_LOCK contenant ces deux bits de verrouillage. De plus nous avons déplacer le bit de validité contenant dans RAM\_TAG jusque dans ce bloc.% Ce déplacement provoque un petit changement : précédement lors que RAM\_TAG indiqué que l'accès était un succès alors ceci signifie que l'adresse envoyé par le processeur est dans une ligne de cache ET que cette ligne de cache est valide. Maintenant RAM\_TAG ne peut plus vérifier cette deuxième condition.

\subSection{Protocole}

Dans cette section, nous allons voir le protocole de gestion de la consistance mémoire.

\printgraphonly{CACHE_protocole}{.55}
 
Lors de l'arrivé d'une requête, la section {\bf SECTION\_DCACHE\_REQ} connait le type et à partir de l'adresse accède au bloc RAM\_TAG pour obtenir le numéro de banc. Avec ce dernier, le cache accède aux blocs RAM\_DATA et RAM\_LOCK.
\begin{itemize} 
\item Si l'accès est une écriture, comme le cache est {\it write through}, cet accès va provoquer l'émission d'une requête sur l'interconnect VCI. 
  \begin{itemize} % write
  \item Si l'écriture fait un succès dans le cache (RAM\_TAG contient l'adresse envoyé par le processeur), alors nous testons s'il n'y a pas une requête (aussi bien de lecture que d'écriture) en cours de traitement et que l'entrée dans le cache est valide. 
    \begin{itemize}  % write hit
    \item Si c'est le cas, alors nous n'acceptons pas cette requête d'écriture (sinon la requête d'écriture que nous evoyons risque de doubler la requête en cours de traitement). 
    \item Si aucun des bits de verrouillage n'est positionnée à 1, alors l'accès peut avoir lieu. Pour cela, nous indiquons qu'une requête d'écriture à lieu sur cette ligne de cache ({\it lock\_by\_write = 1}), puis nous chargeons les sections {\bf SECTION\_VCI\_REQ} et {\bf SECTION\_VCI\_RSP} d'effectuer la transaction avec la mémoire principale. La réception de la réponse par la section {\bf SECTION\_DCACHE\_RSP} va provoquer la mise à zéro du bit {\it lock\_by\_write}.
    \end{itemize}
  \item Si l'écriture fais un échec dans le cache, alors nous choisissons une victime.
    \begin{itemize} % write miss
    \item Si la victime n'est pas valide (les deux bits de verrouillage ne sont pas à 0), alors nous n'acceptons pas la requête d'écriture.
    \item Si la victime est valide, alors nous verrouillons intégralement la ligne. Par intégrale, nous positionnons les bits {\it lock\_by\_write} et {\it lock\_by\_read} à 1. Le verrouillage intégrale empêche toutes lectures ultérieurs. Tous comme un succès d'écriture, la réception de la réponse va provoquer l'invalidation de la ligne de cache. Car comme le cache n'est pas write allocate, la ligne allouée ne sera pas remplit avec des données cohérentes.
    \end{itemize}
  \end{itemize}
\item Si l'accès est une lecture, nous devons tester la présence dans le cache de l'adresse envoyée par le processeur.
  \begin{itemize} % read
  \item Si l'adresse est contenu dans le cache, alors nous devons verifier si la ligne est verrouiller ({\it lock\_by\_read} = 1). Nous n'avons pas besoin de tester si la ligne est verrouiller par une écriture. Si c'est le cas et que l'écriture été une réussite, alors la donnée est à jour dans la ligne de cache, sinon le protocole place le bit {\it lock\_by\_read} à 1.
    \begin{itemize} % read hit
    \item Si ligne est verrouillée alors la requête n'est pas accepté.
    \item Si au contraire, la ligne n'est pas verrouillé, alors la requête est accepté : on lit la donnée dans le bloc RAM\_DATA et on place la requête dans la file d'attente QUEUE\_READ\_HIT. Ensuite, la section {\bf SECTION\_DCACHE\_RSP} va s'occuper d'envoyer la réponse au processeur.
    \end{itemize}
  \item Si l'accès en lecture fait un échec, le cache doit choisir une victime.
    \begin{itemize}
    \item Si la victime n'est pas valide, alors la requête n'est pas acceptée.
    \item Si la victime est valide, la section {\bf SECTION\_DCACHE\_REQ} peut effectuer une réquête. Pour cela elle inscrit les informations dans le bloc RAM\_INFO tout en verrouillant la ligne ({\it lock\_by\_read = 1}). Ensuite la donnée est écrite dans la file QUEUE\_REQ, ce qui provoque une emission puis une reception par les sections contrôlant l'interface VCI. A reception du paquet de réponse, la section {\bf SECTION\_DCACHE\_RSP} va écrire la ligne dans le cache et déverrouiller la ligne ({\it lock\_by\_read = 0}).
    \end{itemize}
  \end{itemize}
\end{itemize}

\subSection{Structure interne}

Dans cette section, nous allons voir comment sont structuré les ressources internes du cache non bloquant.

Avant de détailler les interfaces de chaque composant, nous pouvons préciser que chaque interfaces suivent le protocole fifo. C'est a dire que pour chaque interface, il y a des blocs ``producteurs'' et des blocs ``consommateurs''. Les producteurs possède une sortie {\bf VAL} (c'est une entrée pour les consommateurs) qui indique si la requête qu'ils émettent est valide. Les consomateurs possède sortie {\bf ACK} (c'est une entrée pour les producteurs) qui indique si le consommateur peut accepter une requête. Il y a un transaction si $VAL and ACK = 1$ à la fin d'un cycle d'horloge. 
L'avantage de ce protocole de la gestion intégré du contôle de flux : si un producteur n'a plus de donnée ou un consomateur ne peux plus accepter de transaction, il suffit de positionner respectivement les signaux {\bf VAL} et {\bf ACK} à 0 pour ne pas autoriser de transaction.


Nous allons maintenant détailler les ressources internes du cache non bloquant : 
\begin{itemize}
\item Trois files d'attentes : 
  \begin{description}
  \item[QUEUE\_READ\_HIT :] (figure \ref{CACHE_bloc_QUEUE_READ_HIT}) Cette file d'attente s'occupe de transmettre le plus tôt possible les requêtes de lecture ayant fait un HIT. 
    \begin{description}
    %\item {\it Valid : } Indique si l'entrée correspondante contient une donnée valide 
    \item {\it Index : } Index vers une entrée de RAM\_INFO
    \end{description}
    \printgraphonly{CACHE_bloc_QUEUE_READ_HIT}{.8}
  \item[QUEUE\_REQ :] (figure \ref{CACHE_bloc_QUEUE_REQ}) Cette file est utilisée comme tampon d'écriture et de requête de lecture ayant fait un miss. Elle attende leur envoie à la mémoire.
    \begin{description}
    %\item {\it Valid : } Indique si l'entrée correspondante contient une donnée valide 
    \item {\it Index : } Index vers une entrée de RAM\_INFO
    \end{description}
    \printgraphonly{CACHE_bloc_QUEUE_REQ}{.8}
  \item[QUEUE\_RSP :] (figure \ref{CACHE_bloc_QUEUE_RSP}) La file est utilisée comme tampon pour les réponses provenant de la mémoire.
    \begin{description}
    %\item {\it Valid :} Indique si l'entrée correspondante contient une donnée valide 
    \item {\it Index :} Index vers une entrée de RAM\_INFO 
    \item {\it Line :} Contient une ligne de cache retournée par l'interface de réponse et devant être écrit dans le bloc RAM\_DATA.
    \item {\it Error :} Indique si l'accès effectué à générée une erreur ou pas. L'erreur sera interprété par l'exception générique ``Erreur de Bus''.
    \end{description}
    \printgraphonly{CACHE_bloc_QUEUE_RSP}{.8}
  \end{description}
\item Trois blocs mémoires : 
  \begin{description}
  \item[RAM\_TAG :] (figure \ref{CACHE_bloc_RAM_TAG}) Contient les informations pouvant identifier les adresses contenus dans cette ligne de cache
    \begin{description}
    \item {\it Tag :} Il s'agit de l'étiquette de l'adresse. A partir du numéro de ligne et de l'étiquette, cette RAM peut déterminer si le cache fait un succès ou non.
    \end{description}
    \printgraphonly{CACHE_bloc_RAM_TAG}{.8}
  \item[RAM\_DATA :] (figure \ref{CACHE_bloc_RAM_DATA}) Contient les données de la ligne de cache 
    \begin{description}
    \item {\it Line :} Contient la ligne de cache proprement dite 
    \end{description}
    \printgraphonly{CACHE_bloc_RAM_DATA}{.8}
  \item[RAM\_LOCK :] (figure \ref{CACHE_bloc_RAM_LOCK}) Contient les bits de gestions de dépendances
    \begin{description}
    \item {\it Valid :} Indique si la ligne correspondant contient une donnée valide. 
    \item {\it Lock\_by\_read :} Si le bit est positionné, alors il existe une requête de lecture actuellement en cours de traitement par le cache.
    \item {\it Lock\_by\_write :} Si le bit est positionné, alors il existe une requête d'écriture actuellement en cours de traitement par le cache.
    \end{description}
    \printgraphonly{CACHE_bloc_RAM_LOCK}{.8}
  \item[RAM\_INFO :] (figure \ref{CACHE_bloc_RAM_INFO}) Contient les informations relative au requête pendante. Pour plus de détails voir la section \ref{RAM_INFO}
    \begin{description}
    \item {\it Valid :} Indique si l'entrée correspondante contient une donnée valide 
    \item {\it Trdid, Pktid :} Identifiant de la requête. Le trdid indique le numéro de contexte du processeur qui à émit la requête. Alors que le pktid est le numéro de paquet de ce contexte. Le processeur garantie l'unicité du couple {trdid, pktid}.
    \item {\it Address :} Adresse de la requête. Pour une identification rapide de la ligne concernée.
    \item {\it Type :} Type de la requête (lecture, écriture, taille de l'accès, ...)
    \item {\it Uncached :} Indique si la réponse doit modifier le cache. Dans le cadre d'une lecture par exemple.
    \item {\it Data :} Donnée (en cas d'écriture : DCACHE.REQ\_WDATA, en cas de lecture avec succès : contenu d'un mot de la ligne de cache) 
    \end{description}
    \printgraphonly{CACHE_bloc_RAM_INFO}{.8}
  \end{description}
\item  Quatre automates : 
  \begin{description}
  \item[FSM\_DCACHE\_REQ :] (figure \ref{CACHE_automate-fsm_dcache_req}) %Cet automate gère la consommation des requêtes provenant du cache et, suivant le type d'accès et la réussite de l'accès, l'écriture dans les QUEUE\_REQ et QUEUE\_READ\_HIT 
    \printgraphonly{CACHE_automate-fsm_dcache_req}{1}

  \item[FSM\_DCACHE\_RSP :] (figure \ref{CACHE_automate-fsm_dcache_rsp}) %L'automate gère la consommation de donnée de la QUEUE\_RSP et s'occupe d'écrire dans le cache les lignes chargées.
    \printgraphonly{CACHE_automate-fsm_dcache_rsp}{.8}
  \item[FSM\_VCI\_REQ :] (figure \ref{CACHE_automate-fsm_vci_req}) %L'automate s'occupe de consommer une donnée de QUEUE\_REQ (si la file n'est pas vide) et la lance sur l'interface VCI\_REQ (si l'interface n'est pas occupée). 
    \printgraphonly{CACHE_automate-fsm_vci_req}{.8}
  \item[FSM\_VCI\_RSP :] (figure \ref{CACHE_automate-fsm_vci_rsp}) %L'automate s'occupe de consommer sur l'interface VCI\_RSP (si l'interface n'est pas occupée) et l'écrit dans  la file QUEUE\_RSP (si la file n'est pas pleine).
    \printgraphonly{CACHE_automate-fsm_vci_rsp}{.8}
  \end{description}
\end{itemize}

\subSection{RAM\_INFO en détail}\label{RAM_INFO}
Le bloc RAM\_INFO contient les informations relative aux requêtes pendantes. Elle est accéder par trois section du cache différente : {\bf SECTION\_DCACHE\_REQ} afin d'allouer une entrée dans ce bloc et d'écrire les informations concernant la requête, {\bf SECTION\_VCI\_REQ} afin de lire les informations utilies pour créer une requête VCI, et {\bf SECTION\_DCACHE\_RSP} afin de lire les informations permettant de répondre au processeur et d'écrire dans le cache et de désallouer l'entrée de RAM\_INFO.

Le numéro de l'entrée dans lequel est écrit les informations est souvent utilisé. Aussi bien dans les différentes files QUEUE\_REQ, QUEUE\_RSP et QUEUE\_READ\_HIT, que pour indexer un paquet VCI. Ceci permet de ne pas dupliquer les informations inutilement et donc d'avoir des FIFOs contenant peut d'information.

Le numéro de l'entrée sert également comme identifiant de requête lors d'une transaction VCI. Parce que le cycle de vie de cette identifiant garantie son unicité sur le réseau VCI.

Nous pouvons remarquer que le nombre d'entrée dans le bloc RAM\_INFO indique le nombre de requête pouvant être géré simultanément par le cache. Lorsque ce bloc est plein, aucun nouvelle requête ne peut être accepté.

Le nombre d'entrée de cette mémoire est délimité par les tailles des files QUEUE\_REQ et QEUEUE\_READ\_HIT. C'est à dire, la taille de RAM\_INFO doit être comprit entre :\\
$[ max(\{size\_QUEUE\_REQ\}, \{size\_QUEUE\_READ\_HIT\}) ; \{size\_QUEUE\_REQ\} * \{size\_QUEUE\_READ\_HIT\} ]$

\subSection{Choix de la victime}

Dans cette section nous allons expliquer l'algorithme de selection de la victime et les motiviations de ce choix.

Le chemin entre un processeur et son cache est souvent le chemin critique d'en un processeur. Il passe par la combinatoire qui indique que le processeur demande un accès et fait un aller retour avec l'aquittement du cache de la requête.

Nous avons vut que l'aquittement donner par le cache est dépendante du type et donc du contenu du cache. Suivant le protocole définit dans la figure \ref{CACHE_protocole}, l'aquittement d'une requête dépend de la validité de la victime.

Pour des raisons de rapidité, nous avons décider d'implémenter un algorithme pseudo aléatoire. Par exemple un compteur de ASSOC bits ou un LFSR (Linear Feedback Shift Register) de ASSOC+1 bits (car dans un LFSR, la combinaison 0 n'est pas une combinaison valide).

\subSection{Structure du pipeline}

Dans cette sous section nous allons présenter succintement les étage de pipelines. Suivant le type de la requête, le temps de réponses minimal différe. Pour cela, nous posons N le nombre de cycle aller/retour jusqu'à la mémoire et M le temps nécessaire pour avoir une ligne de cache complète après réception du premier paquet. On considére M et N comme des temps moyens et les files interne comme étant vide.
\begin{description}
\item[Read - Hit          : ] 2 cycles.
\item[Read - Miss         : ] 3 + N + M cycles.
\item[Write               : ] 4 + N cycles.
\item[Lock et Prefetch    : ] 2 cycles.
\item[Invalidate et Flush : ] 2 cycles.
\end{description}

\printgraphonly{CACHE_pipeline}{.8}