Méthode de vectorisation et optimisation

Bonjour,

je travail sur un programme monte carlo écrit en fortran, que j'ai développé il y a un an. Aujourd'hui je souhaite réaliser des simulations beaucoup plus grosse et très gourmande en temps de calcul. Aussi, j'aurais aimé avoir votre avis sur les méthodes à adopter pour optimiser au mieu mon code.

J'ai entendu parlé de méthode de vectorisation mais je ne sais pas à quoi cela correspond et encore moins comment le mettre en place...

J'ai également un tableu 3D, pensez-vous qu'en faire un tableau de pointeur (ce qui n'est pas le cas aujourd'hui) me permettrait de gagner du temps de calcul ?

Enfin vos suggestions seront les bienvenues.

Merci beaucoup,
Yann.

A mon avis, il faut "regler" un peut ta méthode,
par exemple , dans mon cas, si je veux calculer un produit de convolution rapide, je l ecrot comme FFT^-1(FFTg.FFTh), où les FFT sont les transformées de Fourier rapides

pour gagner en temps de calcul, il faut dans un premier temps reduire au maximum les acces disque dur qui sont très lent donc à n'utiliser que pour lire les params au chargement et stocker le res à la fin...

ensuite éviter les calculs inutiles (il vaut mieux stocker Pi en mémoire que de le calculer à chaque fois par exemple) et éviter de calculer deux fois la même chose (très fréquent dans les schéma itératif)

une stratégie "à la linux" est bienvenu aussi: une fonction ne fait qu'une chose et une seule mais la fait bien!

esuite si possible, parallelisé...

et utilisé des algo optimisé...

Merci de vos réponses !

j'avais déjà en effet construit une procédure contenant toutes mes variables afin de ne pas avoir à les recalculer par la suite. Cependant une question m'interpelle, ma grosse matrice 3D est construite une seul et unique fois au lancement du programme. Cependant, les accès vers cette dernière sont permanent.

Comment puis-je être sur que cette matrice est en mémoire vive et non temporairement (le temps d'un run) sur mon disque dur ?

N'est-ce pas à ce propos le fonctionnement par défaut du compilo de stocker un maximum en mémoire vive tant que celle-ci est disponible ?

Enfin, à quoi correspond la vectorisation, celle-la même que je vois sur les boucles DO lorsque j'ajoute une option d'optimisation à la compilation ?

Comment puis-je m'y prendre pour tout vectoriser ?

Merci pour la patience que vous m'accordez,
Yann.

je ne vois pas très bien ce que tu appelle vectorisation puisque ta matrice est en fait un vecteur (au sens informatique, c à dire une liste d'éléments)

de plus pour être sûr qu'elle est bien en ram, cela dépend plus de ton OS que du compilo car si cela dépasse la capacité max de mémoire, c'est sûr, elle sera sur un swap sur le disque dur (et ce que ce soit windows ou linux) cela dit, si tu as un serveur avec un peu de ram (genre 16Go, cela devient classique) alors y a de forte chance pour que ce soit le cas....

pour ce qui est de l'acces à ta matrice ce n'est à mon avis pas là que tu perds du temps... il y a un petit prog (dsl j'arrive pas à retrouvé le nom, je le recherche) qui permet d'analysé ton code à l'éxécution (et le ralenti par la même occasion) et te donne les temps d'éxécution de chaque morceau ainsi tu peux rapidement savoir où ton calcul perd du temps...

sinon si tu pense que ta matrice est la source de ta lenteur, il faut essayer des truc du genre stockage creux, algo de réorganisation des données etc... peut-être en la restructurant, il ira plus rapidement à la valeur que tu veux etc...

je recherche le nom du prog d'analyse temporelle et je te le filie!!

Un tableau de pointeur? Les pointeurs sont plus lents que des variables natives car c'est plus difficile à optimiser pour le compilateur (risque d'accès concurrent via une autre variable ou pointeur) , et l'accès est plus complexe (un pointeur peut référencé un espace non contigu).

En plus de ce que t'a dit genteur slayer, tu dois t'assurer que tes tableaux sont dans le bon ordre ! En Fortran, un tableau A(n,m) est placé comme suit en mémoire : A(1,1), A(2,1), A(3,1),...,A(n,1),A(1,2),...,A(1,m), A(n,m). Si ton programme accède aux éléments dans l'ordre physique de la mémoire, le programme sera plus rapide que dans dans l'ordre inverse. Les compilateurs modernes font de la vectorisation automatique, du pipeline, prefetch (?), etc lorsque tes accès respectent l'ordre physique. Dans le programme suivant, la première double boucle sera plus rapide que la deuxième :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

program Test implicit none real A(100,100) integer i,k real S1,S2 ... S1 = 0. do i = 1, 100 do j = 1, 100 S1 = S1 + A(j,i) enddo enddo   S2 = 0. do i = 1, 100 do j = 1, 100 S2 = S2 + A(i,j) enddo enddo ...

---

Salut,

je me suis amusé avec CALL CPU_TIME(...) qui permet d'afficher le temps d'exécution sur des bouts de code. En effet, le remplissage de la matrice permet de gagner 0.1 seconde par itération. Un gain de temps appréciable sur 15*10^5 itérations :D
Un grand merci !

Pour ce qui est du programme qui permet d'afficher le temps d'exécution des différents bouts de code, volontier, je suis preneur !

Bonne soirée et bon week-end,
Yann.

Citation:

---

Envoyé par Sylvain Bergeron

Un tableau de pointeur? Les pointeurs sont plus lents que des variables natives car c'est plus difficile à optimiser pour le compilateur (risque d'accès concurrent via une autre variable ou pointeur) , et l'accès est plus complexe (un pointeur peut référencé un espace non contigu).

---

J'ai appris aujourd'hui qu'en Fortran, un principe de base était que les tableaux passés en paramètre ne pouvait pas se recouvrir (donc si c est un tableau, on ne devrait pas avoir le droit d'écrire toto(c, c), le comportement est indéfini). L'avantage, c'est que ce système permet d'effectuer des auto-vectorisations de code. Mais donc dans le principe du Fortran, il n'y a pas d'accès concurrent via un autre pointeur ;)

Si tu veux savoir quoi optimiser -> commence par faire un profil, et ensuite on pourra t'aider (oprofile ou valgrind sous Linux).

valgring fait du profile essentiellement sur l'occupation mémoire, le profilage du temps de calcul se fait avec gprof: le profiler de gnu il y a une petit aide ici: http://www.cs.utah.edu/dept/old/texi...gprof_toc.html

cela peut être vraiment sympa, cela dit le fichier qu'il génère est un peu illisible et donc il existe des prog qui mouline un peu dessus et permette de mieu visualiser, en vrac: pfmon , histx ... en tout cas c'est ce qu'il y a sur ma machine de calcul que est en Debian, je ne sais si il y a des version pour les autres platteforme mais je pense que c'est fort possible

Citation:

---

Envoyé par genteur slayer

valgring fait du profile essentiellement sur l'occupation mémoire, le profilage du temps de calcul se fait avec gprof: le profiler de gnu il y a une petit aide ici: http://www.cs.utah.edu/dept/old/texi...gprof_toc.html

---

valgrind a des plugisn pour faire un peu tout. Callgrind est un profileur par émulation et est très puissant.
Ensuite, le problème de gprof, c'est qu'il ne compte pas le temps kernel, donc il faut utiliser oprofile.

Citation:

---

Envoyé par Matthieu Brucher

J'ai appris aujourd'hui qu'en Fortran, un principe de base était que les tableaux passés en paramètre ne pouvait pas se recouvrir (donc si c est un tableau, on ne devrait pas avoir le droit d'écrire toto(c, c), le comportement est indéfini). L'avantage, c'est que ce système permet d'effectuer des auto-vectorisations de code.

---

En plus de l'optimisation, le mécanisme de passage des paramètres n'est pas défini par le langage. En pratique, les références sont faites par des pointeurs, mais ce n'est pas obligatoire. Un compilateur aurait le droit d'utiliser une stratégie de copy in / copy out: call toto(c,c) devient alors copie c dans arg1, copie c dans arg2, exécute toto, copie arg1 dans c, copie arg2 dans c. La valeur de c devient donc dépendante de l'ordre... call toto(c,c) est cependant légal si les arguments sont intent(in).

Citation:

---

Envoyé par Matthieu Brucher

Mais donc dans le principe du Fortran, il n'y a pas d'accès concurrent via un autre pointeur

---

C'est plutôt que par défaut, il n'y a pas d'accès concurrents et que comme programmeur, tu est responsable de ne pas en cacher à travers des appels de sous-programme (comme dans ton call toto(c,c)). Tu as le droit de faire des accès concurrents localement. Comme le compilateur les détectera, il pourra optimiser le programme en conséquence. Mais le langage et la communauté restent frileux envers les pointeurs. Les allocatables sont nettement plus populaire pour gérer des besoins dynamiques de mémoire. Les compilateurs sont plus agressifs pour optimiser les variables ordinaires et les allocatables que les pointeurs.

Citation:

---

Envoyé par Sylvain Bergeron

En plus de l'optimisation, le mécanisme de passage des paramètres n'est pas défini par le langage. En pratique, les références sont faites par des pointeurs, mais ce n'est pas obligatoire. Un compilateur aurait le droit d'utiliser une stratégie de copy in / copy out: call toto(c,c) devient alors copie c dans arg1, copie c dans arg2, exécute toto, copie arg1 dans c, copie arg2 dans c. La valeur de c devient donc dépendante de l'ordre... call toto(c,c) est cependant légal si les arguments sont intent(in).

---

C'est vrai que si l'intent est in, il n'y a pas de problème. Mais c'est un fait qui est peu connu. J'ai un livre qui me paraît bien sur le Fortran, il n'y a pas une seule ligne sur ce problème, ou alors elle n'était pas assez mise en évidence.
Je ne savais même pas que le passage de paramètres n'était pas défini...

Citation:

---

Envoyé par Sylvain Bergeron

C'est plutôt que par défaut, il n'y a pas d'accès concurrents et que comme programmeur, tu est responsable de ne pas en cacher à travers des appels de sous-programme (comme dans ton call toto(c,c)). Tu as le droit de faire des accès concurrents localement. Comme le compilateur les détectera, il pourra optimiser le programme en conséquence. Mais le langage et la communauté restent frileux envers les pointeurs. Les allocatables sont nettement plus populaire pour gérer des besoins dynamiques de mémoire. Les compilateurs sont plus agressifs pour optimiser les variables ordinaires et les allocatables que les pointeurs.

---

En même temps, Fortran permet de faire tellement d'optimisations en plus que le C ou le C++ qu'on ne peut qu'être déjà cotnent de ce qu'il peut faire par lui-même si on travaille correctement ;)

Salut,

après quelques nuits blanche j'ai repensé l'ensemble du code. Limitation du nombre de procédure et minimisation maximum de l'algo. Le temps gagné est très important :yaisse2:.
Pour en gagner encore d'avantage, je parallélise avec HPF, et comme j'ai accès à un gros cluster je gagne encore un max par ce biais.

Je vais quantifier tout ça avec valgring ou callgrind dès que possible.

Merci à vous tous,
Yann.

Salut!

Citation:

---

je travail sur un programme monte carlo écrit en fortran, que j'ai développé il y a un an. Aujourd'hui je souhaite réaliser des simulations beaucoup plus grosse et très gourmande en temps de calcul.

---

Je ne sais pas sur quel problème tu travailles, mais je tiens à te rappeller qu'il y a des problèmes pour lesquels l'utilisation de la méthode de Monte-Marlo peut se justifier, mais qu'elle a aussi été proposée pour des problèmes pour lesquelles son inefficacité est catastrophique.
Jean-Marc Blanc