Programmation parallèle

Modérateur : Michel Quercia

Répondre
Antoine-
Messages : 324
Enregistré le : lun. juin 08, 2015 7:31 pm
Classe : Ecole

Programmation parallèle

Message par Antoine- » sam. juin 03, 2017 12:58 pm

Bonjour,

Quelqu'un sait-il comment, lorsque plusieurs threads s'exécutent en parallèle, arrêter tous les threads dès lors que l'un d'entre eux a fini de s'exécuter, et repérer (avec un numéro par exemple) ce dernier ? J'ai essayé de m'en sortir avec un Flag et une variable censée être égale au numéro du thread ayant fini en premier mais je n'ai pas réussi ...
2015 - 2017 : MPSI & MP* (JdS)
2017 - 2020 : Télécom ParisTech

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » sam. juin 03, 2017 10:16 pm

Ben si tu nous disais déjà de quel langage on parle...
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » sam. juin 03, 2017 10:17 pm

Et aussi pourquoi tu bricoles des threads à la main au lieu d'utiliser une lib de parallélisation de plus haut niveau ;)
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Antoine-
Messages : 324
Enregistré le : lun. juin 08, 2015 7:31 pm
Classe : Ecole

Re: Programmation parallèle

Message par Antoine- » dim. juin 04, 2017 12:14 am

Ah oui c'est en Python pardon !
fakbill a écrit :
sam. juin 03, 2017 10:17 pm
Et aussi pourquoi tu bricoles des threads à la main au lieu d'utiliser une lib de parallélisation de plus haut niveau ;)
Disons que je n'étais absolument pas au courant de l'existence d'une telle chose :mrgreen: Où puis-je trouver quelque chose de ce genre ? Est-ce difficile à utiliser ? Si ça me permet de régler mon problème je serais ravi de m'en servir ...
2015 - 2017 : MPSI & MP* (JdS)
2017 - 2020 : Télécom ParisTech

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » dim. juin 04, 2017 11:40 am

Ca dépend ce ce que tu veux //.
En parallélisation, il faut (comme partout) être pragmatique.
Il faut bien analyser la situation pour savoir ce qui limite la vitesse de processing car, par exemple, si beaucoup de processus tentent d'écrire en même temps dans le même fichier sur disque alors ce sera leeeeeeeeeeent.
Si tu as juste 1000000 petits fichiers à analyser et que chaque analyse est indépendante, il est surement malin de juste lancer 10 fois le même programme python en passant en argument à chaque programme 1/10 des données.
C'est déjà plus compliqué si chaque processus* peut se terminer après un temps de calcul très différent et si certains processus ont besoin du résultat d'un autre processus pour avancer...là...c'est compliqué et c'est un sport que d'avoir une bonne perfo.

Si tu veux juste découper une boucle de traitement du genre for elem in mydata où mydata est disons une liste de grosses matrices alors
https://docs.python.org/3/library/multiprocessing.html
devrait pouvoir faire un travail honnête.

Bref, ça dépend vraiment de ce que tu veux //.
Il faut aussi penser à la pression sur la mémoire. IL n'y a qu'une RAM pour tous les CPU (sauf si on parle d'une architecture spéciale...) donc il ne faut pas croire qu'avec disons 4 coeurs ça ira facilement 4 fois plus vite. Ca dépend :)

Bref, explique nous un peu ce que tu veux paralléliser.

* : au passage, pour des raisons techniques (GIL) on fait plutôt ça avec des processus qu'avec des threads en python. ON peut aller invoquer des threads mais c'est complexe et le gain est souvent plus que douteux.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Antoine-
Messages : 324
Enregistré le : lun. juin 08, 2015 7:31 pm
Classe : Ecole

Re: Programmation parallèle

Message par Antoine- » dim. juin 04, 2017 2:01 pm

En fait je ne recherche pas vraiment une amélioration de performance. Mon but est en fait de modéliser une partie de cartes (c'est un jeu de 55 cartes et chaque carte possède 8 symboles; de plus, 2 cartes distinctes ont exactement un symbole en commun). Au début de la partie, une carte est placée au centre et le reste des cartes est réparti équitablement parmi les joueurs. Le but est de trouver le plus rapidement possible le symbole commun entre la carte centrale et la carte que l'on possède (chaque joueur dispose ses cartes sous forme d'un tas, et ne voit que celle qui est au sommet de celui-ci). Une fois ce symbole trouvé, le joueur en question pose sa carte au centre, et on recommence. Celui qui n'a plus de cartes a gagné.

Maintenant le lien avec la parallélisation.
Après avoir implémenté différentes stratégies à l'aide du module thread, j'aimerais mettre celles-ci en compétition au cours d'une partie. Pour cela, je dispose d'un algorithme "partie" qui prend en entrée les cartes de chaque joueur et les stratégies utilisées par chacun d'entre eux, et contient une boucle while destinée à s'exécuter tant qu'aucun joueur ne s'est débarrassé de toutes ses cartes. Autrement dit, chaque itération représente "un tour". A chaque itération, des threads s'exécutent (chaque thread représente un joueur cherchant le symbole en commun) et une fois qu'ils sont finis, le premier à avoir terminé pose sa carte au centre , puis on réitère.

Pour deux joueurs, il est possible de repérer le dernier à l'aide d'une simple variable accessible à tous, et donc de repérer le premier. Mais pour plus de deux joueurs, cela n'est pas possible et il faut repérer le premier. D'où ma question initiale. Pour schématiser un peu, c'est comme si un professeur demandait à ses élèves de chercher un exercice et dès qu'il y en a un qui a fini, celui-ci va au tableau pour le corriger et les autres l'écoutent, et donc arrêtent de chercher.
2015 - 2017 : MPSI & MP* (JdS)
2017 - 2020 : Télécom ParisTech

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » lun. juin 05, 2017 12:02 am

(c'est un jeu de 55 cartes et chaque carte possède 8 symboles; de plus, 2 cartes distinctes ont exactement un symbole en commun): Ca tombe bien je connais :)

Je pense comprendre mais je ne vois pas trop le pb. Si ce sont vraiment des threads alors ils ont accès au même espace mémoire donc je ne vois pas le problème pour aller mettre disons une variable qui été à 0 au début au numéro de la stratégie dès que celle ci n'a plus de carte.
Si ce sont des processus, alors tu peux aussi...heu j'allais parler de mémoire partagée entre processus mais en fait tu n'as rien à partager dans ton cas. Il y a plein de façon de faire. Par exemple, tu n'as qu'à lancer un timer au début de chaque thread et à le faire écrire dans un fichier le temps qu'il a mis pour finir.
....ha mais tu veux arrêter les autres quand le premier a fini? Bah...que veux tu faire des autres? juste les tuer brutalement? Ou sinon tu fais en sorte que, de temps en temps, ça thread regarde si telle variable est à 0 ou à 1.
Sinon tu as aussi la possibilité d'envoyer des signaux.

Ton bonheur est là dedans : https://docs.python.org/3/library/asyncio.html
avec un peu de google ça devrait le faire.

ps : sais tu qu'il est non trivial de produire les cartes de ce jeu et qu'il y a des maths sympa derrière tout ça?
pps : avec les threads il faut faire gaffe. Si on lit/écrit la même variable, il peut y avoir des pbs de synchronisation. Exemple classique :
x=0
le thread1 fait x=x+1
mais pendant ce temps thread2 lit x...lit il 0 ou 1??? Tout ça peut se résoudre à coup de barrière de synchronisation....sémaphore...mutex...lock free...tout un poème :)
Sur un CPU intel, même faire "+1" n'est pas atomique. Un thread peut aller lire la valeur de la variable "alors que l'addition est en train de se faire".
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » lun. juin 05, 2017 12:08 am

arf non oublie asyncio ce n'est pas trop fait pour ça.
Tu as tout ce que tu veux dans https://docs.python.org/3.6/library/mul ... ssing.html
Ce sont des processus et non des threads mais c'est plus simple.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Antoine-
Messages : 324
Enregistré le : lun. juin 08, 2015 7:31 pm
Classe : Ecole

Re: Programmation parallèle

Message par Antoine- » lun. juin 05, 2017 10:53 am

fakbill a écrit :
lun. juin 05, 2017 12:02 am
....ha mais tu veux arrêter les autres quand le premier a fini? Bah...que veux tu faire des autres? juste les tuer brutalement? Ou sinon tu fais en sorte que, de temps en temps, ça thread regarde si telle variable est à 0 ou à 1.
Sinon tu as aussi la possibilité d'envoyer des signaux.
Non il s'agit juste de les arrêter dès que quelqu'un a trouvé le symbole en commun, puisque dans ce cas, il n'est pas nécessaire de continuer à chercher. Cependant les threads se relancent à chaque itération donc ils ne sont pas vraiment tués brutalement. Mais je pense m'en être sorti avec des flag un peu partout, même si ça reste un peu du bricolage :mrgreen:
fakbill a écrit :
lun. juin 05, 2017 12:02 am
ps : sais tu qu'il est non trivial de produire les cartes de ce jeu et qu'il y a des maths sympa derrière tout ça?
Géométrie projective ou dénombrement, ça dépend de l'approche, mais globalement oui je suis assez au courant :D En ce qui concerne le jeu, j'en ai implémenté un sur Python et j'ai fais une sorte de représentation graphique sous forme de tableau.
fakbill a écrit :
lun. juin 05, 2017 12:02 am
pps : avec les threads il faut faire gaffe. Si on lit/écrit la même variable, il peut y avoir des pbs de synchronisation. Exemple classique :
x=0
le thread1 fait x=x+1
mais pendant ce temps thread2 lit x...lit il 0 ou 1??? Tout ça peut se résoudre à coup de barrière de synchronisation....sémaphore...mutex...lock free...tout un poème :)
Sur un CPU intel, même faire "+1" n'est pas atomique. Un thread peut aller lire la valeur de la variable "alors que l'addition est en train de se faire".
Oui, le truc c'est que je ne sais pas trop quand est-ce que cela se produit et comment synchroniser le tout (merci pour les liens d'ailleurs, je vais aller les lire).
2015 - 2017 : MPSI & MP* (JdS)
2017 - 2020 : Télécom ParisTech

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » lun. juin 05, 2017 11:32 am

Oki tu m'as l'air de maitriser :)
La synchronisation des threads est un art délicat. Tellement délicat qu'il est source de tonnes de bugs souvent subtils.
Tout dépend de la pression sur tes données. Si tu mets à jour une variables toutes les heures et que ça ne prend que qlqs microsecondes alors tu n'auras pas souvent de problème de synchronication :mrgreen: Par contre, si tu fais ça dans un OS qui tourne sur des millions (voire plus) de machines alors tu vas commencer à avoir des utilisateurs qui de bugs étranges que tu n'arrive pas à reproduire. Bref, les threads c'est compliqué. Il y a bien des outils qui "lisent" le code et tente de voir où se trouve les variables non protégées mais ils ne peuvent pas être parfaits (car être parfait est équivalent à résoudre le pb de l’arrêt en informatique...Ce qui est impossible en général).
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Antoine-
Messages : 324
Enregistré le : lun. juin 08, 2015 7:31 pm
Classe : Ecole

Re: Programmation parallèle

Message par Antoine- » lun. juin 05, 2017 12:07 pm

fakbill a écrit :
lun. juin 05, 2017 11:32 am
bugs étranges que tu n'arrive pas à reproduire
Cela pourrait expliquer un des résultats que j'ai obtenu et que je n'ai pas su reproduire par la suite alors ...
fakbill a écrit :
lun. juin 05, 2017 11:32 am
Bref, les threads c'est compliqué.
Oui je suis bien d'accord :lol: En tout cas merci pour ton aide et pour les liens ! :D
2015 - 2017 : MPSI & MP* (JdS)
2017 - 2020 : Télécom ParisTech

Avatar du membre
fakbill
Messages : 11078
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Programmation parallèle

Message par fakbill » lun. juin 05, 2017 1:17 pm

Oui la non reproductibilité est typique d'un programme avec des threads mal sync.
Si c'était du C je dirais que c'est aussi typique d'un dépassement mémoire mais comme c'est du python c'est très très très très très très peu probable (sauf bug dans un module python écrit et C ou, encore moins probable, un bug dans python). IL y a des bugs dans python comme dans tout mais ils sont rares ;)
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités