Discussion :

[jobherzt]

bonjour a tous, je lance un post qui fait plus ou moins suite a celui ci :http://www.developpez.net/forums/sho...d.php?t=185928 , mais je vais rappeler les faits..

je programme un petit logiciel scientifique assez violent en temps de calcul. or, on vient de me proposer dans un premier temps de le faire tourner sur un ordi bi-processeur specialisé (dans un deuxieme temps, on passera peut etre sur un cluster avec un truc du genre openmosix, mais c'est une autre histoire)

donc premiere question naive : pour beneficier des 2 processeurs, mon programme doit il forcement etre en multithread ? je suppose que oui, m'enfin ca coute rien..

donc en supposant que oui, la question est : quelle est la meilleure facon de gerer ca, sachant que l'algo est iteratif mais recursif :-) en fait, l'ideal serait de fixer un nombre de thread, et de se debrouiller pour le maintenir. si un thread fini sa tache, il faudrait qu'il aille piquer du boulot a un autre. voici un pseudo code aussi clair que possible de l'algorithme en question :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
soit P une pile
Soit A l'objet de depart
Soit R le resultat courant, vide au depart
 
on empile A dans P
 
tant que P n'est pas vide
 
   objet_courant <- depiler P
   si objet_courant est deja dans R, on zappe ( pas la peine de faire les calculs)
   sinon, on traite l'objet_courant, puis on fait un test.
   si le test est positif, on fusionne R et objet_courant
   si le test est negatif, on rejette objet_courant et on passe au suivant
   si le test ne permet pas de conclure :
        on coupe objet_courant en 2 partie O1 et O2
        on empile O1 et O2 dans P
   fin si
fin tant que

comme vous le voyez, l'algo est iteratif car il repose sur un while, mais l'esprit est recursif.. donc je cherche a multithreader tout ca, et je ne vois pas bien la demarche. je connais le principe de base des threads, meme si je n'en ai encore jamais programmé, mais ici a la fois on voit clairement que chaque traitement est independant, a la fois je ne vois pas trop comment les dissocier clairement, et surtout commet redistribuer dynamiquement le travail...

en fait, le plus simple serait peut etre de ne gerer qu'une pile de recursion pour tous les threads, comme ca pas de probleme de repartition du travail..

un grand merci aux ames charitables qui passeront par la !

[Eusebe]

en fait, le plus simple serait peut etre de ne gerer qu'une pile de recursion pour tous les threads, comme ca pas de probleme de repartition du travail..

Je pense aussi...
Dans ce cas, l'accès à la pile serait critique.
Il 'suffit' alors de sécuriser ces accès (empiler / dépiler) par des mutex.

PS : étant assez noob, il ne faut pas nécessairement croire tout ce que je dis

[jobherzt]

c'est ce que je pensais.. par contre, s'il y a des parametres constants et commun aux threads, puis-je les partager, sans mettre de Mutex ? pour eviter de copier en memoire X fois les memes données.

[Eusebe]

S'ils sont constants, oui, ça ne pose pas de problème. Si tous les threads n'accèdent à ces données qu'en lecture, il n'y a pas de section critique.

[jobherzt]

ok, reste a savoir comment mettre ca en place concretement, si quelqu'un a une idee.. la forme de l'algo me gene pour savoir comment proceder.. autant pour un serveur, je vois ou placer les threads, autant la.. je vois mais c'est un peu flou !

[borisd]

Je pense que ça devrait marcher, mais je ne suis pas spécialiste du calcul en parallèlle...
- Avoir une seule pile avec tous les accès en exclusion mutuelle
- Définir une variable NT commune à tous les threads correspondant au nombre de traitements en cours (incrémentée juste avant le traitement, décrémentée juste avant la fin de la boucle)
- Définir un mutex comme variable globale accessible à tout le monde (je pense que ce n'est pas propre mais à mon avis ça fonctionne) qui sera occupé lorsque la pile est vide. Pour cela, quand un thread dépile un objet, il doit attendre que le mutex soit libéré. Dès qu'il a dépilé l'objet et si la pile n'est pas vide, il libère le mutex. Tout thread empilant un objet libère le mutex (ça doit donc bien être une variable globale). Ainsi, pour pouvoir dépiler un objet, un thread devra attendre que la pile ne soit plus vide, et ce sans consommer de CPU
- Garder l'algo que tu as donné pour chaque thread, en le modifiant un peu :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
on empile A dans P
Tant que NT>0 ou P non vide faire
   Attente/Dépilement
   Si P non vide alors
      Incrémenter NT
      ... (ton corps de tant que)
      Décrémenter NT
   Fin Si
Fin Tant Que
Libérer le mutex

Ainsi, lorsque un thread est en train de traiter le dernier objet, la pile est vide et le mutex occupé. Lorsqu'il libère le mutex à la sortie de la boucle, tous ses petits copains threads exécutent la boucle sans rentrer dans le si, et sortent puisque NT=0.
Je me demande si je suis clair ...

[jobherzt]

Je me demande si je suis clair ...

3 aspegic et je regarde.. merci !

[jobherzt]

ok, je vois l'idée !! je n'avais meme pas pensé a ca.. il se peut en effet que la pile soit temporairement vide, ce qui n'etait pas le cas avant...

[tut]

donc premiere question naive : pour beneficier des 2 processeurs, mon programme doit il forcement etre en multithread ? je suppose que oui, m'enfin ca coute rien..

Avant de tout réécrire, commence par te renseigner là-dessus... c'est un projet universitaire, je présume ?

[jobherzt]

oui, je me doute, de toute facon, je ne reecrirais rien avant quelque semaine, vu que j'ai pas mal de boulot.. d'ici la, j'espere que quelqu'un pourra me dire si c'est necessaire.. ca me semblerait logique, mais on ne sait jamais !

[ma vie]
en fait, c'est pas vraiment un projet universitaire. je suis etudiant en master de maths, et je bosse plus ou moins officieusement, (en tout cas benevolement :-) ) avec une equipe de chimiste d'une autre fac, pour adpater un algo a leur probleme.. disons que je fait le lien entre de relativement recentes idees en info, et la chimie ou les gens sont pas au cournt de ca..

moi j'y gagne car ca me fait une experience de recherche, et je vais rediger tout ou partie d'un article, eux ils y gagnent car ca n'est pas assez specialisé pour qu'un "vrai" matheux s'y interresse et y passe autant de temps que moi..
[/ma vie]

[borisd]

donc premiere question naive : pour beneficier des 2 processeurs, mon programme doit il forcement etre en multithread ? je suppose que oui, m'enfin ca coute rien..

Je ne suis pas un spécialiste, mais comment le "dispatcheur" entre les processeurs saurait ce qu'il peut effectuer ou non en parallèle (interdépendance des résultats...) ? Le problème me semble impossible à résoudre efficacement en temps réel...

[Edit]
Après une courte réflexion : dans le cas général, ça ne serait pas un problème non Turing calculable ?