Discussion :

[pleasereset]

Bonjour à tous,

Loin d'être expert en C# (junior en labo de recherche au japon ), je conçoit et développe actuellement une application de reconnaissance de forme 3D (cylindres) à partir d'un nuage de points.
Comme vous vous doutez, la phase de calcul est lourde, et pour raccourcir le temps de traitement je me suis évidemment tourné vers le multithreading.

L'approche qui me semblait la plus efficace est : séparer la charge de travail en deux (ou plus suivant le nombre de cpu), et lancer un thread calcul lourd pour chaque "part de boulot".
Le thread 'maman' attends patiemment que les calculs soient terminés, collecte et synthétise les résultats.

Mon souci est le suivant : alors qu'en mono-thread, j'utilise sans défaillir 50% du CPU, avec deux threads, j'utilise seulement 70/85% du CPU... ce qui m'épate, vu qu'il a de quoi s'occuper.

Trace Windows 1 Thread (thread de calcul en rouge) :
http://img43.imageshack.us/img43/6336/trace1cpu.png

Trace Windows 2 Threads (threads de calcul en rouge et bleu) :
http://img41.imageshack.us/img41/5485/trace2cpu.png

Aucune synchro entre les deux threads, donc pas d'attente mutuelle "explicite". L'objet à traiter est crée dans le thread "maman", et donc partagé entre les deux threads, mais ils utilisent différentes zones de cet objet (imaginer une matrice, chaque thread traite 50% de la matrice).

De fait, je constate un ralentissement du temps de traitement moyen d'une "unité" de travail (chaque thread accomplissant 60 unités de travail) :
- 1 thread : 134ms par unité de travail, 15,2s pour le total
- 2 threads : 212ms par unité de travail, 13s pour le total

Je sollicite donc vos cerveaux experts pour me dire que faire pour augmenter les performances de mon application !

(Tout refaire en C++ n'est pas une option, j'ai choisi C# car j'ai des délais de développement serrés )

[emmr.rida]

Tout refaire?! Non, biensure. Mais seulement les parties les plus critiques du calcul.

[theMonz31]

faire du multithread veut pas forcement dire augmenter les performances au final... sauf si le truc va tourner sur plusieurs Core..

Parallel extension pourrait te tenter (fais une recherche)...

sinon, ya surement moyen d'optimiser ton code

[pleasereset]

Il y'a en effet sûrement moyen d'optimiser mon code et mon algorithme de travail, et j'y planche, j'y planche...

Cependant, ce qui me chiffonne pour l'instant c'est le fait de ne pas saturer les CPU avec deux threads, alors que je sature un CPU avec un thread.

En effet mon application est vouée à tourner sur des machines dual/quad core dont je veux utiliser le potentiel au maximum.

Est-il possible d'utiliser Parallel Extensions sous .NET 3.5 ?

Je viens de faire une série de tests qui m'étonne, sur un Core 2 Duo 2.5Ghz, sous Windows 7 :

- 1 thread : 1 unit de calcul en 132ms moyenne, 120 units traitées en 14.9s
- 2 threads : 219ms / 13.4s
- 3 threads : 239ms / 10s (et j'approche 99% d'utilisation cpu, pourtant, il n'y a aucune attente IO ou autre dans mon thread de calcul)
- 4 threads : 323ms / 10.8s
- 5 threads : 368ms / 9.7s
- 6 threads : 413ms / 10.2s

L'augmentation du temps de traitement d'une unité de calcul m'étonne lors du passage 1 à 2 threads (ayant deux cores, elle devrait rester sensiblement équivalente), mais surtout, lors du passage à 3 threads, elle évolue peu... alors que théoriquement je n'ai pas assez de CPU pour mener 3 threads à bien.

[Mac LAK]

Un processeur multicœurs n'est PAS un système multi-CPU, contrairement à ce que l'on pourrait penser... Notamment, tu n'as qu'un seul bus mémoire !

Ce qui fait que si tes deux threads, même correctement répartis sur les cœurs (réglage de l'affinité), cherchent à taper dans la mémoire en même temps, et bien l'un des deux attendra que l'autre aie fini. D'où ton pourcentage d'utilisation CPU non-optimal, alors qu'il l'est avec 3 threads, en fait (N+1) threads, N étant le nombre de coeurs.

Une fois les données chargées et/ou en cache et/ou les threads synchronisés "de force" entre eux, tu te retrouves à priori avec un thread occupé à charger, et deux qui bossent, avec un "cycle" entre les threads.

Si tu veux optimiser plus lourdement ton calcul, il faudra peut-être repenser ton algo : par exemple, avoir un thread "serveur" qui s'occupe de récupérer les données en RAM, et qui alimente les threads de calcul avec des données suffisamment courtes pour tenir à coup sûr dans le cache.

En attendant, sur le type de calcul que tu sembles faire, un si faible gain indique sans nul doute que les transferts mémoire sont trop coûteux par rapport au temps de calcul... Tu n'as gagné "que" 33% de temps total, alors que la phase de calcul "pure" devrait avoir gagné 50% au bas mot. La différence, c'est le chargement / stockage des données, le transfert mémoire donc.
Tu peux toutefois continuer à accélérer en prenant comme base (N+1) threads par rapport au nombre de cœurs, ce sera toujours mieux que rien, mais arriver à (1/N) du temps "monothread" impose à mon avis de repenser ta parallélisation...

[pleasereset]

Merci beaucoup pour ta réponse claire et concise qui éclaire ma lanterne !

Une question de pure curiosité, sur un CPU comme l'AMD Phenom ou l'Intel Core i7, intégrant le controleur mémoire au CPU, le problème se pose toujours ? (Y'a t'il toujours un seul bus mémoire par CPU ou un bus par core ?)

En effet tu as vu très clair dans mon application, l'exécution d'une unité de données suppose la lecture de beaucoup de données (par exemple, l'estimation de la normale d'une surface en un point dans un nuage de points suppose la lecture des points environnants... à la louche, au minimum 256Ko de données (donc trop pour le L1 d'un core).

L'approche thread RAM et thread de calcul semble intéressante... si j'arrive à réduire le volume de données à traiter à moins de 64Ko si je comprends bien, et si la séléction des données pour arriver à ces 64Ko n'est pas trop couteuse.

Dur dur !

[Zubrowka31]

J'ai eu le même genre de problème, a savoir, calcul sur des millions d'enregistrement d'une BDD. Étant donné que les données n'était pas liées entre elles, chaque Thread "fils", instancie son propre objet pour le traitement évitant ainsi tout probleme de synchro entre les threads.

L'objet à traiter est crée dans le thread "maman", et donc partagé entre les deux threads, mais ils utilisent différentes zones de cet objet

Peut être quand travaillant sur deux objet distinct et en fusionnant les deux deux objets apres ton join, tu pourrais grappiller un petit peu!

Sinon topic très intéressant!

[Guulh]

Le parallélisme, il faudra probablement qu'on s'y mette tous Mais vu que son exploitation efficace dépend de la gestion de la mémoire, et qu'elle est manuelle en C++ et automatisée en C#, je ne pense pas que les mêmes recettes puissent s'appliquer indifféremment. En tous, comme le soulignait theMonz, c'est un sujet sur lequel planche l'équipe .Net de Microsoft. cf ce blog, entre autres.

[Mac LAK]

Le parallélisme, il faudra probablement qu'on s'y mette tous

C'est déjà le cas : tu vois souvent des projets monothreads ET monoserveurs ET monoclients ?

Mais vu que son exploitation efficace dépend de la gestion de la mémoire, et qu'elle est manuelle en C++ et automatisée en C#, je ne pense pas que les mêmes recettes puissent s'appliquer indifféremment.

Faux. Son exploitation efficace dépend de l'algorithme à 90%, et si tu "penses" mal, le système fera au mieux avec les boulets que tu lui auras attaché aux pieds... C'est pour ça que simplement threader un algo "normal" en pensant le paralléliser améliore très souvent les performances, mais rarement dans les proportions que l'on espérait (cas précis et exact de l'OP...).

En tous, comme le soulignait theMonz, c'est un sujet sur lequel planche l'équipe .Net de Microsoft. cf ce blog, entre autres.

Ils peuvent plancher tant qu'ils veulent, ils ne pourront jamais prévoir l'infinité d'algorithmes parallèles possibles, sans même parler des tailles de données, des corrélations avec les caches, des optimisations dues au langage et/ou à l'organisation des données, etc.
Ils peuvent aider (un peu) sur des algos "bateau" assez récurrents... Pas sur tout.

La meilleure optimisation de programme parallèle, ça reste le jus de cerveau... Et ceci restera vrai jusqu'à l'avènement de l'IA "réelle", donc pas pour demain.

[Guulh]

C'est déjà le cas : tu vois souvent des projets monothreads ET monoserveurs ET monoclients ?

On joue sur les mots Avec .Net, le multithreading est souvent encapsulé dans des composants. BackGroundWorker dans les clients, threads qui se crée quand un client remoting se connecte à un serveur, etc. Et la seule chose à laquelle il faut faire gaffe, c'est de correctement locker les objets accédés depuis plusieurs threads.
Là, c'est pour des raisons de perf en milieu multi-core / multi-CPU uniquement que l'on devrait écrire son code d'une certaine façon plutôt que d'une autre. C'est ça, qui me semble nouveau.

Faux. Son exploitation efficace dépend de l'algorithme à 90%,

Certes oui ; mais gestion de la mémoire et algo ne sont-ils pas liés ? Etant donné le mode de création et d'allocation différent des objets, ce qui serait optimal dans un langage ne le serait pas dans l'autre, et comme tu l'as dit, au final, "il est POSSIBLE que ta solution passe impérativement par du C / C++."

Ils peuvent aider (un peu) sur des algos "bateau" assez récurrents... Pas sur tout.

C'est déjà vrai dans bien d'autres domaines, ça ! A mon avis, ce qui fait la force de .Net, c'est que ça facilite grandement 90% des tâches les plus courantes. Et vu que dans l'énorme majorité des projets, la maintenabilité prévaut largement sur la performance (bon peut être pas dans le cas de l'OP, certes)...

[Mac LAK]

On joue sur les mots Avec .Net, le multithreading est souvent encapsulé dans des composants. BackGroundWorker dans les clients, threads qui se crée quand un client remoting se connecte à un serveur, etc. Et la seule chose à laquelle il faut faire gaffe, c'est de correctement locker les objets accédés depuis plusieurs threads.

Mouais, bon, je n'appelle quand même pas des threads de connexion ou un thread de calcul "seul" (qui n'a pour seul but que d'empêcher un freeze de l'IHM) de la programmation parallèle...
Surtout que .NET n'a rien inventé à ce sujet : je t'encourage à aller voir du côté de Delphi, pour citer un des plus connus, où c'est comme ça depuis des années.

Là, c'est pour des raisons de perf en milieu multi-core / multi-CPU uniquement que l'on devrait écrire son code d'une certaine façon plutôt que d'une autre. C'est ça, qui me semble nouveau.

Pourtant, ça ne l'est pas. Comme je l'ai dit, c'est du grand classique... OK, je reconnais qu'avoir eu des cours intensifs de programmation parallèle aide à trouver ça "classique"...

Certes oui ; mais gestion de la mémoire et algo ne sont-ils pas liés ? Etant donné le mode de création et d'allocation différent des objets, ce qui serait optimal dans un langage ne le serait pas dans l'autre, et comme tu l'as dit, au final, "il est POSSIBLE que ta solution passe impérativement par du C / C++."

Si tu cherches la performance pure, déjà, les langages managés sont une mauvaise idée, tout comme de façon générale ce qui simplifie un peu trop la vie (la STL en est un excellent exemple, c'est très facile de la mettre à genoux si l'on utilise du "lourd"...).
Ceci étant dit, un langage managé et/ou des objets / entités de haut niveau PEUVENT aider à mettre au point plus rapidement un algo, en évitant justement la tripaille interne qui est toujours longue à mettre au point.
Une fois l'algo "propre" et surtout, optimal, là tu peux remettre un coup de boost à ton programme en le faisant en natif et en collant le plus possible au matériel.

Mais passer direct en natif, en se contraignant en plus par rapport au hard, SANS avoir un algo parfaitement au point, c'est réellement un casse-gueule de première... L'algo d'abord, l'optimisation après. Dans le cas de l'OP, c'est manifestement l'algo qui pêche car il provoque un goulet d'étranglement au niveau de la mémoire (mauvaise séparation et/ou organisation des données).

Un objet, ça alloue la mémoire "automatiquement" si tu l'as bien voulu : t'as souvent (pour ne pas dire toujours) la possibilité d'aligner les données sur les mots-machine, c'est même souvent le cas par défaut. Ensuite, un objet, c'est une VMT, puis les données dans l'ordre de déclaration... T'as une légère surconsommation mémoire, plus une légère perte de temps à l'appel des méthodes si elles sont virtuelles, mais c'est tout. Côté accès aux données, c'est pareil qu'une structure.

C'est déjà vrai dans bien d'autres domaines, ça ! A mon avis, ce qui fait la force de .Net, c'est que ça facilite grandement 90% des tâches les plus courantes. Et vu que dans l'énorme majorité des projets, la maintenabilité prévaut largement sur la performance (bon peut être pas dans le cas de l'OP, certes)...

La force de .NET, c'est d'avoir Microsoft derrière... Côté puissance de dev, je suis désolé, mais ça ne vaut pas tripette par rapport à Visual C++ (gestion des versions Debug / Release pitoyable en C#, gestion des solutions et des dépendances nettement régressives par rapport à ce qui était devenu la "norme" en C++, etc.).
Côté puissance de l'API, je trouve Delphi largement supérieur, avec un langage bien plus fortement typé, une vitesse d'exécution bien supérieure et un système RAD dont Microsoft devrait sérieusement songer à s'inspirer.

Le seul point fort de .NET à mon sens, c'est qu'il supporte plusieurs langages / modes [web, natif, applets, ...] sur la même API de base, et qu'il donne accès à la quasi-totalité des fonctions de l'OS facilement. Mais sûrement pas quelques futures librairies d'aide au parallélisme qui ne seront "utiles" que pour des problèmes très simples, déjà maîtrisés depuis des années dans la plupart des langages natifs.

Pour le reste... On en est au framework 3.5, je crois, et pour l'instant je ne vois aucune raison, à titre personnel, pour passer sur .NET à la place de mon Delphi favori : y'a pas photo côté maintenabilité et rapidité de développement... Le seul gain de .NET, c'est qu'il faut reconnaître que WPF est nettement moins "usine à gaz" que les MFC pour le développement d'IHM, même si c'est au prix d'une vitesse d'exécution légèrement réduite.