Quando si esegue un calcolo - quanti thread devo aprire?

Question

Sto scrivendo un programma che esegue alcuni lunghi calcoli, che posso suddividere in tutte le attività che voglio. Per ragioni di discussione, supponiamo che sto scrivendo un algoritmo per scoprire se un numero p è primo cercando di dividerlo per tutti i numeri compresi tra 2 e p-1. Questo compito può ovviamente essere suddiviso in più thread.

In realtà ho scritto un'app di esempio che fa proprio questo. Come parametro, fornisco il numero che voglio controllare, e il numero di thread da usare (ogni thread ha un intervallo di dimensioni uguali di numeri per provare a dividere p di - insieme coprono l'intero intervallo).

La mia macchina ha 8 core. Ho iniziato a eseguire il programma con un numero elevato che so essere primo (2971215073) e con 1, 2, 3 thread ecc. Fino a raggiungere 8 thread - ogni volta che il programma veniva eseguito più velocemente del precedente, che era quello che mi aspettavo. Tuttavia, quando ho provato i numeri più grandi di 8, il tempo di calcolo continuava a ridursi (anche se di poco)!

Non c'è I/O o qualcosa di simile nei miei thread, solo calcoli di CPU pura. Mi aspettavo che i tempi di esecuzione peggiorassero quando ho passato 8 thread in quanto ci sarebbe stato più cambio di contesto e il numero di thread paralleli continuava a 8. È difficile dire dove sia il picco in quanto le differenze sono molto piccole e cambiare da una corsa all'altra, tuttavia è chiaro che 50 thread in qualche modo gira più veloce di 8 (di ~ 300 ms) ...

La mia ipotesi è che poiché ho così tanti thread, ottengo più tempo di esecuzione da quando avere una porzione maggiore nel pool di thread del sistema, quindi i miei thread vengono selezionati di più. Tuttavia, non sembra logico che più thread creo, più velocemente il programma viene eseguito (altrimenti perché non tutti creano 1000 thread ??).

Qualcuno può offrire una spiegazione e forse una best practice sul numero di thread da creare rispetto al numero di core sulla macchina?

Grazie.

---

Il mio codice per chi è interessato (compilato su 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

Sì. Ecco un piccolo estratto di alcuni test che ho fatto sul mio i7/Vista 64 box, (4 'reali' core + 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 

.. mostrando che, come nei test, un 'over-abbonamento 'dei thread comporta un miglioramento marginale del 2-3% nel tempo complessivo di esecuzione. I miei test hanno presentato semplici operazioni "conteggio di un intero" della CPU a un threadpool con un numero variabile di thread.

La mia conclusione in quel momento era che il miglioramento minore era dovuto al fatto che il maggior numero di fili occupava un'età maggiore del "carico base" sulla mia scatola: l'1-4% del carico dai pochi dei 1000 -Di thread nel quasi-sempre-inattivo Firefox, uTorrent, Word, Taskbar ecc. ecc., che è accaduto per funzionare un po 'durante i test.

Sembrerebbe che, nel mio test, il "overhead di commutazione del contesto", ad esempio, utilizzando 64 thread anziché 8 sia trascurabile e possa essere ignorato.

Questo si applica solo quando i dati utilizzati dalle attività sono molto piccoli. In seguito ho ripetuto un batch simile di test in cui le attività utilizzavano un array 8K: la dimensione della cache L1.In questo scenario "peggiore", l'utilizzo di più thread rispetto ai core ha comportato un rallentamento molto evidente fino a quando, a 16 thread e sopra, le prestazioni sono diminuite del 40% mentre i thread hanno scambiato l'intera cache dentro e fuori. Oltre i 20 thread, il rallentamento non è peggiorato poiché, indipendentemente da quanti thread hanno eseguito le attività, la cache è stata ancora sostituita da ogni core alla stessa velocità.

Nota anche che ho avuto un sacco di RAM e quindi pochissimi errori di pagina.

Answer 2

Si presuppone che ogni thread abbia una quantità di lavoro equivalente, che potrebbe non essere effettivamente il caso. Quello che dovresti guardare sono i tempi di uscita di ciascuna delle tue discussioni. Se uno o più di essi stanno uscendo significativamente prima del resto, avrà senso che l'aggiunta di più thread acceleri. Cioè, se uno si ferma presto significa che un core non sarà più usato, avendo fili extra rompe il carico più equamente.

Ci sono diversi motivi per cui ogni thread può richiedere un tempo di esecuzione diverso. Non conosco i tempi di istruzione sottostanti sul tuo codice, ma forse sono variabili. È anche probabile che ogni thread abbia un diverso set di ottimizzazioni della CPU, come la previsione delle diramazioni. Si può perdere il suo timeslice al sistema operativo, o essere momentaneamente in stallo sulla sua piccola quantità di memoria. Basti dire che ci sono numerosi fattori che potrebbero rendere uno più lento dell'altro.

Qual è il conteggio migliore è difficile da dire. In generale si desidera mantenere le CPU caricate, quindi in genere si è corretti sui thread N per i nuclei N. Tuttavia, sii consapevole di cose come hyperthreading, in cui in realtà non hai core aggiuntivi - a meno che tu non abbia un sacco di uso della memoria, cosa che non fai, l'hyperthreading si metterà in mezzo. Sui nuovi chip di AMD hanno la metà di FPU, quindi le istruzioni per l'intero sono valide, ma il punto in virgola mobile potrebbe bloccarsi.

Se si desidera mantenere ciascuna CPU caricata, l'unico modo per farlo realmente è con un framework basato sul lavoro. Rompi i tuoi calcoli in unità più piccole (come fai tu), ma hai ancora solo un thread per core. Come un thread è fatto con il suo lavoro corrente dovrebbe prendere il prossimo lavoro disponibile. In questo modo non importa se alcuni lavori sono più lunghi/più corti, le CPU liberate passeranno al lavoro successivo.

Questo ovviamente ha senso solo se il calcolo è lungo. Se il tempo totale è di pochi secondi, il sovraccarico dei lavori potrebbe causare un leggero rallentamento. Ma anche a partire da 4-5 secondi dovresti iniziare a vedere i guadagni. Inoltre, assicurati di disattivare il ridimensionamento della frequenza della CPU quando esegui piccoli test di temporizzazione, altrimenti i tempi di accelerazione/decelerazione su ciascuna CPU ti daranno risultati casuali.