[std::thread] Algorithme plus lent que en simple thread

**Trademark** · 11/04/2013, 19h42

Bonjour à tous,

J'ai multithreadé un code, et j'ai des résultats horribles, je ne suis pas expert mais je suspecte les threads qui se vident le cache entre eux. Voici l'algo :

Code :

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

1
2
3
4
5
6
7
8
9
for (int y=y_begin; y<y_end; ++y)
{  
      for (unsigned short x=0; x<w; x++)
      {
        int i=(h-y-1)*w+x;
        // Traitements (peuvent être plus ou moins long
        data[i] = data[i] + /* code */;
       }
}

Et j'appelle les threads de cette façon :

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
    std::vector<Vector> data;
    data.resize(w*h); // Taille par exemple w = 256, h = 196
    int yb = 0;
    int ye = 0;
    std::vector<std::thread> threads(thread-1);
    for(int i=0; i < thread-1; ++i)
    {
      ye += h/thread;
      threads[i] = std::thread(ThreadFunction(), std::ref(data), yb, ye);
      yb = ye;
    }
    ThreadFunction()(data, yb, h);
 
    for(size_t i=0; i < threads.size(); ++i)
    {
      threads[i].join();
    }

En le lançant avec time j'ai ces résultats :

real 0m10.309s
user 0m13.633s
sys 0m21.829s

(coupé avant la fin)

Alors que en single thread j'ai quasi 0 en sys. Je suppose que c'est à cause de nombreux changements de contexte ?

Et finalement pour donner un ordre de grandeur, sur mon processeur 4 coeurs, je met 20 secondes avec un thread et 3 minutes avec 4…

Quelles sont les causes possibles ?

Merci d'avance !

**imperio** · 12/04/2013, 08h22

Créer un thread est plutôt lourd mais pas à ce point ! T'as pas des mutex qui traîneraient quelque part ?

**Emmanuel Deloget** · 12/04/2013, 08h38

Combien est-ce qu'il y a de threads ?

**Trademark** · 12/04/2013, 08h39

Salut,

Non créer les threads ce n'est pas ça qui prend du temps. Et je n'ai pas de mutex car ils accèdent à des endroits différents de la mémoire partagée.

J'ai fait des tests avec 1, 2 et 4 threads, dès qu'il y a plus d'un thread c'est la folie.

Voici quelques résultats :

1 thread :

real 4m11.922s
user 4m11.052s
sys 0m0.064s

2 threads :

real 4m30.792s
user 6m27.484s
sys 1m54.035s

4 threads :

real 6m56.838s
user 9m24.187s
sys 13m21.746s

**JolyLoic** · 12/04/2013, 09h10

Vu que tout ce que tu fais à data, c'est de lui ajouter des valeurs, est-ce que tu as essayé de travailler dans un espace mémoire local, puis à la fin de ton travail, ajouter cet espace mémoire à data, de façon à minimiser les accès à cet emplacement mémoire ?

**Emmanuel Deloget** · 12/04/2013, 09h43

(En supposant, bien sûr, que tu utilises Linux)

Est-ce que tu peux essayer d'utiliser perf ? J'aimerais bien savoir ou ce temps est perdu dans le kernel (je suppose que c'est le scheduler, et probablement la gestion de migration des threads).

Autre chose, la version de Linux que tu utilises - uname -a. Une info sur ton hardware (nombre de coeurs...) serait aussi intéressante.

Je doute que ce soit véritablement un problème de cache (même s'il est possible que la gestion du cache soit un peu plus lente, du fait de l'organisation de ton code ; il est souvent préférable de faire le travail sur de la mémoire locale pour éviter ce problème). Je penche plus pour le bug de migration de thread qui a été corrigé récemment (dans le kernel 3.9 ?), et qui fait que les threads passent leur temps à être migrés d'un coeur à l'autre sans raison. Est-ce que tu pourrais tester avec d'autres versions de Linux ?

**Trademark** · 12/04/2013, 10h18

@JolyLoic : je viens d'essayer et ça ne change strictement rien aux temps (même un peu plus lent du aux copies…).

@Emmanuel :

uname -a : Linux trademark-machina 3.5.0-27-generic #46-Ubuntu SMP Mon Mar 25 19:58:17 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux

J'ai un AMD Phenom II à quatre coeurs.

En ce qui concerne perf, voici les résultats avec 2 threads :

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
perf stat ./a.out 
Performance counter stats for './a.out':
 
      97295.433950 task-clock                #    1.657 CPUs utilized          
         3,537,466 context-switches          #    0.036 M/sec                  
             1,380 CPU-migrations            #    0.014 K/sec                  
               698 page-faults               #    0.007 K/sec                  
   304,803,885,309 cycles                    #    3.133 GHz                     [50.01%]
    20,705,360,598 stalled-cycles-frontend   #    6.79% frontend cycles idle    [50.06%]
   162,879,758,647 stalled-cycles-backend    #   53.44% backend  cycles idle    [50.07%]
   208,827,475,073 instructions              #    0.69  insns per cycle        
                                             #    0.78  stalled cycles per insn [50.00%]
    32,542,377,972 branches                  #  334.470 M/sec                   [49.95%]
     1,551,477,017 branch-misses             #    4.77% of all branches         [49.94%]
 
      58.700255741 seconds time elapsed

Et avec 4 threads :

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
 perf stat ./a.out 
 Performance counter stats for './a.out':
 
     251699.537773 task-clock                #    2.936 CPUs utilized          
        13,062,016 context-switches          #    0.052 M/sec                  
            19,055 CPU-migrations            #    0.076 K/sec                  
               711 page-faults               #    0.003 K/sec                  
   780,541,320,480 cycles                    #    3.101 GHz                     [50.05%]
    43,865,126,625 stalled-cycles-frontend   #    5.62% frontend cycles idle    [49.83%]
   345,774,964,937 stalled-cycles-backend    #   44.30% backend  cycles idle    [49.98%]
   577,614,476,815 instructions              #    0.74  insns per cycle        
                                             #    0.60  stalled cycles per insn [49.96%]
   118,773,519,774 branches                  #  471.886 M/sec                   [50.18%]
     2,561,552,532 branch-misses             #    2.16% of all branches         [50.02%]
 
      85.730728523 seconds time elapsed

Je n'ai pas d'autre machine à disposition malheureusement. Je vais quand même demander à d'autres personnes de tester sur leur machine.

Merci pour l'aide ;-)

**Emmanuel Deloget** · 12/04/2013, 12h53

Envoyé par Trademark

@JolyLoic : je viens d'essayer et ça ne change strictement rien aux temps (même un peu plus lent du au copie…).

@Emmanuel :

uname -a : Linux trademark-machina 3.5.0-27-generic #46-Ubuntu SMP Mon Mar 25 19:58:17 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux

J'ai un AMD Phenom II à quatre coeurs.

En ce qui concerne perf, voici les résultats avec 2 threads :

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
perf stat ./a.out 
Performance counter stats for './a.out':
 
      97295.433950 task-clock                #    1.657 CPUs utilized          
         3,537,466 context-switches          #    0.036 M/sec                  
             1,380 CPU-migrations            #    0.014 K/sec                  
               698 page-faults               #    0.007 K/sec                  
   304,803,885,309 cycles                    #    3.133 GHz                     [50.01%]
    20,705,360,598 stalled-cycles-frontend   #    6.79% frontend cycles idle    [50.06%]
   162,879,758,647 stalled-cycles-backend    #   53.44% backend  cycles idle    [50.07%]
   208,827,475,073 instructions              #    0.69  insns per cycle        
                                             #    0.78  stalled cycles per insn [50.00%]
    32,542,377,972 branches                  #  334.470 M/sec                   [49.95%]
     1,551,477,017 branch-misses             #    4.77% of all branches         [49.94%]
 
      58.700255741 seconds time elapsed

Et avec 4 threads :

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
 perf stat ./a.out 
 Performance counter stats for './a.out':
 
     251699.537773 task-clock                #    2.936 CPUs utilized          
        13,062,016 context-switches          #    0.052 M/sec                  
            19,055 CPU-migrations            #    0.076 K/sec                  
               711 page-faults               #    0.003 K/sec                  
   780,541,320,480 cycles                    #    3.101 GHz                     [50.05%]
    43,865,126,625 stalled-cycles-frontend   #    5.62% frontend cycles idle    [49.83%]
   345,774,964,937 stalled-cycles-backend    #   44.30% backend  cycles idle    [49.98%]
   577,614,476,815 instructions              #    0.74  insns per cycle        
                                             #    0.60  stalled cycles per insn [49.96%]
   118,773,519,774 branches                  #  471.886 M/sec                   [50.18%]
     2,561,552,532 branch-misses             #    2.16% of all branches         [50.02%]
 
      85.730728523 seconds time elapsed

Je n'ai pas d'autre machine à disposition malheureusement. Je vais quand même demander à d'autres personnes de tester sur leur machine.

Merci pour l'aide ;-)

Je suis d'accord pour tester (si c'est possible ; et je préfère recompiler le code source plutôt que de récupérer un exécutable. T'inquiète, le code source sera effacé après le test).

Le nombre de migration CPU me semble élevé, mais il n'est peut-être pas à l'ouest pour un programme qui tourne plusieurs minutes. Je trouve quand même étrange qu'en passant de 2 à 4 threads, on multiplie par 4 le nombre de migrations.

Le nombre de page fault est relativement faible, et la prédiction de branche est correcte (mauvaises prédictions <5%). Pas de soucis de ce coté.

Est-ce que tu as essayé de changer le nice, voire la priorité de ton process ?

Autre chose :

* perf te permet aussi de voir les cache miss (perf stat -e cache-misses ./ton_programme)
* perf top peut aussi être utile, histoire de voir où le temps est perdu : ./ton_programme >& /dev/null & ; sudo perf top -p $(pidof ton_programme)

**Trademark** · 12/04/2013, 15h56

Merci pour ta réponse, je t'envoie le code source par MP, ce n'est qu'un projet d'école mais ça évitera certaines tentations

Pour ce qui est des caches misses :

Code :

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

1
2
3
4
5
 Performance counter stats for './a.out':
 
       782,766,334 cache-misses                                                
 
      88.670537893 seconds time elapsed

Ça me semble beaucoup ?

En ce qui concerne top, 40% du temps il y a __ticket_spin_lock. Je ne sais pas pourquoi il lance le lock.

Avec sudo nice -n-19 ./a.out, pas d'amélioration notable… (toujours 86s. avec 4 threads).

**Emmanuel Deloget** · 12/04/2013, 17h43

J'ai testé ton code en -O3 (-O2 me donne des résultats très similaires)

* le système:

Code :

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

1
2
 
Linux my-machine 3.2.0-4-amd64 #1 SMP Debian 3.2.39-2 x86_64 GNU/Linux

Pour info, c'est un core-i7 (quad core hyperthreadé) avec 8Go de RAM.

* 1 thread

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
 Performance counter stats for './csg':
 
      35033,677640 task-clock                #    0,997 CPUs utilized          
             2 978 context-switches          #    0,000 M/sec                  
                 0 CPU-migrations            #    0,000 M/sec                  
               675 page-faults               #    0,000 M/sec                  
   118 912 877 071 cycles                    #    3,394 GHz                     [83,32%]
    64 411 691 242 stalled-cycles-frontend   #   54,17% frontend cycles idle    [83,33%]
    29 371 854 910 stalled-cycles-backend    #   24,70% backend  cycles idle    [66,67%]
   141 695 986 447 instructions              #    1,19  insns per cycle        
                                             #    0,45  stalled cycles per insn [83,33%]
    18 292 690 270 branches                  #  522,146 M/sec                   [83,34%]
       467 151 048 branch-misses             #    2,55% of all branches         [83,35%]
 
      35,128999844 seconds time elapsed

* 2 thread (plus performant)

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
 Performance counter stats for './csg':
 
      52407,277162 task-clock                #    1,963 CPUs utilized          
            16 327 context-switches          #    0,000 M/sec                  
                59 CPU-migrations            #    0,000 M/sec                  
               685 page-faults               #    0,000 M/sec                  
   175 069 738 885 cycles                    #    3,341 GHz                     [83,35%]
   104 644 496 359 stalled-cycles-frontend   #   59,77% frontend cycles idle    [83,31%]
    60 825 150 572 stalled-cycles-backend    #   34,74% backend  cycles idle    [66,60%]
   166 057 578 995 instructions              #    0,95  insns per cycle        
                                             #    0,63  stalled cycles per insn [83,36%]
    22 504 782 550 branches                  #  429,421 M/sec                   [83,31%]
       546 393 130 branch-misses             #    2,43% of all branches         [83,43%]
 
      26,697580749 seconds time elapsed

* 4 threads

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
 Performance counter stats for './csg':
 
     137307,186213 task-clock                #    2,957 CPUs utilized          
         8 919 639 context-switches          #    0,065 M/sec                  
             1 220 CPU-migrations            #    0,000 M/sec                  
               698 page-faults               #    0,000 M/sec                  
   399 417 895 840 cycles                    #    2,909 GHz                     [83,32%]
   264 364 419 360 stalled-cycles-frontend   #   66,19% frontend cycles idle    [83,33%]
   186 454 188 882 stalled-cycles-backend    #   46,68% backend  cycles idle    [66,65%]
   251 081 099 303 instructions              #    0,63  insns per cycle        
                                             #    1,05  stalled cycles per insn [83,21%]
    45 984 525 618 branches                  #  334,903 M/sec                   [83,38%]
       832 670 729 branch-misses             #    1,81% of all branches         [83,31%]
 
      46,439413762 seconds time elapsed

Mais d'où viennent ces context switch ? Un petit strace...

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAKE_PRIVATE, 1) = 0
futex(0x7f2f78ca7b50, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)

Oops... des appels à futex(2) à n'en plus finir. Cet appel système est utilisé pour implémenter des mutex. A chaque fois qu'on fait un appel système, on quitte le contexte userspace pour entrer dans le contexte kernel - et hop, un context switch. Le kernel peut alors donner la main à un autre thread - et hop, un autre context switch.

Il y a un lock quelque part. Et un gros, puisqu'il prends pas mal de temps CPU. Un profiler quelconque (j'ai utilisé gprof) devrait nous en dire plus.

Et bingo. CSG::Random().

Tu y passes 10% du temps d'exécution (15 secondes pour 7 millions d'appels ; c'est beaucoup). Cette fonction ne fait qu'appeler rand() ; et rand() est plus que probablement protégée par un mutex (générateur congruentiel linéaire dont l'état est stocké dans une globale - il faut bien protéger la globale, non ?).

Il faudrait peut-être voir à utiliser un algorithme plus adapté à un environnement multithread. Histoire de voir, j'ai remplacé par un return 0.4583; (valeur garantie random). Le résultat parle de lui-même :

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
 Performance counter stats for './csg':
 
      35660,131729 task-clock                #    3,883 CPUs utilized          
             3 107 context-switches          #    0,000 M/sec                  
                43 CPU-migrations            #    0,000 M/sec                  
               687 page-faults               #    0,000 M/sec                  
   113 773 609 484 cycles                    #    3,190 GHz                     [83,32%]
    67 977 601 458 stalled-cycles-frontend   #   59,75% frontend cycles idle    [83,33%]
    34 423 384 432 stalled-cycles-backend    #   30,26% backend  cycles idle    [66,67%]
   128 062 527 826 instructions              #    1,13  insns per cycle        
                                             #    0,53  stalled cycles per insn [83,34%]
    15 156 295 020 branches                  #  425,021 M/sec                   [83,35%]
       348 775 141 branch-misses             #    2,30% of all branches         [83,34%]
 
       9,182770308 seconds time elapsed

Woops. Presque plus de context switch ; presque plus de migration de tâche, et un temps d'exécution grosso-modo équivalent à 1/4 du temps d'exécution originel. Avec deux threads, j'arrivent bien à environ 18s (en fait, je varie entre 7s-9s, 15s-20s et 30s-40s selon le nombre de thread. Avec 8 threads, je suis à 6-7 secondes, ce qui tendrait à montrer qu'il y a un autre accès sérialisé quelque part).

Reste à savoir comment remplacer l'appel à rand() - là, je te laisse la main

**Iradrille** · 12/04/2013, 17h59

Envoyé par Trademark

Code :

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

1
2
3
 
   208,827,475,073 instructions              #    0.69  insns per cycle (2 threads)
   577,614,476,815 instructions              #    0.74  insns per cycle (4 threads)

Étonnant le nombre d'instructions qui triple avec 4 threads.

**Emmanuel Deloget** · 12/04/2013, 18h08

Envoyé par Iradrille

Étonnant le nombre d'instructions qui triple avec 4 threads.

C'était du au temps passé dans le lock de rand(). Une fois rand() supprimé, on redescend grosso-modo au même nombre d'instructions que pour 1 seul thread (il y a quand même des switch de context et des tas de truc en plus, donc on est toujours au dessus ; mais c'est plus cohérent).

**Trademark** · 12/04/2013, 19h28

Punaise, c'est génial ça. Je n'avais jamais utilisé de profiler avant mais vu l'utilisation que tu en fais, ça semble génial. Et hop, un truc à rajouter à la pile des choses à apprendre ;-)

Bon ça me fera une bonne excuse pour essayer la lib c++11 random !

Merci beaucoup pour l'aide

EDIT : <random> me permet d'utiliser un générateur local et par conséquent les temps d'exécution sont finalement bien divisé par ~3.5. Super !

**Flob90** · 12/04/2013, 22h26

Tu es certain qu'utiliser des générateurs locaux (y compris de même type et intialisés de la même façon) te garantie d'avoir une répartition correct sur l'ensemble ? Dit autrement qu'utiliser n générateur locaux est équivalent à un seul générateur ? Personnelement, j'en doute très fortement, ca doit énormément dépendre des algorithmes utilisés et de la facon dont ils sont initialisés.

Typiquement, deux génrateurs avec le même algo et la même initialisation va probablement conduire à deux générateurs fortement corrélé. Ensuite deux générateurs avec le même algo et deux initialisations différentes pourrait probablement conduire à deux générateurs plus ou moins corrélé. Et finalement deux algo (fondamentalement différents) a, AMA, peu de risque de produire deux générateurs corrélé.

**Trademark** · 12/04/2013, 22h32

Tu as a moitié raison. J'utilise random_device http://en.cppreference.com/w/cpp/num.../random_device pour l'initialisation. Par conséquent ça devrait me donner des nombres assez différents. Par contre, vu que la fonction est appelée à des intervalles très proches, ça reste à prouver. Une technique pourrait être de lancer les threads à intervalle régulier (ainsi l'entropie du système changera vu que la charge ne sera pas la même — plus ou moins de threads en cours d'exécution).

Mais dans mon cas, ça ne biaise pas la validité de l'algorithme d'avoir des séquences aléatoires corrélées. Donc tout va bien

Merci de ta remarque, j'avoue que je n'y avais pas pensé !

**Matthieu Brucher** · 15/04/2013, 11h50

Envoyé par Trademark

Punaise, c'est génial ça. Je n'avais jamais utilisé de profiler avant mais vu l'utilisation que tu en fais, ça semble génial. Et hop, un truc à rajouter à la pile des choses à apprendre ;-)

Bon ça me fera une bonne excuse pour essayer la lib c++11 random !

Merci beaucoup pour l'aide

EDIT : <random> me permet d'utiliser un générateur local et par conséquent les temps d'exécution sont finalement bien divisé par ~3.5. Super !

Pour de la generation de nombre aleatoire en parallele, utilise un generateur parallel comme Random123. C'est la seule solution pour ne pas avoir un bottleneck sur ta generation aleatoire. Ca devient non deterministe, mais c'est normal.
Utiliser la nouvelle bibliotheque random du c++ ne resoudra pas entierement le probleme : l'appel devra etre protege par un mutex si tu ne veux pas que ca parte en vrille.

**Matthieu Brucher** · 15/04/2013, 11h51

Envoyé par Trademark

Tu as a moitié raison. J'utilise random_device http://en.cppreference.com/w/cpp/num.../random_device pour l'initialisation. Par conséquent ça devrait me donner des nombres assez différents. Par contre, vu que la fonction est appelée à des intervalles très proches, ça reste à prouver. Une technique pourrait être de lancer les threads à intervalle régulier (ainsi l'entropie du système changera vu que la charge ne sera pas la même — plus ou moins de threads en cours d'exécution).

Mais dans mon cas, ça ne biaise pas la validité de l'algorithme d'avoir des séquences aléatoires corrélées. Donc tout va bien

Merci de ta remarque, j'avoue que je n'y avais pas pensé !

Initialiser des Mersenne Twister est tres complique. Il vaut nieux ne pas se baser sur eux pour faire des generateurs paralleles.

**Arzar** · 15/04/2013, 16h53

Envoyé par Matthieu Brucher

Utiliser la nouvelle bibliotheque random du c++ ne resoudra pas entierement le probleme : l'appel devra etre protege par un mutex si tu ne veux pas que ca parte en vrille.

Ben pourquoi ?
Trademark parle bien d'utiliser un générateur *local* pour chaque thread (donc sans aucun appel global ou état partagé global) je ne vois pas bien ce qui pourrait poser problème ?