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

Version imprimable

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:

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:

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 !

12/04/2013, 08h22
imperio

Créer un thread est plutôt lourd mais pas à ce point ! T'as pas des mutex qui traîneraient quelque part ?
12/04/2013, 08h38
Emmanuel Deloget

Combien est-ce qu'il y a de threads ?
12/04/2013, 08h39
Trademark

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
12/04/2013, 09h10
JolyLoic

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 ?
12/04/2013, 09h43
Emmanuel Deloget

(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 ?

@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:

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:

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 ;-)

Citation:

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:

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:

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)

12/04/2013, 15h56
Trademark
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 :P

Pour ce qui est des caches misses :
Code:

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).

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

* le système:

Code:

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:

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:

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:

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:

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:

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 :)

Citation:

Envoyé par Trademark

Code:

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. :aie:

12/04/2013, 18h08
Emmanuel Deloget

Citation:

Envoyé par Iradrille

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

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).
12/04/2013, 19h28
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 :ccool:

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 !
12/04/2013, 22h26
Flob90

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é.
12/04/2013, 22h32
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é !
15/04/2013, 11h50
Matthieu Brucher

Citation:

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 :ccool:

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.
15/04/2013, 11h51
Matthieu Brucher

Citation:

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.
15/04/2013, 16h53
Arzar

Citation:

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 ?
15/04/2013, 17h17
Matthieu Brucher

Je n'avais pas vu son edit, effectivement.
En revanche, le probleme de l'initialisation du generateur reste.
16/04/2013, 01h37
Iradrille

Citation:

Envoyé par Matthieu Brucher

Je n'avais pas vu son edit, effectivement.
En revanche, le probleme de l'initialisation du generateur reste.

Initialiser chaque thread avec un rand() (un srand()) sur le thread hôte promet une certaine "aléatoirité" (j'invente un mot, osef) )
16/04/2013, 10h55
Matthieu Brucher

Non, ca ne suffit pas. J'ai deja tente ce genre de chose, la seule bonne solution est de prendre un generateur qui est prevu pour ca, comme un generateur cryptographique. De plus, ils sont plus rapides que les Mersenne Twister sur les derniers procs Intel, du meme ordre pour les autres, consomment moins de memoire et en plus ils sont robustes, contrairement au Mersenne Twister. En fait, il n'y a plus aucune raison mathematique de prendre le generateur de la bibliotheque standard...
16/04/2013, 14h11
Emmanuel Deloget

Citation:

Envoyé par Matthieu Brucher

Non, ca ne suffit pas. J'ai deja tente ce genre de chose, la seule bonne solution est de prendre un generateur qui est prevu pour ca, comme un generateur cryptographique. De plus, ils sont plus rapides que les Mersenne Twister sur les derniers procs Intel, du meme ordre pour les autres, consomment moins de memoire et en plus ils sont robustes, contrairement au Mersenne Twister. En fait, il n'y a plus aucune raison mathematique de prendre le generateur de la bibliotheque standard...

Pour le cas d'utilisation, il faut juste un générateur aléatoire qui offre une bonne distribution. Inutile d'aller jusqu'à un générateur cryptographique (et s'ils sont rapides, c'est parce qu'ils s'appuient sur le système, par exemple via un device ; hors, les accès à ce device sont rendus séquentiels par le système, de manière à ne pas donner la même donnée à deux lecteurs différents. Sans compter que si on épuise l'entropie, alors le système va bloquer la récupération de données jusqu'à ce que l'entropie soit revenue. On retomberait alors dans un cas similaire, voire pire).

Si rand() fonctionne suffisamment bien pour obtenir une bonne qualité d'image, alors un autre générateur congruentiel linéaire offrant au moins la même qualité fournira le même service. Le tout est qu'il faut que ce générateur stocke son état - par opposition à un état global. Mersenne Twister offre de meilleure garantie sur la période et sur la distribution des valeurs, mais je ne sais pas dans quelle mesure ce gain est appréciable s'il s'accompagne d'une perte de performance (dans ce cas d'utilisation, les performances sont critiques, sinon on ne chercherait pas à disperser le travail sur plusieurs threads).

Le seul problème d'un générateur linéaire dans ce cas précis, c'est la graine. Et pour générer une graine pour chaque threads, on peut utiliser rand() ou un autre générateur random - il faut éviter d'utiliser time(), car on risque d'obtenir la même valeur de graine pour plusieurs threads).

Personnellement, je partirai sur une distribution uniforme, un générateur congruentiel linéaire, et une graine obtenue avec random_engine. Je ne suis pas sûr que ça vaille le coup d'aller beaucoup plus loin.

Par contre, je ferais aussi des tests avec d'autres distributions, histoire de voir si la qualité finale de l'image est dégradée ou améliorée.
16/04/2013, 15h28
Matthieu Brucher

Citation:

Envoyé par Emmanuel Deloget

Pour le cas d'utilisation, il faut juste un générateur aléatoire qui offre une bonne distribution. Inutile d'aller jusqu'à un générateur cryptographique (et s'ils sont rapides, c'est parce qu'ils s'appuient sur le système, par exemple via un device ; hors, les accès à ce device sont rendus séquentiels par le système, de manière à ne pas donner la même donnée à deux lecteurs différents. Sans compter que si on épuise l'entropie, alors le système va bloquer la récupération de données jusqu'à ce que l'entropie soit revenue. On retomberait alors dans un cas similaire, voire pire).

Il me semble aue non. On calcule juste le hash d'un compteur avec une cle particuliere. Il n'y a pas de device particulier utilise.

Citation:

Envoyé par Emmanuel Deloget

Si rand() fonctionne suffisamment bien pour obtenir une bonne qualité d'image, alors un autre générateur congruentiel linéaire offrant au moins la même qualité fournira le même service. Le tout est qu'il faut que ce générateur stocke son état - par opposition à un état global. Mersenne Twister offre de meilleure garantie sur la période et sur la distribution des valeurs, mais je ne sais pas dans quelle mesure ce gain est appréciable s'il s'accompagne d'une perte de performance (dans ce cas d'utilisation, les performances sont critiques, sinon on ne chercherait pas à disperser le travail sur plusieurs threads).

Justement, un MT n'est pas une bonne solution pour un generateur parellele car il est difficile de l'initialiser proprement, justement a cause de sa longue periodicite.

Citation:

Envoyé par Emmanuel Deloget

Le seul problème d'un générateur linéaire dans ce cas précis, c'est la graine. Et pour générer une graine pour chaque threads, on peut utiliser rand() ou un autre générateur random - il faut éviter d'utiliser time(), car on risque d'obtenir la même valeur de graine pour plusieurs threads).

Malheureusement non, ca ne suffit pas.

On peut conseiller ici, dans ce cas precis, de faire une solution a l'arrache pas propre, OK. Tu es l'un des seuls a avoir le code et a savoir ce qu'il fait. Mais dans le cas general de la generation de nombre aleatoires en parallele, il faut utiliser un outil qui soit correct, soit donc un generateur tel que ceux proposes par Random123. Dans le doute, il suffit de lire la publication associee a la bibliotheque presente a SC12 ;)
16/04/2013, 23h14
Emmanuel Deloget

Citation:

Envoyé par Matthieu Brucher

Il me semble aue non. On calcule juste le hash d'un compteur avec une cle particuliere. Il n'y a pas de device particulier utilise.

Je vois.

Citation:

Envoyé par Matthieu Brucher

Justement, un MT n'est pas une bonne solution pour un generateur parellele car il est difficile de l'initialiser proprement, justement a cause de sa longue periodicite.

Je ne comprends pas trop. Chaque thread a son propre générateur, créé avec une graine différente.

Est-ce que tu pourrais m'éclairer sur le sujet ?

Citation:

Envoyé par Matthieu Brucher

Malheureusement non, ca ne suffit pas.

On peut conseiller ici, dans ce cas precis, de faire une solution a l'arrache pas propre, OK. Tu es l'un des seuls a avoir le code et a savoir ce qu'il fait. Mais dans le cas general de la generation de nombre aleatoires en parallele, il faut utiliser un outil qui soit correct, soit donc un generateur tel que ceux proposes par Random123. Dans le doute, il suffit de lire la publication associee a la bibliotheque presente a SC12 ;)

C'est vrai que j'ai un peu d'avance sur vous :) Ceci dit, c'est un champ que tu connais bien, donc je ne vais pas te faire l'insulte de te prendre de haut :)

Sur le fond, je suis d'accord avec toi - encore qu'aller jusqu'au niveau cryptographique me semble exagéré.

J'espèce ne pas trop en dire : on est dans un cas proche d'une simulation Monte Carlo, donc l'idée est principalement d'avoir une distribution parfaite et un grand nombre de samples. Une générateur linéraire peut, dans ce cas, provoquer des artefacts - dans le sens où le générateur pourrait être biaisé ou avoir une distribution relativement moyenne. Mais s'il est suffisamment bon, alors la diffusion des samples sera elle aussi suffisamment bonne. Le but là n'est pas d'avoir du random pour du random - mais d'être capable de dire "si j'ai 1000 balles a tirer vers 10000 trous, alors chaque trou aura en moyenne 0,1 balles".

Edit : trouvé un papie de NVIDIA qui dit, effectivement, que des générateur MT sur plusieurs threads peuvent être correllés - ce qui n'est peut-être pas génial ici - (encore que, parce que chaque lanceur de balle est affecté à une série de trou, et ne peut pas perturber ses voisins ; du coup, même si tous les lanceurs lancent de la même manière ça ne change pas vraiment grand chose - c'est juste dommage d'un point de vue intellectuel). Le papier de NVIDIA cite un papier de Matsumoto & Nishimura (http://www.math.sci.hiroshima-u.ac.j...T/DC/dgene.pdf) qui, à priori, règle le problème. Leur idée est d'encoder le thread id dans les paramètres qui permettent de créer le générateur MT. A lire...

Ceci dit, ça ne change pas vraiment le fait que MT soit plus lent que d'autres générateurs random :)
17/04/2013, 10h52
Matthieu Brucher

Citation:

Envoyé par Emmanuel Deloget

Je ne comprends pas trop. Chaque thread a son propre générateur, créé avec une graine différente.

Est-ce que tu pourrais m'éclairer sur le sujet ?

Le probleme, c'est que tu ne sais pas si tu prends une graine toto et une autre toto +1 quand la premiere suite tombera sur la suivante. Il semblerait qu'avec les generateurs bases sur des compteurs, ce probleme specifique ne se pose pas (autant ?). La publication de Random123 a SC12 en parle, je crois qu'elle est sur leur site Web.

Citation:

Envoyé par Emmanuel Deloget

Sur le fond, je suis d'accord avec toi - encore qu'aller jusqu'au niveau cryptographique me semble exagéré.

Completemenent d'accord. D'ailleurs Random 123 propose des genereateurs bases sur une partie de fonction crytpographique si on veut. Avec le jeu d'instructions crypto d'Intel, on fait directement le travail, donc on peut se permettre sans aucun surcout de prendre une vraie fonction cryptographique (qui sera don crush resistant). Tout depend donc de ce qu'on peut se permettre. En tout cas, on peut se permettre d'avoir le choix maintenant, c'est bien :)