Discussion :

[mister3957]

Bonjour à tous,

Je connais le principe des threads mais ne les ayant jamais appliqués mes connaissances ne sont que théoriques.

J'ai admettons 10 unités (le 10 n'étant connu qu'à l'exécution, ça peut être 5 comme 15 ou 20) et des algorithmes permettent de travailler sur 2 unités en même temps pour les "mélanger" afin d'obtenir un résultat tendant vers un "idéal".

Actuellement les algorithmes tournent en séquentiels sur les unités :

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
 
[1 - 2]
[1 - 3]
[1 - 4]
...
[1 - 10]
 
puis
 
[2 - 1]
[2 - 3]
[2 - 4]
...
[2 - 10]
 
puis à la fin
 
[10 - 1]
[10 - 2]
[10 - 3]
...
[10 - 9]

L'ensemble est long à s'exécuter et en faisant un htop on voit qu'il n'y a qu'un processeur logique sur 8 qui est à 100%. Alors l'idée est d'exploiter les performances de la machine un peu mieux en admettant que l'on puisse exécuter les algorithmes [1 - 2], [3 - 4], [5 - 6], [7 - 8] ou [1 - 3], [2 - 4], [5 - 7], [6 - 8] etc. en même temps, mais avant d'exécuter par exemple l'algorithme sur [1 - 3] il faut attendre la fin des threads [1 - 2], [1 - 4], [1 - 5], [1 - 6], [1 - 7], [1 - 8], [2 - 1], [3 - 1], [4 - 1], [5 - 1], [6 - 1], [7 - 1], [8 - 1] car sinon ça va toucher à 1 et 3 qui sont en cours d'exécution. Je vous passe le nombre de combinaisons possibles, et encore plus celui des dépendances.

Le but est d'explorer tous les couples [X - Y] sans que jamais 2 threads travaillent sur X ou Y en même temps.

Donc je pense qu'il faut commencer générer tous les couples [X - Y] possibles, ça ne va pas être compliqué. Ensuite il faut générer les "incompatibilités d'exécution", donc que [X - Y] n'est pas exécutable en même temps que [X - Z], [Y - Z], [Z - X] et [Z - Y], et après je suis perdu pour savoir comment ça peut se traduire avec les threads, les mutex et surtout comment organiser l'ensemble pour que les "compatibles" se lancent en parallèles dont chacun va attendre la fin d'exécution des "non compatibles".

A mon avis il me faut faire une classe qui va fonctionner comme l'une de ces pieuvres que l'on voit dans Men In Black.

Première question : Est-ce que le raisonnement est bon, ou plutôt utopique ?
Deuxième question : Si ça n'est pas utopique, vous auriez une première approche technique en pseudo code ?

Merci à vous,

Bonne soirée et bon weekend,

Kin

[bacelar]

Vos problème de dépendance montre que votre algorithme n'est pas vraiment conçu pour être parallèle.
Il faut peut-être revoir l'algorithme pour qu'il soit plus parallélisable.
Vous pouvez aussi réduire les dépendances en faisant des copies des données en entrée.
De plus, il serait peut-être plus simple de ne pas résonner sur un nombre fixe de threads.
Il se peut que les dépendances entrainent un nombre plus important de threads possibles en début ou en fin de processus en fonction de l'algorithme choisi.
L'utilisation d'un découpage de l'algorithme en tâches et en utilisant un pool de thread permettrait de mieux adapter la puissance de calcul à parallélisme non constant.

[mister3957]

Vos problème de dépendance montre que votre algorithme n'est pas vraiment conçu pour être parallèle. Il faut peut-être revoir l'algorithme pour qu'il soit plus parallélisable.

Je pense que si puisque lorsqu'un algorithme travaille sur les unité 1 et 2, il est cloisonnée aux données des unités 1 et 2, donc un autre peut travailler sur 3 et 4 par exemple.

Vous pouvez aussi réduire les dépendances en faisant des copies des données en entrée.

Les copies de données sont délicates étant donné que je suis dans un univers de calculs, recherche opérationnelle etc. et la volumétrie étant importante j'aurais peur pour les performances.

De plus, il serait peut-être plus simple de ne pas résonner sur un nombre fixe de threads. Il se peut que les dépendances entrainent un nombre plus important de threads possibles en début ou en fin de processus en fonction de l'algorithme choisi.

Oui bien sûr, mais y a-t-il une limite au niveau du système ? Est-ce que gérer de nombreux threads consomme beaucoup de CPU ?

L'utilisation d'un découpage de l'algorithme en tâches et en utilisant un pool de thread permettrait de mieux adapter la puissance de calcul à parallélisme non constant.

C'est déjà pas mal découpé. En fait il n'y a pas un seul algorithmes, mais 9 algorithmes avec des tâches bien spécifiques et qui sont complémentaires entre eux. De plus, pour chaque algorithme on peut leur spécifier leur périmètre d'action en leur imposant de travailler avec tel couple d'unité.

En résumé, on peut lancer AlgoA(u1, u2), AlgoA(u3, u4), AlgoB(u5, u6), AlgoC(u7, u8) en même temps mais pas deux algos (qu'il soient le même ou différent) sur les mêmes unités en même temps, donc on ne peut pas lancer AlgoA(u1, u2) et AlgoB (u2, u3) en même temps.

Aujourd'hui le programme lance les algos les uns à la suite des autres. Chaque algorithme indique s'il a pu améliorer quelque chose permettant potentiellement aux autres algos de trouver à leur tour des améliorations. Le programme s'arrête lorsque plus aucun algo ne peut améliorer la solution. C'est de la recherche combinatoire.

J'ai pensé à une autre solution, ce serait de diviser pour mieux régner en précisant le nombre de division (donc de threads à utiliser) et de manière dégressive. Par exemple pour 10 unité et 4 threads définis, on divise le contexte en :
1 - [u1 -> u3]
2 - [u4 -> u6]
3 - [u7 -> u8]
4 - [u9 -> u10]

Une fois tous les threads exécutés on découpe autrement jusqu'à ce que tous les threads aient travaillés sur les différentes découpes.

Puis on passe à des découpages à 2 threads :
1 - [u1 -> u5]
2 - [u6 -> u10]

Puis 1 thread
1 - [u1 -> u10]

Aujourd'hui ça n'utilise qu'un thread [u1 -> u10] mais avec ce schéma là peut-être que le "diviser pour mieux gérer" aura abouti à une solution déjà bien dégrossit en beaucoup moins de temps que ça ne le mettrait avec un seul thread depuis le début.

Ça fait deux pistes de recherche mais je pense que le mieux serait de construire un arbre des dépendances avec une petite machinerie permettant de dire "toi vas-y, go go go", "toi 2 minutes, on attend lui, lui et lui qu'ils aient terminés" etc. avec un paramètre limitant le nombre de thread à exécuter en même temps s'il y a des restrictions au niveau du système.

Il ne faut pas non plus que cette machinerie pompe trop de performance sinon ça reviendrait à déshabiller Pierre pour habiller Paul.

Je pense qu'il y a moyen de s'amuser

[bacelar]

Les copies de données sont délicates étant donné que je suis dans un univers de calculs, recherche opérationnelle etc. et la volumétrie étant importante j'aurais peur pour les performances.

C'est une histoire de compromis (tradeoff), il faut les évaluer et pas faire des assertions à la serpe.

Oui bien sûr, mais y a-t-il une limite au niveau du système ? Est-ce que gérer de nombreux threads consomme beaucoup de CPU ?

En général, oui.
Il n'y a jamais de OUI et de NON absolu => on en revient toujours à un calcul de compromis.

C'est déjà pas mal découpé

Découper arbitrairement, cela n'a pas de sens. Il faut découper pour réduire les couplages et donc avoir POTENTIELLEMENT, un meilleur parallélisme.

Il vous faut aussi un algorithme, même pour gérer votre schedulling des thread.
Ce que vous donnez comme indice montre un problème de stabilité, rien n'empêche l'algorithme de travailler pour toujours.(problème de stabilité numérique,etc...).
Votre méta algorithme n'est clairement pas fait pour être parallélisable.

Un thread peut exécuter un "Algo" à un moment et un autre plus tard, etc...

Comme vous avez un nombre limité de "u", vous pouvez faire une gestion "automatique" des dépendances en utilisant des mutex et autres mécanismes de synchronisation.

Le pool de thread permet de réduire "naturellement" le nombre de thread.

Il n'y a pas de solution miracle, vous devez étudier la répartition en temps de calcul des algorithmes en fonction des types d'unité pour chercher à optimiser la répartition du temps de calcul.

[white_tentacle]

J’aborderai les choses d’une manière différente.

Si j’ai bien compris, les traitements n’ont pas besoin de s’exécuter dans un ordre particulier. Donc, ce que je ferai en première étape, pour n éléments :

- générer la liste des couples à traiter (en simple thread, le nombre est petit de ce que j’ai compris)
- créer n/2 threads, qui vont ensuite « piocher » dans la liste des couples à traiter un couple « disponible ».
- un couple est « disponible » si chacun de ses deux membres est « disponible ».
- quand un couple est choisi par un thread, il marque chacun de ses deux membres comme n’étant plus disponibles (en utilisant, par exemple, un sémaphore)
- si un thread ne trouve pas de couple disponible, il se met en attente (en utilisant, par exemple, une condition variable)
- lorsqu’un thread finit son traitement sur un couple, il rend « disponible » chacun de ses éléments, réveille les autres threads et regarde s’il peut trouver un nouveau couple « disponible » à traiter parmi la liste, etc...
- et ainsi de suite jusqu’à ce que la liste des couples à traiter soit vide.

Cela devrait permettre de bénéficier du parallélisme sans vraiment se préoccuper de la charge répartie à chaque thread : ils prennent en fonction de ce qui est dispo.

Néanmoins, il y a quelque chose qui me chiffonne dans le problème initial :
- le traitement est supposé toucher aux données initiales (sinon, on peut très bien y accéder depuis plusieurs threads)
- l’ordre d’exécution ne serait pas important

Ces deux propriétés sont généralement incompatibles entre elles...

[mister3957]

J’aborderai les choses d’une manière différente.

Si j’ai bien compris, les traitements n’ont pas besoin de s’exécuter dans un ordre particulier. Donc, ce que je ferai en première étape, pour n éléments :

- générer la liste des couples à traiter (en simple thread, le nombre est petit de ce que j’ai compris)
- créer n/2 threads, qui vont ensuite « piocher » dans la liste des couples à traiter un couple « disponible ».
- un couple est « disponible » si chacun de ses deux membres est « disponible ».
- quand un couple est choisi par un thread, il marque chacun de ses deux membres comme n’étant plus disponibles (en utilisant, par exemple, un sémaphore)
- si un thread ne trouve pas de couple disponible, il se met en attente (en utilisant, par exemple, une condition variable)
- lorsqu’un thread finit son traitement sur un couple, il rend « disponible » chacun de ses éléments, réveille les autres threads et regarde s’il peut trouver un nouveau couple « disponible » à traiter parmi la liste, etc...
- et ainsi de suite jusqu’à ce que la liste des couples à traiter soit vide.

Cela devrait permettre de bénéficier du parallélisme sans vraiment se préoccuper de la charge répartie à chaque thread : ils prennent en fonction de ce qui est dispo.

Néanmoins, il y a quelque chose qui me chiffonne dans le problème initial :
- le traitement est supposé toucher aux données initiales (sinon, on peut très bien y accéder depuis plusieurs threads)
- l’ordre d’exécution ne serait pas important

Ces deux propriétés sont généralement incompatibles entre elles...

Oui je le vois comme ça aussi, mais n'ayant pas beaucoup d'expérience dans ce type de travail je préférais avoir confirmation que l'idée n'était pas mauvaise avant de passer du temps dessus.

Pour les aspects qui te chiffonnent, effectivement l'ordre d'exécution a une importance sur la rapidité avec laquelle on obtiendra les résultats mais ça je le gérerai lorsque j'implémenterai des stratégies évolutives (et / ou génétiques), je dois encore bien saisir le concept avant de plonger les mains dedans.

D'après ce que j'ai compris des stratégies évolutives, il s'agit de collecter des informations durant les opérations afin qu'elles puissent être réutilisées par la suite et éviter de tester des combinaisons (et donc limiter les traitements) dont on sait à l'avance qu'elle ne mèneront à rien. Et comme chaque algorithme a son périmètres définit, la collecte comme la lecture de ces informations ne devraient pas faire l'objet de conflits entre différents threads.

Je vais tenter quelque chose ce weekend, on verra bien ce que ça donnera.

Merci,

A bientôt