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

\Section{Quelques problèmes du modèle simplifié}\label{problem}

Cette section est une énumérations de problèmes fonctionnels du modèle de base. Pour chacun d'entre eux, nous allons présenter un exemple où le problème peut survenir, ensuite nous allons exposer la nature du problème et enfin nous allons apporter des solutions et débattre de chacune d'entre elles.

Pour cela, nous enlevons toutes les hypothèses vut en introduction de section \ref{overview_partial}.

\subSection{Requêtes multiples d'échec de lectures}\label{multiple_read_miss}

\subsubSection{Contexte}

Le processeur execute un appel de fonction. Le prototype est en 7 étapes :
\begin{enumerate}
\item Sauvegarde des registres utilisés dans la pile
\item Modification du pointeur de pile
\item Corps de la fonction
\item Ecriture du résultat dans le registre de retour
\item Restauration du pointeur de pile
\item Restauration des registres
\item Retour vers l'appellant
\end{enumerate}

Nous nous placons dans un envirronement 32 bits, de plus nous supposons que l'étape 6 est à une adresse de début d'une ligne de cache. Par exemple à l'adresse 0x100 avec un cache de 8 lignes de 4 mots.

Nous allons supposer que la requête de lecture à l'adresse 0x100 fait un échec de lecture, alors les requêtes aux adresse consécutives suivante font également des échecs de lectures (les adresses 0x104, 0x108, 0x10C ...).

\subsubSection{Problème}

Deux problèmes ce présente :
\begin{enumerate}
\item Le premier étant la résolution par le cache de plusieurs échecs de lecture. Or la ligne concernée est identique pour toute les requêtes.
\item Le premier point n'est pas vraiment un problème, car il va juste rendre plus long les accès mémoires. Or si le cache n'est pas direct-map, alors la duplication des requêtes concernant la même ligne de cache va impliquer que la ligne concernée va être logée dans plusieurs endront du cache. Donc une même ligne peut être dans deux emplacements de lignes de cache différents. Dans ce cas, quels lignes modifier en cas d'écriture ?
\end{enumerate}

Les causes sont les suivants :
\begin{enumerate}
\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{enumerate}


\subsubSection{Solutions}

Il y a trois solutions pour remédier à ces problèmes :
\begin{enumerate}
\item Ajouter un port de lecture au bloc RAM\_TAG. Dans la section {\bf SECTION\_DCACHE\_RSP}, lors de la lecture du paquet réponse contenu dans la file QUEUE\_RSP, nous allons vérifier si l'accès au cache réalise toujours un MISS. Si c'est le cas alors on met à jour le cache. Sinon aucune mise à jour ne devra être effectué.
  \begin{description}
  \item[Avantages :] 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[Inconvénients :] Accès à la mémoire inutile, les coût des miss deviennent plus long car on rappatrie une ligne entière à chaque fois
  \end{description}
\item La deuxième solution est d'empêcher ce cas d'arriver. Pour cela il faut avoir un historique des requêtes. Pour chaque ensemble (un ensemble est la totalité des destinations où une lignes de caches peut être stockées. Un ensemble est composé de ASSOC lignes et il y a NB\_LINE / ASSOC ensembles dans un cache) nous ajoutons un bit de verrouillage.

Lors de l'allocation d'une ligne, le bit est positionné à 0. Lors d'un échec de lecture on verrouille la ligne en positionant le bit à 1. Lors de la résolution du miss , donc lors du retour des paquets réponses, ce bit est remis à 0. Nous n'acceptons une requête que si le bit de verrouillage est positionné à 0.
  \begin{description}
  \item[Avantages :] Pas de duplication des requêtes.
  \item[Inconvénients :] Ajout d'éléments mémorisant : 1 bit par ensemble. Solution non scalable avec l'augmentation de l'associativité : le nombre d'élément mémorisant va diminué mais le nombre de ligne vérrouiller va inversement augmenter.
  \end{description}

\item La troisième solution reprends l'idée de verrouillage mais en l'appliquant non plus au niveau de l'ensemble mais au niveau de la ligne. Le nombre de ligne verrouiller sera toujours de 1. Or dans la solution précedente, nous avons verrouiller un ensemble car nous savons que la ligne récupérer par l'échec de lecture va être placé dans un ensemble. Or le choix de la victime de fait lors de la réception de la réponses.

Ici la solution est de placer le choix de la victime lors de l'émission de la requête, c'est à dire dans la section {\bf SECTION\_DCACHE\_REQ}. 
  \begin{description}
  \item[Avantages :] Une seule ligne est vérrouillée.
  \item[Inconvénients :] Coûte 1 bit par ligne de cache. De plus, entre l'allocation de la requête et l'écriture de la ligne dans le cache, le contenu de la ligne est indisponible. Nous avons potentiellement supprimé une ligne qui aurait put être utilisé durant cette tranche de temps.
  \end{description}
\end{enumerate}

{\it Remarque : } Le cycle d'acceptation de la requête (c'est à dire le signal DCACHE.REQ\_ACK) ne dépends plus seulement de l'état des FIFOs (disponible au début du cycle) mais également de la requête elle même. La chaîne critique sera donc un aller / retour entre le processeur et le cache. A cause du besoin de ne pas bloquer les requêtes, pipeliner cette accès devient difficile car quand nous refusons une requête, il ne faut pas quel soit taggué comme lancer par le processeur. Sinon, des problèmes de consistance mémoires peuvent arriver. Pour plus de détails, voir les sections \ref{pipeline} et \ref{consistance}


La différence principales entre les deux dernières solutions porte sur le nombre de lignes verrouillées. Ceci influe directement sur le coût en surface et sur la perte de performance. Dans la section \ref{consistance} nous allons voir que les solutions proposer sont basé sur le verrouillage de lignes de caches, donc afin d'uniformisé la solution retenue, nous n'allons pas choisir la première solution.

%\subSection{Évincement précoce de ligne }
%
%\subsubSection{Contexte}
%
%\subsubSection{Problème}
%
%\subsubSection{Solutions}
%
%
%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 mémoire}

La hierarchie mémoire doit assurer la cohérence mémoire (détermine quelle valeur est renvoyée par une lecture). Or les problèmes de cohérence mémoire ne surviennent que dans le cas d'un environnement avec un système multi-processeur et/ou avec des périphériques d'entrée/sortie. Nous n'aborderons pas ici les solutions matérielles pour résoudre ce problème. Le problème pouvant être résolu de manière logicielle en effectuant la séquence suivante présentée dans le graphe \ref{CACHE_coherence_memoire}

\printgraphonly{CACHE_coherence_memoire}{.8}
 
\subSection{Gestion de la Consistance mémoire}\label{consistance}

La hierarchie mémoire doit également assurer la consistance mémoire (détermine quand une valeur écrite sera récupérée par une lecture).

\subsubSection{Contexte}

On suppose que le processeur effectue une requête de lecture à l'adresse 0x100 puis une requête d'écriture à cette même adresse. Nous supposons également que la ligne contenant l'adresse 0x100 n'est pas présente dans le cache. Dans ce cas, le cache peut alors lancer la requête de lecture sur l'interconnect VCI. Sans attendre la réponse de cette requête, le cache peut lancer la requête d'écriture.

\subsubSection{Problème}

La norme VCI n'impose pas à l'interconnect une garantie sur l'ordre d'acheminement des paquets. La norme VCI garantie seulement l'atomicité d'une réponse VCI (pas d'entrelacement de deux réponses VCI vers la même entité). Avec une telle propriété, les transactions de lecture et d'écriture entre en compétition pour l'accès à la zone mémoire. Ainsi ces requêtes 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. Dans ce cas pour un cache de 4 mots de 32 bits par lire, un accès en écriture à l'adresse 0x100 et une lecture à l'adresse 0x104 sont conflictuelle : la lecture se fait sur les adresses 0x100, 0x104, 0x108 et 0x10C. Et contient donc l'adresse de l'écriture. Il y a donc 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.

Les problèmes de consistances mémoires peuvent se résumer en énumérant les 4 types de dépendances possibles :
\begin{description}
\item[RaR (Read after Read)   :] Il s'agit de deux lectures successives vers la même ligne de cache.\\
Dans le cadre d'une dépendance RaR, deux lectures concurentes ne posent de problèmes que si elles accèdent à une variable partagé par un autre processeur. Or ceci est résolue par les mécanisme de cohérence mémoire. Un autre problème a été vu à la section \ref{multiple_read_miss}, qui est la gestion de plusieurs échecs de lecture ciblant la même ligne de cache.
\item[WaR (Write after Read)  :] Il s'agit d'une lecture suivit d'une écriture vers la même ligne de cache.\\
Du point de vue du processeur et 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. Ceci inclue également les instructions de lecture mémoire. 
Or les lectures sont bloquantes : tant que la donnée de la lecture n'est pas arrivé, la lecture ne peut se terminé. Donc au moment où la donnée arrive, le processeur peut savoir si la lecture à réaliser une exception. Le processeur gére alors les dépendances WaR.
\item[WaW (Write after Write) :] Il s'agit de deux écritures successives vers la même adresse.\\
Dans l'item précédent, nous avons vut que le processeur ne doit pas lancer une écriture si toute les instuctions précédentes ne sont pas terminées. Donc au moment où une écriture est lancée, toute les lectures précedentes ont leurs opérandes et n'ont pas réaliser d'exception (Sinon le processeur appel la routine d'exception). 
Or les écritures ne sont pas bloquantes. C'est à dire qu'il n'y a pas d'acquittement. Donc au moment où le processeur envoye une requête d'écriture au cache, il peut avoir plusieurs requêtes d'écriture en cours d'éxecution. C'est alors au cache de gérer ces dépendances.
\item[RaW (Read after Write)  :] Il s'agit d'une écriture suivit d'une lecture vers la même ligne de cache.\\
Les dépendances RaW sont les moins triviaux. Le processeur ne peut pas gérer ces dépendances pour la même raison que dans l'item précédent : il ne reçoit pas de réponse lorsque l'écriture est effective. De plus, en cas d'échec lors de l'accès au cache, une lecture va chargé une ligne. Donc les dépendance se font au niveau de la ligne, or le processeur ne connaissant pas la taille de la ligne, c'est au cache de gérer ces dépendances.
\end{description}

\subsubSection{Solutions}

Pour gérer ces différents problèmes, il y a deux solutions :
\begin{enumerate}
\item Gestion par le CPU : pour cela le processeur doit connaître la taille maximale d'une ligne de cache (nous définissons par taille maximale, la taille de la ligne de cache contenus dans le dernier niveau de cache avant la mémoire principal ou avant un cache possédant des mécanismes de gestions de consistance mémoires.)

De plus, il faut aussi que toute les requêtes émisent par le processeur soit aquitter. Ceci inclue les requêtes d'écritures. 

Avec ces deux conditions, l'unités de gestion mémoire du processeur peut connaître quand deux instructions mémoires sont en dépendances. Et peut alors agir en conséquence en interdisant leur envoie.

Or le cache que nous définissons va être utilisé avec un processeur qui lance dans le désordre les instructions et lance également dans le désordre les instructions mémoires. Les instructions mémoires sont stoqués dans une file d'attente (généralement appelé la LSQ (Load Store Queue)). Chaque adresse de chaque accès mémoire sera comparé avec les adresses de tous les accès mémoires précédents. Ceci permet de vérifier si un accès mémoire est indépendant d'un autre. Ce mécanisme peut être utilisé pour détecter les dépendances.

Pour une file de taille $N$, il y a $\frac{(N-1)*N}{2}$ comparateurs de 32 ou 64 bits.

En prenant les hypothèses fournit dans la section \ref{hypothese}, nous avons 1 accès mémoire par cycle, 1 instruction d'écriture tous les 3 cycles et un aller retour processeur/mémoire de 30 cycles. Si les instructions d'écriture doivent être aquitter avant de libérer une case, alors chaque instructions d'écriture doivent attendre 30 cycles avant de libérer l'entrée qu'il occupe dans la load store queue. Et pendant se laps de temps, il y a eu 30*4 soit 120 instructions nouvellement chargés dont 120*10\% = 12 nouvelles instructions d'écritures. Le processeur doit également attendre la fin d'une écriture avant d'en éxécuter une nouvelle.

Nous pouvons conclure que quelque soit la taille de la LSQ, le débit entrant d'instruction d'écriture est 12 fois plus important que le débit sortant de ces mêmes instructions.

C'est pour ces raisons que la gestion de la consistance mémoire ne doit par être gérer par le processeur.
\item Gestion par le Cache : 

Dans la section \ref{multiple_read_miss}, nous avons vu une manière de gérer de multiples requêtes de lectures qui réalisent un accès sur une ligne de caches non présente. Nous pouvons voir ce problème de manière plus général comme étant un problème de dépendance RaR.

Nous allons réutiliser la solution du verrouillage de ligne de cache et l'étendre à toute les requête. Le principe étant simple : lors d'une requête (lecture ou écriture), nous vérrouillons la ligne qui contient (ou va contenir) l'adresse envoyer par le processeur. Ensuite lors de la réception de la réponse, nous déverrouillons la ligne.

Si entre temps il y a une requête qui accède à une ligne verrouillé alors elle n'est pas accepter par le cache.

Tout comme la section \ref{multiple_read_miss}, nous pouvons soit faire du verrouillage de famille soit faire du verrouillage de ligne. Pour les même raisons de scalabilité, nous préférons la solution de verrouiller au niveau ligne. Donc nous devons faire de l'allocation précose de ligne. Pour cela, nous devons avoir dans le cache l'étiquette de la ligne qui va être envoyé sur l'interconnect VCI. Ceci concerne les échec de lecture ainsi que les succès d'écriture. Mais également les échec d'écriture. Ceci signifie que nous allons évincer une ligne de cache afin d'avoir l'étiquette de l'échec d'écriture dans le cache. Or le cache n'est pas write allocate donc lors de la réception du paquet réponses, nous ne rappatrions pas une ligne de cache. C'est pour cela que dans ce cas préçit nous devons invalider la ligne.


\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\\
            & Verrouillage de la ligne de cache       & Déverrouillage de la ligne de cache\\
Write Hit   & Ecriture de la donnée                   & \\
            & Verrouillage de la ligne de cache       & Déverrouillage de la ligne de cache\\
Write Miss  & Allocation d'une ligne de cache         & \\
            & Verrouillage de la ligne de cache       & Invalidation de la ligne (write no-allocate)\\
\end{tabular}
\end{enumerate}

\subSection{Multi-Contexte}

Le cache que nous sommes en train de spécifier doit pouvoir être utiliser avec un processeur multi-contexte (par exemple qui implémente du SMT (Simultaneous Multi Threading). 
Le cache que nous nous proposons de faire sera physiquement indéxé et physiquement tagué. C'est à dire que la traduction entre l'adresse virtuelle et l'adresse physique ce fait en amont du cache.
Ceci à pour effet qu'il n'y a aucune difference entre la gestion d'un processeur mono contexte et d'un processeur multi contexte.

Nous pouvons néanmoins montrer quelques effets de bords :

Le cache est optimisé pour utiliser les propriétés de localité spatiale et temporelle d'un programme. Avec l'ajout du multi-contexte, le cache est soumi à plusieurs flot qui sont indé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. On appelle cette évènement le ``pourrissement du cache''. Afin de minimiser ces effets, le cache doit avoir un degré d'associativité qui est un multiple du nombre de contextes.

Un autre effet de bord et la nécessité d'avoir un cache non bloquant. Si un contexte est bloqué à cause d'un évènement, les autres contextes ne sont pas forcément bloqués. 

Pour les solutions sur la consistance mémoire : avec l'augmentation conseillé de l'associativité, ainsi que l'augmentation de probabilité de deux requête accédant à la même famille, la solution du verrouillage de ligne va être plutôt choisit par rapport à la solution de verrouiller les familles.