Bei einer Berechnung - wie viele Threads soll ich öffnen?

Question

Ich schreibe ein Programm, das einige lange Berechnungen durchführt, in die ich so viele Aufgaben einbinden kann, wie ich möchte. Für die Diskussion nehmen wir an, dass ich einen Algorithmus schreibe, um herauszufinden, ob eine Zahl p eine Primzahl ist oder nicht, indem ich versuche, sie durch alle Zahlen zwischen 2 und p-1 zu teilen. Diese Aufgabe kann offensichtlich auf viele Threads aufgeteilt werden.

Ich schrieb tatsächlich eine Beispiel-App, die genau das tut. Als Parameter gebe ich die Nummer an, nach der ich suchen möchte, und die Anzahl der zu verwendenden Threads (jedem Thread wird ein Bereich von gleicher Größe gegeben, um p zu teilen und zu teilen - zusammen decken sie den gesamten Bereich ab).

Meine Maschine hat 8 Kerne. Ich fing an, das Programm mit einer großen Zahl, die ich weiß, ist Prime (2971215073), und mit 1, 2, 3 Threads usw., bis 8 Threads zu erreichen - jedes Mal lief das Programm schneller als das vorherige, was ich erwartet hatte. Wenn ich jedoch Zahlen größer als 8 ausprobierte, wurde die Rechenzeit tatsächlich immer kleiner (wenn auch nur geringfügig)!

Es gibt keine I/O oder ähnliches in meinen Threads, nur reine CPU-Berechnungen. Ich hatte erwartet, dass die Laufzeit sich verschlechterte, wenn ich 8 Threads passierte, da es mehr Kontextwechsel geben würde und die Anzahl der parallel laufenden Threads bei 8 bleibt. Es ist schwer zu sagen, wo der Peak ist, da die Unterschiede sehr gering sind und sich ändern von einem Lauf zum anderen, aber es ist klar, dass zB 50 Threads irgendwie schneller als 8 läuft (um ~ 300 ms) ...

Meine Vermutung ist, dass, da ich so viele Threads habe, ich mehr Laufzeit seit ich bekomme einen größeren Anteil im Thread-Pool des Systems haben, sodass meine Threads mehr ausgewählt werden. Es scheint jedoch keinen Sinn zu machen, dass je mehr Threads ich erstelle, desto schneller läuft das Programm (sonst erstellen nicht alle 1000 Threads ??).

Kann jemand eine Erklärung geben und vielleicht eine Best-Practice, wie viele Threads relativ zur Anzahl der Kerne auf der Maschine zu erstellen sind?

Danke.

---

Mein Code für wer interessiert (kompiliert unter Windows, VS2012):

#include <Windows.h> 
#include <conio.h> 
#include <iostream> 
#include <thread> 
#include <vector> 

using namespace std; 

typedef struct 
{ 
    unsigned int primeCandidate; 
    unsigned int rangeStart; 
    unsigned int rangeEnd; 
} param_t; 


DWORD WINAPI isDivisible(LPVOID p) 
{ 
    param_t* param = reinterpret_cast<param_t*>(p); 

    for (unsigned int d = param->rangeStart; d < param->rangeEnd; ++d) 
    { 
     if (param->primeCandidate % d == 0) 
     { 
      cout << param->primeCandidate << " is divisible by " << d << endl; 
      return 1; 
     } 
    } 

    return 0; 
} 

bool isPrime(unsigned int primeCandidate, unsigned int numOfCores) 
{ 
    vector<HANDLE> handles(numOfCores); 
    vector<param_t> params(numOfCores); 
    for (unsigned int i = 0; i < numOfCores; ++i) 
    { 
     params[i].primeCandidate = primeCandidate; 
     params[i].rangeStart = (primeCandidate - 2) * (static_cast<double>(i)/numOfCores) + 2; 
     params[i].rangeEnd = (primeCandidate - 2) * (static_cast<double>(i+1)/numOfCores) + 2; 
     HANDLE h = CreateThread(nullptr, 0, reinterpret_cast<LPTHREAD_START_ROUTINE>(isDivisible), &params[i], 0, 0); 
     if (NULL == h) 
     { 
      cout << "ERROR creating thread: " << GetLastError() << endl; 
      throw exception(); 
     } 
     handles[i] = h; 
    } 

    DWORD ret = WaitForMultipleObjects(numOfCores, &handles[0], TRUE, INFINITE); 
    if (ret >= WAIT_OBJECT_0 && ret <= WAIT_OBJECT_0 + numOfCores - 1) 
    { 
     for (unsigned int i = 0; i < numOfCores; ++i) 
     { 
      DWORD exitCode = -1; 
      if (0 == GetExitCodeThread(handles[i], &exitCode)) 
      { 
       cout << "Failed to get thread's exit code: " << GetLastError() << endl; 
       throw exception(); 
      } 

      if (1 == exitCode) 
      { 
       return false; 
      } 
     } 

     return true; 
    } 
    else 
    { 
     cout << "ERROR waiting on threads: " << ret << endl; 
     throw exception(); 
    } 
} 

int main() 
{ 
    unsigned int primeCandidate = 1; 
    unsigned int numOfCores = 1; 

    cout << "Enter prime candidate: "; 
    cin >> primeCandidate; 
    cout << "Enter # of cores (0 means all): "; 
    cin >> numOfCores; 
    while (primeCandidate > 0) 
    { 
     if (0 == numOfCores) numOfCores = thread::hardware_concurrency(); 

     DWORD start = GetTickCount(); 
     bool res = isPrime(primeCandidate, numOfCores); 
     DWORD end = GetTickCount(); 
     cout << "Time: " << end-start << endl; 
     cout << primeCandidate << " is " << (res ? "" : "not ") << "prime!" << endl; 

     cout << "Enter prime candidate: "; 
     cin >> primeCandidate; 
     cout << "Enter # of cores (0 means all): "; 
     cin >> numOfCores; 
    } 

    return 0; 
} 

Answer 1

Ja. Hier ist ein kleiner Auszug aus einigen Tests hat mich auf meinem i7/Vista 64 Feld (4 'echte' Kerne + Hyperthreading):

8 tests, 
400 tasks, 
counting to 10000000, 
using 8 threads: 
Ticks: 2199 
Ticks: 2184 
Ticks: 2215 
Ticks: 2153 
Ticks: 2200 
Ticks: 2215 
Ticks: 2200 
Ticks: 2230 
Average: 2199 ms 

8 tests, 
400 tasks, 
counting to 10000000, 
using 32 threads: 
Ticks: 2137 
Ticks: 2121 
Ticks: 2153 
Ticks: 2138 
Ticks: 2137 
Ticks: 2121 
Ticks: 2153 
Ticks: 2137 
Average: 2137 ms 

.. das zeigt, wie in Ihren Tests, eine ‚Überzeichnung Die Anzahl der Threads führt zu einer geringfügigen Verbesserung der Ausführungszeit um 2-3%. Meine Tests reichten einfache 'CPU-intensive Tasks mit ganzzahliger Ganzzahl' zu einem Threadpool mit einer unterschiedlichen Anzahl von Threads aus.

Meine Schlussfolgerung zu dieser Zeit war, dass die kleinere Verbesserung darin bestand, dass die größere Anzahl von Gewinden ein größeres Alter der Grundlast auf meiner Box einnahm - die 1-4% der Last von den wenigen der 1000 -ould threads im fast-immer-Leerlauf-Firefox, uTorrent, Word, Taskbar usw., die während der Tests ein wenig laufen.

Es scheint, dass in meinem Test der "Context Switching Overhead" von sagen wir, mit 64 Threads anstelle von 8 ist vernachlässigbar, und kann ignoriert werden.

Dies gilt nur, wenn die von den Aufgaben verwendeten Daten sehr klein sind. Später wiederholte ich eine ähnliche Reihe von Tests, bei denen die Tasks ein 8K-Array verwendeten - die Größe des L1-Cache.In diesem Worst-Case-Szenario führte die Verwendung von mehr Threads als Cores zu einer sehr deutlichen Verlangsamung, bis die Performance bei 16 Threads und darüber um 40% sank, da die Threads den gesamten Cache ein- und austauschten. Oberhalb von etwa 20 Threads wurde die Verlangsamung nicht schlechter, da, egal wie viele Threads die Tasks ausführten, der Cache immer noch mit der gleichen Rate aus jedem Core ausgelagert wurde.

Beachten Sie auch, dass ich viel RAM und so sehr wenige Seitenfehler hatte.

Answer 2

Sie machen eine Annahme, dass jeder Thread die gleiche Menge an Arbeit zu leisten hat, was möglicherweise nicht der Fall ist. Was Sie beachten sollten, ist die Ausgangszeiten jedes Ihrer Threads. Wenn einer oder mehrere von ihnen signifikant früher als der Rest austreten, wird es Sinn machen, dass das Hinzufügen von mehr Threads es beschleunigen wird. Das heißt, wenn man früh aufhört, bedeutet dies, dass ein Kern nicht mehr verwendet wird, indem er durch zusätzliche Threads die Last gerechter aufteilt.

Es gibt mehrere Gründe, warum jeder Thread eine andere Ausführungszeit benötigt. Ich kenne die zugrunde liegenden Instruktionszeiten in Ihrem Code nicht, aber vielleicht sind sie variabel. Wahrscheinlich hat jeder Thread andere CPU-Optimierungen, wie die Verzweigungsvorhersage. Man kann sein Zeitfenster gegenüber dem Betriebssystem verlieren oder vorübergehend auf seiner winzigen Speichermenge stehen bleiben. Es genügt zu sagen, dass es zahlreiche Faktoren gibt, die einen langsamer machen könnten als den anderen.

Welches ist die beste Zählung ist schwer zu sagen. Im Allgemeinen möchten Sie die CPUs geladen halten, so dass Sie im Allgemeinen über N Threads für N-Cores korrekt sind. Achten Sie jedoch auf Dinge wie Hyperthreading, bei denen Sie eigentlich keine zusätzlichen Kerne haben - es sei denn, Sie haben viel Speicher verwendet, was Sie nicht tun, das Hyperthreading wird nur in die Quere kommen. Auf AMDs neueren Chips haben sie halb so viele FPUs, also sind Ihre Integer-Anweisungen in Ordnung, aber Floating-Point könnte blockieren.

Wenn Sie möchten, dass jede CPU geladen wird, ist die einzige Möglichkeit, es wirklich zu tun, mit einem Job-basierten Framework. Brechen Sie Ihre Berechnung in kleinere Einheiten (wie Sie), aber immer noch nur einen Thread pro Kern. Da ein Thread mit seinem aktuellen Job ausgeführt wird, sollte er den nächsten verfügbaren Job übernehmen. Auf diese Weise ist es egal, ob einige Jobs länger oder kürzer sind, die freigesetzten CPUs werden einfach zum nächsten Job weitergehen.

Dies macht natürlich nur Sinn, wenn die Berechnung lang ist. Wenn die Gesamtzeit nur ein paar Sekunden beträgt, kann der Overhead der Jobs zu einer leichten Verlangsamung führen. Aber schon ab 4-5 Sekunden sollten Sie beginnen, Gewinne zu sehen. Stellen Sie außerdem sicher, dass Sie die CPU-Frequenzskalierung ausschalten, wenn Sie kleine Zeittests durchführen, da sonst die Geschwindigkeit der Aufwärts-/Abwärtszeiten auf jeder CPU im Prinzip zu zufälligen Ergebnissen führt.