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.
[^] # Re: Est-ce le cache CPU ?
Posté par Nicolas Boulay (site web personnel) . En réponse au message étudier le fonctionnement du cache. É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é"