I thread POSIX non producono accelerazione in C

Question

Sto imparando l'elaborazione parallela utilizzando Pthreads. Ho un processore quad core. Sfortunatamente, la parte parallelizzata del seguente codice gira approssimativamente 5 volte più lentamente del codice non parallelizzato. Cosa sto facendo di sbagliato qui? Grazie in anticipo per l'aiuto.

#include <stdio.h> 
#include <time.h> 
#include <pthread.h> 
#include <stdlib.h> 
#define NTHREADS 4 
#define SIZE NTHREADS*10000000 

struct params { 
    int * arr; 
    int sum; 
}; 

/* The worker function for the pthreads */ 
void * myFun (void * x){ 
    int i; 
    struct params * b = (struct params *) x; 
    for (i = 0; i < (int)(SIZE/NTHREADS); ++i){ 
    b->sum += b->arr[i]; 
    } 
    return NULL; 
} 

/* unparallelized summing function*/ 
int arrSum(int * arr, int size){ 
    int sum = 0; 
    for (int i = 0; i != size; ++i){ 
    sum += arr[i]; 
    } 
    return sum; 
} 

int main(int argc, char * argv[]){ 
    clock_t begin, end; 
    double runTime; 
    int rc, i; 
    int sum1, sum2 = 0; 
    pthread_t threads[NTHREADS]; 

    /* create array to sum over */ 
    int * myArr = NULL; 
    myArr = (int *) calloc(SIZE, sizeof(int)); 
    if (myArr == NULL){ 
    printf("problem allocating memory\n"); 
    return 1; 
    } 
    for (int i = 0; i < SIZE; ++i){ 
    myArr[i] = 1; 
    } 

    /* create array of params structs to feed to threads */ 
    struct params p; 
    p.sum = 0; 
    struct params inputs[NTHREADS]; 
    for(i = 0; i != NTHREADS; ++i){ 
    p.arr = myArr + i*(int)(SIZE/NTHREADS); 
    inputs[i] = p; 
    } 

    /* spawn the threads */ 
    begin = clock(); 
    for(i = 0; i != NTHREADS; ++i){ 
    rc = pthread_create(&threads[i], NULL, myFun, (void *) &inputs[i]); 
    } 

    /* wait for threads to finish */ 
    for(i = 0; i != NTHREADS; ++i){ 
    rc = pthread_join(threads[i], NULL); 
    } 
    end = clock(); 
    runTime = (double)(end - begin)/CLOCKS_PER_SEC; 
    printf("Parallelized code run time: %f\n", runTime); 

    /* run the unparallelized code */ 
    begin = clock(); 
    sum2 = arrSum(myArr, SIZE); 
    end = clock(); 
    runTime = (double)(end - begin)/CLOCKS_PER_SEC; 
    printf("Unparallelized code run time: %f\n", runTime); 

    /* consolidate and print results from threads */ 
    for(i = 0; i != NTHREADS; ++i){ 
    sum1 += inputs[i].sum; 
    } 
    printf("sum1, sum2: %d, %d \n", sum1, sum2); 

    free(myArr); 

    /* be disappointed when my parallelized code showed no speedup */ 
    return 1; 
} 

Answer 1

Ti manca un aspetto importante della programmazione parallela.

I thread di lavoro devono essere creati una volta per processo, non per ogni attività.

La creazione e la distruzione di thread richiedono tempo.

La soluzione è utilizzare un pool di thread e inviare attività al pool.

Il mio suggerimento è quello di utilizzare OpenMP che semplifica notevolmente questa attività e funziona con molti compilatori.

Esempio:

int sum = 0 
#pragma omp for shared(sum) 
for(int i=0; i<SIZE; ++i) 
{ 
    #pragma omp atomic 
    sum += myArr[i] 
} 

per fare questo lavoro più velocemente, fare qualche ciclo di svolgimento - per esempio calcolare la somma di 8 numeri in un singolo ambito del ciclo for.

Answer 2

Il problema principale è che si sta usando clock() which does not return the wall time but the cumulative CPU time. Questo è l'errore più comune con il tag OpenMP con SO (e se l'elenco delle frequenze era utile su SO dovrebbe mostrarlo).

Il modo più semplice per ottenere il tempo di parete è utilizzare una funzione da OpenMP: omp_get_wtime(). Funziona con Linux e Windows con GCC, ICC e MSVC (e presumo Clang che ora supporta OpenMP 3.1).

quando uso questo con il codice ottengo sul mio/otto iper-thread di sistema i7 IVB quattro core:

Parallelized code run time: 0.048492 
Unparallelized code run time: 0.115124 
sum1, sum2: 400000000, 400000000 

---

Alcuni altri commenti. La tua pianificazione è soggetta a errori. È possibile impostare l'array per ogni thread di

p.arr = myArr + i*(int)(SIZE/NTHREADS); 

E poi ogni esecuzione filo sopra (SIZE/NTHREADS). Ciò può dare risultati errati agli errori di arrotondamento per alcuni valori di SIZE e NTHREADS.

si dovrebbe avere ogni esecuzione filo sopra

int start = ithread*SIZE/NTHREADS; 
int finish = (ithreads+1)*SIZE/NTHREADS; 

E poi ogni punto thread per l'inizio della matrice e fare

int sum = 0; 
for (i = start; i < finish; ++i){ 
    sum += b->arr[i]; 
} 

Questo è essenzialmente ciò che OpenMP di schedule(static) fa. In realtà è possibile ottenere lo stesso effetto di pthreads usando OpenMP facendo

int sum = 0; 
#pragma omp parallel for reduction(+:sum) 
for (int i = 0; i < size; ++i){ 
    sum += arr[i]; 
} 

Qui c'è il codice che ho usato

//gcc -O3 -std=gnu99 t.c -lpthread -fopenmp 
#include <stdio.h> 
#include <time.h> 
#include <pthread.h> 
#include <stdlib.h> 
#include <omp.h> 

#define NTHREADS 4 
#define SIZE NTHREADS*100000000 

struct params { 
    int * arr; 
    int sum; 
}; 

/* The worker function for the pthreads */ 
void * myFun (void * x){ 
    int i; 
    struct params * b = (struct params *) x; 
    int sum = 0; 
    for (i = 0; i < (int)(SIZE/NTHREADS); ++i){ 
    sum += b->arr[i]; 
    } 
    b->sum = sum; 
    return NULL; 
} 

/* unparallelized summing function*/ 
int arrSum(int * arr, int size){ 
    int sum = 0; 
    for (int i = 0; i < size; ++i){ 
    sum += arr[i]; 
    } 
    return sum; 
} 

int main(int argc, char * argv[]) { 
    double runTime; 
    int rc, i; 
    int sum1, sum2 = 0; 
    pthread_t threads[NTHREADS]; 

    /* create array to sum over */ 
    int * myArr = NULL; 
    myArr = (int *) calloc(SIZE, sizeof(int)); 
    if (myArr == NULL){ 
    printf("problem allocating memory\n"); 
    return 1; 
    } 
    for (int i = 0; i < SIZE; ++i){ 
    myArr[i] = 1; 
    } 

    /* create array of params structs to feed to threads */ 
    struct params p; 
    p.sum = 0; 
    struct params inputs[NTHREADS]; 
    for(i = 0; i < NTHREADS; ++i){ 
    p.arr = myArr + i*(int)(SIZE/NTHREADS); 
    inputs[i] = p; 
    } 

    /* spawn the threads */ 
    runTime = -omp_get_wtime(); 
    for(i = 0; i != NTHREADS; ++i){ 
    rc = pthread_create(&threads[i], NULL, myFun, (void *) &inputs[i]); 
    } 

    /* wait for threads to finish */ 
    for(i = 0; i != NTHREADS; ++i){ 
    rc = pthread_join(threads[i], NULL); 
    } 

    runTime += omp_get_wtime(); 
    printf("Parallelized code run time: %f\n", runTime); 

    /* run the unparallelized code */ 
    runTime = -omp_get_wtime(); 
    sum2 = arrSum(myArr, SIZE); 
    runTime += omp_get_wtime(); 
    printf("Unparallelized code run time: %f\n", runTime); 

    /* consolidate and print results from threads */ 
    for(i = 0; i != NTHREADS; ++i){ 
    sum1 += inputs[i].sum; 
    } 
    printf("sum1, sum2: %d, %d \n", sum1, sum2); 

    free(myArr); 

    /* be disappointed when my parallelized code showed no speedup */ 
    return 1; 
}