Préchargement de données dans un logiciel DSM

Jean Christophe Beyler (ICPS-LSIIT)

Michael Klemm (Uni. Erlangen)

Ronny T. Lampert (Uni. Erlangen)

01/06/2006

Plan

Présentation

Esodyp

Jackal

Synthèse

Conclusion

Présentation

Interaction entre deux systèmes :Esodyp (Entirely Software Dynamic Prefetcher):

Prédicteur Markovien Système développé à l’ICPS

Jackal : Système Software DSM en JavaDéveloppé par les universités d’Erlangen et

Amsterdam

Esodyp

Prédicteur d’accès aux donnéesEtudie le comportement mémoire

Les accès mémoireLes défauts de cache

Il permet de :Savoir quelles données seront nécessairesPrécharger les données dans le cache

Modèle Markovien

Analyse statistique d’une suite S d’éléments (des accès mémoire dans notre cas)

Mise sous forme de couples (X,Y) où: X et Y sont des éléments de la suite X précède directement Y

Mais aussi (S’,Y) où: S’ est une sous suite de S La séquence S’ précède directement Y

Un exemple de graphe

2

232

1

2

1

1

32

2

2

2

2

16

16

2

1

1

12

2

Deux phases

Déroulement du modèle : Le modèle construit le graphe

Temps de construction du graphe élevé

Utilise les informations reçues Précharge les données Vérifie si le modèle correspond

Remet à zéro si nécessaire

Phase de construction et phase de prédiction

Distance de préchargement

Paramètre important du prédicteurTrop petite : la donnée risque de ne pas

être dans le cache (latence)

Trop grande : la donnée risque d’être écrasée dans le cache

La distance dépend de l’application et du flux de données

Jackal

DSM : Distributed Shared Memory

Système en software

Le programmeur perçoit la mémoire comme étant entièrement partagée

C’est au système DSM de gérer les communications et transferts entre les noeuds.

Jackal

Double problème : Il faut limiter le nombre de messages Il faut limiter le nombre de défauts de cache

Le prédicteur doit donc : Etre précis dans la prédiction des N prochains

accès

Vérification d’accès

Vérification d’accès

Comparaison• Avec un processeur :

• Facilité pour les prédictions

• Utilisation des sauts mémoire

• Avec Jackal :• Plus compliqué pour les prédictions

• On ne peut pas utiliser les sauts

Appels vers Esodyp

Fenêtre de préchargement

Différence pour la prédiction

Besoin d’unicité pour les prédictionsLors de la création de la liste

Parcourt le graphe en coloriant les noeuds pour ne pas y revenir

L’utilisation des adresses :Grossit le grapheLe rend plus exact donc plus sensible au

changement de phase

Vue Générale

Limitations

Les objets sont tous sur des noeuds différents On doit envoyer autant de messages que sans la prédiction

Utiliser une heuristique pour limiter les messages

Les objets préchargés ne servent pas Le coût d’un message envoyant 5 objets est presque le

même qu’envoyer un seul objet

Performances

Nom Original(ms) Optimisé (ms) Ratio

Liste chaînée 1024 elem – 25 iter

11992 4559 2.6

Tableau 2560 elem – 500 iter

13819 4613 3

Stencil 2 thread – 200 elem – 5 iter

4894 3147 1.56

Stencil 2-200-20 19523 8806 2.2

Stencil 2-400-5 17174 12910 1.33

Stencil 2-400-20 68603 39873 1.72

Conclusion

L’ajout d’un prédicteur dans un système comme Jackal peut être bénéfiqueLe nombre de communications peut être largement réduit en concaténant les demandes de transfert.Le surcoût du système de prédiction peut être rentabilisé par ce gain de temps.