source: trunk/IPs/systemC/processor/Morpheo/Documentation/Source/Documents/document-cache-specification/fr/root.tex @ 44

\Section{Introduction}
\subSection{Motivations}
Les processeurs haute performance lancent plusieurs instructions, de manière non ordonnée et spéculativement. Un défaut de cache ne doit pas bloquer le processeur. Le cache doit être non blouqant, c'est à dire qu'il doit pouvoir accepter des requêtes venant du processeur pendant le traitement d'un MISS.

\subSection{Démarche du document}
Le document est accès en quatre parties :
\begin{itemize}
\item Section \ref{overview_partial} : dans un premier temps, nous allons présenter une architecture qui satisfait des requêtes courantes (lectures / écritures, succès / échec) sur des adresses non conflictuelles. Cette première architecture est utilisable dans la majorité des cas.
\item Section \ref{problem}          : dans cette section, nous allons analyser des problèmes arrivant lors d'accès à des adresses conflictuelles, et/ou dans un environnement multi contexte. Pour chaque problème, nous proposons des solutions.
\item Section \ref{overview_full}    : cette section est la synthèse des deux précedentes. Nous allons modifier l'architecture de départ afin d'apporter des solutions aux problèmes énumérés dans la section \ref{problem}.
\item Section \ref{description}      : cette dernière section énumère les structures internes, ainsi que les automates de la solution retenue dans la section \ref{overview_full}.
\end{itemize}

\subSection{Paramètres nécessaires}
\subsubSection{Paramètres interne du cache}

\begin{center}
  \begin{tabular}{|ll|ccc|}
    \hline
    Paramètres                &             &                       Min &                            Max & Pas \\
    \hline
    Taille du mot             & SIZE\_WORD  &                   32 bits &                        64 bits &  *2 \\
    Nombre de lignes par mot  & NB\_WORD    &                     1 mot &                        64 mots &  *2 \\
    Nombre de lignes          & NB\_LINE    &                   1 ligne &                    1024 lignes &  *2 \\
    Associativité             & ASSOC       & 1 banc de NB\_LINE lignes & NB\_LINE/16 bancs de 16 lignes &  *2 \\
    Taille des files internes & SIZE\_QUEUE &                    1 case &                       64 cases &  *2 \\
    \hline
  \end{tabular}
\end{center}

\subsubSection{Paramètres de l'interface cache / processeur}

\begin{center}
  \begin{tabular}{|ll|ccc|}
    \hline
    Paramètres                              &             &     Min &     Max & Pas \\
    \hline
    Taille d'une donnée                     & SIZE\_DATA  & 32 bits & 64 bits &  *2 \\
    Taille de l'adresse                     & SIZE\_ADDR  & 32 bits & 64 bits &  *2 \\
    Taille de l'identifiant du propriétaire & SIZE\_TRDID &  0 bits &  4 bits &  +1 \\
    Taille de l'identifiant de transaction  & SIZE\_PKTID &  0 bits &  4 bits &  +1 \\
    \hline
  \end{tabular}
\end{center}

\subSection{Spécification}
\begin{itemize}
\item Write through     (Les données sont à la fois écrite dans le bloc du cache et dans le bloc de la mémoire de niveau inférieur).
\item Write no allocate (Les échecs d'écriture n'affectent pas le cache, le bloc n'est modifié que dans le niveau mémoire inférieur).
\item Cache associatif  (Le cache est découpé plusieurs banc et une ligne peut être placé dans n'importe quel banc.)
\item Non bloquant      (Le cache permet d'avoir plusieurs requêtes en cours de résolution)
\item Le modèle de consistance mémoires du processeur est relachés (Nous permettons aux lectures et aux écritures de se lancer et de se terminer de manière non ordonnées.)
\end{itemize}

\subSection{Hypothèse de travail}

Nous allons supposer que le cache sera connecté à un processeur superscalaire d'ordre 4. Que le code exécuté contient 20\% de lectures et 10 \% d'écritures. Nous avons donc en moyenne 1 accès mémoire par cycle. 
Si nous ciblons un cache ayant au minimum 90\% de réussites, nous obtenons alors les ratios suivants :
\begin{itemize}
\item 60 \% de lectures qui réussissent.
\item 30 \% d'écritures qui réussissent.
\item 6,6\% de lectures qui échouent.
\item 3,3\% d'écritures qui échouent.
\end{itemize}

\Section{Vue d'ensemble - 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, de l'interface des réponses. Pour cela, 4 automates gèrent les interfaces et la gestion des ressources. La micro-architecture du cache ce décompose comme suit :
\begin{itemize}
\item Quatre automates : 
  \begin{description}
  \item[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 blocs QUEUE\_REQ et QUEUE\_READ\_HIT 
  \item[FSM\_DCACHE\_RSP :] L'automate gère la consommation de réponses contenues dans la QUEUE\_RSP et s'occupe d'écrire les lignes chargés dans le cache.
  \item[FSM\_VCI\_REQ    :] L'automate s'occupe de consommer une requête contenue dans la 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). 
  \item[FSM\_VCI\_RSP    :] L'automate s'occupe de consommer des réponses 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). 
  \end{description}
\item Trois files d'attentes : 
  \begin{description}
  \item[QUEUE\_READ\_HIT :] Cette file d'attente s'occupe de transmettre le plus tôt possible les requêtes de lectures ayant fait un HIT.
  \item[QUEUE\_REQ       :] Cette file est utilisée comme tampon d'écriture et de requête de lecture ayant fait un miss. Elle attend leur envoi à la mémoire.
  \item[QUEUE\_RSP       :] La file est utilisée comme tampon pour les réponses provenant de la mémoire.
  \end{description}
\item Trois blocs mémoires : 
  \begin{description}
  \item[RAM\_TAG  :] Contient les informations pouvant identifier les adresses contenues dans cette ligne de cache. Ce bloc est composé de ASSOC bancs de tailles identiques.
  \item[RAM\_DATA :] Contient les données de la ligne de cache. Ce bloc est composé de ASSOC bancs de tailles identiques.
  \item[RAM\_INFO :] Contient les informations relative aux requêtes pendantes.
  \end{description}
\end{itemize}

\subSection{Acheminement des requêtes}
Dans cette section, nous allons voir l'acheminement d'une requête suivant son type.

\begin{description}
\item[Read - Hit  :] La requête accède en parallèle aux RAM\_TAG et au RAM\_DATA. La donnée lue est écrite dans la RAM\_INFO, alors que le pointeur vers RAM\_INFO est sauvegardé dans le bloc QUEUE\_READ\_HIT. Ensuite la requête attend d'être sélectionnée par l'automate FSM\_DCACHE\_RSP, puis lit les informations à partir de la RAM\_INFO et est acheminée vers le port de réponse.
\item[Read - Miss :] La requête de lecture réalisant un miss, écrit les informations concernant la requête dans la RAM\_INFO. Le pointeur de RAM\_INFO sera écrit dans la QUEUE\_REQ. L'automate FSM\_VCI\_REQ va envoyer la requête sur le réseau VCI. La réponse reviendra par l'intermédiaire de l'automate FSM\_VCI\_RSP qui enregistre la ligne de cache en cours d'arrivée dans un tampon. Dès la réception de la fin de paquet, le tampon est enregistré dans la QUEUE\_RSP. L'identifiant de requête vci sera un index vers RAM\_INFO, c'est pour cela que lorsque l'automate FSM\_DCACHE\_REQ récupère une réponse dans la QUEUE\_RSP, elle peut retrouver les informations de la requêtes dans RAM\_INFO.
\item[Write - Hit  :] La gestion d'un write hit est équivalent à celle d'un read-miss : lors de la requête les informations sont stockées dans la RAM\_INFO (ainsi que la donnée à écrire). Lors de la réponse, (à la différence d'un read-miss, il n'y a pas de retour de ligne) la donnée à écrire va l'être dans le bloc RAM\_DATA.
\item[Write - Miss :] Un échec d'écriture est équivalent à une réussite d'écriture mais sans mise à jour du cache.
\item[Lock et Prefetch :] Ce cache n'implémentant ces fonctionnalités et étant le dernier niveau de cache avant l'accès à l'interconnect, alors ces requêtes sont traitées comme étant des Read Hit (sans lecture du cache)
\item[Invalidate :] Ce cache étant le dernier niveau de cache avant l'accès à l'interconnect, il est transmis à l'interface des réponses au travers de la QUEUE\_READ\_HIT. Lors de la lecture de cette file, on va accéder au cache et mettre le bit valid de la ligne à 0
\item[Flush :] Le cache étant un cache write through, il y a une cohérence entre le contenu du cache et le contenu de la mémoire. L'effet de cette commande est identique à une commande Invalidate. 
\end{description}
Une petite remarque concernant le Write-Hit :

 Quel automate doit gérer la mise à jour du cache : FSM\_DCACHE\_REQ ou FSM\_DCACHE\_RSP? Le premier à l'avantage de rendre la modification de la ligne visible rapidement pour les autres requêtes. Or il faudra soit rajouter un nouveau port d'écriture aux bancs RAM\_TAG et RAM\_DATA, soit synchroniser les automates afin de partager le port d'écriture. Le deuxième cas à pour avantage de n'avoir qu'un seul port d'écriture.

Nous optons pour la deuxième solution. Ce choix est également motiver pour uniformiser les solutions proposées pour les problèmes de consistances mémoires.

\Section{Quelques problèmes du modèle simplifié}\label{problem}
Dans cette section, nous allons voir quelques problèmes fonctionnelle du modèle de base et nous allons présenter des solutions.

\subSection{Requêtes multiples d'échec de lectures}
Supposons le cas où le processeur réalise une suite d'accès en lecture sur des adresses consécutives en mémoire. Par exemple le processeur demande l'adresse 0x100, 0x104, 0x108, 0x10C pour une taille de ligne de 4 mots et un nombre de ligne de 8 lignes. Si la première requête de lecture fait un miss, alors les 3 autres requêtes vont également échouer.

Il y aura dans ce cas deux problèmes. Le premier étant l'émission, par le cache, de 4 demandes de lignes, alors qu'une seule requête est vraiment utile. Ce n'est pas un problème en soit, mais ceci nous amène au deuxième problème : si le cache n'est pas direct-map, dans ce cas les 4 lignes identiques vont être logées à plusieurs endroit dans le cache.
\begin{itemize}
\item {\it Le premier problème est causé par la non sauvegarde par le cache de l'historique des requêtes. }
\item {\it Le deuxième problème est causé par le non accès à la RAM\_TAG, au moment des réponses. }
\end{itemize}

Il y a trois solutions pour remédier à ces problèmes :
\begin{enumerate}
\item Ajouter un port de lecture au TAG. Quand les réponses arrivent, il faut tester si la requête de lecture fait toujours un miss. Si ce n'est plus le cas, alors aucune mise à jour de cache sera effectué. 
  \begin{description}
  \item[+ :] coût minimum si on implémente le banc de registre TAG par un banc de registres multi-bancs (mais synchronisation entre les automates FSM\_DCACHE\_REQ et FSM\_DCACHE\_RSP).
  \item[- :] accès lecture de mémoire inutile, coût des miss plus long 
  \end{description}
\item Empêcher ce cas d'arriver en faisant l'allocation de la ligne lors de la requête. Pour cela, nous allons ajouter un bit dans le TAG : "valid\_data", ce bit est mis à 0 lors d'une requête et positionné à 1 lors de la réponse. On accepte une requête si (valid\_data = 1). 
  \begin{description}
  \item[+ :] pas de duplication des requêtes inutile.
  \item[- :] coûte 1 bit par ligne de cache, suppression d'une ligne de cache alors qu'elle pouvait encore être utile. Si la requête n'est pas accepté, le processeur peut croire que le cache est bloqué et dans ce cas, maintient la requête. 
  \end{description}
\item Empêcher ce cas d'arriver en verrouillant les index. Pour chaque index, on rajoute un bit de lock. Ce bit est positionné à 0 lors d'une requête qui fait MISS et remit à 1 lors de la réponse. On accepte une requête qui fait miss si lock[index] = 0 
  \begin{description}
  \item[+ :] pas de duplication des requêtes, par rapport à la solution précédente, on a pas supprimé une ligne encore utile. 
  \item[- :] coûte 1 bit par index. Avec l'augmentation de l'associativité, on va diminué le coût mais augmenter le nombre de ligne verrouiller. 
  \end{description}
\end{enumerate}

Pour les deux dernières solutions, nous pouvons faire deux remarques :
\begin{itemize}
\item Au lieu de refuser les requêtes qui ne satisfont pas les conditions, nous pouvons les accepter et les indiquer comme "uncached". Ceci aura pour effet de ne pas mettre à jour le cache, d'accepter les requêtes et donc d'avoir les réponses rapidement (car lors d'un accès non caché, nous n'avons pas besoin de chercher une ligne entière).
\item DCACHE.REQ\_ACK ne dépend plus que de l'état des FIFOs (donc disponible au début d'un cycle) mais également des requêtes entrantes (qui sont disponible en fin de cycle). Pour couper cette chaîne critique, nous pouvons pipeliner les accès au port de requêtes. Pour plus d'information, voir la section \ref{pipeline}
\end{itemize}

La différence principales entre les deux dernières solutions porte sur le nombre de ligne verrouiller. Donc sur le coût du vérrouillage mais engendre des pertes de performances lors d'un cache fortement associatif. De plus, la solution de verrouiller l'index n'oblige pas de faire l'allocation de la ligne de cache lors de la requête. Car la totalité de l'index est verrouillé, alors il ne peut avoir aucune miss.

\subSection{Évincement précoce de ligne }

Dans le cas d'un write HIT, lors de la requête, on détermine le numéro de ligne, et le numéro de banc où la donnée doit être écrite. L'écriture effective se fait lors de la réponse. La ligne cible peut pendant ce temps être évincer par une autre réponse (un Read MISS par exemple).
Les solutions apportés par ce problème sont presque les mêmes que pour le problème précèdent :
\begin{enumerate}
\item Ajouter un port d'écriture. Dans ce cas, l'écriture effective se fait lors de la requête. 
\item Verrouillage des lignes : ceci va empêcher l'évincement de la ligne concerné par l'écriture.
\item Verrouillage des index : ceci va empêcher les évincements des lignes de cache.
\end{enumerate}

\subSection{Gestion de la Cohérence et Consistance mémoire}

Le système mémoire doit assurer la cohérence mémoire (détermine quelle valeur est renvoyé par une lecture) et la consistance mémoire (détermine quand une valeur écrite sera récupérée par une lecture).

Les problèmes de cohérence mémoire ne survienne que dans le cas d'un environnement multiprocesseur ou avec des périphériques d'entrée/sortie. Nous n'aborderons pas ici les solutions matériels pour résoudre ce problème. Le problème pouvant être résolue de manière logicielle en effectuant la séquence suivante présenté dans le graphe \ref{CACHE_coherence_memoire}

\printgraphonly{CACHE_coherence_memoire}{.8}
 
Nous allons principalement nous intéresser aux problèmes de consistance mémoire.
Le problème est le suivant : le cache lance deux requêtes, une lecture et une écriture. Ces requêtes ciblent le même bloc mémoire. L'interconnect qui relie le cache au bloc mémoire ne garantie pas l'ordre des requêtes. (La norme VCI n'impose pas d'interconnect qui délivre les messages dans l'ordre). La lecture et l'écriture entre en compétition pour l'accès à la zone mémoire, et peuvent accéder à la zone mémoire dans un ordre différent que dans l'ordre d'émission

Ce problème est amplifié par le fait qu'une demande de lecture va lire une ligne de cache entière, donc il y a également des dépendances si les deux adresses  sont dans la même ligne de cache et que l'un des deux accès est une lecture.

Il y a 4 types de dépendances :
\begin{description}
\item[RaR (Read after Read)   :] Il s'agit de deux lectures successives vers la même ligne de cache.
\item[WaW (Write after Write) :] Il s'agit de deux écritures successives vers la même adresse.
\item[WaR (Write after Read)  :] Il s'agit d'une lecture suivit d'une écriture vers la même ligne de cache. 
\item[RaW (Read after Write)  :] Il s'agit d'une écriture suivit d'une lecture vers la même ligne de cache.
\end{description}

En reprenant les 4 types de dépendances, nous allons voir comment ces dépendances sont gérées :
\begin{itemize}
\item Dans le cadre d'une dépendance RaR, le seul problème provoqué est le lancement de requête multiple de lecture faisant des miss. (voir la section concerné). 
\item Du point de vue du processeur, dans le cadre d'exception précise, une écriture n'a le droit de modifier le contexte visible du programmeur que si les instructions avant l'écriture sont terminée. Dans ce cas, les dépendances WaR sont gérées par le processeur. 
\item Les dépendances WaW peuvent être implicitement géré par le processeur si les writes sont bloquants (donc attendent une réponse du cache). Les performances sont alors fortement dégradées car un write aura le même coût qu'un read faisant un MISS dans tous les niveaux de la hiérarchie mémoire. Nous pouvons tout de même noter qu'un write bloquant permet d'avoir une exception précise.
\item Les dépendances RaW sont moins triviale : le cpu peut vérifier les cas de RaW sur la même adresse et bypasser l'accès au cache. Or comme les lectures lisent une ligne de cache entière, deux adresses peuvent être différentes mais cibler la même ligne de cache. 
\end{itemize}

Pour gérer ces différents problèmes, il y a deux solutions :
\begin{enumerate}
\item Gestion par le CPU : les écritures demandent des acquittement une fois que la mémoire à été mise à jour. Dans ce cas à tous moment le processeur peut savoir si une écriture est en cours d'éxècution. Les lectures peuvent être lancées s'il n'y a pas de dépendances au niveau ligne avec des écritures. De même entre deux lectures et écritures. Malheureusement cette méthode à la mauvaise propriété de saturer l'unité de mémoire avec des écritures lancées mais attendant leur écriture en mémoire. Ce problème de latence peut être diminué si l'acquittement des écritures se fait jusqu'au premier niveau de cache qui intègre des mécanismes de consistance mémoire. 
\item Gestion par le Cache : les problèmes d'évincement précoce de ligne de cache sont du à des lectures qui évincent une ligne qui aurait du contenir le résultat d'une écriture. C'est donc une dépendance RaW car les deux adresses ont les même index. Donc nous pouvons réutiliser la solution pour les problèmes de consistance mémoire. La solution proposée içi reprend celle proposée pour les deux problèmes analysés aux sections précédentes : 
\end{enumerate}

\begin{tabular}{l|ll}
Cas         & Action lors d'une requête du processeur & Action lors d'une réponse du bus \\
\hline
Read Hit    & Lecture de la donnée                    & Aucune réponse attendue          \\
            & Pas de requête envoyée au bus           & \\
Read Miss   & Allocation d'une ligne de cache         & Écriture de la ligne et déverrouillage \\
            & Verrouillage                            & \\
Write Hit   & Verrouillage de la ligne de cache       & Écriture de la ligne et déverrouillage \\
Write Miss  & Allocation d'une ligne de cache         & Invalidation de la ligne (write no-allocate)\\
            & Verrouillage                            & \\
\end{tabular}

Dans la deuxième solution, aucune requête provenant du processeur n'est accepté si elle concerne une ligne de cache verrouillée.

\subSection{Multi-Contexte }
Ce cache non bloquant doit pouvoir être utilisé dans un environnement multi-contexte (exécution en parallèle de plusieurs threads). L'implication du multi-contexte ne va pas modifier le comportement du cache (Car ce cache est physiquement indéxé et tagué).

Le cache est optimisé pour utiliser les propriétés de localité spatiale et temporelle d'un programme. Avec le multi-contexte, le cache va être soumit à plusieurs flot qui ne sont pas dépendant entre eux. Ceci va entraîner des évincements de lignes en faveur d'un contexte, alors que la ligne victime pouvait être utilisée par un autre contexte. De plus, ceci va augmenter le phénomène décrit dans la section "Évincement précoce de ligne" : des écritures non encore finalisées vont voir leur lignes cibles évincées.

\Section{Vue d'ensemble - 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}

Nous allons maintenant modifier le modèle de base en vue d'intégrer la solution retenue. La solution consiste en l'implémentation des deux principaux mécanismes vut précédemment : l'allocation précoce de victime et le verrouillage de lignes. Ces solutions ont l'avantage de garder les structures déjà présente dual-port, et de régler simplement les problèmes de consistance mémoire.

Pour cela, nous ajoutons un banc de registre, RAM\_LOCK, qui contiendra 3 bits par ligne :
\begin{itemize}
\item Valid : qui est le bit valid anciennement contenu dans la RAM\_TAG. 
\item Lock\_by\_read : indique si une lecture est actuellement pendante. 
\item Lock\_by\_write : indique si une écriture est actuellement pendante. 
\end{itemize}

Détaillons les différentes actions :

\printgraphonly{CACHE_protocole}{.6}
 
Le choix de la victime est réalisé lors de l'émission de la requête. Un read hit vérifie si une requête de lecture est en cours sur cette même ligne de cache. Si c'est le cas, alors la requête sera non cachée (donc ne mettra pas à jour le cache).
Dans le cas d'un write hit ou d'un read miss, la ligne de cache correspondant va être verrouillée. Il est à noter que dans le cas d'un write qui fait miss, le cache va allouer une ligne pour ce write. Comme le cache est write no allocate, la ligne va être invalidée lors de la réponse.

Reprenons les différents dépendances entre requêtes mémoires :

\begin{tabular}{l|ll}
Dépendance & Dépendance de ligne et adresse identique & Dépendance de ligne et adresse différente\\
\hline
RaR        & Bypass dans le processeur                & Rend la deuxième lecture non cachée \\
WaW        & Géré par le processeur (mono contexte)   & Pas de problème \\
WaR        & Géré par le processeur (mono contexte)   & La lecture verrouille la ligne.\\
           &                                          & L'écriture devra attendre la fin de la lecture\\
RaW        & Bypass dans le processeur                & L'écriture verrouille la ligne.\\
           &                                          &  La lecture devra attendre la fin de l'écriture\\
\end{tabular}

\Section{Description détaillée}\label{description}

\subSection{Structure interne}

Pour chaque composant interne, les interfaces suivent le protocole fifo (le producteur possède une sortie VAL qui indique s'il a une requête valide et le consommateur possède une sortie ACK qui indique s'il peut accepter une transaction. Il y a une transaction si VAL et ACK sont tous les deux à 1 à la fin d'un cycle). L'avantage est qu'il est très facile de faire du contrôle de flux.

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 :] 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 :] 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 :] 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 la donnée retournée par l'interface de réponse
    \item {\it Error :} Indique si l'accès effectué à généré une erreur ou pas. 
    \end{description}
    \printgraphonly{CACHE_bloc_QUEUE_RSP}{.8}
  \end{description}
\item Trois blocs mémoires : 
  \begin{description}
  \item[RAM\_TAG :] Contient les informations pouvant identifier les adresses contenus dans cette ligne de cache
    \begin{description}
    \item {\it Tag :} Numéro du tag correspondant à la ligne
    \end{description}
    \printgraphonly{CACHE_bloc_RAM_TAG}{.8}
  \item[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 :] 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 lecture pendante
    \item {\it Lock\_by\_write :} Si le bit est positionné, alors il existe une écriture pendante 
    \end{description}
    \printgraphonly{CACHE_bloc_RAM_LOCK}{.8}
  \item[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
    \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
    \item {\it Uncached :} Indique si la réponse doit modifier le cache
    \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 :] 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 :] 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 :] 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 :] 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}
La RAM\_INFO contient les informations relative aux requêtes pendantes. Elle possède trois ports : 2 ports de lecture et 1 port d'écriture.
Le numéro de registre dans lequel est écrit les informations est enregistré dans les files QUEUE\_REQ, QUEUE\_RSP et QUEUE\_READ\_HIT. Ceci permet de ne pas dupliquer les informations.

Pour cela, lors d'une transaction acceptée sur l'interface DCACHE\_REQ, il faut allouer un registre de la RAM\_INFO. La dés-allocation de ce registre aura lieu pendant une transaction acceptée sur l'interface DCACHE\_RSP.
Le numéro de registre sert également comme identifiant de requête lors d'une transaction VCI. (Le cycle de vie de cette identifiant garantie son unicité sur le réseau VCI)

Nous pouvons noter alors que nous pouvons accepter une requête sur le l'interface DCACHE\_REQ si la file de destination n'est pas vide ET s'il y a encore une place de libre dans RAM\_INFO.

%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Dans un premier temps, la taille de RAM\_INFO sera le nombre maximal de requêtes pendantes que le processeur peut admettre soit : \{nombre de contexte\} * \{taille de la load store queue\} (dans ce premier cas, RAM\_INFO n'a pas besoin de contenir le pktid et le trdid de la requête). De plus le nombre de port de lecture sera de 2.

Les optimisations possibles sont :
\begin{itemize}
\item Diminution du nombre de registres : en pratique, la taille de RAM\_INFO devra être comprit entre max(\{taille de la QUEUE\_REQ\}, \{taille de la QUEUE\_READ\_HIT\}) et \{taille de la QUEUE\_REQ\} * \{taille de la QUEUE\_READ\_HIT\}. 
\item Un seul port de lecture : implémentation multi-banc de RAM\_INFO. Pour la gestion de conflit, il faut utiliser la même priorité que pour le choix entre la QUEUE\_READ\_HIT et la QUEUE\_RSP.
\end{itemize}

\printgraphonly{CACHE_implementation_RAM_INFO}{1}

\subSection{Pipeliner l'accès au cache}\label{pipeline}
Nous avons vut que DCACHE.REQ\_ACK ne dépend pas que de l'état des FIFOs (donc disponible au début d'un cycle) mais également des requêtes entrantes (qui sont disponible en fin de cycle). Pour couper cette chaîne critique, nous pouvons pipeliner l'accès au port de requêtes ainsi que celui des réponses. 

\subsubSection{DCACHE\_RSP}

Sur cette interface, les réponses sont maintenues par le cache jusqu'à ce que le processeur accepte la réponse. Pour cela, nous pouvons implémenter une simple barrière de pipeline.

\subsubSection{DCACHE\_REQ}

Sur cette interface, les requêtes ne sont pas maintenues par le processeur quand le cache n'accepte pas une requête. Cette spécification permet au processeur de choisir une autre requête si elle n'a pas été acceptée. (Nous rappelons qu'une requête n'est pas acceptée si la file de destination est pleine ou si une requête précedente a verrouillée la ligne.)

Dans ce cas ajouter une barrière de pipeline va consommer la requête mais le cache va être dans l'imposibilité de l'accepter et va empêcher d'en choisir une autre.

\subSection{Choix de la victime}
Pour la sélection des lignes à evincer, nous allons implémenter un algorithme pseudo aléatoire.
L'avantage de cet algorithme est de ne pas avoir besoin de sauvegarder un historique des accès.

\subSection{RAM mono-port}\label{mono-port}

La mémoire la plus dense est de la mémoire mono-port (soit une lecture, soit une écriture par cycle). 

Comme chaque interface des blocs de RAM ont une interface fifo, elle intègre donc un contrôle de flux. Ceci les rends indépendant du nombre de port intégrer dans chaque bloc mémoire. (Par exemple, un le bloc RAM\_DATA est implémenté avec de la mémoire dual-port, alors les sorties READ\_ACK et WRITE\_ACK seront toujours égals à 1).

Néanmoins, nous devons prendre soin à ce que chaque étage du cache ne commande pas deux interfaces d'un même bloc RAM. Or dans la solution retenue, nous avons les blocs RAM\_TAG et RAM\_LOCK qui ont besoin de deux interfaces durant la partie DCACHE\_REQ. Pour cela nous devons réaliser une barrière de pipeline.

Le premier étages va réaliser les lectures, alors que le second va mettre à jour ces bancs. Il est à noter qu'il va devoir avoir un bypass car comme la RAM\_LOCK ainsi que le bloc RAM\_TAG n'a pas encore été mis à jour, cette requête peut être suivit par une autre requête qui entre en conflit.

Le graphe \ref{CACHE_overview_mono-port} montre les modifications à apporter au cache pour n'avoir qu'un port par étage.

\printgraphonly{CACHE_overview_mono-port}{.8}

\subSection{Structure du pipeline}

Suivant le type d'une requête, le temps de réponse minimal n'est pas le même (On pose N le nombre de cycle aller retour jusqu'a la mémoire et M le temps pour avoir une ligne de cache complète) :
\begin{itemize}
\item Read - Hit : 2 cycles.
\item Read - Miss : 4 + N + M cycles.
\item Write : 5 + N cycles.
\item Lock et Prefetch : 2 cycles.
\item Invalidate et Flush : 2 cycles.
\end{itemize}

\printgraphonly{CACHE_pipeline}{.8}

%\subSection{Signaux de contrôles}
%Dans cette section, nous allons voir les fonctions combinatoires permettant de gérer les différents signaux de contrôles