Discussion :

[Trademark]

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]

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

[Emmanuel Deloget]

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

[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

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

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

[Trademark]

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