Questions de base sur le multithreading

Version imprimable

07/02/2010, 14h00
math_lab

Questions de base sur le multithreading

Bonjour, je développe actuellement un programme de simulation physique qui se trouve être un poil trop lent à mon gout. J'ai donc pensé a paralléliser calcul en donnant une liste de primitives à chaque core. Le problème est que je n'ai bien evidemment jamais fait de multithreading avant.

J'aimerai tout d'abord savoir si le multithreading vaut le coup car chaque thread risque de lire et écrire dans des variables utilisées par d'autres threads (et si je les bloque, je me retrouve avec les mêmes performances qu'un simple thread, non ?).
Ensuite, d'après ce que j'ai pu lire, la bibliothèque boost ne permet pas de choisir sur quel core le thread sera exécuté. Faut-il donc impérativement passer par les commandes de windows ?

Merci d'avance.
07/02/2010, 22h36
Aratox

Salut,
Il est effectivement vrai que si deux threads écrivent dans la même variable ça peu poser problème, exemple :
si tu lance 2 threads qui font l'action suivante :
++var;

imaginons que var vaut initialement 0, les deux threads vont lire la variable, faire chaqu'un de son coté 0 + 1 = 1... puis ils vont tous les deux écrire 1 dans var...

var sera donc égal à 1, et non pas 2...

Sinon pour la question de quel thread sur quel core, j'ai toujours travailler avec plusieurs thread sous linux ou avec Qt. J'ai un quad-core et si je lance 4 threads, mes 4 cores tourne à 100%, jamais eu de soucis. Sauf erreur c'est toujours le système qui choisi que thread va sur quel coeur.
08/02/2010, 10h30
3DArchi

Bonjour,

Citation:

Envoyé par math_lab

J'aimerai tout d'abord savoir si le multithreading vaut le coup car chaque thread risque de lire et écrire dans des variables utilisées par d'autres threads (et si je les bloque, je me retrouve avec les mêmes performances qu'un simple thread, non ?).

Ca peut dépendre de beaucoup de paramètres.
D'abord si des données sont uniquement accédées en lecture et donc constantes tous le long de la simulation (typiquement, une géométrie), alors pas besoin de mettre en oeuvre un mécanisme de verrou pour gérer l'accès concurrent.
Si des données sont écrites par un ou des threads avec des risques de race conditions, alors là effectivement, il faudra un mécanisme de contrôle de l'accès concurrent qui aura un coût. Mais cela peut être fait uniquement au moment de l'accès. Tu peux aussi regarder des patterns type reader/writer consumer/producer, etc.
A la base, tu peux commencer par voir comment découper tes simulations pour minimiser ces éventuels conflits.

Citation:

Envoyé par math_lab

Ensuite, d'après ce que j'ai pu lire, la bibliothèque boost ne permet pas de choisir sur quel core le thread sera exécuté. Faut-il donc impérativement passer par les commandes de windows ?

Je ne sais pas si avec boost c'est possible. Peut être que d'autres bibliothèques le permettent ? Sinon, faudra passer par l'api windows...
08/02/2010, 12h33
Mac LAK

Citation:

Envoyé par math_lab

J'aimerai tout d'abord savoir si le multithreading vaut le coup car chaque thread risque de lire et écrire dans des variables utilisées par d'autres threads (et si je les bloque, je me retrouve avec les mêmes performances qu'un simple thread, non ?).

De façon générale, passer en MT coûte plus de temps CPU que du monothread. Si tu préfères, tu gagnes du temps "réel" (humain, des heures / minutes / secondes), mais au prix de plus de ressources consommées (threads et objets de synchronisation) et plus de temps CPU.

Pour t'expliquer brièvement : imagine un traitement qui se fait en une minute en monothread. Une fois en MT (deux threads), tu vas le faire en, disons, 35 secondes, c'est à dire proche du gain maximum possible.
Or, si tu calcules le temps CPU consommé, tu vas arriver à 35 s X 2 (threads), donc ... 70 secondes ! Plus que les 60 initiales. Tu charges donc plus ta machine, même si (heureusement !) la plupart du temps ça ne gêne en rien car tu as largement plus de puissance disponible que tu n'en utilises.

Donc, comme le précise 3DArchi, ça va dépendre de beaucoup de paramètres, et il n'y a pas de règle absolue. Certains traitements ne peuvent pas être parallélisés par nature (ex : calcul d'une série / suite mathématique), d'autres sont difficilement parallélisables (sous-entendu "en obtenant un gain significatif"), d'autres sont quasi-triviaux.

Citation:

Envoyé par 3DArchi

Je ne sais pas si avec boost c'est possible. Peut être que d'autres bibliothèques le permettent ? Sinon, faudra passer par l'api windows...

C'est une grosse lacune de beaucoup de librairies portables de gestion des threads : elles ne gèrent pas l'affinité processeur.
Donc, direction l'API Windows pour ça. Pour ma part, je ne connais pas de librairie portable permettant de gérer l'affinité processeur, du moins dans les dernières versions que j'ai pu voir.
11/02/2010, 15h17
math_lab

Merci pour vos réponses.
Étant donné que ma fonction n'écrira dans les variables qu'à la fin du traitement, je pense que la synchro ne devrait pas être trop handicapante, et au pire, j'imagine que je peux même m'en passer en construisant un tableau temporaire qui stockerait les résultats et qui permettrait au programme principal de faire la mise à jour des variables.
Sinon, je me rend bien compte que le multithreading a un certain cout et que le programme sera moins efficace, mais j'ai 8 cœurs a ma disposition, donc ce serait stupide de pas en tirer avantage.

J'en profite d'ailleurs pour poser une autre question: doit-on créer et supprimer les threads à la volée quand on a besoin ? Je sais qu'avec join, on peut attendre la fin du thread, mais doit-il être détruit et reconstruit après pour pouvoir être re-exécuté ?
11/02/2010, 17h15
3DArchi

Citation:

Envoyé par math_lab

doit-on créer et supprimer les threads à la volée quand on a besoin ?

Lorsque on doit le faire souvent, alors on peut passer par un pool de threads.
Ils sont créés en début de programme et se mettent en attente de boulot. Lorsque tu as un traitement, tu en prends un libre, tu l'actives en lui donnant le traitement à faire. Lorsqu'il a finit il revient dans le pool des threads dispo et s'endort (çad se met en attente d'un évènement pour un nouveau traitement).
16/02/2010, 18h06
yan

Dans un premier temps, regarde peut être OpenMP.
16/02/2010, 21h20
JolyLoic

Citation:

Envoyé par Mac LAK

C'est une grosse lacune de beaucoup de librairies portables de gestion des threads : elles ne gèrent pas l'affinité processeur.
Donc, direction l'API Windows pour ça. Pour ma part, je ne connais pas de librairie portable permettant de gérer l'affinité processeur, du moins dans les dernières versions que j'ai pu voir.

En quoi est-ce problématique quand il s'agit de faire du parallélisme pour les performances ?
L'idée dans ce cas est de faire abstraction des primitive bas niveau et coûteuses comme les thread, les outils de lock au niveau du noyau,... et encore plus de l'affinité. Si tu règles l'affinité, comment fonctionnera le programme quand tu aura upgradé ta machine pour une avec 64 cœurs ?

Côté bibliothèque, je conseillerais plus TBB d'Intel ou PPL de Microsoft que boost::thread pour ce genre d'usage. Elles fournissent des API permettant de s'abstraire de cette tuyauterie, et d'être plus efficace (notion de tâche plus légère qu'un thread, conteneur pour des échange de donnée multithread règlés finement en temre de minimisation des locks...).
17/02/2010, 09h45
Mac LAK

Citation:

Envoyé par JolyLoic

En quoi est-ce problématique quand il s'agit de faire du parallélisme pour les performances ?

Parce que la charge n'est pas toujours idéalement répartie, tout simplement. Tu peux voir une illustration de ce problème sur ce vieux topic.

En règle générale, dans le cas d'une optimisation maximale, tu en viens à être plus ou moins obligé de régler les affinités de façon à éviter la migration involontaire de threads, et/ou le regroupement de threads qui seraient soit "légers", soit non-concurrents.

Mais pour faire ça, il faut avoir très bien compris ce que font chacun des threads de son application, et compris comment ils se synchronisent. Je te concède bien volontiers que ce n'est pas à la portée du premier débutant en parallélisme, et que ce n'est pas non plus un niveau d'optimisation requis pour toutes les applications.

Citation:

Envoyé par JolyLoic

L'idée dans ce cas est de faire abstraction des primitive bas niveau et coûteuses comme les thread, les outils de lock au niveau du noyau,... et encore plus de l'affinité.

C'est bien pour ça que j'utilise usuellement des API portables à ce sujet, qui sont d'ailleurs encore encapsulées dans des objets d'encore plus haut niveau de façon à simplifier tout ça au maximum... Tout en gardant une implémentation performante, car c'est souvent fait à base de templates et donc inliné un maximum.

Et je continue donc de trouver très con de ne pas implémenter ces API d'affinités, quitte à les stubber sur les OS où cela pose problème... Tout le reste est implémenté, t'as même parfois des systèmes de priorité (inclus la modification du scheduling), et totalement portables, qui sont implémentés... L'affinité ne "coûtait" pas bien plus "cher" à ajouter.

Citation:

Envoyé par JolyLoic

Si tu règles l'affinité, comment fonctionnera le programme quand tu aura upgradé ta machine pour une avec 64 cœurs ?

Première règle d'une application gérant manuellement l'affinité : compter le nombre de cœurs / CPU disponibles réellement (= analyse du masque d'affinité du processus) en début d'application, et obtenir une map des coeurs/CPU utilisables.
Ensuite, penser à utiliser cette map, avec les contraintes de répartition des threads requises par l'algo bien sûr, lors de la création de nouveaux threads.

Je ne vois absolument pas où est le problème... ;)
18/02/2010, 23h35
JolyLoic

Citation:

Envoyé par Mac LAK

Parce que la charge n'est pas toujours idéalement répartie, tout simplement. Tu peux voir une illustration de ce problème sur ce vieux topic.

J'ai parcouru ce topic, mais je n'ai rien vu qui permette de penser que tripatouiller l'affinité aurait améliorer quoi que ce soit en l'occurrence (par contre, un meilleur découpage des tâches avec une meilleure gestion de la mémoire, oui, probablement). Et j'ai envie de dire que, d'autant plus quand la charge n'est pas idéalement répartie, il vaut mieux laisser le système faire du task stealing, ce qui est incompatible avec une affinité gérée par le développeur

Citation:

Envoyé par Mac LAK

En règle générale, dans le cas d'une optimisation maximale, tu en viens à être plus ou moins obligé de régler les affinités de façon à éviter la migration involontaire de threads, et/ou le regroupement de threads qui seraient soit "légers", soit non-concurrents.

Sauf que le système de tâche placé au dessus des threads est déjà fait pour ça, normalement, et j'ai l'impression que c'est le genre de chose qui peut se gérer automatiquement mieux qu'à la main (sauf éventuellement si la main est celle d'un véritable génie), tout comme à une époque l'attribution des registres était une activité normale d'optimisation, alors que maintenant on laisse faire le compilateur. Tout ce que l'utilisateur a à faire est de fournir un découpage avec la bonne granularité (ni trop, ni trop peu), qui respecte bien l'agencement mémoire (des données devant être touchées par deux tâches différentes doivent être physiquement loin les unes des autres, et inversement), et qui minimise les synchronisations nécessaires (dans l'idéal, aucune). A partir de là (ce qui est déjà beaucoup demander), au système de se débrouiller.
C'est d'autant plus vrai hors du monde embarqué, où l'on ne maîtrise par tout ce qui tourne sur la machine et où une optimisation manuelle fine risque de devenir une vraie pessimisation pour peu qu'un autre programme tourne derrière, et fasse lui aussi beaucoup de calculs.

Citation:

Envoyé par Mac LAK

Mais pour faire ça, il faut avoir très bien compris ce que font chacun des threads de son application, et compris comment ils se synchronisent. Je te concède bien volontiers que ce n'est pas à la portée du premier débutant en parallélisme, et que ce n'est pas non plus un niveau d'optimisation requis pour toutes les applications.

J'ai l'impression que c'est aussi inutile, voire néfaste, dans la très grande majorité des cas. As-tu un cas réel ou ça a eu un impact en tête (attention, je ne parle pas de parallélisme pour répondre à un évènement rapidement, là l'affinité peut avoir de l'intérêt, mais du parallélisme pour calculer vite) ?

Citation:

Envoyé par Mac LAK

L'affinité ne "coûtait" pas bien plus "cher" à ajouter.

Je ne sais pas trop de quel système tu parles, mais dans ceux que je connais un peu (TBB et PPL), j'ai l'impression que ne pas exposer l'affinité n'est pas un manque, mais une décision consciente visant à "obliger" les développeurs à prendre de la distance par rapport au système.
19/02/2010, 11h48
Mac LAK

Citation:

Envoyé par JolyLoic

J'ai parcouru ce topic, mais je n'ai rien vu qui permette de penser que tripatouiller l'affinité aurait améliorer quoi que ce soit en l'occurrence (par contre, un meilleur découpage des tâches avec une meilleure gestion de la mémoire, oui, probablement).

En fait, lorsque tu es dans un cas où il n'est pas possible d'atteindre 100% de charge avec un thread par cœur [ce qui est souvent signe de données trop volumineuses, mais on n'a pas toujours le choix], tu vas devoir avoir un thread supplémentaire pour récupérer le reste de charge disponible... Et dans un tel cas, tu ne dois avoir qu'un seul thread déplaçable, les autres doivent rester verrouillés sur un cœur en particulier.

Citation:

Envoyé par JolyLoic

Et j'ai envie de dire que, d'autant plus quand la charge n'est pas idéalement répartie, il vaut mieux laisser le système faire du task stealing, ce qui est incompatible avec une affinité gérée par le développeur

A un détail près : qui te dit qu'il sera possible d'améliorer la granularité de tes calculs ? Typiquement, tous les calculs de suite/série ne peuvent pas être individuellement parallélisés, par exemple... Et ils peuvent pourtant porter sur des données volumineuses.

Citation:

Envoyé par JolyLoic

Sauf que le système de tâche placé au dessus des threads est déjà fait pour ça, normalement, et j'ai l'impression que c'est le genre de chose qui peut se gérer automatiquement mieux qu'à la main (sauf éventuellement si la main est celle d'un véritable génie), tout comme à une époque l'attribution des registres était une activité normale d'optimisation, alors que maintenant on laisse faire le compilateur.

Jusqu'à présent, j'ai toujours dû équilibrer manuellement mes threads pour obtenir des performances maximales. L'OS n'est absolument pas suffisant à ce niveau, même s'il offre une assistance non négligeable.
De plus, les systèmes d'aide au parallélisme ne savent en général pas correctement gérer les éléments dynamiques (threads créés à la volée en réponse à un évènement extérieur, par exemple).

Citation:

Envoyé par JolyLoic

Tout ce que l'utilisateur a à faire est de fournir un découpage avec la bonne granularité (ni trop, ni trop peu), qui respecte bien l'agencement mémoire (des données devant être touchées par deux tâches différentes doivent être physiquement loin les unes des autres, et inversement), et qui minimise les synchronisations nécessaires (dans l'idéal, aucune). A partir de là (ce qui est déjà beaucoup demander), au système de se débrouiller.

Sauf que c'est cette partie que tu décris la plus longue et la plus difficile, et de très très loin !! La "tripaille" derrière, notamment le réglage de l'affinité, n'est qu'une broutille en comparaison.

Citation:

Envoyé par JolyLoic

C'est d'autant plus vrai hors du monde embarqué, où l'on ne maîtrise par tout ce qui tourne sur la machine et où une optimisation manuelle fine risque de devenir une vraie pessimisation pour peu qu'un autre programme tourne derrière, et fasse lui aussi beaucoup de calculs.

Heu, si t'as un calculateur pour lequel tu ne sais pas ni quelle est sa charge restante, ni si quelque chose tourne ou pas derrière, crucifies son administrateur : c'est un charlot... ;)
Tu as l'affinité processeur pour chaque processus devant être exécuté (les threads devant faire avec ce qui est alloué au processus), sans même parler d'éventuelles plages de réservation du calculateur, donc c'est un argument qui ne tient pas la route. Que ce soit dans le monde de l'embarqué ou du calcul intensif, la maîtrise de la machine est essentielle.

Citation:

Envoyé par JolyLoic

J'ai l'impression que c'est aussi inutile, voire néfaste, dans la très grande majorité des cas. As-tu un cas réel ou ça a eu un impact en tête (attention, je ne parle pas de parallélisme pour répondre à un évènement rapidement, là l'affinité peut avoir de l'intérêt, mais du parallélisme pour calculer vite) ?

En fait, c'est important pour pouvoir traiter beaucoup de calculs dans des laps de temps très courts et répétitifs (acquisition de données notamment). En effet, tu ne peux pas te permettre de pics de charge, ni de prendre du retard. Donc, tu dois non seulement réagir vite à l'arrivée de données brutes, mais EN PLUS les rendre traitées avant une échéance donnée... Sans perturber pour autant le reste du système, bien entendu.
Ce que je reproche au parallélisme "automatique", c'est justement cette absence de contrôle sur les pics de charge et sur la vitesse de réaction : en effet, tu ne sais PAS ce que les quelques macros / primitives que tu utilises provoquent réellement, et ça ne te permet donc pas d'être certain de ce qui va se passer.

Citation:

Envoyé par JolyLoic

Je ne sais pas trop de quel système tu parles, mais dans ceux que je connais un peu (TBB et PPL), j'ai l'impression que ne pas exposer l'affinité n'est pas un manque, mais une décision consciente visant à "obliger" les développeurs à prendre de la distance par rapport au système.

Je parle notamment des librairies POCO, ACE et ICE, qui possèdent toutes une abstraction portable des threads.
19/02/2010, 14h36
JolyLoic

Citation:

Envoyé par Mac LAK

Que ce soit dans le monde de l'embarqué ou du calcul intensif, la maîtrise de la machine est essentielle.

Sauf que justement, le parallélisme sort des ces deux domaines, pour devenir un prérequis aussi pour les applications tout venant tournant sur les portables de M. Toutlemonde. Donc le luxe de maîtriser sa machine n'est pas toujours disponible...

Citation:

Envoyé par Mac LAK

En fait, c'est important pour pouvoir traiter beaucoup de calculs dans des laps de temps très courts et répétitifs (acquisition de données notamment). En effet, tu ne peux pas te permettre de pics de charge, ni de prendre du retard. Donc, tu dois non seulement réagir vite à l'arrivée de données brutes, mais EN PLUS les rendre traitées avant une échéance donnée... Sans perturber pour autant le reste du système, bien entendu.

Et on est là dans le domaine du temps réel, qui a ses propres contraintes différentes du simple parallélisme pour la performance.

Citation:

Envoyé par Mac LAK

Je parle notamment des librairies POCO, ACE et ICE, qui possèdent toutes une abstraction portable des threads.

POCO et ICE, je ne connais pas, mais ACE est clairement fait pour gérer des threads, dans un contexte réactivité, par pour gérer du parallélisme pour les performances uniquement, avec des notions comme tasks, concurrency runtime, task stealing...
19/02/2010, 15h13
Mac LAK

Citation:

Envoyé par JolyLoic

Sauf que justement, le parallélisme sort des ces deux domaines, pour devenir un prérequis aussi pour les applications tout venant tournant sur les portables de M. Toutlemonde. Donc le luxe de maîtriser sa machine n'est pas toujours disponible...

Bof : pour 99% des gens, le parallélisme, c'est des threads d'IHM et de communication, avec éventuellement un ou deux trucs plus ou moins parallélisé pour utiliser plus d'un seul cœur...

Des "M. Toutlemonde" qui ont BESOIN de perfs brutales, je n'en connais pas beaucoup (pour ne pas dire un seul !), c'est presque systématiquement quelque chose pour le boulot, ou alors ce sont des fondus d'informatique (et là, ce n'est plus le lambda moyen).

Pour les utilisateurs uniquement (car ces API ne concernent que les dévs, hein...), ils se contrefichent royalement de l'API sous-jacente tant que ça pédale.

Citation:

Envoyé par JolyLoic

Et on est là dans le domaine du temps réel, qui a ses propres contraintes différentes du simple parallélisme pour la performance.

Le temps réel est quand même un des plus gros "client" du parallélisme, avec le calcul intensif... Et les deux domaines ont besoin de pouvoir contrôler la charge.
Or, n'oublie pas quand même que ce sont des domaines qui peuvent, de par le grand nombre d'applications liées, être les plus à même de tester intensivement les API MT. C'est pour ça que je trouve franchement crétin de ne pas permettre de gérer l'affinité dans ces API : ce n'est qu'une poignée de fonctions en plus, dont l'utilisation n'est ni obligatoire, ni requise.

Il est quand même extrêmement courant d'avoir des API fournissant une partie "basique", simple d'utilisation et convenant à 90% des cas, plus une partie "avancée" pour résoudre les quelques problèmes spécifiques qui ne peuvent pas se contenter des fonctions de base. Win32 ou POSIX en sont remplies, tout comme la quasi-totalité des librairies ou frameworks courants.

Cela ne dérange personne, et ça rend service à ceux qui en ont besoin : c'est pour ça que je trouve crétin de ne pas les ajouter.

Citation:

Envoyé par JolyLoic

POCO et ICE, je ne connais pas, mais ACE est clairement fait pour gérer des threads, dans un contexte réactivité, par pour gérer du parallélisme pour les performances uniquement, avec des notions comme tasks, concurrency runtime, task stealing...

Les trois librairies sont basées sur le même "principe" de base : l'abstraction du tronc commun de la gestion des threads entre les différents OS sur lesquels elles existent.
EDIT : et, accessoirement, c'est AUSSI pour les perfs que je les utilise... ;)

Le problème, c'est qu'ils ont "un peu" oublié au passage certaines parties spécifiques... Certaines sont ajoutées / refaites (ex : mutex avancés, type lecteurs/rédacteur), d'autres sont adaptées (ex : fonctionnalité type "pthread_join"), et d'autres sont cruellement absentes (l'affinité et le partage mémoire inter-processus notamment).
22/02/2010, 00h51
math_lab

Bonjour à tous. J'ai finalement pu régler tout ça en utilisant les fonctions de Windows. Pour ceux qui sont intéressés, voila en gros l'architecture du programme:
- Le programme principal crée n threads qui tournent en continu et attendent le signal pour commencer à bosser.
- A un certain point (quand j'ai besoin du calcul parallélisé de physique), le programme principal divise le boulot en n petit paquets de primitives (dans mon cas, plein de petits tétraèdres) et donne le signal de départ.
- Chaque thread calcule la physique sur ses primitives, (comme mes tétraèdres ont des sommets en commun, il y a un mutex qui protège l'écriture des forces) et envoi un signal au programme principal pour dire quand il a terminé.
- Le programme principal attend le signal de tous les threads et peut ensuite continuer normalement.

Ceux qui auraient besoin d'explications ou d'un peu de doc sur les commandes, allez voir ce tutorial: http://bob.developpez.com/tutapiwin/article_46.php

Ça s'est révélé plus simple que je le pensais. Et merci à ceux qui ont pu m'éclairer quelque peu.