Bonjour!
Nous avons un programme (très intensif au niveau CPU) que nous suspectons de mal utiliser le cache (une méthode d'une vingtaine de lignes consomme 70% du temps, qui se compte en jours...).
Avec un simple 'valgrind --tool=cachegrind', il est déjà possible d'avoir pas mal d'infos sur ce qui se passe, mais existe-t-il des outils permettant de voir plus en détail ce qui se passe au niveau du cache, à l'échelle d'une méthode c++? (ie: à quel moment nous corrompons le cache, etc)
Tous vos conseils sont les bienvenus!
Mathias
Forum Programmation.c++ étudier le fonctionnement du cache
9
juin
2009
# Compteurs papi
Posté par tuxyl . Évalué à 3.
Par contre c'est pas forcement si simple que ça à utiliser: car pour accéder aux compteurs hardware, on est souvent amener à patcher le noyau.
Tuxyl
# Commentaire supprimé
Posté par Anonyme . Évalué à 4.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 3.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 2.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Est-ce le cache CPU ?
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 2.
Tu peux sans doute casser ton algo en deux ou plus, et traiter que la moitié d'abord, et le reste ensuite. Ca pourrait éventuellement faire tenir toute ta (demi) ligne dans le cache.
Sinon, t'as plein de siouxeries, (genre déclaration d'un tableau de struct au lieu de deux tableaux de même taille, si tu as des parcours en parallèle, alignement des déclarations par taille de type, etc).
Enfin, on n'aura rien de concrêt sans le code (ou une version simplifiée de l'algo qui rame), sans le vrai algo (que si il est dans NP, on est plus à ça près), et sans les specs hardware (le CPU, le nombre de caches leur taille, etc)
Les caches CPU, tu peux facilement trouver leur taille. Après, à toi d'optimiser ton code en prenant ça en compte…
[^] # Re: Est-ce le cache CPU ?
Posté par Mathias Bavay (site web personnel) . Évalué à 1.
Et comme j'avais vu il y a quelques mois que valgrind nous détectait plein de cache miss, nous avons mis un stagiaire sur le coup, qui doit étudier la question et proposer des améliorations. Je veux bien poster mon bout de code, mais malgré tout, dans l'esprit du sujet de stage, c'est plus au stagiaire de faire le boulot qu'a Linuxfr!! :-) Mais je crois qu'il y a la plusieurs pistes intéressantes sur lesquelles je peux le lancer et de plus, il vient de me dire aujourd'hui qu'il avait vu que nous parcourions les tableaux dans le mauvais sens...
Au niveau de l'outil idéal auquel je rêve, ce serait un simulateur qui me permette de voir le contenu du cache sur une certaine ligne de code, les données qui sont demandées, et du coup le rechargement du cache qui en résulte... ou bien de quoi voir quelles lignes provoquent des cache miss afin de pouvoir ensuite les étudier plus en détail (comme dans mon rêve au haute voix de plus haut). Je crois qu'avec perfmon2 nous ne sommes pas loin d'avoir cela (a condition d'apprendre a utiliser le dit outil...)
Encore une fois, merci beaucoup pour tous ces commentaires constructifs!!
Mathias
[^] # Re: Est-ce le cache CPU ?
Posté par Nicolas Boulay (site web personnel) . Évalué à 2.
"La première sécurité est la liberté"
[^] # Re: Est-ce le cache CPU ?
Posté par Mathias Bavay (site web personnel) . Évalué à 1.
// variables needed to optimize the computational speed
const double lw_radius2=lw_radius*lw_radius;
const double z_shoot=z[i_shoot][j_shoot];
const double t_snow_shoot=t_snowold[i_shoot][j_shoot];
// every grid cell receives radiation from the chosen one with coordinates (a,b)
for ( int j = 0; j < dimy; j++ ) {
for ( int i = 0; i < dimx; i++ ) {
const double bx = (double)(i_shoot - i) * cellsize; // bx = dx (m) going from (i_shoot,j_shoot) to (i,j)
const double by = (double)(j_shoot - j) * cellsize; // by = dy (m) going from (i_shoot,j_shoot) to (i,j)
const double bz = z_shoot - z[i][j]; // bz = dz (m) going from (i_shoot,j_shoot) to (i,j)
// distance between the surfaces
const double dist2 = ( (bx * bx) + (by * by) + (bz * bz) );
// the longwave radiation will only be emitted if the radius is lower than
// a preassumed radius (lw_radius) -> changeable in: lw_t(a,b) * lw_radius
//please note that it also excludes the current shooting cell itself!
if ( dist2 <= lw_radius2 && dist2>0.) {
const int ij = j * dimx + i;
const int ab = j_shoot * dimx + i_shoot;
vf[0][0] = vf[ij][ab];
// formulation of the long-wave radiation coming from the terrain:
const double rad = ( 0.000009886 * (pow( 0.5 * log(dist2),1.07 )) * (meteo2D[i][j].ta - t_snow_shoot)
+ 0.000003456 * meteo2D[i][j].ta + 0.0001452 * t_snow_shoot - 0.0304 )
* vf[0][0] * 10000. * PI;
// the received amount is added to the total radiation at ij
lwi[i][j] += rad;
// the next ('shooting') grid cell with the most unshot radiation is selected
// taking into account an air column reduction factor,
// the actual (slope) area size, emittable longwave radiation
// and the sum of total terrain view factor
if ( lw_t[i][j] * vf_t[i][j] > diffmax_lw ) {
diffmax_lw = lw_t[i][j] * vf_t[i][j];
*e = i;
*f = j;
}
s++;
} // end of if only for distances lower than lw_radius
// stopping criterion : Delta B^(k) * Sum_j(Fij) * A
eps_stern += fabs( lw_t[i][j] * vf_t[i][j] );
} // end of for i loop
} // end of for j loop
// set the emitted 'shot' radiation at that cell to zero, but in contrast to the
// shortwave radiation exchange taking into account multiple reflections here
// every grid cell emitts only once
lw_t[i_shoot][j_shoot] = 0.;
Bien sur, cela ne compile pas, il manque plein de choses, etc mais le code complet est volumineux.
Mathias
[^] # Re: Est-ce le cache CPU ?
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 3.
Tu peux le remonter hors de la boucle.
>> const double dist2 = ( (bx * bx) + (by * by) + (bz * bz) );
tu peux alors précalculer hors de la boucle aussi (by*by)
>> const int ij = j * dimx + i;
>> const int ab = j_shoot * dimx + i_shoot;
Tu peux précalculer aussi j*dimx hors de la boucle même si tu l'utilises pas (à tester en fonction du nombre de fois ou le test est vrai).
Aussi, ton ab est connu hors des 2 boucles.
>> log/pow
Bon, ça, ça coute cher. Faut voire tes données si t'as pas des invariants mathématiques.
C'est de l'optimisation locale un peu naive, mais ça devrait le faire un minimum.
[^] # Re: Est-ce le cache CPU ?
Posté par Nicolas Boulay (site web personnel) . Évalué à 5.
Au niveau du compilateur, si tu bosses avec gcc sur des machines intel, tu peux tenter de compiler en -msse3 ou -msse2 et -mfpmath=sse. Les cpu intel sont plus rapide si on utilise le SSE. (x87 est plus rapide sur les athlon et si il y a beaucoup d'opération comme sin/cos,... bref à tester surtout si tu compiles avec -fieee-fp)
Si gcc est plus ancien -ftree-vectorize permet d'utiliser l'auto-vectorisation.
"-march=native" permet d'éviter de se prendre la tête, si la machine de compile utilise la même architecture que celle d'exécution (cela évite de devoir rajouter -msse2 ou autre).
Vu les boucles, il faudrait tester --funroll-all-loops, cela marche bien avec de gros caches.
Code
Comme dit plus haut, les parcourt de tableau ne se font pas dans le bonne ordre, sur un tableau 2D, "tab[i][j]", l'offset le plus petit est sur le "j". Il faut donc intervertir les 2 boucles. Ou alors, tourner sur le [ab] de vf[][].
En général, pour les compteurs de boucle, il faut utiliser un "unsigned", cela évite certain teste en cas de wrap around.
Est-ce que le type "double" est toujours utile ? float est entre 2 à 4 fois plus rapide.(ne pas oublier qu'un littéral "2.4" et de type double, écrire 2.4f sinon)
Si un tableau est affecté puis réutiliser, il vaut mieux passer par un temporaire, on est sûr de passer par un registre.( cas de vf[0][0])
La boucle la plus interne, serait celle en "j", car il s'agit de la plus petite dimension à bouger. Tout ce qui ne dépend pas de "j" doit sortir de cette boucle. Le coeur d'une boucle ne doit comporter que le strict nécessaire. Il faut tout calculer avant, y compris les accès aux tableaux 2D avec un tmp_array2D=&(array2D[i][0]). Je pense qu'il doit être possible de fonctionner en utilisant des "step" d'addition au lieu de tout recalculer à chaque fois. Le but est de penser que j ou by, ou ab, s'incrémente d'une unité par tour, et de fonctionner par delta.
Le coeur de boucle est entouré d'un gros if, je me demande si il ne serait pas possible de changer complètement le calcul des bornes de i,j pour parcourir les valeur nécessaires au lieu de tout parcourir (surtout si dimx*dimy est gros devant le rayon). Au pire, il faut rajouter un calcul purement en entier pour calculer "dist2 <= lw_radius2" purement avec des entiers, en divisant le tout par cellsize. Cela évite des testes/calculs flottant.
Il faut faire en sorte que les tableaux restent le plus longtemps en mémoire, par exemple, si "meteo2D[i][j].ta" est petit, devant "meteo2D[i][j]", il faudrait plutôt créer un tableau "meteo2D_ta[i][j]". Cela évite une indirection et cela augmente les chances d'être en cache.
Si je comprends bien, le code, il y a encore une double boucle plus haute avec i_shoot et j_shoot. Il y a donc potentiellement un quadruple parcourt des tableaux 2D. Ce qui veut dire que que chaque array2d[i][j] est parcouru i_shoot_max*j_shoot_max fois. Ce qui est énorme. Selon leur taille, cela peut sortir du cache L1 et faire perdre beaucoup de temps en cache miss.
Il existe une téchnique le "strip mining", pour faire une découpe des données, et rester dans un sous domaine de [i;j] de faire tout les calculs dans ce domaine avant de passer à la suite. En gros, cela revient à rajouter une boucle sur "i" et de la remonter au dessus des boucle de i_shoot et j_shoot, pour découper le traitement et rester dans le cache L1.
Une autre astuce peut aussi être utilisé, c'est du déroulage de boucle manuel sur une des boucles bien choisies. En faisant 2 travaux en parallèle, cela permet de mieux remplir un pipeline, avec un peu de chance, le vecoriser peut aussi faire son oeuvre (-ftree-vectorizer-verbose=n de 0 à 7 pour avoir des infos). Mais, ici, vu les dépendance, il doit y avoir moyen de réduire le travail à faire.
"La première sécurité est la liberté"
[^] # Re: Est-ce le cache CPU ?
Posté par Mathias Bavay (site web personnel) . Évalué à 1.
Note au passage: en effet, cette fonction est elle-même appelée dans une boucle qui peut potentiellement balayer tous les tableaux en affectant (i_shoot,j_shoot) (le but est que chaque cellule du maillage peut être choisie comme cellule qui émet du rayonnement, puis ensuite on calcule pour l'ensemble du tableau ce qui est reçu par cette cellule émettrice)
Pour l'instant, nous nous dirigeons vers une réorganisation de la structure de ces boucles (sachant que nous limitons la distance pour laquelle une cellule peut émettre son rayonnement, il est idiot de continuer à parcourir le tableau en entier). Mais plusieurs des astuces données ici devraient pouvoir être réutilisées dans la version réorganisée... (et nous devrions passer en float)
Encore une fois, merci pour toutes vos suggestions!
Mathias
[^] # Re: Est-ce le cache CPU ?
Posté par Nicolas Boulay (site web personnel) . Évalué à 3.
Pour résumer en 100*100 : c'est dans le cache, en 100*100*100*100, cela n'y est pas.
J'aurais tendance à récrire les boucles i,j,i_shoot,j_shoot, pour parcourir une seul fois vf et ne pas sauter partout en faisant des caches miss. Je changerais les boucles naïves et le tests par un calcul mathématique des bornes des boucles.
"La première sécurité est la liberté"
# oprofile ?
Posté par benoar . Évalué à 5.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.