Paralleliser un algorithme

Citation:

---

Envoyé par mchk0123

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 :mrgreen:

---

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

Citation:

---

Envoyé par ol9245

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:

---

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 :

Citation:

---

Envoyé par Jeane

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

---

En fait ce qui prend vraiment du temps c'est le calcul des trajectoires.
Donc je pense que le mieux est de calculer les trajectoire dans chaque sous-cube et pour le transport effectif des molecules on n a pas besoin de paralleliser.

cad
1- envoit des donnee des sous-cub a chaque processeur
2- calcul des trajectoire par chaque proc
3- Transport des molecule par rapport au tajectoire calculer et actualisation des concentration de tous les noeud sur un seul proc
ainsi de suite...

D'ailleurs,

Mon code est en c++. MPI c l'un des mieux fait pour parralelliser ou il en existe des plus performant?

c'est quoi ton architecture pour la parrallelisation ?

Tu as aussi OpenMP qui est une bibliothèque libre ;)

Par contre non testé mais il parait qu'elle est inclue d'emblée avec VC8.

Citation:

---

Envoyé par 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?

---

Q1/ Tu es entrain de nous décrire une stratégie typique d'une architecture à mémoire partagée. Est-ce le cas ?
Q2/ As-tu regardé les pages sur la parrallélisation du schéma Eulérien, et qu'en as-tu retenu ?
OL

Le site de OpenMP c'est ici.

Pour OpenMP sur VC8, c'est ici.

Pour une comparaison rapide des différentes solutions de para c'est ici.

Enfin, un lien vers un cours http://chergui.developpez.com/cours/.../livre-openmp/ !

Citation:

---

Tu es entrain de nous décrire une stratégie typique d'une architecture à mémoire partagée. Est-ce le cas ?

---

Si j'ai bien compris ce qu'est une arcitecture a memoire partagee je ne crois pas que se soit se que je veux faire car dans mon cas je veux calculer les trajectoire de facon parallele (pour le calcul des tajectoire je ne pense pas qu'il y ai de tache critique car on ne modifie pas a cet etape la la concentration des differnt Noeud) et ensuite je veux effectuer le transport des moleculessur un seul proc

Jeane dans ton premier message tout nous donnais un estimation du temps de traitement demandé par ton programme :

Citation:

---

Envoyé par Jeane

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.

---

Est-ce tu penses pouvoir affiner un peu et nous dire, parmis les 68% , quelle est la proportion de temps passée à faire :
- le calcul des nouvelles trajectoires
- le déplacement effectif et le calcul des nouvelles concentrations
?

Ca aiderais à voir les goulots d'étranglement ...

Citation:

---

Est-ce tu penses pouvoir affiner un peu et nous dire, parmis les 68% , quelle est la proportion de temps passée à faire :
- le calcul des nouvelles trajectoires
?

---

cela varie entre 70% et 80% du temps utiliser dans la fonction Transport
soit environ 50-60% du temps totale

Citation:

---

- le déplacement effectif et le calcul des nouvelles concentrations

---

cela varie entre 15% et 20% du temps utilise dans la fonction Transport
soit environ 10-15% du temps totale

Oui donc les 80% du calcul de trajectoires (répartis sur n procs) sont théoriquement divisables infiniment pour peu que le nombre de procs n est grand. Sur ce sous-calcul (enfin peut-être que je fait erreur) mais tu ne devrais pas avoir de soucis de noeuds frontières.

Par contre, les 20% de l'application des mouvements & calculs de nouvelles concentrations seront surement irréductibles. Mais vu que cela ne représente "que" 10% du temps total, ton idée de faire le calcul simplement dans un seul proc me parait adéquat.

C'est ce que je pensais ;)

je vais essayer comme ca!
Merci de l'aide

Citation:

---

Sur ce sous-calcul (enfin peut-être que je fait erreur) mais tu ne devrais pas avoir de soucis de noeuds frontières.

---

Faudra quand meme que j'envoit les information des noeud voisin au noeud frontiere.

D'ailleurs j'ai une autre question.

Il faut que un et un seul processus est les valeurs de tous les noeuds pour pouvoir a chaque iteration envoyer les informations necessaire a chaque proc et rappatrier les transformation a la fin . Ce serait le proc qui s'occuperait de la fonction transport.

Faut-il resverver ce proc exclusivement a ce travail de donner et recevoir les donne et effectuer le transport ou bien peut il aussi faire le calcul des trajectoire pounr un sous-cube?

Merci

Bonjour,

Citation:

---

il aussi faire le calcul des trajectoire pour un sous-cube?

---

A priori oui, au lieu d'attendre sans rien faire le résultat des autres calculs.

Au niveau implémentation, je séparerai les process de calculs et de transport et je mettrai sur le maitre un process de calcul identique à celui tounant sur les esclaves.

Citation:

---

Envoyé par Jeane

Faudra quand meme que j'envoit les information des noeud voisin au noeud frontiere.

---

Oui bien sur, surtout si tu est sur une archi distribuée pysiquement (grappe de serveurs) et pas logiquement (multi-proc et/ou cores), tu ne peux te passer d'envoyer les données par réseau.

Si je ne me trompe pas, à un instant i le calcul des nouvelles trajectoires dépend, certes, des données des noeuds voisins mais celles ci ne sont pas "encore" modifiées (elles sont en lecture seule) puisqu'elles ont la valeur de l'instant i (et pas encore celles de l'instant i+1).

Si tu as besoin de stocker, en attendant, leurs nouvelles valeurs à l'instant i+1, tu n'as qu'à le faire dans une seconde "page" mémoire. Inspire toi du principe de double-buffering (et bit-blitting) qui existe dans le domaine du rendu graphique. Si tu veux des explications, je peux t'en donner.

Je ne comprends pas pourquoi tu veux centralsiser tousles eéchages. A l'intérieur d'un sous cube, le proc esclave peux se débrouiller tout seul. Les prob n'existent que aux frontières et ce sont typiquelement des questions de synchronisation.

OL

Citation:

---

Envoyé par ol9245

Je ne comprends pas pourquoi tu veux centralsiser tousles eéchages.OL

---

J'ai jamais dit ça !

Citation:

---

Envoyé par mchk0123

Oui bien sur, ..., tu ne peux te passer d'envoyer les données par réseau.

---

Citation:

---

Envoyé par mchk0123

J'ai jamais dit ça !

---

Je suis déolé que tu ai pris ça pour toi. on es dans une discussion technique, pas personelle. Chaque personne qui amène sa propre expertie est absolument bienvenuenue. Mon idée est qque le seul prob de ce topic est un prob de synchronidarion et que, à l'intérieur des sous cubes, il n'y a pas de prob de synchronisation.