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 ?

[jobherzt]

c'est ce qu'il me semblait, mais je voulais etre sur, imagine que j'ai :

Code :

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

1
2
3
4
5
6
7
8
 
 
a=3;
..
..
 
b=2/a;
c=a*4;

le dispatcheur aurait pu etre assez intelligent pour faire le premier calcul sur un proc, et l'autre sur l'autre.. c'est un exemple a la con, mais j'ai l'impression qu'il y a pas mal de petite operations qui peuvent etre coupé, sans avoir a savoir a quoi elle serve.. donc j'imagine bien qu'il ne sait pas separer clairement les taches d'un point de vue "macroscopique", comme je le ferais avec des threads, mais je pensais que peut etre au niveau "microscopique" il aurait pu savoir..

[borisd]

Je pense en effet que quand on a une séquence connue et finie d'opérations (ton niveau microscopique ?), le problème revient à la décomposition d'un graphe en niveaux (polynomial). Mais, à plus grande échelle, on ne sait pas a priori quelle séquence d'opérations va être effectuée avant de l'avoir fait. Il existe peut-être des plateformes qui gèrent les optimisations "locales", je n'en ai aucune idée.
Reste à attendre le passage d'un vrai spécialiste...

[homeostasie]

N'ai pas vraiment d'expérience mais je me disais, pourquoi pas utiliser le modèle SIMD vu que tu as deux processeurs.

Chaque processeur réalise de manière synchrone le même programme sur des données différentes.

Un réseau d'interconnexion permettrait l'échange entre les processeurs.

Une idée pourrait être de réaliser la pile décrite plus haut au niveau de chaque processeur. Puis d'empiler alternativement les nouveaux objets de départ sur P1 puis sur P2 etc...

Un thread sur un processeur donné pourrait joué essentiellement ce rôle.

Puis tu fais tourner à l'identique le même prog sur les deux processeurs.

Voilà!

[jobherzt]

c'est pas idiot, sauf que je suivant les "branches" le temps de calcul peut etre tres tres variable. donc un programme risque de finir longtemps avant l'autre, d'ou la necssité qu'ils partagent la pile en temps reel !

[borisd]

Une autre question à se poser aussi : est-ce que travailler sur n processeurs (et donc au plus n fois plus vite ) est utile ?
Si tes jeux de données doublent de taille, ton problème ayant l'air plutôt difficile à résoudre, il y a fort à parier que le temps de calcul va plus que doubler.
Est-ce que tu ne ferais pas mieux d'améliorer ta méthode de calcul (te concentrer uniquement sur un ensemble plus restreint de tes objets possédant des caractéristiques permettant de mettre en oeuvre un calcul plus efficace, trouver des règles d'élimination des objets plus fortes pour limiter l'arborescence...) ?

[jobherzt]

Est-ce que tu ne ferais pas mieux d'améliorer ta méthode de calcul (te concentrer uniquement sur un ensemble plus restreint de tes objets possédant des caractéristiques permettant de mettre en oeuvre un calcul plus efficace, trouver des règles d'élimination des objets plus fortes pour limiter l'arborescence...) ?

c'est ce que je fais depuis bientot 4 mois :-) je suis un matheux, je programme dspuis pas mal d'annéee, mais je ne suis pas un "pro de chez pro".. ceci dit, j'ai quand meme multiplié par pres de 20 la vitesse de l'algo original en le "specialisant" pour le probleme qui nous interresse ( vu qu'a la base il etait fait pour une classe de probleme legerement differente)

j'ajouterais que mon programme occupe tres peu d'espace memoire, quasi rien en fait, c'est surtout du calcul. j'ai un certain nnombre de données constantes qui correspondent grand max a un petit millier de float et qui ne bougent pas, le resulta courant lui a une taille constante d'environ une trentaine de float, et la pile depasse rarement la 50-aine de float... donc au total je n'ai vraiment pas de probleme de memoire.

[homeostasie]

Alors dans le thread qui joue le rôle de remplir alternativement l'une ou l'autre pile, il pourrait aussi vérifier l'état actuel des piles des processeurs.
Ainsi il pourrait retirer un objet de la pile du processeur occupé et l'ajouter à celle du processeur innocupé, dont sa pile est en principe vide.

[borisd]

au total je n'ai vraiment pas de probleme de memoire

Je ne parlais pas de conso mémoire, mais de temps (d'ailleurs, tu y as certainement déjà pensé, mais peut-être qu'en en utilisant plus tu pourrais aller plus vite).
Ce que je voulais dire, c'est qu'il est courant, en optimisation combinatoire par exemple, ce dont ton problème semble s'approcher, de rencontrer des problèmes dont le doublement de la taille des données entraine un facteur 10 ou plus pour le temps de résolution pour une méthode donnée. Multiplier le nombre de processeurs ou leur puissance peut alors paraître vain, et il faut parfois se résoudre à changer profondément de méthode ou à fournir des solutions de qualité non optimale...
Par curiosité, ton problème a un nom connu ?

[jobherzt]

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

je ne vois pas ce que tu veux dire, en quoi le fait de multiplier les nombre de processeur doublerait le nombre de mes données ?? par definition, les données c'est ce que j'ai au depart, c'est fixe. apres, le temps de calcul ne depend que de la difficulté a resoudre le probleme, et c'est tres variable suivant les cas. mais le nombre de données n'influe pas du tout la dessus..

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

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