C++ Girl
  1. C++ Girl
  3. Benchmark multi-threading
Intereting Posts
Erreur de section de données partagées DLL Comment fonctionne la syntaxe de conversion selon le style de fonction? Écrire sur une masortingce dans un fichier .oct sans avoir à boucler? Complexité des opérations sur les tableaux RapidXML donnant des noeuds CDATA vides comment définir les centres initiaux de K-means openCV c ++ Obtention du chemin de service vers l’exécutable Comment travailler avec des vecteurs nesteds en C ++? Variable statique de symbole externe non résolue (variable utilisée par la méthode définie dans l’en-tête) Faute de segmentation Utiliser typedef fort comme alternative plus légère à la bibliothèque Boost Parameter? Cmg: Impossible de reconnaître le format jpg Où le libellé standard permet-il des types incomplets dans les déclarations de fonction, mais exige des types complets dans les définitions de fonction? QT Hériter de QTableWidgetItem vers Widget et remplacer l’opérateur ‘<' L’optimiseur de compilateur C ++ est-il autorisé à interrompre la capacité de mon destructeur à être appelé plusieurs fois?

Benchmark multi-threading

J’ai eu un calcul mathématique lourd pour compter le nombre de nombres premiers jumeaux dans une plage et j’ai divisé la tâche entre des threads.

Vous voyez ici le profil du temps d’exécution par rapport au nombre de threads.

Mes questions portent sur la justification de:

  1. Pourquoi les threads simples et doubles ont-ils des performances très similaires?

  2. Pourquoi le temps d’exécution diminue-t-il lorsqu’il est à 5 ou 7 threads alors que le temps d’exécution augmente lorsque 6 ou 8 threads sont utilisés? (J’ai expérimenté cela dans plusieurs tests.)

  3. J’ai utilisé un ordinateur à 8 cœurs. Puis-je prétendre que 2 × n (où n est le nombre de cœurs) est un bon nombre de threads en règle générale?

  4. Si j’utilise un code avec une utilisation élevée de la RAM, est-ce que je m’attendrais à des tendances similaires dans le profil ou changeraient-elles radicalement avec un nombre croissant de threads?

repère multithreading

Ceci est la partie principale du code uniquement pour montrer qu’il n’utilise pas beaucoup de RAM. 

bool is_prime(long a) { if(a<2l) return false; if(a==2l) return true; for(long i=2;i*i<=a;i++) if(a%i==0) return false; return true; } uint twin_range(long l1,long l2,int processDiv) { uint count=0; for(long l=l1;l<=l2;l+=long(processDiv)) if(is_prime(l) && is_prime(l+2)) { count++; } return count; }

Caractéristiques: 

 $ lsb_release -a Dissortingbutor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 94 Model name: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz Stepping: 3 CPU MHz: 799.929 CPU max MHz: 4000.0000 CPU min MHz: 800.0000 BogoMIPS: 6815.87 Virtualisation: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 8192K NUMA node0 CPU(s): 0-7 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

Mise à jour (après la réponse acceptée)

Nouveau profile:

Performance multi-threading

Le code amélioré est comme suit. Maintenant, la charge de travail est répartie équitablement. 

 bool is_prime(long a) { if(a<2l) return false; if(a==2l) return true; for(long i=2;i*i<=a;i++) if(a%i==0) return false; return true; } void twin_range(long n_start,long n_stop,int index,int processDiv) { // l1+(0,1,...,999)+0*1000 // l1+(0,1,...,999)+1*1000 // l1+(0,1,...,999)+2*1000 // ... count=0; const long chunks=1000; long r_begin=0,k=0; for(long i=0;r_begin<=n_stop;i++) { r_begin=n_start+(i*processDiv+index)*chunks; for(k=r_begin;(k<r_begin+chunks) && (k<=n_stop);k++) { if(is_prime(k) && is_prime(k+2)) { count++; } } } std::cout <<"Thread "<<index<<" finished." <<std::endl<<std::flush; return count; }

Considérez que votre programme se terminera lorsque le dernier thread aura fini de vérifier sa plage de nombres. Peut-être que certains threads sont plus rapides que d’autres?

Combien de temps faut-il à is_prime() pour déterminer qu’un nombre pair est premier? Il le trouvera à la première itération. Pour trouver la primalité d’un nombre impair, il faut au moins deux itérations et éventuellement jusqu’à sqrt (a) itérations si a est premier. is_prime() sera beaucoup plus lent quand on lui donnera un nombre premier plus grand qu’un nombre pair!

Dans votre cas de deux threads, un thread vérifie la primalité de 100000000, 100000002, 100000004, etc., tandis que l’autre thread vérifie 100000001, 100000003, 100000005, etc. Un thread vérifie tous les nombres pairs tandis que l’autre vérifie tous les nombres impairs. (y compris tous ces primes lentes!).

Demandez à vos threads d’imprimer ("Thread at %ld done", l1) quand ils ont fini, et je pense que vous constaterez que certains threads sont beaucoup plus rapides que d’autres, en raison de la façon dont vous divisez le domaine entre les threads. Un nombre pair de threads donnera toutes les valeurs paires au (x) même thread (s), ce qui entraîne un partitionnement particulièrement médiocre. C’est pourquoi vos numéros de threads pairs sont plus lents que les impairs.

Cela ferait une superbe bande dessinée XKCD-esque. “Nous devons vérifier tous ces numéros pour trouver les nombres premiers! À la main!” “Ok, je vais vérifier le tout, tu fais les cotes.”

Votre vrai problème ici est qu’une décomposition de domaine fixe, comme vous l’avez faite, nécessite que chaque partition prenne le même temps pour être optimale.

La solution à ce problème consiste à effectuer le partitionnement de manière dynamic. Un modèle couramment utilisé implique un pool de threads de travail qui demandent un travail en morceaux. Si le bloc est petit comparé au travail total effectué par un thread, tous les threads termineront leur travail dans le même laps de temps.

Pour votre problème, vous pourriez avoir un start_number, stop_number, total_twins global protégé par mutex start_number, stop_number, total_twins . Chaque thread sauvegardera start_number avant d’incrémenter sa valeur globale de chunk_size . Ensuite, il effectue une recherche dans la plage [saved_start_number, saved_start_number+chunk_size) , en ajoutant le nombre de jumeaux trouvés au total_twins fois l’opération terminée. Les threads de travail continuent à le faire jusqu’à start_number >= stop_number . L’access aux globals utilise le mutex pour la protection. Il faut ajuster la taille du bloc pour limiter l’inefficacité du coût de l’obtention d’un bloc et de la contention sur le mutex par rapport à l’inefficacité des threads de travail inactifs n’ayant plus de morceaux à allouer pendant qu’un autre thread travaille encore sur le dernier morceau. Si vous utilisez un incrément atomique pour demander un bloc, la taille du bloc pourrait être aussi petite qu’une valeur unique, mais si vous aviez besoin d’une requête réseau dans un système informatique réparti, sa taille devrait être beaucoup plus grande. C’est la vue d’ensemble de la façon dont cela fonctionne.

En passant, votre test is_prime() est naïf et extrêmement lent. Si un nombre n’était pas divisible par 2, peut-il être divisé par 4? On peut faire beaucoup mieux!

8 threads ne fonctionneront pas plus vite que 7 car vous avez 8 processeurs (qui ne traitent évidemment qu’un seul thread – EDIT: grâce à @Algridas – de votre application ), chacun d’entre eux et votre main() besoin d’un thread pour s’exécuter.