Discussion :

[piteon]

Bonjour,

Pour mon travail je dois réaliser un outil de simulation multi-agent, en physique.
Imaginez un grand nombre de particules dans un espace en 2D. Chaque particule à ses coordonnés (x,y) et se déplace au hasard sur le plan.
Chaque fois qu'une particule se rapproche d'une autre elle est repoussé suivant une fonction mathematique assez lourde (avec des exponentielles).

Comment j'ai procédé :
En gros j'ai un Thread principal qui contient une boucle. Cette boucle calcul la prochaine position de chaque particule en fonction de toute les autre (il faut les comparer une à une). Lorsque toutes les particules sont mise à jour, j'incremente le temps de simulation et je recommence.

Apres quelques semaines de boulot mon programme JAVA est pret. Mais malheurs, dès que le nombre de particule dépasse une soixantaine, le programme rame comme pas possible (avec ou sans affichage graphique). L'utilisation normal c'est au moins avec 500 voir 1000 agents en meme temps.
Je peux pas rendre ce prog, il faut que je l'optimise un peu, mais je ne sais pas du tout comment faire. Est ce que vous pourriez me donner quelques conseils ?
Quel genre d'operations est le plus lourd ?
y a t il des 'trucs' pour aller plus vite?
Est ce que j'ai bien fait de choisir Java?
Est ce que c'est plutot lié au pc moyennement performant ou au programme mal codé ?
Existe t il des outils qui permette d'optimiser automatiquemnt un code?
Existe t il des outils qui permette de mesurer la "lourdeur du code" ?

MErci pour votre aide.
a+

[Nicolas_75]

Bonjour,

Cette boucle calcul la prochaine position de chaque particule en fonction de toute les autre (il faut les comparer une à une).

Peux-tu nous donner plus d'informations sur la façon dont tu fais cela ? Tu compares vraiment toutes les particules avec toutes les autres, soit n² opérations ?

N'est-il pas possible de "négliger" l'influence des particules loin de celle qu'on étudie ?

Nicolas

PS - voir aussi le forum algorithmique de ce site.

[sinok]

Tu pourrais également passer ton programme dans un Profiler afin de voir quelles sont les parties de ton code qui font office de golet d'étranglement, et pouvoir réagir en conséquence...


Tu as par exemple le profiler de netbeans qui est parfait pour ce genre d'opérations:

http://profiler.netbeans.org/

[piteon]

Merci pour vos réponses, peux tu m'en dire plus sur les Profilers? c'est un soft? ça se telecharge ?

[Nicolas_75]

C'est un module de l'environnement de programmation (IDE) Netbeans. Dans quoi codes-tu ?

[®om]

Si tu pouvais nous montrer quelques bouts de codes susceptibles d'être longs (le calcul en lui-même, et la méthode paintComponent(Graphics) de ton composant d'affichage des particules).

[piteon]

Je code avec JCreator.

Je vais essayer de vous passer quelques bouts de code. Mais ça ne sera pas facile, parceque j'ai un découpage en sous-classes très important, va falloir que je réécrive certaine partie pour vous montrer.

Je reviens vous voir bientot.
En attendant, tout nouveau conseil est le bienvenue !
Merci

[matoze]

Avec des boucles et des calculs complexe le processeur est constamment sollicité essaye de voir si tu peux changer tes formules de calculs puis de tester leur temps d'exécution. Autre remarque si tu as plusieurs processeurs sur ta machine tu peux créer plusieurs threads afin qu'ils soient tous utilisés.

[vahid]

si tu peux changer tes formules de calculs

et aussi stocker des résultats intermédiaires intervenant souvant dans les calculs

[deltree]

Bonjour,

par "Agent" je crois qu'on imagine plus ou moins un Thread. Or 6000 Thread en même temps, c'est trop gourmand en ressoruce, 60 ça devrais passer.

Si tu crée un Thread par agent, il faut aussi pense à ne pas en créer trop... ni trop peu: en créer quelques-uns pour paralléliser un minimum le traitement, mais tu traiter tes agents linéairement par paquet dans un pool de Thread, pour distinguer en quelques sortes tes tâhces alogrithmique, et le sThread systèmes. (un peu à la manière de la classe TimerTask)

si toutfois le problème viens des Thread: ça tu le vois facilement dans Eclipse ou avec un profiler.

[CyberChouan]

Je suis d'accord. Si tu veux simuler plusieurs milliers de particules, un Thread par particule, pas étonnant que ton programme n'arrive pas à gérer.

Dans ce genre de cas, le mieux est de créer une liste de tes objets particules, et de les faire se déplacer une par une en bouclant sur ta liste.

Ensuite, à toi de gérer intelligemment les répulsions pour ne pas allourdir les calculs (chaque objet "particule" pourrait connaître les 10 particules les plus proches et négliger les autres... cette liste étant évidemment mise à jour après déplacement)

[piteon]

Bonjour et merci pour vos nombreuses réponses.

Concernant les Threads, je pense que la discussion est interessante.
En fait je n'ai PAS un thread par particule , mais un seul thead en tout dans mon programme.
Ce thread contient une boucle 'while' dans laquelle se trouve une routine de mise à jour de chaque particule une par une , grosso modo :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
Tant que (simulationEnCours)
 
     Pour i de 1 à taille(listeParticule)
 
          Particule p = listeParticule(i) ;
          p.miseAJour(listeParticule) ;
 
     Fin
 
Fin

Sachant que la fonction Particule.miseAJour(liste) parcours à nouveau la liste pour calculer les differentes répulsions.
Un calcul de replusion entre deux particules consiste à résoudre 3 fonctions qui contiennent chacune des exponentielles. (eh ouai ,ça explose vite le nombre d'operations tout ça!)
Peut etre devrais-je utiliser mon thread differement ?


Sinon petite remarque. Je veux bien considerer uniquement les 10 plus proches particules. Mais pour savoir quelles sont les 10 plus proches , il faut bien que je parcours la liste au complet et que je rajoute un calcul de distance en plus. Je ne suis pas certain que ça aille réellement plus vite.

Qu'en pensez-vous ?

[®om]

Ton problème à mon avis n'est pas lié au thread.

Peux-tu exécuter ton calcul sans l'interface graphique (juste faire des println) pour voir si c'est bien le calcul qui te ralentit ou si ça n'est pas une mauvaise gestion de l'affichage?

[Nicolas_75]

Sinon petite remarque. Je veux bien considerer uniquement les 10 plus proches particules. Mais pour savoir quelles sont les 10 plus proches , il faut bien que je parcours la liste au complet et que je rajoute un calcul de distance en plus. Je ne suis pas certain que ça aille réellement plus vite.

En première approximation, tu peux dire : pour calculer le déplacement de la particule x, je ne considère que les particules situées à moins d'une distance d (où d est fixe). Mais il ne faut pas que cela détruise ton modèle physique...

Nicolas

[piteon]

Rom :

Peux-tu exécuter ton calcul sans l'interface graphique (juste faire des println) pour voir si c'est bien le calcul qui te ralentit ou si ça n'est pas une mauvaise gestion de l'affichage?

C'est fait et ça ne change rien. L'affichage n'est pas en cause, ça va toujours aussi lentement (ou presque).

Nicolas:

En première approximation, tu peux dire : pour calculer le déplacement de la particule x, je ne considère que les particules situées à moins d'une distance d (où d est fixe). Mais il ne faut pas que cela détruise ton modèle physique...

Mais pour trouver "les particules situées à moins d'une distance d" il faut que je parcours toutes ma liste de particule, en calculant la distance à chaque fois, pour décider si je vais la garder ou non... ça n'accelere pas mon programme tant que ça... (un peu quand meme , mais je ne peux pas trop réduire la distance d'iteraction.)

euhh...
Ben je ne sais plus trop quoi tenter ...
Est ce que je gagnerais du temps si je mets à jour les positions des differentes particules en parrallele , plutot que sequentiellement comme je le fait dans ma boucle?

[®om]

Bon alors là c'est la complexité de l'algorithme qui est en cause, pas l'implantation...

[deltree]

Dans ce sens: séquentiel vers parallèle, cela oblige à revoir un peu l'algorithme de calcul: quels sont les calcul interdépendant et qu'il faut faire l'un après l'autre... un peu complexe à définir sans connaitre les détails du calcul.

Si tu le fais: fais un découpage paramétrable en plusieurs groupe de particules, et exécute le avec 2, 4 ou 8 .. découpages pour éventuellement utiliser plusieurs core. (un nombre assez limité de Thread quoi)
Et définit les points de synchronisation entre les Thread (le moins souvent possible pour optimiser, mais quand cela est nécessaire pour garantir un résultat juste)


bref, je ne suis pas sûr que le parallélisme te feras gagner beaucoup de temps (il faut au moins que tu aie un dual-core),
ça veut peut-être aussi dire qu'il faut revoir l'algo: privilégier comme on disait les particules proches, (i.e. estimer quelles seront les valeur négligeables dans le calcul) et donc organiser les données pour qu'à chaque particule on puisse facilement associer une liste des particules proches, sans trop de calculs: un simple calcul de distance ne devrait pas être trop couteux ??

important pour optimiser les boucles
essaie de resuivre les calculs aussi: de sortir des boucles les calculs les plus couteux: racines carrée, exponentielles (le fonctions ) et les divisions, pour te restreindres aux additions et multiplications.
Par exemple pour le calcul de distance: ne calcule que la somme des carrés, mais pas la racine: tu travaille directement sur les carrés de distance.

Autre idée: si l'exponentielle est trop couteuse, il y a peut-être moyen de simplifier les calcul par développements limités en négligeant la partie "epsilon" du DL.

@om> tout à fait, mais l'implémentation est un terme plus adapté que l'implantation, qui peut porter à confusion dans certains contexte

[piteon]

Re,

Pour information, le Profiler JPROBE a analysé mon code et associe la grande majorité du temp de calcul à la fonction particule.miseAJour() et en particulier à la methode qui implemente le calcul de répulsion entre particule.
Cette methode à un temp de calcul elevé et est appellé plusieurs millions de fois pendant 10 secondes de simulation.
Donc c'est bien cette fonction mathematique que je dois optimiser.

Je vais essayer les conseils d'optimisation mathematiques de Deltree , que je remercie chaleureusement!

[benratti]

Il faut donc tout faire pour limiter la complexité de la methode miseajour.

La piste que tu dois explorer est, à mon avis, de limiter le nombre de particule qui peuvent "repulser" la particule à mettre à jour.

Pour cela il t'a été proposé de prendre les particules se trouvant à une distance donnée de ta particule mais cela nécessite toujours de parcourir toutes tes particules même si le calcul de l distance et assez simple.

Une autre solution pourrait être le découpage de l'espace en zone et de te limiter uniquement à la zone dans laquelle se trouve la particule ainsi que les zones adjacentes. Tu peux associer à chaque zone les particules s'y trouvant en la mettant à jour à chaque fin de mise à jour de particule.

A toi de voir laquelle des deux solutions te fait gagner le plus mais fait attention à l'implementation que tu vas faire car cela peut ne rien amélioré si tu ne fait pas attention.

[miloux32]

Il faut donc tout faire pour limiter la complexité de la methode miseajour.

La piste que tu dois explorer est, à mon avis, de limiter le nombre de particule qui peuvent "repulser" la particule à mettre à jour.

Pour cela il t'a été proposé de prendre les particules se trouvant à une distance donnée de ta particule mais cela nécessite toujours de parcourir toutes tes particules même si le calcul de l distance et assez simple.

Une autre solution pourrait être le découpage de l'espace en zone et de te limiter uniquement à la zone dans laquelle se trouve la particule ainsi que les zones adjacentes. Tu peux associer à chaque zone les particules s'y trouvant en la mettant à jour à chaque fin de mise à jour de particule.

A toi de voir laquelle des deux solutions te fait gagner le plus mais fait attention à l'implementation que tu vas faire car cela peut ne rien amélioré si tu ne fait pas attention.

De même tu peux regarder si tu as des constantes qui sont recalculées à chaque boucle ou pas.
Attention par constante, j'entends des constantes ou des constantes par particules. ( genre pas la peine de calculer à chaque fois des éléments qui varie pas pour une particule donnée)

Et regarde la parallélisation ou un pool de thread pour faire le calcul.

(genre j'ai 60 particules mais j'ai 6 threads de calcul par exemple)