[C] - Una domanda sui threads...

[Pegasus84]

Salve a tutti!

Vorrei porre un quesito a tutti voi, dato che io non capisco: può capitare che aumentando il numero di threads, ad esempio da 4 threads a 5, l'esecuzione di un codice parallelo possa vedere leggermente degradate le proprie prestazioni per poi tornare a migliorare? Perché?

Qualcuno mi sa illuminare? E' una cosa che mi fa sclerare... :p

[Cait Sith]

Per dare una risposta con cognizione di causa si dovrebbe sapere come è fatto il programma e che cosa fanno i singoli thread.
Comunque dipende anche dal numero di core del processore: se hai 4 core, 5 thread che occupano le stesse risorse hardware (per esempio l'unità floating point) non credo che aiutino a migliorare le performance di un programma.

[Pegasus84]

Intel® Xeon® Processor E5410 ha 4 cores, quindi se passa da 4 a 5, peggiora leggermente le prestazioni per poi tornare a migliorare...

Comunque un programma semplice che ho collaudato effettua la somma di N numeri double su un sistema con shared memory... Utilizzando OpenMP, ovviamente...

[Cait Sith]

Probabilmente paghi l'overhead di openmp: fai conto che la creazione di regioni parallele ha un costo, come pure la schedulazione e l'evenutale sincronizzazione dei thread. Se non si hanno beneficio nello sfruttamente dell'hardware, non vale la pena aprire thread in più.

[Pegasus84]

Probabilmente paghi l'overhead di openmp: fai conto che la creazione di regioni parallele ha un costo, come pure la schedulazione e l'evenutale sincronizzazione dei thread. Se non si hanno beneficio nello sfruttamente dell'hardware, non vale la pena aprire thread in più.

Questo è il mio codice...


int main (int argc, char *argv[])
{
int i, N, nthreads, tid, nloc, nloc_threads, rest;
double *x, sumtot=0.0;

/* Converte in int il numero di threads da utilizzare inserito dall'utente */
sscanf (argv[1], "%d", &nthreads);
/* Converte in int il numero di reali da generare casualmente inserito dall'utente */
sscanf (argv[2], "%d", &N);

/* Setta il numero di threads da utilizzare inserito dall'utente */
omp_set_num_threads(nthreads);

x = (double *)calloc(N,sizeof(double));

srand(time(NULL));
for (i=0; i<N; i++)
x[i] = 100.0 * (double) rand() / (double) 0x7fffffff;

/* Calcolo del numero di addendi da assegnare ad ogni thread */
nloc_threads=N/nthreads;
rest=N%nthreads;
/* In caso affermativo: incremento del numero di addendi ottenuti */
if ( rest!=0 )
nloc=nloc_threads+1;
else /* In caso negativo */
nloc=nloc_threads;

#pragma omp parallel
somma( x, &sumtot, nloc, N );
printf ("\nLa somma totale e' %lf\n\n", sumtot);
/* Deallocazione memoria */
free(x);

return 0;
}


void somma ( double *x, double *sumtot, int nloc, int N )
{
/* Variabili */
int i, tid;
double sum=0.0;

/* Ricava l'identificativo del thread corrente */
tid = omp_get_thread_num();

#pragma omp private (sum, nloc, i) shared(*sumtot)
{
sum=0;
for (i=0; i<nloc; i++)
sum=sum+x[i+nloc*tid];
//printf("Sono il thread %d - Somma parziale %lf\n", tid, sum);
#pragma omp critical
(*sumtot)+=sum;
}
}

Che ne pensi della mia idea di somma?

Ma poi secondo me non ha senso provare con 1-2-3-4-5-6-7-8 threads... Mi pare più corretto provare con una potenza di 2 del numero di threads, cioè 1-2-4-8... O sbaglio?

[Cait Sith]

Non è che stavo dicendo che il tuo programma può essere scritto meglio, ma che quando il numero di thread supera il numero di core fisici, non è così strano che le prestazioni non aumentino o addirittura diminuiscano. Se lanci con 200 thread sarà ancora peggio.
Poi che i thread siano o non siano potenze di due non credo c'entri molto. Su 4 core sono sicuramente meglio 3 thread rispetto a 2.

Il tuo programma l'ho guardato velocemente e non mi torna la variabile nloc. Se ho 4 thread e 7 addendi, nloc non può essere uguale per tutti i thread perchè vorrebbe dire che sommo 2 addendi ogni thread per un totale di 8. Del resto nloc non può nemmeno essere diverso per i vari thread perchè lo usi per costruire l'offset dell'array nella somma. Così com'è si rischia un segmentation fault (se il numero di thread è piccolo difficilmente si verificherà).
Ti conviene usare come stride il numero totale di thread, come indice iniziale del ciclo l'indice del thread e fare:

for(k=tid;k<N;k+=Nthreads) sum+=x[k];

Con a seguire il blocco critico. In questo modo non ti devi preoccupare di quali thread devono sommare un elemento in meno degli altri nel caso ci sia il resto.


Poi la direttiva

#pragma omp private (sum, nloc, i) shared(*sumtot)

non credo che serva perchè sum, loc e i sono state allocate nello stack della funzione che a sua volta è stata chiamata da ogni singolo thread (quindi ogni thread ha il suo stack), e sumtot, anche se è allocato in stack diversi punta sempre alla stessa variabile

[Pegasus84]

Non è che stavo dicendo che il tuo programma può essere scritto meglio, ma che quando il numero di thread supera il numero di core fisici, non è così strano che le prestazioni non aumentino o addirittura diminuiscano. Se lanci con 200 thread sarà ancora peggio.
Poi che i thread siano o non siano potenze di due non credo c'entri molto. Su 4 core sono sicuramente meglio 3 thread rispetto a 2.

Hai ragione... :)


Il tuo programma l'ho guardato velocemente e non mi torna la variabile nloc. Se ho 4 thread e 7 addendi, nloc non può essere uguale per tutti i thread perchè vorrebbe dire che sommo 2 addendi ogni thread per un totale di 8. Del resto nloc non può nemmeno essere diverso per i vari thread perchè lo usi per costruire l'offset dell'array nella somma. Così com'è si rischia un segmentation fault (se il numero di thread è piccolo difficilmente si verificherà).
Ti conviene usare come stride il numero totale di thread, come indice iniziale del ciclo l'indice del thread e fare:

for(k=tid;k<N;k+=Nthreads) sum+=x[k];

Con a seguire il blocco critico. In questo modo non ti devi preoccupare di quali thread devono sommare un elemento in meno degli altri nel caso ci sia il resto.

In effetti anche qui hai ragione: pensandoci bene neanche io mi trovo con nloc... Ho seguito il tuo consiglio e funziona benissimo... :)


Poi la direttiva

#pragma omp private (sum, nloc, i) shared(*sumtot)

non credo che serva perchè sum, loc e i sono state allocate nello stack della funzione che a sua volta è stata chiamata da ogni singolo thread (quindi ogni thread ha il suo stack), e sumtot, anche se è allocato in stack diversi punta sempre alla stessa variabile

Forse la direttiva serve solo per sumtot dichiarandola variabile condivisa, perché comunque devo fare la somma totale prendendo le somme parziali dei threads vari...

Ti ringrazio tanto! Mi hai chiarito molte idee e mi hai anche fatto snellire il codice con i tuoi suggerimenti! Un grazie tante ancora! :)

Un'altra domanda: ma se ho 4 core fisici ed 8 threads, è normale lo stesso se da 4 a 5 threads peggiora lievemente come prestazioni per poi tornare a crescere? Da 2 a 3, invece, mi trovo! ;)

[Cait Sith]

La direttiva shared di solito è sottintesa. Tieni conto che, non puoi rendere privata un'area di memoria puntata da un puntatore. Se hai un vettore

float *x;
x=calloc(10,sizeof(float));

Tu puoi rendere privato l'indirizzo, ovvero il contenuto della variabile x, ma non l'area puntata da x (gli elementi x[0],x[1],x[2]).

Per quanto riguarda i core fisici e logici, penso dipenda, come avevo accennato, alle risorse che utilizzano i thread. Non sono un esperto quindi non prendermi alla lettera, ma penso che l'unità floating point difficilmente si riesce a condividere in modo ottimale tra due thread che girano sullo stesso core. Se vuoi fare esperimenti prova a fare la somma di interi anzichè di double, magari lì si nota il guadagno dell'hyperthreading.

[Pegasus84]

La direttiva shared di solito è sottintesa. Tieni conto che, non puoi rendere privata un'area di memoria puntata da un puntatore. Se hai un vettore

float *x;
x=calloc(10,sizeof(float));

Tu puoi rendere privato l'indirizzo, ovvero il contenuto della variabile x, ma non l'area puntata da x (gli elementi x[0],x[1],x[2]).


Questo perché è comunque un puntatore, giusto? Mentre nella realtà la variabile vera e propria NON è privata? Ho capito bene? :)

Comunque alla fine ho deciso di togliere la funzione somma e posizionare il suo corpo direttamente nel main, come segue:

/* Viene creato un "team" di threads che provvederanno a sommare simultaneamente */
#pragma omp parallel private (sum, i, tid) shared (sumtot)
{
/* Ricava l'identificativo del thread corrente */
tid = omp_get_thread_num();

for (i=tid; i<N; i+=nthreads)
{
sum+=x[i];
printf ("Sono il thread %d - x[%d] = %lf\n", tid, i, x[i]);
}

printf("Sono il thread %d - Somma parziale %lf\n", tid, sum);

#pragma omp critical
sumtot+=sum;
}


In questo modo evito incoerenze riguardo l'uso del puntatore sumtot nelle direttive omp... :)

[Cait Sith]

Per curiosità ho provato a compilare (con gcc) un codice con

#pragma omp parallel shared(* var)

e mi da un warning perchè non riconosce *, non so come fai a compilare.
Secondo me nella lista di variabili non puoi mettere asterischi per la deferenziazione di puntatori
Comunque già che c'ero ho verificato che gli array allocati staticamente, li puoi rendere privati, mentre gli array allocati dinamicamente ovviamente no.
Spero di chiarire con il seguente esempio:

float x_sta[1];
float *x_din;
x_din=calloc(1,sizeof(float));
#pragma omp parallel private(x_sta,x_din)
{
x_sta[0]=omp_get_thread_num(); // questo elemento dell'array è privato per ogni thread
x_din[0]=omp_get_thread_num(); // questo elemento dell'array è condiviso dai thread, quindi qui si verifica una race condition se non si mette blocco critico
x_din=calloc(1,sizeof(float)); // sovrascrivo il puntatore x_din, che è privato, con l'indirizzo di una nuova area di memoria allocata, che è diversa per ogni thread (quindi ho Nthread allocazioni)
x_din[0]=omp_get_thread_num(); // questo elemento dell'array, è diverso per ogni thread, perchè ora l'x_din di ogni thread punta a diverse aree di memoria, quindi qui non ci sono race condition
}

[Pegasus84]

Per curiosità ho provato a compilare (con gcc) un codice con

#pragma omp parallel shared(* var)

e mi da un warning perchè non riconosce *, non so come fai a compilare.
Secondo me nella lista di variabili non puoi mettere asterischi per la deferenziazione di puntatori
Comunque già che c'ero ho verificato che gli array allocati staticamente, li puoi rendere privati, mentre gli array allocati dinamicamente ovviamente no.
Spero di chiarire con il seguente esempio:

float x_sta[1];
float *x_din;
x_din=calloc(1,sizeof(float));
#pragma omp parallel private(x_sta,x_din)
{
x_sta[0]=omp_get_thread_num(); // questo elemento dell'array è privato per ogni thread
x_din[0]=omp_get_thread_num(); // questo elemento dell'array è condiviso dai thread, quindi qui si verifica una race condition se non si mette blocco critico
x_din=calloc(1,sizeof(float)); // sovrascrivo il puntatore x_din, che è privato, con l'indirizzo di una nuova area di memoria allocata, che è diversa per ogni thread (quindi ho Nthread allocazioni)
x_din[0]=omp_get_thread_num(); // questo elemento dell'array, è diverso per ogni thread, perchè ora l'x_din di ogni thread punta a diverse aree di memoria, quindi qui non ci sono race condition
}


Hai provato a compilare nel seguente modo:

gcc -fopenmp -lgomp -o eseguibile codice.c ?

A me compila correttamente senza warning...

Tuttavia, se il vettore lo fai condividere a tutti i threads, solo in lettura, non accade nessuna race condition, o erro? Sei d'accordo? Mmmmm, ma non è che si debba mettere la direttiva omp critical dove i threads fanno le somme parziali, cioè dove c'è il ciclo seguente:


for (i=tid; i<N; i+=nthreads)
{
sum+=x[i];
printf ("Sono il thread %d - x[%d] = %lf\n", tid, i, x[i]);
}

Ma penso che sia inutile, perchè sul vettore non viene eseguita alcuna operazione di scrittura... Alla fine non credo che nel caso della sola lettura si possano produrre race conditions...

[Cait Sith]

in effetti ho compilato con -fopenmp ma senza mettere -lgomp, però il programma mi sembra funzioni quando lo compilo

una race condition si verifica solo quando più thread tentano di scrivere un elemento di memoria condiviso, in lettura non ci sono mai problemi

il sum non lo devi mettere nel blocco critical perchè la variabile è privata, quindi ogni thread aggiorna la sua copia, altrimenti la variabile sum non servirebbe, ma agiresti direttamente su sumtot
è solo alla fine, quando calcoli la somma totale, che devi usare un blocco critical