TP gestion de cache

[Eld]

Dans le cadre de TP système, je participe à la rédaction d'un sujet sur les caches processeur. Les étudiants devront implémenter un gestionnaire de cache (assez basique) avec différentes politiques (taille définie mais associativité variable ...).
L'idée est ensuite d'utiliser ce cache à travers différentes applications qui mettront en évidence les avantages/défauts de certaines politiques et les feront réfléchir à l'optimisation de leur code pour minimiser les cache miss.
Je compte sur vous pour m'aider à trouver des problèmes tordus niveau optimisation de l'utilisation du cache

[Tramb]

Tu peux leur faire un parcours de liste chaînée dans deux cas : les noeuds sont contigüs (pool-alloués), et les noeuds sont dispersés en mémoire avec du garbage avant/après pour leur montrer que c'est plus efficace.
Ou 1000 recherches linéaires par clé dans une collection
struct Pair
{
int Key;
char Value[256],
}

en SOA et en AOS aussi.

Sinon un autre exercice avec des buffers qui aliasent les même lignes de cache ou pas.

Voila quelques idées

[newbie06]

Tu veux qu'ils implémentent un cache en soft, c'est ça ?

Pour montrer le fonctionnement de ce cache, il va falloir que tu l'alimentes en transactions mémoire. Donc il te faudra des traces de simulation. L'idée serait de leur proposer un problème à programmer et qu'ils se rendent compte que le cache tourne mal, et ensuite de les faire réfléchir à comment améliorer ce programme ; un bon exemple pas trop compliqué est le crible d'Erathostène, qui est infiniment (bon j'exagère ) plus rapide en version segmentée.

Le problème va être d'obtenir des traces mémoires ; il va te falloir un simulateur ; et si ton simulateur n'est pas du x86, il va aussi falloir un compilateur croisé. Une approche jouable est de prendre qemu et de le patcher pour qu'il crache des traces ; ce n'est pas immédiat, mais réalisable. Si tu veux je peux t'en préparer une, mais pour ARM

[Møgluglu]

Le problème va être d'obtenir des traces mémoires ; il va te falloir un simulateur ; et si ton simulateur n'est pas du x86, il va aussi falloir un compilateur croisé.

Je pense qu'Eld voulait juste remplacer chaque accès à la mémoire par un appel de fonction genre cache.read() ou cache.write(). Évidemment on rate plein d'accès, genre la pile et les instructions, mais pour faire comprendre le principe ça suffit...
(Et même, je trouve que travailler sur des traces est moins parlant que de simuler le cache directement pendant l'exécution...)

Sinon des cas d'école qui font foirer le cache on doit pouvoir en trouver plein, mais faudra pas oublier non plus d'inclure un ou deux exemples représentatifs de la vraie vie avec plein de localité.
Sinon les étudiants vont repartir avec l'impression qu'un cache ça sert à rien.

Au fait, le but, c'est de montrer comment optimiser le cache, optimiser le code ou les deux?

[Eld]

ça va rester très basique, pour l'instant j'imagine un truc du genre
la mémoire est un fichier sur le disque (ou meme d'une grosse zone mémoire, on peut de toute façon ajouter nous même les pénalités de cache miss avec un sleep ...)
un cache d'une taille fixe qu'ils doivent implémenter permet d'accéder à cette mémoire sur disque, on peut configurer différentes politiques de cache
ils font un programme en passant par le cache pour accéder aux données
donc là je cherche des applications un peu en dehors des grands classiques de je bosse sur 3 tableaux alignés dans un cache associatif par ensemble de 2 pour les faire réfléchir

[newbie06]

(Et même, je trouve que travailler sur des traces est moins parlant que de simuler le cache directement pendant l'exécution...)

Ca dépend : si tu as l'infrastructure pour générer les traces, ça permet aussi de montrer comment utiliser ce genre d'outils et de réfléchir à comment améliorer l'infrastructure de benchmark (SimPoint et autres).

Enfin ce n'est pas ce que veut Eld de toute façon

Eld, tu bosserais pas avec Seznec par hasard ?

[Neo_13]

Dans le cadre de TP système, je participe à la rédaction d'un sujet sur les caches processeur. Les étudiants devront implémenter un gestionnaire de cache (assez basique) avec différentes politiques (taille définie mais associativité variable ...).
L'idée est ensuite d'utiliser ce cache à travers différentes applications qui mettront en évidence les avantages/défauts de certaines politiques et les feront réfléchir à l'optimisation de leur code pour minimiser les cache miss.
Je compte sur vous pour m'aider à trouver des problèmes tordus niveau optimisation de l'utilisation du cache

t'as un délai ?

[Yasko]

t'as un délai ?

3 cycles pour le L1, 12 pour le L2.

C'était ma contribution à ce topic, faites-en bon usage.

[Eld]

encore quelques semaines, disons 2
il y a de toute façon de quoi faire un tp basique, c'est juste que si on peut avoir des scénarios tordus en plus c'est mieux

[Neo_13]

encore quelques semaines, disons 2
il y a de toute façon de quoi faire un tp basique, c'est juste que si on peut avoir des scénarios tordus en plus c'est mieux

OK...

[fefe]

L'exercice classique consiste a demarrer avec un cache direct mapped et une copie memoire genre A[i]=B[i] avec A et B alignes sur la taille du cache. Tu te retrouves a 100% d'echecs quel que soit la taille de la ligne, question suivante qu'est ce que ca donne avec un cache 2 way associatif .
L'etape d'apres est le produit matrice vecteur avec une matrice qui tient dans 1/2 le cache, et un vecteur aligne. On se rend compte que suivant l'ordre de parcours de la matrice (colonne, ligne) les resultats sonts differents.
Ces exemples se decomposent facilement en 4 ou 5 questions, et permet de comprendre les concepts de base comme la taille de la ligne et l'associativite. Apres on peut jouer a inverser la politique de remplacement de LRU a MRU.
Augmente ensuite la taille des tableaux, (ou utilise des fonctions qui accedent plusieurs matrices en ordre alterne) et ajoute un autre niveau de cache, ca fait encore un peu de complexite.

Pour des exercices plus avances, regarde du cote de codes simple qui ecrivent pas mal de donnees (et les relisent eventuellement) et combine ca avec des changements de la politique d'allocation (write back/write through, write allocate/write non allocate).

La question classique qui amene a la conclusion qu'il est important de comprendre les caches est de les faire coder un produit de matrices qui ne tiennent pas dans le cache, et etape par etape les faire blocker l'algorithme pour la taille de chaque niveau de hierarchie, faire calculer les divers temps d'executions en considerant une machine deterministe in-order (avec des latences de cache realiste).
Tout ca est trivial cote programmation, mais pose de reels problemes de comprehension des caches, et en general apres avoir blocke un produit de matrice pour 2 niveaux de cache, je n'ai vu personne qui ne comprenait plus comment ca marchait et pourquoi (mais suivant le niveau de tes eleves et le temps imparti il n'est pas toujours evident d'en arriver la).

[Eld]

merci beaucoup pour les conseils
je pense qu'effectivement les exemples simples sur un travail sur n tableaux allignés en faisant varier l'associativité du cache peuvent permettre de se mettre dans le bain, et la multiplication de matrices pourrra servir d'exercice plus compliqué nécessitant plus de réflexion au niveau de l'algorithme
je ne sais pas si on poussera jusqu'à la politique d'allocation, ça dépendra si on divise le tp en 2 séances ou pas

[fefe]

Quelques exemples de ce qui se donne en partiel en licence:
www.lri.fr/~de/S-EX-L3-0405.pdf (section caches)

Les TDs de la licence info d'orsay se trouvent sur la page de Daniel Etiemble (le traducteur du Hennessy Patterson en Francais):
http://www.lri.fr/~de/ArchiL3-0809.htm
module S7

bonne lecture.

[Eld]

le cours ressemblent globalement à ce qu'ils ont pour la partie cache/pagination, sauf qu'eux ont ça au milieu des threads pipes et sémaphores
ils sont en 4ème année informatique (dans une école d'ingé dont je tairai le nom, sauf en message perso éventuellement ^^), donc j'aimerai bien les faire réfléchir un peu
les premières question du tp seront sur la constatation de la performance du cache sur un algo au comportement très prévisible vis à vis du cache, et la seconde partie sera là pour leur faire optimiser un algo pour un cache donné, et là je pense partir sur la multiplication de matrice que tu suggérais