Multi-Threading-Benchmark

Question

Ich hatte eine schwere mathematische Berechnung, um die Anzahl der twin prime Zahlen innerhalb eines Bereichs zu zählen, und ich habe die Aufgabe zwischen Threads aufgeteilt.

Hier sehen Sie das Profil der Ausführungszeit gegen die Anzahl der Threads.

Meine Fragen sind über Rechtfertigung:

1. Warum einzigen Thread und Dual-Threads haben sehr ähnliche Leistung haben?

2. Warum wird die Ausführungszeit reduziert, wenn es 5- oder 7-threaded ist, während die Ausführungszeit erhöht wird, wenn 6 oder 8 Threads verwendet werden? (Ich habe das in mehreren Tests erfahren.)

3. Ich habe einen 8-Kern-Computer verwendet. Kann ich behaupten, dass 2 × n (wobei n ist die Anzahl der Kerne) ist eine gute Anzahl von Threads als Faustregel?

4. Wenn ich einen Code mit einer hohen RAM-Auslastung verwende, würde ich ähnliche Trends im Profil erwarten, oder würde er sich mit einer steigenden Anzahl von Threads dramatisch ändern?

Dies ist der Haupt nur der Codeteil zu zeigen, es RAM nicht viel nutzen.

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

Spezifikationen:

$ lsb_release -a 

Distributor 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 

---

Update (Nach der Antwort akzeptiert)

Neues Profil:

Der verbesserte Code ist wie folgt. Jetzt ist die Arbeitsbelastung gerecht verteilt.

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

Answer 1

Beachten Sie, dass Ihr Programm beendet wird, wenn der letzte Thread seinen Nummernbereich überprüft hat. Vielleicht sind manche Threads schneller als andere?

Wie lange dauert is_prime(), um zu bestimmen, dass eine gerade Zahl prim ist? Es wird dies bei der ersten Iteration finden. Das Finden der Primzahl einer ungeraden Zahl erfordert mindestens zwei Iterationen und möglicherweise bis zu sqrt (a) Iterationen, wenn a prim ist. is_prime() wird sehr viel langsamer sein, wenn es eine große Primzahl erhält als eine gerade Zahl!

In Ihrem Fall mit zwei Threads prüft ein Thread die Primalität von 100000000, 100000002, 100000004 usw., während der andere Thread 100000001, 100000003, 100000005 usw. prüft. Ein Thread prüft alle geraden Zahlen, während der andere prüft all die ungeraden Zahlen (einschließlich all dieser langsamen Primzahlen!).

Lassen Sie Ihre Threads ("Thread at %ld done", l1) ausdrucken, wenn sie fertig sind, und ich denke, Sie werden feststellen, dass einige Threads sehr viel schneller als andere sind, aufgrund der Art, wie Sie die Domäne zwischen den Threads aufteilen. Eine gerade Anzahl von Threads liefert alle geraden Werte an den gleichen Thread (s), was zu einer besonders schlechten Partitionierung führt, weshalb Ihre geraden Thread-Nummern langsamer sind als die ungeraden.

Dies würde eine große XKCD-esque Comic machen. "Wir müssen alle diese Zahlen überprüfen, um Primzahlen zu finden! Mit der Hand!" "Ok, ich überprüfe die Unterschiede, du machst die Chancen."

Ihr echtes Problem hier ist, dass eine feste Domain-Dekomposition, wie Sie getan haben, erfordert, dass jede Partition die gleiche Menge an Zeit benötigt, um optimal zu sein.

Die Lösung besteht darin, die Partitionierung dynamisch durchzuführen. Ein häufig verwendetes Muster umfasst einen Pool von Worker-Threads, die eine Arbeit in Chunks anfordern. Wenn der Chunk klein ist im Vergleich zu der gesamten Arbeit eines Threads, werden alle Threads ihre Arbeit in ähnlicher Zeit beenden.

Für Ihr Problem könnten Sie einen Mutex geschützten globalen Datensatz start_number, stop_number, total_twins haben. Jeder Thread speichert start_number, bevor er seinen globalen Wert um chunk_size erhöht. Dann durchsucht es den Bereich [saved_start_number, saved_start_number+chunk_size) und fügt die Anzahl der gefundenen Zwillinge zur globalen total_twins hinzu, wenn sie fertig ist. Die Worker-Threads machen dies bis start_number >= stop_number. Zugriff auf die Globals verwenden den Mutex zum Schutz. Man muss die Chunk-Größe anpassen, um die Ineffizienz von den Kosten des Erhaltens eines Chunks und der Konkurrenz auf dem Mutex gegen die Ineffizienz von leerlaufenden Worker-Threads, die keine Chunks mehr haben, zuzuteilen, während ein anderer Thread noch an seinem letzten Chunk arbeitet. Wenn Sie ein atomares Inkrement zum Anfordern eines Chunks verwendet haben, könnte die Chunk-Größe möglicherweise so klein wie ein einzelner Wert sein. Wenn jedoch eine Netzwerkanforderung in einem verteilten Computersystem benötigt würde, müsste die Chunk-Größe viel größer sein. Das ist der Überblick, wie es funktioniert.

BTW, Ihr is_prime() Test ist naiv und äußerst langsam. Wenn eine Zahl nicht durch 2 teilbar ist, kann sie durch 4 geteilt werden? Man kann viel besser machen!

Answer 2

8 Threads als 7 nicht schneller arbeiten, da Sie 8 CPUs (die ein Thread offensichtlich nur sind Handling - EDIT: Dank @Algridas - aus Ihrer Anwendung) und Sie Ihre main() einen Thread benötigt weiterlaufen.