\Section{Introduction}\label{introduction}
\subSection{Motivations}
Les processeurs haute performance lancent plusieurs instructions, de manière non ordonnée, spéculativement et provenant de plusieurs contextes matériels. Le processeur va donc exécuter plusieurs flots d'instructions contenant des accès mémoires et qui ne sont pas forcéments utiles (car spéculatif). Pour ces raisons, un défaut de cache (MISS) doit éviter de bloquer le processeur. Le cache doit être non bloquant, c'est à dire qu'il doit pouvoir accepter de nouvelles requêtes venant du processeur pendant le traitement d'un défaut d'une requête précédente.

\subSection{Constitution du document}
Le document axé accès en cinq parties :
\begin{itemize}
\item Section \ref{introduction}     : la section actuelle présente le comportement que doit avoir le cache, ainsi que les paramètres retenus.
\item Section \ref{overview_partial} : dans un second temps, nous allons présenter une architecture qui satisfait les 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 les problèmes arrivant lors d'accès à des adresses conflictuelles, et/ou dans un environnement multi contextes. Pour chaque problème, nous proposons plusieurs solutions et nous énumérons leurs avantages et inconvénients.
\item Section \ref{overview_full}    : cette section est la synthèse des deux précédentes. Nous allons modifier l'architecture de départ afin d'introduire des solutions aux problèmes énumérés dans la section \ref{problem}.
\item Section \ref{optimisation}      : cette dernière section présente quelques optimisations pouvant être apportées au modèle défini dans la section \ref{overview_full}.
\end{itemize}

\subSection{Paramètres}
Dans cette sous section, nous allons définir les paramètres du cache ainsi que les paramètres de l'interface entre le cache et le processeur.

Pour chaque paramètre, nous précisons :
\begin{enumerate}
\item Une courte description présentant le paramètre
\item Un nom qui sera utilisé dans la suite du document
\item Un intervale de valeurs que peut prendre le paramètre
\item Un pas qui indique la fonction à appliquer pour passer d'une valeur à l'autre.
\end{enumerate}

\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 & 16 bancs de NB\_LINE/16 lignes &  *2 \\
    Taille des files internes    & SIZE\_QUEUE &                    1 case &                       64 cases &  *2 \\
    Nombre de requêtes pendantes & MAX\_REQ    &                2 requêtes &                    64 requêtes &  *2 \\
    \hline
  \end{tabular}
\end{center}

\printgraphonly{CACHE_parameters}{.8}

La taille du cache est $NB\_LINE * NB\_WORD * SIZE\_WORD~bits$.

\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{Comportement}
\begin{description}
\item[Hierarchie mémoire : ] La hierarchie mémoire consiste à placer plusieurs mémoires entre le processeur et la mémoire principale. Le niveau d'un cache représente sa localisation par rapport au processeur. Plus le niveau est bas, plus le cache est proche du processeur. Un défaut de cache demande l'envoye d'une requête vers le niveau suivant (le niveau supérieur). Ce cache est prévu pour être un cache de niveau 1 (communiquant directement avec le processeur) et est également le cache qui communique avec le bus système.
\item[Write through      : ] L'ajout d'un cache dans un système va provoquer une duplication des données. Lorsque le processeur va effectuer une requête d'écriture, le cache à l'obligation de modifier également la mémoire. Soit il le fait à chaque écriture, soit il attend l'évincement de la ligne. Ce cache implémente la statégie des écritures simultanées (Write Through) : chaque donnée est à la fois écrite dans le bloc du cache et dans le bloc de la mémoire de niveau supérieur. Ce protocole provoque une augmentation du trafic sur le bus, mais rend le cache plus simple et permet une gestion de la cohérence mémoire plus simplement.
\item[Write no allocate  : ] Nous avons vus précédement qu'à chaque écriture, le processeur va également provoquer une écriture au niveau mémoire suivant. Il y a également une mise à jour du cache si la ligne est présente. Mais en cas d'absence de la ligne, faut il la rappatrier dans le cache? Si oui, il s'agit d'une écriture alloué. Or ce cache fait des écritures non alloué (Write no allocate). C'est à dire que les échecs d'écriture n'affectent pas le cache, le bloc n'est modifié que dans le niveau mémoire supérieur. Ceci permet de limiter le traffic sur le bus et de ne pas évincer une ligne qui peut encore être utile au profint d'une ligne pouvant ne pas être utile (le processeur est une architecture load-store : quand le programme écrit une variable en mémoire c'est que la variable est en fin de vie).
\item[Cache associatif   : ] Un cache peut stocker plusieurs lignes de cache. Mais où peut on stocker une ligne précise dans le cache? S'il n'y a qu'une place possible alors le cache est appellé {\it direct map}, si le ligne peut être stockée n'importe où dans le cache alors le cache est appellé {\it full associatif}. Entre ces deux extrêmes, il y a les caches {\it semi-associatif}. Le cache est alors découpé en N bancs contenant chacun un nombre de lignes identiques. Une ligne peut être placée dans n'importe quel banc, mais ne peut être stockée qu'à un seul endroit dans chaque banc. Selon cette définition, un cache {\it direct map} ne contient qu'un seul banc alors qu'un cache {\it full associatif} n'a qu'une seule ligne par banc. Le cache que nous spécifions est {\it semi-associatif} qui est un bon compromit entre la compléxité et la performance.
\item[Non bloquant       : ] Il s'agit de la principal caractéristique de notre cache. Comme expliquer en introduction, le cache est partagé entre plusieurs contextes, et cache contexte execute leurs instructions de manières désordonnées et spéculative. Un défaut de cache ne doit pas bloquer le cache. 
\item[Processeur avec consistance mémoires relachées : ] Du point de vue du programmeur, les accès mémoires doivent se faire dans l'ordre du programme et que chaque accès mémoire doivent être lancée après que toute les instructions précédents soient terminées. Ceci assure une consistance mémoire parfaite, mais la dégradation de performance est catastrophique. Pour cela les processeurs implémentes des modèles de consistances mémoires relachés. Dans notre cas, le cache doit gérer les problèmes de consistance mémoire.
\end{description}

\subSection{Hypothèse de travail}\label{hypothese}

Nous allons supposer que le cache sera connecté à un processeur superscalaire d'ordre 4, que le code exécuté contient 20\% d'instructions de lectures et 10 \% d'instructions d'écritures. Nous avons donc en moyenne 4*30\%=1.2 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}

On va supposer qu'un aller retour entre le processeur et la mémoire principal à une latence de 30 cycles en moyennes.
