Discussion :

[Jeane]

Bonjour

On ma donne un code que je dois paralelliser(si c possible). Comme je n'ai jamais fait ca tout les conseils sont les bienvenues
En gros il s'agit d'un cube composer de n*n*n noeud. Chaque noeud est composer d'un nombres x de molecules appartenant a 5types possible (H2O, CA++ etc...)
A chaque pas de temps les molecules d'eau de CA++ etc se deplacent d'un noeud a l'autre selon certaines regles de porpagation.
Le programme se decompose en :
1- Les intialisation (qui ne prenne pas bcp de temps)
Pour chaque pas de temps:
-> Calcul quel sont les noeuds qui vont etre modifier pour l'iteration presente ( 7% du temps)
-> Transport de Molecules pour les noeud actif (68% du temps) : - pour chaque noeud actif et chaque type de molecule on calcul la probabilite que n molecules se deplace vers l'un des voisisns puis on effectue les modifictaions.

On reitere l'operation un grand nombre de fois

Je pensais peut etre decouper le cube en sous cube et faire les calcul independemment sur differnt processeur. Mais au frontiere comme un noeud agit sur ces voisins je pense que ca risque de poser probleme

Quelqu'un aurait une idee ou un conseil?

Merci

[jobherzt]

tu ne pourrais pas faire l'inverse, cad :

plutot que de partir du cube qui "sait" quelle sont les molecules a chaque noeud, pourquoi ne pas faire en sorte que ca soit plutot les molecules qui "sachent" a quel noeud elles appartiennent.

de cette facon, plus de probleme de frontiere : tu repartis les molecules entre les differentes machines, et chacune d'elle se debrouille de facon autonome.

apres, peut etre que ca n'est pas possible.

[Graffito]

Bonjour,

on calcule la probabilite que n molecules se deplace vers l'un des voisisns

De quoi dépend la probabilité de déplacement d'une molécule M ?

• proportion ou quantité de molecules M dans le noeud ?
• proportion ou quantité de molecules M, N, ... dans le noeud ?
• proportion ou quantité de molecules M ou M, N, ... dans le noeud voisin ?
• proportion ou quantité de molecules M ou M, N, ... dans l'ensemble des noeuds voisins ?
• proportion ou quantité de molecules M ou M, N, ... dans les voisins du voisin ?
• du fait que le noeud voisin a une face commune ou juste un sommet commun?

[mchk0123]

@jobherzt ton idée est trés bonne, reste à savoir si les molécules sont interdépendantes, ce qui n'est pas sur

Une autre idée possible (mais fort improbable) est de découper la durée d'expérimentation en 2 (ou +). Et de paralléliser sur ces deux durées.
Cela n'est possible que si l'on suppose que le système passe par un état intermédiaire connu.

Ou alors faire du backtrack temporel (si par exemple le système converge à coup sur vers un seul état stable) :
- on part à la fois de t = 0 en incrémentant t
- on part à l'envers de t = T en décrémentant t
Lorsque l'on arrive à t = T/2 on à terminé.

[souviron34]

si c'est ce à quoi je pense (on m'a soumis il y a 4 mois un code de ce style à optimiser, puis après une évaluation on m'a dit "qu"on savait faire et qu'on se passerait de mes services", donc c'est peut-être celui-là... ), il faut simplement travailler à l'optimisation des boucles et parcours de l'algo Transport de Molecules.

Mais de toutes façons, l'optimisation peut être extrêmement dépendante de la programmation..

[Nemerle]

A chaque pas de temps les molecules d'eau de CA++ etc se deplacent d'un noeud a l'autre selon certaines regles de porpagation...
Merci

Tu peux préciser? Si l'eau se déplace vers un noeud, que se passe-t-il?

[Jeane]

Bonjour

On ma donner un code que je dois parralelliser(si c possible). Comme je n'ai jamais fait ca tout les conseils sont les bienvenues
En gros il s'agit d'un cube composer de n*n*n noeud. Chaque noeud est composer d'un nombres x de molecules appartenant a 5types possible (H2O, CA++ etc...)
A chaque pas de temps les molecules d'eau de CA++ etc se deplace d'un noeud a l'autre selon certaines regles de porpagation


Merci pour vos reponses et desole de ne pas avoir repondu avant mais j'avais quelques probleme technique.

Pour vous repondre. En gros une molecule ne peux se deplacer a chaque iteration que vers l'un de ces 6 voisins. la probabilite de deplacement se calcul en gros selon :
POur chaque voisin pris dans un ordre aleatoire:
-> calcul d'une probabilite de mobilite dans la direction de ce voisin qui depend de la concentration au noeud donne et du potentiel electrique . on note prob cette probabilite
Si on note N le nombre de molecules de type i au noeud donne (le noeud central):
-> Si N>5*nb_voisins ( soit 5*6=30) alors deplanament de N*prob Molecule dans la direction du voisin
-> Sinon pour chaque molecule k du noeud calcul d'un autre coeef de probabilite p2:
-> Si p2 < prob : deplacement de la molecule vers le voisin.
Sinon la molecule reste au noeud.


J'espere avoir ete a peu pres claire.
Encore merci

[Jeane]

desole le debut de ma reponse est a effacer

[Jeane]

@ mchk0123 : Je ne pense pas que se soit possible car ce n'est pas possible de partir de l'etat finale entant donne que c la simulation qui va nous donner l'etat finale . Non?

[Graffito]

Bonjour,

A priori, l'opération qui consomme des ressources CPU est le calcul des probabilités p et le cas échéant p2.

Il y aurait peut-être beaucoup à gagner si on pouvait enregistrer les configurations d'entrée du calcul de la probabilité de façon à fournir directement la valeur si le calcul a dèjà été fait (ce n'est peut-être pas envisageable du fait du nombre de configurations possibles ).

[mchk0123]

Pas forcément, certains systèmes d'équations convergent toujours vers un état stable ou stationnaire quand t -> infini.

Si tu est dans ce cas, l'état final est connu et tu pourrais découper ton intervalle de temps [0, T] en 2.

[Jeane]

Merci Graffito.

L'idee ne me parait pas bete surtout que apparemment la valeur de prob a chaque iteration est souvent identique. Je vais regarder ca de plus pres .
Merci du conseil

[Graffito]

Bonjour,

Pour en revenir au système des "sous-cubes", supposons que :

• notre volume comporte 24 x 24 x 24 cellules
• ce volume est divisé en 27 sous-cubes de 8x8x8, de taille,
• on dispose d'un processeur maitre et N esclaves (un par sous cube).

Aprés avoir transféré les données intiales des sous-cubes aux exclaves, on peut alors procéder ainsi à chaque pas :

• demander aux processeurs esclaves de travailler sur les sous-cubes dont ils ont la charge sans toucher aux cellules situées au bord,
• rapatrier sur le processeur maitre, les cellules "voisines" du bord des sous-cubes (pour accélerer le traitement on traitera ces cellules en priorité et on les enverra au maitre sans attendre d'avoir traité tout le sous-cube),
• Dans le maitre, on traitera dès que possible (c'est à dire qu'on ddispose de toutes les infos en provenance des esclaves) les cellules du bord des sous-cube,
• transférer à chaque esclave les cellules du bord traitées par le maitre concernant un des sous-cubes traité par cet esclave,

Au final, le maitre fait aux esclaves une requête pour récupérer les cellules des sous-cubes (sauf celle des bords).

[ol9245]

Bjr,

Je suis pas spécialiste, mais je met mon grain de sel quand même

Quelle est l'architecture qui va faire la parrallélisation ?
C'est très différent selon qu'on a beaucoup de processeurs (ordi parrallèle) ou 2 ou 4 (un bicoeur ou quadricoeur type Pentium). différent aussi selon que la mémoire est partagée (bi/quadri coeur) ou distribuée (parrallélisation sur ordis en réseau).

L'algo ressemble à :
1/ obtenir l'état initial au voisinage e la cellule
2/ calculer les déplacements
3/ effectuer les déplacements.

le 1/ nécessite de communiquer avec les process qui gèrent la frontière de mon sous-domaine
le 2/ est totalement interne à chaque process
le 3/ nécessite de communiquer ET de synchroniser (deux process ne peuvent pas écrire en même temps sur les mêmes cellules. Synchroniser veut dire qu'un process va se réserver l'accès exclusif, chez lui ET chez le voisin, à certaines mailles de sa frontière le temps d'y écrire ses modifs. C'est la partie sensible de la parrallélisation. Si tout le monde attend tout le monde le rendement s'effondre.

Très probablement, la solution est d'afecter des blocs de cellules à chaque process, en optimisant le rapport nombre de cellules interne/nombrre de cellules en surface. donc des sous-cubes.

Très probablement encore, il faudra travailler la phase 3 pour pas que les process se bloquent mutuellement lors de la synchro.

Le reste dépend beaucoup de la distribution des données et du cout en temps pour qu'une donnée passe d'un process à l'autre. et aussi e la puissance comparée des différents procs qui vont mouliner. si puissance identique, on peut prévoir à priori une chorégraphie bien organisée ou chacun fait son petit pas de danse sans gêner l'autre et le tout bien synchro. Si différent, il faut faire asynchrone donc gérer des files d'attente (plutôt des files de priorité) des mailles qu'on peut traiter et des autres.

OL

[Jeane]

Encore merci a tous

En fait A chaque iteration i le deplacement des molecules de chaque noeud depend de la configureation du cube a l'etat i-1. Les deplacements sont calculer prealablement. Cad que a l'instant i on calcul pour chaque noeud un vecteur trajectoire de taille 6=le nombre de voisin qui comporte de nombre de molecule qui etait presente a ce noeud a l'iteration precedente et qui vont se deplacer vers le noeud voisin a l'iteration suivante. Une fois que les vecteur trajectoire on ete calculer pour tous les noeud on effectu les deplacement.

@graffito: il semblerait que prob ne prenne effectivement que 5 ou 6 valeur differente alors qu'il est recaculer un grand nombre de fois

[ol9245]

Encore merci a tous

En fait A chaque iteration i le deplacement des molecules de chaque noeud depend de la configureation du cube a l'etat i-1. Les deplacements sont calculer prealablement. Cad que a l'instant i on calcul pour chaque noeud un vecteur trajectoire de taille 6=le nombre de voisin qui comporte de nombre de molecule qui etait presente a ce noeud a l'iteration precedente et qui vont se deplacer vers le noeud voisin a l'iteration suivante. Une fois que les vecteur trajectoire on ete calculer pour tous les noeud on effectu les deplacement.

@graffito: il semblerait que prob ne prenne effectivement que 5 ou 6 valeur differente alors qu'il est recaculer un grand nombre de fois

donc cf mon post precedent tu as des problemes de synchronisqtio pour faire les déplacements. cad que si deux noeuds voisins veulent calculer leurs déplacement en même temps l'un doit bloquer l'autre jusqu'à ce qu'il ait fini et réciproquement. (sinon résultats faux et erreurs non reproductibles donc bonjour les dégats)

Mon conseil :
1/ si nécessaire, prend d'abord connaissance de la question de la synchronisation par exemple : ici
et ici
2/ définis une stratégie pour résoudre ces pb dans ton appli, puis construit le reste de ta parrallélisation au-dessus de ta solution de synchronisation.

Finalement comme le schéma numérique que tu utilises (qui s'appelle le schéma eulérien) est un gros cheval de labour, je me suis dit que des solutions de parrallélisation devaient déja exister et, effectivement, il y a du monde :

synchronisation parallélisation eulerian scheme

il y a meme des pages en Franais :

synchronisation parallélisation schéma eulerien

OL

[Jeane]

En fait je pensais plutot a Diviser le travail de chaque sous cube parmis les proc.
Le maitre ne servira qu'a donner les infos des noeud voisin au proc escalve, mais le travail sera effectuer par le proc esclave et ensuite recuperer par le maitre.

Car si le maitre traite tous les noeud frontiere j'ai peur qu'il soit un proc bloquant

Qu'en pensez-vous?

[mchk0123]

Il y a un truc qui me taraude depuis le début avec ces histoires de proc maître/esclave et noeud frontières, mais j'arrivais pas à savoir quoi. Je crois avoir trouvé ! :

@Jeane : Tu dis que chaque noeud est dépendant de son voisin, et que chaque état d'un noeud au temps i dépend de son état au temps i-1.

Tout d'abord il faut séparer les variables de chaque noeuds en 2 catégories :
- pour un noeud k, toutes les variables xi(k) de base qui permettent de décrire l'état d'un noeud (comme les concentrations de chaque molécules, ...)
- toujours au noeud k, toutes les variables yj(k) qui sont calculées temporairement et qui sont déductibles de xi(k) (comme prob et prob2, les trajectoires, ...)

Maintenant si je ne me trompe pas, en se placant à l'instant i ; on peut découper le calcul des déplacement en 2 étapes et :

1. Tant qu'aucun déplacement effectif n'est encore réalisé, toutes les variables xi(k) sont en "lecture seule". Donc comme ces xi(k) ne changent pas, les calculs des yj(k) sont complètement indépendants.
2. Les trajectoires (faisant parties des variables yj(k)) calculées, on effectue les déplacements. Comme les déplacements sont déjà entièrements calculés,
ils peuvent être réalisés complètement indépendaments.

Autrement dit, dans l'étape 1, tous les calculs sont parallèlisables quelques soit le découpage des noeuds en cubes !

Pour l'étape 2, il en va de même car les tous les calculs étants faits, il n'y a pas de dépendances entre les déplacements.

L'erreur que l'on a tous fait depuis le début était de croire que les trajectoires étaient calculés et appliquées noeuds après noeuds ; alors que si on les calculs tous d'un coup, on se synchronise, et les appliques, alors on peut massivement paralléliser les calculs.

Autrement dit, la seule dépendance entre "proc" étant lors du passage de l'instant i à l'instant i+1 : à ce moment il faut que tous les "procs" aient finis les 2 étapes (point de synchronisation, également appellé "procs join").

Donc plus besoin de notion de proc maître / procs esclaves ; ni de notion de noeuds frontières !

CQFD

[Graffito]

Bonjour,

Car si le maitre traite tous les noeud frontiere j'ai peur qu'il soit un proc bloquant

Effectivement c'est une amélioration. On peut passer aux esclaves les noeuds situés de l'autre coté de ses frontières et les laisser faire le traitement. Les traitements de frontières sont alors répétés dans différents esclaves, mais comme ils donneront le même résultat, pas de problème.

Le gain dépendra de la taille des sous-cube, par exemple pour 27 suous-cubes, le traitement des frontières par le maitre représente 6x18 faces tandis que les traitement par un esclave correspondront à un nombre de faces comris entre 3 faces (pour un cube d'angle) et 6 faces (pour le cube central).
Si on prend des cotés de taille N, le gain sera de ((18x6)-6) x N xN / N x N x N = 102/N, 10% de gain si N=1000, 50% si N=200 et montre que le travail ddu maitre sur les frontières prend autant de temps que le travail des esclaves sur leurs sous-cubes si N=100 (ce n'est toutefois pas "bloquant").

[ol9245]

Pour l'étape 2, il en va de même car les tous les calculs étants faits, il n'y a pas de dépendances entre les déplacements.


Donc plus besoin de notion de proc maître / procs esclaves ; ni de notion de noeuds frontières !

CQFD

non, pas tout à fait.
soient 3 noeuds voisins A B C.
A et B appartiennt au proc 1
C
A et B sont génrés gérés par deux procs différents.
disons que c'est le proc A qui fait le calcul (ça doit être décidé d'avance. Chaque frontière doit être génrée par un seul des deux noeuds).