Discussion :

[dharkan]

Bonjour,

j'ai besoin d'un conseil en ce qui concerne le choix du multi threadin ou de rester sur un seul thread.

J'ai un bête programme qui tourne en console qui se compose de trois boucle imbriquée variant de 0 à 65 chacune.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for i=0 to 65
    ...
    for j = 0 to 65
        ...
        for k = 0 to 65
            ....
        next
    next
next

la question que je me pose est la suivante :

Est-il préférable de rester sur le thread principal ou est-ce mieux de faire 4 procédures dans lesquelles les boucles de premier niveau sont initalisée à : 0, 1, 2 et 3 tout en incrémentant de 4
et en lancant chacune des procédures dans un thread propre à ces procédure ?

procédure 1 :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for i=0 to 65
    ...
    for j = 0 to 65
        ...
        for k = 0 to 65
            ....
        next
    next
next

procédure 2 :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for i=1 to 65 step 4
    ...
    for j = 0 to 65
        ...
        for k = 0 to 65
            ....
        next
    next
next

procédure 3 :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for i=2 to 65 step 4
    ...
    for j = 0 to 65
        ...
        for k = 0 to 65
            ....
        next
    next
next

procédure 4 :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for i=3 to 65 step 4
    ...
    for j = 0 to 65
        ...
        for k = 0 to 65
            ....
        next
    next
next

D'avance je vous remercie.

[dinobogan]

Pour le multi-thread, il y a une multitude d'approches différentes. C'est selon le développeur, selon le problème rencontré, selon les performances attendues, selon les ressources machines....
Tu ne dis rien sur le traitement effectué, mais ton approche de découpage n'est vraiment pas pratique car le code est spécifique pour chaque thread. Quand on commence à multi-threader, c'est parce qu'on a de véritables arguments sur l'apport de performances (en temps, en CPU, en RAM, en ce que tu veux). Dans le cas général, on ne sait pas combien de thread seront utiles pour faire le travail. C'est pratique de modifier facilement le nombre de threads durant la phase de bench.
On pourrais imaginer une solution beaucoup plus souple avec une zone mutex pour incrémenter la première variable "i". Chaque thread prend une valeur de "i" et l'incrémente dans la zone du mutex puis effectue son travail avec les boucles "j" et "k" de 0 à 65. L'avantage de cette technique est que tu peux utiliser pleins de threads, peu importe le nombre. Oui, c'est 65 thread max mais dans la grande majorité des cas, on n'utilise pas autant de threads.

[DonQuiche]

Bonjour.

Paralléliser tend à significativement accroître la complexité du code, sa compréhensibilité et sa maintenabilité. Notamment parce que cela crée des problèmes insidieux et difficiles à comprendre et détecter. Pour cette raison on n'y a recours que lorsque c'est nécessaire à des fins de performance ou de réactivité (ne pas geler l'UI par ex).


Quant à la bonne façon de paralléliser, mieux vaut en général répartir dynamiquement la charge de travail. D'abord parce que tous les coeurs ne travailleront pas à la même vitesse (disponibilité des données dans le cache voisin, hyperthreading, etc) et ensuite parce que le système est libre d'allouer les ressources de chaque coeur à d'autres usages que ta seule application. Tu peux par exemple utiliser le motif producteur-consommateur ou ses variantes, ou une file d'attente partagée où l'on placera les travaux en attente.

Si toutefois tu insistes pour une répartition fixe à l'avance, tu ne devrais avoir qu'une seule procédure, le pas étant passé en paramètre. Si ton langage interdit cela, utilise une boucle "tant que" et incrémente manuellement ta variable.

[dharkan]

Pour le multi-thread, il y a une multitude d'approches différentes. C'est selon le développeur, selon le problème rencontré, selon les performances attendues, selon les ressources machines....
Tu ne dis rien sur le traitement effectué, mais ton approche de découpage n'est vraiment pas pratique car le code est spécifique pour chaque thread. Quand on commence à multi-threader, c'est parce qu'on a de véritables arguments sur l'apport de performances (en temps, en CPU, en RAM, en ce que tu veux). Dans le cas général, on ne sait pas combien de thread seront utiles pour faire le travail. C'est pratique de modifier facilement le nombre de threads durant la phase de bench.
On pourrais imaginer une solution beaucoup plus souple avec une zone mutex pour incrémenter la première variable "i". Chaque thread prend une valeur de "i" et l'incrémente dans la zone du mutex puis effectue son travail avec les boucles "j" et "k" de 0 à 65. L'avantage de cette technique est que tu peux utiliser pleins de threads, peu importe le nombre. Oui, c'est 65 thread max mais dans la grande majorité des cas, on n'utilise pas autant de threads.

En ce qui concerne le traitement effectué c'est le parcourt d'un tableau de caractères afin de reconstituer toutes chaine possible de 3 caractères et je vais jusque 15 caractères (15 boucles imbriquées ) => j'oublie la récursivité par soucis de performance.
Je ne sait pas ce que tu en penses ?


PS : Je pense aussi borner les boucles afin d'exécuter des "morceaux différents de boucle" sur un ensemble de machine que j'ai à ma disposition afin "d'accroitre" la puissance de calcul en plus du multhithreading.

[dharkan]

Bonjour.

Paralléliser tend à significativement accroître la complexité du code, sa compréhensibilité et sa maintenabilité. Notamment parce que cela crée des problèmes insidieux et difficiles à comprendre et détecter. Pour cette raison on n'y a recours que lorsque c'est nécessaire à des fins de performance ou de réactivité (ne pas geler l'UI par ex).


Quant à la bonne façon de paralléliser, mieux vaut en général répartir dynamiquement la charge de travail. D'abord parce que tous les coeurs ne travailleront pas à la même vitesse (disponibilité des données dans le cache voisin, hyperthreading, etc) et ensuite parce que le système est libre d'allouer les ressources de chaque coeur à d'autres usages que ta seule application. Tu peux par exemple utiliser le motif producteur-consommateur ou ses variantes, ou une file d'attente partagée où l'on placera les travaux en attente.

Si toutefois tu insistes pour une répartition fixe à l'avance, tu ne devrais avoir qu'une seule procédure, le pas étant passé en paramètre. Si ton langage interdit cela, utilise une boucle "tant que" et incrémente manuellement ta variable.

je ne pense pas saisir ce que tu veux m'expliquer. Mais les thread s'ils ne sont pas synchrone je m'en "fou". L'UI n'est pas geler car c'est une application console .NET dans laquelle j'instancie le thread de cette manière :

Code :

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

1
2
3
 
Dim thread4P As System.Threading.Thread = New System.Threading.Thread(AddressOf Test4Impair)
Dim thread4I As System.Threading.Thread = New System.Threading.Thread(AddressOf Test4Pair)

pour ensuite appeler la méthode start sur mes thread.

[dinobogan]

En ce qui concerne le traitement effectué c'est le parcourt d'un tableau de caractères afin de reconstituer toutes chaine possible de 3 caractères et je vais jusque 15 caractères (15 boucles imbriquées ) => j'oublie la récursivité par soucis de performance.
Je ne sait pas ce que tu en penses ?

Tu ne pourras jamais stocker tous les résultats pour toutes les combinaisons de 15 caractères choisis parmi 65 choix possible chacun. Cela dépasse le stockage global détenu par n'importe quelle entreprise sur la planète Terre.
Lorsqu'un thread a généré une nouvelle combinaison, il en fait quoi ?

[picodev]

En ce qui concerne le traitement effectué c'est le parcourt d'un tableau de caractères afin de reconstituer toutes chaine possible de 3 caractères et je vais jusque 15 caractères (15 boucles imbriquées ) => j'oublie la récursivité par soucis de performance.
Je ne sait pas ce que tu en penses ?


PS : Je pense aussi borner les boucles afin d'exécuter des "morceaux différents de boucle" sur un ensemble de machine que j'ai à ma disposition afin "d'accroitre" la puissance de calcul en plus du multhithreading.

Je pense que la terre aura été soufflée par le soleil transformé en géante rouge avant que ton programme n'ai fait 2% du boulot.
Ce que tu veux faire n'est pas réalisable ni en terme d'espace comme le précise Dinobang, ni même en terme de temps.

Mais bon … tu peux avoir du bol si tu tapes au hasard dans l'espace de recherche. Tu peux accéder à un tuple quelconque avec des algo rank/unrank. Tu peux même passer au suivant avec des algo loopless. Mais bon, le multithreading, l'utilisation d'opcodes SIMD ne te feront pas gagner un temps suffisant pour espérer gagner une attaque brute force surtout si tu utilises la technologie .Net sans vouloir lancer de troll.

C'est ce qu'on appelle une explosion combinatoire.

[dharkan]

En ce qui concerne le stockage pas de soucis (car 65^15 solutions tu m'étonnes que c'est instockable ) je test le contenu de ma variable (en bypassant si il y a 3 fois la même lettre en suivant, après je cherche encore des optimisations) directement avant d'ouvrir la db si la connexion s'ouvre c'est le bon mdp si l'exception est levée je passe au loop suivant (je précise que je n'agis pas illégalement mais comme Picodev à compris, je tiens à le préciser).

J'ai essayé de programmer (c'est un grand mot lol) un algo me générant le nombre combinaisons arrangées en utilisant cette expression :n=65 p=3: (65*64*63)/(3*2*1)
pour déterminer le nombre de possibilités de chaine de trois caractère mais j'ai vite abandonné lors de la "construction" de contenu de ma variable du fait de vouloir "contrôler" l'aléatoire .
Du coup, je me suis arrêter à la formule n^p.

Pour le temps d’exécution j'ai lu que si je n'ai pas de bol le programme tournerai encore après la fin de l'univers (plus de 100 milliard d'années quand même )
Déjà entre la construction des différentes possibilités d'une chaîne de 3 caractères (en deux thread séparé pair et impair) et les possibilité de 4 se font sentir plus qu'exponentiellement. C'est à dire pour les chaines de trois caractère en 1h j'ai tout testé par contre pour celles de 4, le programme est parti pour tourner tout le week end je pense (la première boucle ayant bouclé 2 fois seulement pour chacun des thread à la fin de la journée ).

[DonQuiche]

j'oublie la récursivité par soucis de performance.

Le gain n'est pas significatif, tu pourris ton code pour rien.

En fait il se peut même que tu le ralentisses : plus ton code est gros moins il tient dans les différents niveaux de cache. Or le chargement de données de la mémoire vers les caches ou d'un niveau de cache à l'autre tend à dominer les temps de calculs.

je ne pense pas saisir ce que tu veux m'expliquer.

Mettons que tu stipules que quatre threads examineront chacun 16 combinaisons. Maintenant que se passe t-il si l'un des processeurs est parfois occupé ou tourne plus lentement que les autres ? Les trois premiers processeurs auront terminé et c'est le quatrième qui dominera le temps de calcul.

La solution est de répartir dynamiquement la charge. Par exemple via le motif "producteur(s)-consommateur(s)" : crée une ConcurrentQueue statique et places-y des objets spécifiant les lots à traiter (par exemple "toutes les combinaisons commençant par A"). Puis crée N-1 threads qui piocheront dans cette file jusqu'à ce qu'elle soit vide et fais la même chose sur le thread principal. Enfin il te faut un mécanisme pour attendre que tous les threads aient terminé, tu peux utiliser pour ça Barrier ou WaitHandle.WaitAll.

Ou bien utilise directement Parallel.For ou Foreach, qui feront quelque chose d'à peu près équivalent à tout ça. Petit bonus ou bémol : il ajustera dynamiquement le nombre de threads mais pour que ce soit optimal il vaut mieux des lots de quelques millisecondes.