Discussion :

[borisd]

en fait, c'est un probleme de modellisation mais avec beaucoup, beaucoup de parametres..

ok, je remballe ma curiosité

en quoi le fait de multiplier les nombre de processeur doublerait le nombre de mes données

Ce n'est pas du tout ce que je voulais dire . J'ai cru lire dans un de tes posts que ton programme marchait pas mal jusqu'à ce qu'on te soumette des jeux de données plus gros. Je parle de la taille des différentes instances du problème, des données de départ quoi.
Si ce n'est toujours pas clair : si ton objet de départ a une "taille" de 100, tu résoudras peut-être le problème en moyenne en 1h, mais avec une taille de 200, tu auras une moyenne de 10h. Avec deux processeurs, tu réduiras peut-être le temps de calcul à 5h, mais pour un problème de taille 1000, il te faudra... beaucoup de processeurs pour terminer en moins d'une heure. C'était juste pour souligner le fait que si tu n'as pas de réponse à ton problème après 5 jours, c'est peut-être qu'il te faudra peut-être attendre 3 semaines, et 10 jours avec deux processeurs, et que multiplier le nombre de processeurs ne divise le temps de calcul que linéairement face à une augmentation exponentielle selon la taille des données.

pourrait tu me donner un exemple concret, ou l'augmentation du nb de processeur ne change rien ?? ca m'interresse, par curiosité..

Juste pour le plaisir, puisque ça n'est pas du tout ce que je voulais dire :

Code :

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

1
2
3
4
5
 
i <- 0
Tant que i<100
   i <- i+1
Fin Tant que

[jobherzt]

ok, je remballe ma curiosité

non, ya pas grand chose a dire de plus : il s'agit de fitter des points, de trouver l'ensemble des courbes qui passent suffisamment pres des points pour etre compatibles avec l'erreur experimentale.

Ce n'est pas du tout ce que je voulais dire . J'ai cru lire dans un de tes posts que ton programme marchait pas mal jusqu'à ce qu'on te soumette des jeux de données plus gros. Je parle de la taille des différentes instances du problème, des données de départ quoi. [...]

au temps pour moi.. j'etais focalisé sur la parallelisation.. oui, tu as tout a fait raison, seulement, je crois qu'il n'y a pas de solution miracle.. le but c'est justement de voir si c'est de l'ordre du possible. mais ca n'est pas a cause de données plus grandes, seulement que les données sont moins bonnes et qu'il ya plus de parametres.. mais effectivement, on frise l'explosion combinatoire :-) d'ou la presence de pas mal de routine d'optimisation !

Juste pour le plaisir, puisque ça n'est pas du tout ce que je voulais dire :

Code :

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

1
2
3
4
5
 
i <- 0
Tant que i<100
   i <- i+1
Fin Tant que

bien vu, mais je ne pensais pas a ca non plus :-)

[homeostasie]

Juste comme cela. L'augmentation de µp a évidemment ses limites pour un traitement parallèle des données. Nous dirons que c'est assez expérimental à connaître le nombre de µp à utiliser pour optimier au mieux la répartition du temps. En fait, la courbe ressemble à une cloche. Il y a un maxima puis si on en rajoute, les performances sont dégradées.

Pourquoi? Surtout à cause du temps d'intercommunication entre les différents processeurs.

En ce qui concerne la mémoire, si on a une mémoire partagée pour N processeurs, alors évidemment, puisque chaque processeur effectue en parallèle le même programme, la mémoire occupée sera N fois plus grande si tout les processeurs sont actifs.

De plus, si tu cherches à acquérir les meilleurs peformances de tes proc, attention de ne pas désamorcer le pipe line trop souvent...

homeostasie> quel serait l'avantage par rapport a une pile partagée ?

J'y réfléchirais demain ;o). Comme cela, je ne pourrais te répondre puis c'est le soir!

Bonne soirée.

[jobherzt]

je croyais naivement que l'interet d'une memoire partagée dans un cluster etait justement de minimiser les echanges...

[homeostasie]

Qu'entends tu par cluster? Pour moi ca signifie regroupement....

Alors en ce qui concerne les échanges, je ne pense pas qu'ils soient minimisés mais par contre bien plus rapide quand on utilise une mémoire partagée.

Ainsi donc, les données de l'appli sont toutes placées dans la mémoire partagée. Ce qui entraine cela:

• Les processeurs s'échangent s'échangent des informations au travers des variables communes, notamment le trnasfert de l'adresse des données.
• Le surcout lié aux communications et à la synchronisation a été évité, donc les communications inter-processus sont très rapide
• les codes et les données partagées résident dans une zone de la mémoire commune, d'où la migration de processus d'une unité de traitement vers une autre est assez facile, donc bonne tolérance aux pannes.

Mais étant donné que tu as seulement 2 proc, il n'y a pas à s'inquiéter d'éventuels conflits d'accés et les performances seront bien accrues à mon avis.

[jobherzt]

oui, c'est ce que je voulais dire par "minimiser les echanges", je voulais dire minimiser leur cout.. si j'ai bien compris, une memoire partagée est une memoire accessible rapidement par tous les processeurs, et qui evite de trop se poser la question de la lenteur des communications reseaux..

et je pense au cluster, parce que c'est peut etre la prochaine etape !

[homeostasie]

Oui avec une mémoire partagée, les échanges entre proc ne se font pas par passage de message sur le réseau, ce qui augmente le temps de communication. Cette manière d'échanger correspond aux architectures à mémoire distribuée.

[jobherzt]

cool, dans l'eventualité ou je passe sur le cluster, ca m'enleve un sacré gravier de la sandale..

[homeostasie]

En fait tu as combien de proc en tout? deux c'est bien cela pour une carte donnée?

Apparemment ensuite, tu comptes appliquer ton algo à l'identique sur plusieurs pc distants. Dans ce cas, comment comptes tu que l'ensemble de tes processeurs accèdent à la mémoire partagée?

[jobherzt]

en fait, c'est pas moi qui m'en occupe.. on m'a dit que je pourrais avoir acces a un cluster (je veux dire un vrai, fait pour ca) avec une memoire partagée, mais que pour l'instant c'etait ps au point donc que je ne pouvais utiliser q'un seul des ordis... donc les ordis ne seront pas "distants"

[homeostasie]

Alors d'accord, le sacré gravier de la sandale est bien enlevé ;o) mais ca ne sera pas si simple à mettre en oeuvre à mon avis.

[jobherzt]

c'est le moins qu'on puisse dire.. mais a prior, si j'arrive a le passer en multithread, apres avec le systeme Mosix ca devrait passer tout seul.. le seul truc qui me genait c'etait justement la gestion des communications, et apparemment la memoire partagée resout ce probleme !

apropos : est ce que quelqu'n connait une bonne lib pour faire du multithreading sous linux et windows ?? j'avais entendu parler d'un truc du genre 'ptype" mais je n'arrive pas a remttre la main dessus...

[edit] en fait c'etait ptypes, donc j'ai trouvé, mais si qqn a mieux !

[jobherzt]

qu'on fasse la fete dans les chaumieres, je viens de reussir a le passer en multithread, sans trop de difficulté, finalement !!

merci a tous, notamment a borisd pour avoir soulevé le probleme de la pile qui peut etre vidée par un thread sans pour autant que le boulot soit fini :-) c'est ce qui m'a posé le plus de difficulté, je ne sais pas si ma methode est tres "propre".

en gros, j'ai une variable "atWork" que j'incremente et qui contient le nombre de traitement en cours. ensuite, j'ai un truc comme ca :

Code :

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

1
2
3
4
5
6
7
8
 
tant que la pile n'est pas vide ou atWork > 0
   si la pile n'est pas vide
          atWork++
          (traitement)
          atWork--
   fin si
fin tant que

du coup, si la pile est vide mais qu'un thread est au boulot, les autres parcourent la boucle en rond sans rentrer dans le "si".. je ne sais pas, du coup, s'il bouffent du temps de calcul... en meme temps, si j'avais fait ca avec un verrou, qqpart il y aurait bien eu un

Code :

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

1
2
3
4
 
tant que le verrou est bloqué
   (rien)
fin tant que

donc ca doit revenir au meme ! enfin, je pense.. si quelqu'un a une critique, c'est avec plaisir, je met quand meme ca en résolu. sur des cas simplex, ca ne semble pas mettre plus de temps qu'avec l'ancien prog.

[borisd]

qu'on fasse la fete dans les chaumieres, je viens de reussir a le passer en multithread, sans trop de difficulté, finalement !!

Félicitations, ce soir on se met la tête !

je ne sais pas, du coup, s'il bouffent du temps de calcul.

Bah... ptet pas trop la fête alors. Moi je suis persuadé que oui, ils bouffent du temps de calcul (rien ne leur dit de ne pas faire leur boucle vide à fond). Un mutex résoudrait le problème puisque lorsqu'un thread attend qu'il soit dispo, son exécution est stoppée par l'OS qui la relance quand le mutex est dispo (du moins sous windows XP, après je ne sais pas).
Mais est-ce bien génant si tu travailles sur des processeurs dédiés à ton programme de bouffer du CPU alors que personne d'autre n'en a besoin ?

[jobherzt]

ben a priori, s'ils bouffent du CPU, ils en bouffent.. pour les autres threads qui eux sont en train de bosser.. comme c'est une situation qui ne doit pas se presenter tres souvet ni tres longtemps, je ne m'inquiete pas trop.. mais je vais essayer avec un mutex, en fait, ca ne doit pas etre si compliqué, un truc du genre :

Code :

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

1
2
3
4
5
6
7
8
 
tant que la pile n'est pas vide
 
  depiler
  si du coup la pile est vide, on verrouille (donc les autres threads sont en stand by
  traitement
  si on avait verrouillé, on deverouille
fin tant que

du coup, on a pas besoin du nombre de process en cours..

une question me taraude toutefois.. je ne maitrise pas encore bien les mutex, mais je trouve curieux qu'ils ne soient pas associé a une ressource particuliere.. du coup, quand un thread accede a la pile, il bloque les autres, meme si ils n'etaient pas du tout sr le point d'y toucher, non ??
corollaire de la question : dans quel cas peut on avoir besoin de plusieurs mutex, vu qu'a priori on n'a que 2 possibilité : soit on bloque tous les autres threads, soit non.

c'est peut etre idiot, mais je n'ai rien trouvé qui repondent a ca !

[Eusebe]

Ton algorithme pose problème : si tu as 3 threads, et 3 calculs à faire...

Les deux premiers pernnent leurs calculs, pas de problème.
Le troisième arrive, prend son calcul, se rend compte que la pile est vide et... bloque la pile...

Si les threads 1 et 2 terminent, et qu'ils veulent ajouter de nouveaux calculs à la pile, ils ne peuvent pas : elle est bloquée par le 3. Ils doivent donc attendre que le calcul du 3 soit terminé...

Sinon, je n'ai pas bien compris ta question sur les mutex... c'est à toi de créer autant de mutex qu'il y a de ressources critiques.

[borisd]

Je ne suis pas un expert, mais j'ai une expérience perso des mutex.
Dans l'API de Windows, il existe une fonction WaitForSingleObject qui stoppe l'exécution du thread à l'exéction de la fonction si l'objet en question (ici, un mutex) n'est pas dispo, jusqu'à temps qu'il puisse l'avoir. Ca ne bloque pas les threads durant leur calcul, mais seulement lorsqu'ils veulent taper dans la pile vide, si tu reprends l'algo que je t'ai donné plus haut. A mon avis, il fonctionne et on a besoin de la variable NT.
Tu peux le regarder de plus près et me taper dessus si je me suis planté...
[edit] j'ai expliqué dans le même post quand prendre et libérer le mutex. Un seul suffit je pense pour la gestion de la pile.

[jobherzt]

Ton algorithme pose problème : si tu as 3 threads, et 3 calculs à faire...

Les deux premiers pernnent leurs calculs, pas de problème.
Le troisième arrive, prend son calcul, se rend compte que la pile est vide et... bloque la pile...

Si les threads 1 et 2 terminent, et qu'ils veulent ajouter de nouveaux calculs à la pile, ils ne peuvent pas : elle est bloquée par le 3. Ils doivent donc attendre que le calcul du 3 soit terminé...

bien vu..

Sinon, je n'ai pas bien compris ta question sur les mutex... c'est à toi de créer autant de mutex qu'il y a de ressources critiques.

ben oui, mais justement, les mutex ne sont pas associé a une ressource !! avec boost, voila comment ca semble fonctionner :

je cree un mutex que j'appelle verrou

quand je vais toucher a une donnée critique, je bloque verrou, puis je debloque quand j'ai fini. mais le verrou ne "sait" pas quelle ressource est critique !! dans mon code ca se traduit comme ca :

Code :

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

1
2
3
4
5
 
lock.lock();
atWork++;
current=pile.top();	pile.pop();
lock.unlock();

donc je ne bloque pas "la pile", je bloque "tout court" le temps que j'ai fait ce qu'il y avait a faire....

[borisd]

Si tu code sous windows, pourquoi ne pas utiliser l'API, c'est assez simple dans ce cas...
Dans tous les cas, l'accès à la pile n'est pas seulement une section critique, tu dois aussi prendre en compte le fait qu'on doit attendre si elle est vide, et pour ça, une section critique ne pourra pas t'aider.

[jobherzt]

non, je suis sous linux..

oui, je sais que la ca ne suffit pas, mais ma question est plus generale sur les Mutex : je pensais qu'ils etaient "associés" a une ressource, alors que ca ne semble pas etre le cas....