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.

[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..

[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?

[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

[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).

[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 appartient au proc 2
la frontière A-b est gérée par le proc 1 (logique).
la frontière B-C est gérée par le proc 2

Alors, à la fois le proc 1 et le proc 2 veulent accéder aux variables d'état du noeud B. C'est typiquement un cas de synchronisation.
Je m'explique :
modifier l'état de B c'est :
lire l'état de B dans une case mémoire X
faire une addition, disons B+P1
écrire le résultat dans X

si les deux procs font leur addition exactement en même temps, alors le résultat final sera, de manière imprévisible, soit l'un (B+P1), soit l'autre (B+P2), mais pas la somme des deux (B+P1+P2). C'est le problème type de syncrhonissation.
La solution est que le premier qui accède à B bloque tout autre accès à B et ne débloque que quand il a fini d'écrire son résultat :
blocage
lecture
addition
écriture
déblocage

comme on ne peut pas définir un objet synchro pour chaque case mémoire, il faut bien faire gaffe car en fait l'étape "blocage" va bloquer tout un paquet de noeuds en même temps; d'ou goulot d'étranglement si mal réfléchi au départ.

OL

[mchk0123]

comme on ne peut pas définir un objet synchro pour chaque case mémoire, il faut bien faire gaffe car en fait l'étape "blocage" va bloquer tout un paquet de noeuds en même temps; d'ou goulot d'étranglement si mal réfléchi au départ.

Je ne comprend pas en quoi bloquer tous les noeuds en même temps pose pb. Normalement tous les proc devraient mettre plus ou moins le même temps, à un epsilon près, pour traiter un cube (temps d'un proc = temps total / nb de procs).

Il y a vraiment un pb avec le blocage noeuds par noeuds :

Supposons que la variable x[B] au noeud B soit la concentration d'un type de molécule. D'aprés ton exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Dans le proc 1 :       Dans le proc 2 :
 
blocage de x[B]
lecture de x[B]
addition de x[B] + p1  blocage de Bx
écriture de x[B]       ...
déblocage de x[B]      ...
                       lecture de x[B]
                       addition de x[B] + p2
                       écriture de x[B]
                       déblocage de x[B]

Le problème c'est que il n'y a pas que des molécules qui arrivent sur B, mais il y a aussi des molécules qui partent de B. Donc dans l'exemple que tu donnes, si les calculs de trajectoires partantes de B ont lieu aprés l'ajout de p1 ou p2 ou p1 + p2 ; ben on calcul les nouvelles trajectoires à partir des concentrations de l'instant i+1 et non pas de l'instant i.

Car le calcul des trajectoires dépend de la concentration au noeud B :

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