Discussion :

[Seabirds]

Bonjour à toutes et à tous !

J'ai fini une première version d'un bout de code. En gros, on fait tourner l'algo suivant (avec un modèle plus complexe que std::poisson, et le code ci-dessous n'a que vocation d'illustration ).

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
20
21
22
23
24
25
26
 
using data_type = int;
using model_type = std::poisson_distribution<data_type>;
using param_type = model_type::param_type;
 
std::default_random_engine g;
 
model_type model(20);
data_type observed = model(g);
 
std::uniform_distribution<param_type> search_domain(0,100);
param_type threshold(2);
std::vector<param_type> acceptations;
 
current_accepted = 0;
while(nb_accepted < 1000000){
  param_type try = search_domain(g);
  model.param(try);
  data_type simulation = model(g);
  if( data.distance_to(simulation) <= threshold) {
     acceptations.push_back(try); // oui, bon on pourrait faire un reserve, mais c'est pour l'exemple ^^
     ++current_accepted;
  }
}
// on print acceptations dans un fichier
// on calcule la moyenne de acceptations et on espère que c'est pas trop loin de 20.

Le nombre de simulations à accumuler est assez gros (millions/milliards), et évidemment on ne fait pas ça avec la loi de poisson : le modèle de simulation est un poil long à calculer également.
Pour une version très allégée du modèle et un nb_accepted très restreint, ça met déjà plusieurs heures à tourner. Du coup là j'atteins le moment où la question de l'optimisation devient légitime n'est-ce-pas

Pour note, mon ordi est multi-coeur et j'ai accès à la grappe de calcul du labo.

Comme chaque itération est indépendante, on pourrait paralléliser la boucle for et faire un gain de performance d'un ordre de grandeur équivalent au nombre de coeurs (désolé pour les écarts de langage, je sais à peine ce qu'est un coeur ) n'est ce pas ?

• Quand je lis le chapitre Programmation Concurrente du bouquin de Scott Meyers (Programmer efficacement en C++11/14), le mot clé est multitâche, à coup de std::async, std::future ... J'ai sans doute mal interprété le cadre dans lequel émerge ce besoin, mais j'ai cru comprendre que c'était une bonne direction à prendre (mais j'ai pas tout compris ).
• Quand je lis différentes ressources, il y a des std::threads un peu partout, ça je comprends à peu près.
• Quand je lis les messages du forum Threads&Processus, ce qui semble correspondre à mon besoin serait OpenMP, mais j'ai peur d'y aller tous azimuts en me plantant allègrement de direction.

Pourriez-vous me faire part de vos conseils quant à la direction à prendre ? Si j'ai une première direction je pourrai focaliser mes efforts de documentation dessus
En vous remerciant

[Matt_Houston]

Paralléliser une boucle de calcul scientifique (i.e. : où tous les threads font grosso modo la même chose sur un jeu de données indépendant), c'est typiquement le cas d'utilisation où OpenMP excelle. C'est mis en œuvre en trois, quatre lignes avec un parallel for.

[Seabirds]

Cool ça me rassure merci !!! je fonce relire la doc de OpenMP alors

Par curiosité, quels sont les cas classiques où j'aurais du me dire "mmhhh là je vais plutôt std::async" ou "là c'est un cas typique de std::thread" ? Il y a beaucoup de tutos pour les unes ou les autres méthodes, mais j'ai trouvé peu d'indications sur les cas où mettre en oeuvre telle ou telle approche

Question peut-être liée : admettons que j'utilise OpenMP pour la boucle la plus externe du programme. Est-ce qu'il y a encore moyen (pour le noob que je suis) de gratter des perfs avec le multithreading/multitasking/parrallelisation ? Je pense aux petites régions parallélisables plus internes du code. On peut avoir une intuition sur les performances espérées ou bien en est on réduit à benchmarker chaque implémentation pour voir son gain éventuel ?

[dalfab]

Bonjour,

En fait, les trois moyens que tu as vu, sont différentes facette de la capacité à utiliser le CPU disponible. OpenMP et async sont les plus accessibles pour des calculs, les threads sont toujours la même chose avec plus de possibilités. Il est inutile de les combiner. Attention avec 4 coeurs tu devrais au mieux diviser tes temps par 2.

[Seabirds]

Bonjour,

En fait, les trois moyens que tu as vu, sont différentes facette de la capacité à utiliser le CPU disponible. OpenMP et async sont les plus accessibles pour des calculs, les threads sont toujours la même chose avec plus de possibilités. Il est inutile de les combiner. Attention avec 4 coeurs tu devrais au mieux diviser tes temps par 2.

Ok, donc en gros une fois que j'ai utilisé OpenMp sur la boucle extérieure, inutile d'espérer gratter plus de CPU disponible. Il faudra j'imagine aller gratter côté algorithmes et structures de données
Aie zut, seulement un facteur 2 ? Saperlipopette, mon intuition était donc fausse !

[bacelar]

Si les traitement sont hautement parallèles, on peut voir du coté des GPU à la place de CPU.

[Ehonn]

Ok, donc en gros une fois que j'ai utilisé OpenMp sur la boucle extérieure, inutile d'espérer gratter plus de CPU disponible.

Si le problème s'y prête, et que le compilateur ne le fait pas déjà, tu peux vectoriser le calcul (avec les instructions SIMD.
Par exemple, si tu utilises des float de 32 bits et que ton processeur supporte AVX2 (registre de 256 bits), tu peux (espérer) gagner un facteur 8 (256 / 32).

Tu dois aussi vérifier si tu fais les accès mémoire "dans le bon sens" ; c'est-à-dire, dans le sens de la mémoire.

Mais effectivement, il faut regarder / vérifier l'algorithme avant.

[Pyramidev]

Bonjour,

Dans la boucle, je vois qu'il y a des accès à un objet commun std::default_random_engine.
Pour éviter de synchroniser les accès à un générateur commun (qui serait construit hors de la boucle) et pour éviter aussi de créer 1 000 000 générateurs (qui seraient chacun construit dans la boucle), je pense que chaque thread devrait travailler avec des générateurs séparés.
Idem pour les autres objets qui sont communs dans le code d'origine.

On pourrait partir d'une double boucle for de la forme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
acceptations.resize(1000000);
for(k = 0; k < 4; ++k) {
    std::default_random_engine g;
    model_type model(20);
    data_type observed = model(g);
    std::uniform_distribution<param_type> search_domain(0,100);
    param_type threshold(2);
    for(i = k*250000; i < (k+1)*250000; ++i) {
        // affecter une valeur à acceptations[i]
    }
}

Ensuite, on pourrait paralléliser les itérations de la boucle for englobante.
En C++17, la manière standard de le faire serait d'utiliser std::for_each avec en premier paramètre un std::execution::par pour paralléliser.
En attendant C++17, je pense que le mieux est d'utiliser OpenMP. Je ne l'ai jamais utilisé et je ne l'ai pas encore étudié, mais il semble que, dans le code, il suffit juste d'ajouter #pragma omp parallel for au dessus de la boucle for englobante.

[ternel]

Notons que si tu accédes à une grille de calcul, il doit y avoir une documentation de la manière de répartir le calcul sur plusieurs machines.
A moins qu'elle n'apparaisse magiquement comme un super processeur à beaucoup de cœurs, ce qui m'étonnerait quand même beaucoup.

Si tes itérations sont réellement indépendantes, tu ne devrais pas avoir de différence significative entre

• exécuter une fois ton programme pour produire un million de résultats, dans un fichier de sortie
• exécuter mille fois ton programme pour produire mille résultats à chaque fois, et concatener les mille fichiers produits.

Partant de là, rends configurable le nombre d'itérations (argument en ligne de commande, au besoin, boost::program_options).
Ainsi, tu pourras exécuter le programme, pour un nombre limité d'itérations, sur chaque noeud de la grille de calcul.

éventuellement, tu n'auras même pas à paralléliser le programme en lui-même. Tu pourrais imaginer le lancer plusieurs fois sur chaque noeud (par exemple, nombre de cœur -1).

[Seabirds]

Si les traitement sont hautement parallèles, on peut voir du coté des GPU à la place de CPU.

Je note l'information, merci . C'est accessible à quel point à un débutant ?

Si le problème s'y prête, et que le compilateur ne le fait pas déjà, tu peux vectoriser le calcul [...] Tu dois aussi vérifier si tu fais les accès mémoire "dans le bon sens" ; c'est-à-dire, dans le sens de la mémoire.

Ok je garde ça dans un coin de ma tête ! Ton allusion au sens de la mémoire a trait au sens de déclaration des variables membres, à l'alignement des données ? (sorry, noob again ).

Si le problème s'y prête, et que le compilateur ne le fait pas déjà, tu peux vectoriser le calcul (avec les instructions SIMD ou avec Boost.SIMD).

"Si les données s'y prêtent bien" ... j'imagine que ça veut dire que matrices et tableaux abonderaient dans le code ... Hum. Soit que j'ai choisi les mauvaises structures de données (toujours possible ) soit que mon problème ne s'y prête à la base pas très bien (y'a plein de stochasticité partout), mais je n'ai aucun tableau et aucune matrice (mais beaucoup de std::vector, std::unordered_map, std::unordered_set ...).

En C++17, la manière standard de le faire serait d'utiliser std::for_each avec en premier paramètre un std::execution::par pour paralléliser.

Sacré C++17, que n'es-tu pas sorti avant ma thèse ...

A moins qu'elle n'apparaisse magiquement comme un super processeur à beaucoup de cœurs, ce qui m'étonnerait quand même beaucoup.

Je suis en train de me renseigner. Je crois que c'est pas forcément une grappe de calcul, mais un serveur multiprocesseur. Pas sûr, à voir, je note l'idée !

Merci à tous pour vos réponses et ces nombreuses pistes, j'imagine que j'en ai pour des années à explorer tout ça ! Ecrire un programme qui tourne est une chose, écrire un programme lisible qui tourne en est une autre, écrire un programme lisible, évolutif, qui tourne est une aventure que je veux bien tenter, mais quant à écrire un programme lisible, évolutif, fonctionnel ET EFFICACE ...

[ternel]

Il y a aussi le concept de thread pool qui peut t'intéresser.

Rappelle-toi, cependant, qu'un programme fait quelque chose.
Il doit le faire bien. Il doit être compréhensible que c'est ca qu'il fait. Le code doit être assez clair pouvoir comprendre comment il le fait.

Maintenant, chaque fois que tu changes ne serait-ce qu'un détail du "quelque chose", ton programme peut devenir totalement inadapté.

En l'occurence, tu as codé pour un processeur simple. C'était ton objectif.
Si tu veux maintenant viser plusieurs système séparés ou des cœurs d'un processeur, certaines parties de ton programme peuvent avoir à être modifiée.

Changer l'objectif, c'est aussi changer la solution.
C'est la partie très délicate de la spécification d'un programme.

[Seabirds]

En l'occurence, tu as codé pour un processeur simple. C'était ton objectif.
Maintenant, chaque fois que tu changes ne serait-ce qu'un détail du "quelque chose", ton programme peut devenir totalement inadapté.

Aie, petite pointe de stress. J'avais dans l'idée que on pouvait progresser incrémentalement de sous-objectif en sous-objectif. Typiquement, je codais pour l'instant pour mon petit ordi, si ça marchait déjà sur un processeur c'était cool, le multi-processeur je verrais après. Autrement dit, je n'avais pas vraiment idée que le nombre de processeurs pouvait beaucoup influer sur la solution !

Je serais bien tenté de demander la recette magique pour prévoir si un sous-objectif est critique ou pas, mais j'imagine que la réponse serait quelque chose du genre "beaucoup d'expérience, de la pratique, de la veille technique, de l'intelligence et du travail".

[foetus]

Je serais bien tenté de demander la recette magique pour prévoir si un sous-objectif est critique ou pas

Si tu es gourmand , tu pense à une application comme à un mille-feuille

Plus tu modifies les couches basses, plus tu dois refaire les couches au-dessus.

Exemple

• couches hautes: suppression d'une fonctionnalité, suppression d'une entrée dans un menu
• couches intermédiaires: faire un système de droits
• couches basses: le "multi-threading", un "logger", l'internationalisation

[ternel]

J'ai plus l'impression que c'est "Toujours. Surtout si tu ne t'y attends pas."

En fait, à chaque fois que tu prends une décision dans ton code (le moindre if, par exemple), tu le fais par rapport à ton objectif.

Par exemple, si tu dois fabriquer une voiture pour aller faire tes courses, 3m³ de coffre, c'est pas mal.
Si tu rajoute "pour 300 personnes", ce n'est plus vrai.

Mais ca ne change pas que le problème du coffre, il faudra aussi choisir un moteur plus puissant, et un autre profil aérodynamique.
Et si tu ajoutes encore "pour un mois", passer à un camion est peut-être une bonne idée.

D'une manière générale, les changements de quantité sont une cause assez fréquente de grosse restructuration du projet. (tant dans la représentation de données que dans la forme des algorithmes).

[Seabirds]

Ok, donc là si ça se trouve j'ai fait un mille-feuille de 3cm³ à Paris pour alimenter les 3000 clients d'un restaurant Tokyo, et le mille-feuille fait Paris-Tokyo dans la poche arrière d'un livreur en trotinette, c'est ça ?
Cela dit, à ma décharge et pour mon orgueil, les clients du resto ont le choix du dessert, et peuvent aussi commander un éclair au chocolat géant manufacturé en Patagonie et livré en patin à glace, comme quoi ma solution est quand même évolutive.

D'une manière générale, les changements de quantité sont une cause assez fréquente de grosse restructuration du projet. (tant dans la représentation de données que dans la forme des algorithmes).

Ok, ça laisse un peu de mou quand même. Donc là j'imagine qu'on remercie l'OCP, l'encapsulation, l'abstraction etc...

Plus tu modifies les couches basses, plus tu dois refaire les couches au-dessus.

Dans mon inertie de débutant, et c'est peut-être le point positif de l'affaire, je n'ai pas vraiment eu le loisir d'accumuler les couches ^^

[ternel]

Je ne suis pas pleinement d'accord avec cette histoire de couches.

plus tu as des couches distinctes, moins les changements dans l'une d'elle implique de changements conséquents dans celles d'au dessus.

Idéalement, sauf changement de nature, une couche devrait être totalement invisible d'une autre qui ne serait pas directement basée dessus.

[Bousk]

En théorie, tant que l'interface public ne bouge pas tu ne devrais pas avoir besoin de modifier quoi que ce soit externe au code que tu touches.

[Seabirds]

Merci pour tous ces bons rappels

Question naïve sur laquelle j'aimerais avoir votre ressenti et votre expérience :

Comme je vous disais, sur une version très allégée du modèle bien en deçà des ambitions, je commence à avoir quelques résultats de mes simulations (ce qui est bienvenu pour la thèse en cours). Cela dit, je me sens déjà restreint dans les possibilités d'analyse (avec le coût calculatoire, ça va être dur d'explorer les conditions de simulation aussi facilement et rapidement que la statistique le voudrait... ). Et si j'ai bien suivi, ce n'est pas l'ordre de grandeur en moins apporté par le parallélisme sur 64 processeurs qui va faire voler le rocher.

Quand un résultat simplistique prend plus d'une semaine à sortir, et qu'on a que quelques mois pour accumuler le plus de résultats possibles, comment s'y prendre ?

• les techniques d'optimisation citées plus haut sont-elles à ma portée en si peu de temps ?
• quel gain d'efficacité peut-on espérer ? ça dépend peut-être beaucoup trop des cas d'utilisation pour pouvoir répondre aussi facilement... désolé de la question piège
• est-ce que ça vaut le coup d'investir du temps pour aller traquer les goulot d'étranglement dans les algos ?
• ou bien de toute façon tout ce que je pourrai faire à mon niveau serait totalement insuffisant et il serait préférable de foncer sur "quelques" résultats quitte à faire fondre les processeurs ?

Merci de vos réponses

[JolyLoic]

• quel gain d'efficacité peut-on espérer ? ça dépend peut-être beaucoup trop des cas d'utilisation pour pouvoir répondre aussi facilement... désolé de la question piège
• est-ce que ça vaut le coup d'investir du temps pour aller traquer les goulot d'étranglement dans les algos ?
• ou bien de toute façon tout ce que je pourrai faire à mon niveau serait totalement insuffisant et il serait préférable de foncer sur "quelques" résultats quitte à faire fondre les processeurs ?

Merci de vos réponses

Il m'est déjà arrivé en 2j de travail de passer un algo de quelques heures à quelques secondes (genre en remplaçant du O(n5) par du O(n log n)). Mais tout dépend du niveau de codage de la solution actuelle. Mais je pense que ça vaut le coup d'essayer d'optimiser un minimum la solution de base avant de partir vers de la parallèlisation. Est-ce que les algorithmes ont la bonne complexité, est-ce que les bonnes structures de données sont utilisées, est-ce qu'il serait possible de mettre en cache des données intermédiaires (attention, peut être contraire à la parallélisation, donc ne le faire que si le gain est réel)., mes algos se prêtent-ils à la vectorisation ? Où mon algo passe-t-il son temps (utiliser un profiler) ?

Et n'oublie pas qu'une manière de paralléliser consiste à lancer ton programme plusieurs fois sur plusieurs jeux de données. Ce qui a l'avantage de pouvoir lancer plusieurs versions du programme sur le même jeu de données, ce qui peut être pratique aussi.

Après il faut trouver le bon équilibre, et savoir s'arrêter au bout d'un moment si on sent que les gains ne vont plus être significatifs.

[ternel]

Dans ton cas, tu effectues plein de simulations autonome, chacune étant ainsi construite:

initialisation de données strictement locale, dans un espace de taille N
initialisation d'une matrice N² de "fonction de transition", en gros des probabilité de transfert (partiel ou non) de contenu entre deux cases de l'espace.

à chaque itération:

1. il y a d'abord évolution locale de chaque case selon une fonction déterminée (un foncteur créé plus ou moins dynamiquement pendant l'initialisation)
2. puis application de la matrice de transition.

Fonctionnellement, ta simulation totale devrait avoir une complexité temporelle de l'ordre de T * N * Durée(évolution locale) + T * N * Durée(une transition) * N
Ton facteur limitant est le plus grand entre la durée d'une évolution locale et celle de l'application des transitions d'une case précise vers toutes les autres.
Ce sont les deux grandeurs que tu devrais essayer de minimiser.
Une piste: essaie de voir si tu peux limiter les transitions à "vers quelques cases" seulement.

Par contre, comme ton besoin est sur des calculs numériques, essaye d'optimiser le temps d'exécution des parties "atomique": l'évolution locale et la transition.
Et là, il n'y a qu'une seule manière correcte de le faire: utiliser un profiller pour savoir quelle partie du code est vraiment coûteuse.