DUMAS: Pré-chargement avancé pour une hiérarchie mémoire

De Ensiwiki
Aller à : navigation, rechercher


Pré-chargement avancé pour une hiérarchie mémoire

Labo TIMA
Equipe SLS
Encadrants stephane.mancini@imag.fr

Étudiant

Julie Dumas, 2A SLE

Contexte

De nos jours les processeurs deviennent de plus en plus performant et les mémoires n'évoluent pas avec la même rapidité. Les accès à la mémoire sont donc déterminant dans les temps de calculs. Pour palier à la lenteur des mémoires, on utilise des caches dans des hiérarchies mémoires qui effectuent des prédictions sur les prochains accès mémoires à partir des adresses mémoires accédées précédemment. Ces prédictions ne sont pas efficaces pour des algorithmes tel que le traitement d'image et tout autre algorithme multidimensionnel. Zahir Larabi [1] propose dans sa thèse d'utiliser un cache nD-AP (n Dimension adaptative et prédictive). Ses travaux ont été poursuivi entre autre par Stéphane Mancini [2].

Au cours de cette IRL nous allons nous intéresser aux performances du cache en effectuant des tests ainsi que sur les possibilités d'améliorations dans les prédictions faites par le cache.

Cache nD-AP

Architecture du cache 2D-AP
Le cache nD-AP est un cache composé de :
  • une RAM avec les données
  • une unité de contrôle qui fait les demandes de mise à jour du cache,
  • un prédicteur par dimension.

Les prédictions du cache sont faites sur les indices et non sur les adresses ce qui permet de conserver la structure de donnée. On peut donc facilement se déplacer dans une image dans toutes les directions.

Pour que le cache soit efficace il faut que les accès à la mémoire soit fait selon un modèle de trait de pinceau. C'est à dire un déplacement rapide autour d'une vitesse de déplacement lente pour accès à la mémoire.

Le cache nD-AP différent des caches conventionnels car il s'adapte en fonction de l'évolution de la latence d'accès à la mémoire. Pour cela il dispose de quatre paramètres sur chacune des dimensions :

  • une constante de temps qui correspond à la fréquence de coupure du filtre,
  • la demi-taille de la zone de garde,
  • la demi-taille de la zone en cache,
  • la vitesse de déplacement du cache, c’est-à-dire le pas de déplacement lors de la mise à jour du cache.

Analyse des performances

Avant d'évaluer des performances du cache, il faut s'intéresser aux différents éléments qui influence l'efficacité du cache. Pour cela nous effectuons des tests sur l'ensemble des algorithmes pour des latences différentes. Les graphiques ci-dessous nous montre que plus la latence est grande plus l'efficacité diminue. Cela s'implique car plus la latence d'accès à la mémoire est importante plus le temps de mise à jour des données en cache est grand. Il faut donc que le cache soit plus grand si la latence est grande.

Algorithme Rotation : Influence de la latence et démarrage à chaud

Nous nous intéressons ensuite à l'influence de la longueur des séquences d'accès à la mémoire. Pour simuler différente longueurs de séquences on effectue les tests en lançant deux, quatre et six fois le même algorithme. Les tests sur l'algorithme Rotation montre que ce dernier n'obtient pas des résultats meilleurs en répétant les séquences d'accès. Nous effectuons le même test avec l'algorithme sinusoïde qui dont les séquences d'accès sont plus courtes. Les courbes suivantes montrent qu'en relançant le test on a une meilleure efficacité en particulier avec une latence importante. Il faut donc un certain temps pour que le cache apprenne à s'adapter correctement.

Algorithme Sinusoïde : Influence de la latence et démarrage à chaud

Nous cherchons ensuite à voir si l'auto-paramétrage du cache est efficace et si il est meilleurs qu'un paramétrage manuel qui est long à réaliser et propre à chaque algorithme. Pour cela il faut extraire les paramètres du cache à la fin de chaque simulation pour plusieurs latence. Ici nous allons prendre des latences de 50 et 100 cycles car on veut que le cache soit efficace pour ces latences. Nous pouvons distinguer des résultats très différents selon l'algorithme. Pour le premier exemple, on reprendre l'algorithme de Rotation et on peut observer que pour ce dernier l'auto-paramétrage permet d'obtenir une efficacité proche d'un paramétrage manuel. Cela est du à de nombreuses oscillations (de plus en plus fréquente quand la latence augmente) quand le cache fait des mises à jour une fois dans un sens puis dans l'autre sens, ce qui ralentis l'accès aux données.

Algorithme Rotation : Efficacité de l'auto-paramétrage

Pour d'autres algorithmes tel que la Sinusoide, on obtient de meilleurs résultats que le paramétrage manuel. Sur les courbes ci-dessous on remarque que l'efficacité du cache avec les paramètres extraits pour une latence de 100 cycles donnent de très bon résultats lorsque la latence est inférieur à 50 cycles. Cela s'explique car la taille du cache est sur-dimensionné pour cette latence et donc peu de mise à jour sont nécessaires. L'algorithme Sinusoïde obtient de très bon résultat aussi car ses accès à la mémoire respectent le modèle nécessaire pour utiliser un cache nD-AP.

Algorithme Sinusoïde : Efficacité de l'auto-paramétrage

Nous pouvons en conclure que l'efficacité du cache dépend de :

  • la latence,
  • la longueur des séquences d'accès à la mémoire,
  • la ressemblance au modèle d'accès de type trait de pinceau.

Conclusion

Références

[1] Z. Larabi. Architecture et stratégies de caches pour les circuits de traitement d’images. PhD thesis, Télécom ParisTech, 2010.

[2] S. Mancini. Gestion des données pour les systèmes numériques intégrés. In Thèse pour obtenir de grade d’habilitation à diriger des recherches, 2013.

Documents additionnels

Média:Rapport_DUMAS_IRL.pdf

Média:Soutenance_DUMAS_IRL.pdf