paralléliser un code en C++ ?

Version imprimable

10/01/2011, 11h36
membreComplexe12

paralléliser un code en C++ ?

Bonjour tous,
une fois de plus je sollicite votre aide...:oops:

j'ai entendu parler vaguement de "parallélisation" pour diminuer les temps de calcul et je voudrais appliquer cela à un programme que j'ai réalisé j'ai réalisé en C++.
==> le problème: de parallélisation je ne connais que le nom :aie: je ne sais pas comment appliquer cela, de plus je suis un "gros débutant en programmation" j'aurais besoin de quelques pistes.... :calim2:

1°) mon programme:
- il récupère les données d'un fichier texte et classe cela dans 400000 vectors où il y a environ 1000 données pour chacun.

- une fois que cela est récupéré on lance une fonction qui fait un certain calcul (qui dure au maximum 1min) pour chaque vector et on enregistre les resultats dans un vector de 400000lignes.

2°) ce que je voudrais faire

je voudrais faire deux choses en parallèle: récupérer les données et lancer les calculs car je pense que le temps de récupération de toutes ces données doit être long (cette partie du programme n'est pas achevée) et je voudrais dès que j'ai un vector lancer le calcul mais tout en continuant en tache de font à récuper les autres vectors.

3°) questions:
- es ce possible de faire avec n'importe quel langage de programmation? et donc avec le c++?
- avez vous des pistes/liens qui explique comment faire ou pouvez vous me donner des pistes ou des exemples sur des cas simples?

Merci d'avance pour votre aide

:ccool:
10/01/2011, 11h47
fregolo52

Ce que tu veux faire est un programme multi-thread.
1 thread pour l'acquisition
1 thread pour le calcul

Comme tout programme multi-thread il faut gérer la synchro entre les threads.
Il y a plein d'exemple sur le Net, et il y a sûrement un cours sur ce site.

Tu peux développer en .NET (VB.NET, C#), C/C++, Java ... pour faire ça.
10/01/2011, 11h56
seeme

Bonjour!

Avant de chercher à parralèliser, il faut se poser la question suivante: "Mon programme nécessite-t-il plusieurs processus?" :)

A savoir: est-il nécessaire reprendre ton programme (parralèliser est souvent très lourd den terme de refactoring) ou des optimisations pourraient suffire?

Sinon, beaucoup de langages sont parralèlisables (java, C, C++, python...), certains ne le sont pas (VBA).

Pour faire ça, il faut bien comprendre ce qu'est un processus, et un processus léger (thread). Tu peux t'orienter vers boost::thread ou libpthread (plus orienté fonctionnel je crois).

Il faut isoler les traitement. Sur le papier, tu regardes à quel moment tu peux déclencher quel traitement. Il faut être sûr qu'un thread ne va pas tout bloquer (un autre l'attend) et que les variables sont correctement protégées (oui, il y a un espace mémoire commun avec les processus légers, à toi de le gérer).

Les principaux danger avec les threads sont:
* Les goulots: tu pensais améliorer ton programme, mais il met 4 fois plus de temps à cause d'un thread qui fait goulot).

* Ce que j'appelle le faux threading: au final tu as une succession de thread qui dépendent de leur père, tu n'as rien parralèlisé (dans certains cas ça peut être le but recherché, mais assez rarement)

* Les interblocages: là c'est un art.. Il faut protéger les ressources partagées entre les threads. Il faut à tout prix être sûr que quand un thread veut accèder à une ressource (lecteur CD.. Fichier), il est le seul à le faire pour éviter qu'un petit mariole aille modifier les données que tu es en train de lire.

Renseigne toi sur les sémaphores, les files de messages et les moniteur pour voir les différentes problèmatiques et leurs solutions.

Dans ton cas, il y a plusieurs approches..

* Un processus lit les lignes du fichier, et à mesure que les objets sont disponibles, un autre processus effectue le calcul.

* Plusieurs processus lisent des blocs du fichier (par exemple un processus lit 10 lignes et les traite, et tu mets plusieurs processus :p ). A mon avis une de splus intéressante.

* Un processus lit le fichier et plusieurs s'occupent du calcul

* Plusieurs lisent le fichier et un seul fait le calcul

* Plusieurs lisent le fichier et plusieurs font les calculs (à mon avis une des plus mauvaise..)

Et il y en a d'autres...
10/01/2011, 11h57
membreComplexe12

:ccool: merci d'avoir pris le temps de répondre :ccool:

Citation:

Envoyé par fregolo52

Ce que tu veux faire est un programme multi-thread.
1 thread pour l'acquisition
1 thread pour le calcul

merci déjà je viens d'apprendre deux nouveaux mots :oops: :ccool:

Citation:

Envoyé par fregolo52

Comme tout programme multi-thread il faut gérer la synchro entre les threads.

oui, cela je ne pense que ca ne doit pas être trop compliqué en utilsant des mot clef du type "pause" et "stop" dans le programme lorsqu'un des thread est fini...
ce qui m'inquiete plus est comment lancer telle tache sur tel processeur ou autre et qu'elles sont les mots clefs et fonction pour faire cela...

Citation:

Envoyé par fregolo52

Il y a plein d'exemple sur le Net, et il y a sûrement un cours sur ce site.
Tu peux développer en .NET (VB.NET, C#), C/C++, Java ... pour faire ça.

je déjà regardé avec les mots clefs que tu m'as donné et il y a effectivement beaucoup plus de réponses! :ccool:
10/01/2011, 12h03
seeme

En général, il est plus prudent de laisser le scheduleur attribuer les threads aux différents processeurs. Dans 99% des cas, on ne peut que règler l'affinité avec un processeur, le scheduleur va le prendre en compte et essayer de complaire à tes attentes, mais c'est sans garanties.

C'est un peu plus compliqué que pause et start, mais c'est ça :) (mot clef: yield)

Et pour protéger une ressource, c'est P() et V() (en général, je crois que ça vient d'une convention hongroise un truc du genre..).

edit:

Citation:

Les noms canoniques P et V venez des initiales de Hollandais mots. V stands pour verhogen, ou « augmentation ». Plusieurs explications ont été données pour P (y compris passeer pour le « passage », probeer « essai », et pakken le « encavateur »), mais en fait le Dijkstra a écrit qu'il a prévu P pour se tenir pour préparé valise mot prolaag,[1] abréviation verlagen de te de probeer, ou « essayer-et-diminuez » [1][2] (A moins ambigu, et une traduction en anglais plus précise et seraient « essaià- diminution ".)
10/01/2011, 12h06
fregolo52

Eh oui !! Le plus compliqué dans une recherche c'est d'avoir les bons mots clés !! ;)
10/01/2011, 12h06
membreComplexe12

salut seeme, merci pour cette reponse très complete :ccool:

Citation:

Envoyé par seeme

Avant de chercher à parralèliser, il faut se poser la question suivante: "Mon programme nécessite-t-il plusieurs processus?" :)

je n'ai pas bien compris: tu veux dire que si la lecture prends 30sec et les calculs 30min ca sert à rien de paralléliser, c'est cela ou j'ai mal compris ce que tu voulais dire?

Citation:

Envoyé par seeme

A savoir: est-il nécessaire reprendre ton programme (parralèliser est souvent très lourd den terme de refactoring) ou des optimisations pourraient suffire?

mon programme n'est pas très long et assez modulable donc pas de problème de ce coté là. coté optimisation je ne peux pas faire beaucoup mieux je pense car il est vraiment classique.

Citation:

Envoyé par seeme

Sinon, beaucoup de langages sont parralèlisables (java, C, C++, python...), certains ne le sont pas (VBA).

ok, moi j'utilise C/C++ mais j'aurais peut etre quelque chose à faire en fortran plus tard. est il parallélisable?

Citation:

Envoyé par seeme

Pour faire ça, il faut bien comprendre ce qu'est un processus, et un processus léger (thread). Tu peux t'orienter vers boost::thread ou libpthread (plus orienté fonctionnel je crois).
Il faut isoler les traitement. Sur le papier, tu regardes à quel moment tu peux déclencher quel traitement. Il faut être sûr qu'un thread ne va pas tout bloquer (un autre l'attend) et que les variables sont correctement protégées (oui, il y a un espace mémoire commun avec les processus légers, à toi de le gérer).
Les principaux danger avec les threads sont:
* Les goulots: tu pensais améliorer ton programme, mais il met 4 fois plus de temps à cause d'un thread qui fait goulot).
* Ce que j'appelle le faux threading: au final tu as une succession de thread qui dépendent de leur père, tu n'as rien parralèlisé (dans certains cas ça peut être le but recherché, mais assez rarement)
* Les interblocages: là c'est un art.. Il faut protéger les ressources partagées entre les threads. Il faut à tout prix être sûr que quand un thread veut accèder à une ressource (lecteur CD.. Fichier), il est le seul à le faire pour éviter qu'un petit mariole aille modifier les données que tu es en train de lire.
Rensegne toi sur les sémaphores, les files de messages et les moniteur pour voir les différentes problèmatiques et leurs solutions.
Dans ton cas, il y a plusieurs approches..
* Un processus lit les lignes du fichier, et à mesure que les objets sont disponibles, un autre processus effectue le calcul.
* Plusieurs processus lisent des blocs du fichier (par exemple un processus lit 10 lignes et les traite, et tu mets plusieurs processus :p ). A mon avis une de splus intéressante.
* Un processus lit le fichier et plusieurs s'occupent du calcul
* Plusieurs lisent le fichier et un seul fait le calcul
* Plusieurs lisent le fichier et plusieurs font les calculs (à mon avis une des plus mauvaise..)
Et il y en a d'autres...

:ccool: je vais regarder tous cela, merci pour ces pistes :ccool:

Citation:

Envoyé par seeme

En général, il est plus prudent de laisser le scheduleur attribuer les threads aux différents processeurs. Dans 99% des cas, on ne peut que règler l'affinité avec un processeur, le scheduleur va le prendre en compte et essayer de complaire à tes attentes, mais c'est sans garanties.
C'est un peu plus compliqué que pause et start, mais c'est ça :) (mot clef: yield)
Et pour protéger une ressource, c'est P() et V() (en général, je crois que ça vient d'une convention hongroise un truc du genre..).

d'accord, merci pour ces infos
10/01/2011, 12h12
fregolo52

Citation:

Envoyé par seeme

* Ce que j'appelle le faux threading: au final tu as une succession de thread qui dépendent de leur père, tu n'as rien parralèlisé (dans certains cas ça peut être le but recherché, mais assez rarement)

Ca reste quand même le plus simple. Tu fais plusieurs threads dans un même processus. Ca évite les contraintes multi-processus, il y en aura déjà avec avec les synchros et les inter-blocage !!

Citation:

salut seeme, merci pour cette reponse très complete

Citation:

Envoyé par seeme
Avant de chercher à parralèliser, il faut se poser la question suivante: "Mon programme nécessite-t-il plusieurs processus?"

je n'ai pas bien compris: tu veux dire que si la lecture prends 30sec et les calculs 30min ca sert à rien de paralléliser, c'est cela ou j'ai mal compris ce que tu voulais dire?

En effet, ca ne sert à rien (à part pour apprendre), sauf si tu peux paralléliser la partie calcul.
10/01/2011, 12h13
seeme

En fait mes 2 premières remarques viennent d'experience sur un forum de débutants. La plupart cherchaient à parralèliser là où en fait un peu de logique permettait de passer par exemple de O(e^n) à O(n).

Mais is tu as de l'experience et que tu sais que ton code est bien comme ça et que les gains en optimisation seront minimes, ne t'angoisse pas et regarde le multi thread :)

Je ne connais pas fortran mais une recherche rapide sur google montre qu'il existe des lib et des backends avec pthread par exemple. Donc oui, ça doit êtr e possible.
10/01/2011, 12h16
membreComplexe12

Citation:

Envoyé par fregolo52

En effet, ca ne sert à rien (à part pour apprendre), sauf si tu peux paralléliser la partie calcul.

- tu as raison rien que pour apprendre qu'es ce que paralléliser je pense que je vais essayer.

- par contre pour l'utilité je ne sais pas trop car je n'ai pas la notion du temps de calcul pour lire toutes ces données (et comme je ne les ai pas encore je ne peux pas faire le test)
10/01/2011, 12h21
seeme

Je pense que c'ets le calcul qui va prendre le plus de temps. Et là ça devient clairement plus complexe (dépendant de la nature de ton calcul). Il faut essayer de découper ton calcul en étapes qui ne soient pas dépendantent.

Donc si tu as disons 3 étapes A, B, C avec A et B indépendant, et C qui dépend de A et de B, tu peux essayer de parralèliser le calcul de A et de B avec C qui attent les résultats des 2 autres.

Note: fait attention à ne pas tomber dans le piège de l'attente active...
10/01/2011, 12h21
membreComplexe12

Citation:

Envoyé par seeme

Mais is tu as de l'experience et que tu sais que ton code est bien comme ça et que les gains en optimisation seront minimes, ne t'angoisse pas et regarde le multi thread :)

en fait je n'ai pas beaucoup d'expérience en C++ (quasiment =0) mais comme mon programme est très court je ne pense pas que je peux optimiser grand chose.
la seule chose qui prend du temps est la gestion du pas de calcul et cela je vais essayer de l'optimiser au mieux.

Citation:

Envoyé par seeme

Je pense que c'ets le calcul qui va prendre le plus de temps. Et là ça devient clairement plus complexe (dépendant de la nature de ton calcul). Il faut essayer de découper ton calcul en étapes qui ne soient pas dépendantent.

le calcul n'est pas parallelisable car j'ai 3 étapes totalement dépendantes...

Citation:

Envoyé par seeme

Note: fait attention à ne pas tomber dans le piège de l'attente active...

qu'es ce que c'est que cela?
10/01/2011, 12h37
JolyLoic

Je dirais que si tu veux paralléliser simplement et efficacement, il ne faut pas parler thread, ni semaphore (les P et V), ni rien de ces routines bas niveau et complexes à utiliser.

Déjà, il faut se poser la question : Est-ce que mes calculs sont indépendant les uns des autres. Ici, ça a l'air d'être le cas : Chaque vecteur peut être traité à part des autres, et en parallèle (sauf l'écriture du résultat final, mais là aussi, comme on écrit dans des cases différentes, si le vecteru a été pré alloué, pas de soucis).

Ensuite, prendre une bibliothèque adaptée, comme Intel TBB (libre), ou PPL de microsoft. Ou une extention au C++ comme OpenMP.

Et alors, tout ce que tu auras à faire est de remplacer ta boucle principale par une version parallèle de cette boucle.
10/01/2011, 14h11
seeme

J'avoue que j'ai appris uniquement en bas niveau et n'ai pas encore eu besoin d'aller plus haut niveau.

L'attente active, c'est par exemple un

Citation:

while(!continuer){}

avec continuer un booleen à l'étape n-1. Ici on attend que l'étape précédente soit terminée, mais c'est une manière à éviter (tu manges des cycles CPU à ne rien faire), il existe d'autres moyens.

Les seules fois où j'ai dû faire de l'attente active c'était en ASM sur un processeur ARM (et encore, la plupart du temps on peut s'en tirer avec les interuptions.. mais bon c'est un autre sujet :p )
10/01/2011, 15h06
membreComplexe12

salut loic,

Citation:

Envoyé par JolyLoic

Je dirais que si tu veux paralléliser simplement et efficacement, il ne faut pas parler thread, ni semaphore (les P et V), ni rien de ces routines bas niveau et complexes à utiliser.

ca m'interesse beaucoup tout cela, car plus c'est facile mieux c'est.:ccool:

Citation:

Envoyé par JolyLoic

Déjà, il faut se poser la question : Est-ce que mes calculs sont indépendant les uns des autres. Ici, ça a l'air d'être le cas : Chaque vecteur peut être traité à part des autres, et en parallèle (sauf l'écriture du résultat final, mais là aussi, comme on écrit dans des cases différentes, si le vecteru a été pré alloué, pas de soucis).

oui c'est bien cela mon cas.

Citation:

Envoyé par JolyLoic

Ensuite, prendre une bibliothèque adaptée, comme Intel TBB (libre), ou PPL de microsoft. Ou une extention au C++ comme OpenMP.
Et alors, tout ce que tu auras à faire est de remplacer ta boucle principale par une version parallèle de cette boucle.

quand je serais en train de mettre tout cela en place, si je n'y arrive pas je pense que je vous relancerez pour un coup de main ;)