prédiction données/instructions

Hello à tous,

Davidbrcz posait la question sur IRC et je trouve que c’est suffisamment intéressant pour être posé ici :

Sur un exam de scheduling, partie sur les calculs de worst case execution time. Dans le cas d'une analyse du pire temps d'exécution, il est plus difficile de prévoir le comportement du cache instruction que le comportement du cache de données. Est-ce que cette proposition est correcte ? Justifier votre réponse.

Ma réponse était la suivante :

le cache d’instruction reste plus facile a optimiser que le cache de données parce que les processeurs ont des algo de prédiction de branchement en générale. Dans le cas le plus générale j’aurais tendance à dire que les principes de localité et de temporalité sont meilleurs pour les instructions que pour les données.
Mais j’imagine que ça reste à justifier, faudrait demander à Mewtwo. Pas qu’il ai forcément la vérité vrai, mais son avis est sans doute intéressant.

C'est marrant tu défend le point de vue inverse de ce qui est proposé par la question.

le cache d’instruction reste plus facile a optimiser que le cache de données parce que les processeurs ont des algo de prédiction de branchement en générale.

Justement, en l'absence d'algos complexes, il est plus facile de prévoir le comportement, non ? Pour le cache de données, est ce que la mise en cache ne se résume pas à "les derniers trucs utilisés sont en cache" ce qui est plus facile à prévoir que le comportement d'un algo de prédiction de branchement qui va être spécifique à chaque processeur et dont le fonctionnement réel peut etre complexe et non documenté ?

Lu'!

A priori le pire cas, c'est celui où tes données sont telles que :

• tu vas avoir du mal à prévoir quelle prochaine page tu vas devoir choper,
• tes prédictions de branchements seront souvent fausses.

Je peux fortement me tromper (ça fait longtemps que j'ai fait de la perf) mais je trouve la question un poil trop imprécise. Typiquement, si tes données font que tu te gourres souvent de branchement, dans les deux branches :

• soit tu manipules les mêmes données mais avec des instructions très différentes : tu as foutu ton cache d'instruction à la rue ;
• soit tu manipules des données localisées de manière très différentes mais avec les mêmes instructions : tu as foutu ton cache de données à la rue ;
• soit c'est le cas murphyque et tout le monde est à la rue.

Vu que la question a été posée dans un examen de scheduling, et non dans un examen d'architectures des ordinateurs ou d'assembleur, je dirais que la réponse attendue était que les performances liées au données sont plus prévisibles. Mais rien à voir avec une quelconque raison architecturale : c'est juste que quand tu code dans un langage de "haut-niveau" (de type C, ou plus haut-niveau), tu ne sais rien de ce que tu fais avec ton cache d'instruction.

Tu ne sais pas combien tes boucles vont prendre en mémoire et si elles tiendront dans le cache, tu ne sais pas comment ton compilateur te compile les branchements et ne peut pas utiliser tes connaissances sur la prédiction de branchement pour savoir comment les optimiser, tu ne sais pas ce que le compilateur a inliné et ce qu'il fera de tes mots-clés inline, tu ne sais même pas où il te placera les fonctions en mémoire, etc. Du point de vue des instructions, c'est essentiellement le compilateur qui a la main dessus.

Pour les données, c'est différent : tu sais quelles sont le structures de données que tu utilise, tu sais comment tu y accède, tu peux faire des calculs de complexité algorithmique qui comptent les défauts de cache, bref : tu as le contrôle, pas le compilateur.