Kleine Leistungssteigerung bei Verwendung mehrerer Threads

Question

Ich implementierte Multithread-Jordan-Gauss-Methode zum Lösen eines linearen Systems und ich sah, dass auf zwei Threads nur etwa 15% weniger Zeit als auf Einzel-Thread statt ideal 50% ausgeführt wurde. Also habe ich ein einfaches Programm geschrieben, das dies wiedergibt. Hier erstelle ich eine Matrix 2000x2000 und gebe 2000/THREADS_NUM Zeilen zu jedem Thread, um einige Berechnungen mit ihnen zu machen.

#include <stdlib.h> 
#include <stdio.h> 
#include <pthread.h> 
#include <time.h> 

#ifndef THREADS_NUM 
#define THREADS_NUM 1 
#endif 

#define MATRIX_SIZE 2000 


typedef struct { 
    double *a; 
    int row_length; 
    int rows_number; 
} TWorkerParams; 

void *worker_thread(void *params_v) 
{ 
    TWorkerParams *params = (TWorkerParams *)params_v; 
    int row_length = params->row_length; 
    int i, j, k; 
    int rows_number = params->rows_number; 
    double *a = params->a; 

    for(i = 0; i < row_length; ++i) // row_length is always the same 
    { 
     for(j = 0; j < rows_number; ++j) // rows_number is inverse proportional 
             // to the number of threads 
     { 
      for(k = i; k < row_length; ++k) // row_length is always the same 
      { 
       a[j*row_length + k] -= 2.; 
      } 
     } 
    } 
    return NULL; 
} 


int main(int argc, char *argv[]) 
{ 
    // The matrix is of size NxN 
    double *a = 
     (double *)malloc(MATRIX_SIZE * MATRIX_SIZE * sizeof(double)); 
    TWorkerParams *params = 
     (TWorkerParams *)malloc(THREADS_NUM * sizeof(TWorkerParams)); 
    pthread_t *workers = (pthread_t *)malloc(THREADS_NUM * sizeof(pthread_t)); 
    struct timespec start_time, end_time; 
    int rows_per_worker = MATRIX_SIZE/THREADS_NUM; 
    int i; 
    if(!a || !params || !workers) 
    { 
     fprintf(stderr, "Error allocating memory\n"); 
     return 1; 
    } 
    for(i = 0; i < MATRIX_SIZE*MATRIX_SIZE; ++i) 
     a[i] = 4. * i; // just an example matrix 
    // Initializtion of matrix is done, now initialize threads' params 
    for(i = 0; i < THREADS_NUM; ++i) 
    { 
     params[i].a = a + i * rows_per_worker * MATRIX_SIZE; 
     params[i].row_length = MATRIX_SIZE; 
     params[i].rows_number = rows_per_worker; 
    } 
    // Get start time 
    clock_gettime(CLOCK_MONOTONIC, &start_time); 
    // Create threads 
    for(i = 0; i < THREADS_NUM; ++i) 
    { 
     if(pthread_create(workers + i, NULL, worker_thread, params + i)) 
     { 
      fprintf(stderr, "Error creating thread\n"); 
      return 1; 
     } 
    } 
    // Join threads 
    for(i = 0; i < THREADS_NUM; ++i) 
    { 
     if(pthread_join(workers[i], NULL)) 
     { 
      fprintf(stderr, "Error creating thread\n"); 
      return 1; 
     } 
    } 
    clock_gettime(CLOCK_MONOTONIC, &end_time); 
    printf("Duration: %lf msec.\n", (end_time.tv_sec - start_time.tv_sec)*1e3 + 
      (end_time.tv_nsec - start_time.tv_nsec)*1e-6); 
    return 0; 
} 

Hier, wie ich es kompilieren:

gcc threads_test.c -o threads_test1 -lrt -pthread -DTHREADS_NUM=1 -Wall -Werror -Ofast 
gcc threads_test.c -o threads_test2 -lrt -pthread -DTHREADS_NUM=2 -Wall -Werror -Ofast 

Nun, wenn ich laufe ich bekommen:

./threads_test1 
Duration: 3695.359552 msec. 
./threads_test2 
Duration: 3211.236612 msec. 

Welche 2-Faden-Programm bedeutet, läuft 13% schneller als Single-Thread, auch obwohl es keine Synchronisation zwischen Threads gibt und sie keinen Speicher teilen. Ich fand diese Antwort: https://stackoverflow.com/a/14812411/5647501 und dachte, dass hier einige Probleme mit dem Prozessor-Cache sein können, so fügte ich Polsterung, aber immer noch blieb das Ergebnis gleich. Ich änderte meinen Code wie folgt:

typedef struct { 
    double *a; 
    int row_length; 
    int rows_number; 
    volatile char padding[64 - 2*sizeof(int)-sizeof(double)]; 
} TWorkerParams; 

#define VAR_SIZE (sizeof(int)*5 + sizeof(double)*2) 
#define MEM_SIZE ((VAR_SIZE/64 + 1) * 64 ) 
void *worker_thread(void *params_v) 
{ 
    TWorkerParams *params = (TWorkerParams *)params_v; 
    volatile char memory[MEM_SIZE]; 
    int *row_length =  (int *)(memory + 0); 
    int *i   =  (int *)(memory + sizeof(int)*1); 
    int *j   =  (int *)(memory + sizeof(int)*2); 
    int *k   =  (int *)(memory + sizeof(int)*3); 
    int *rows_number =  (int *)(memory + sizeof(int)*4); 
    double **a  = (double **)(memory + sizeof(int)*5); 

    *row_length = params->row_length; 
    *rows_number = params->rows_number; 
    *a = params->a; 

    for(*i = 0; *i < *row_length; ++*i) // row_length is always the same 
    { 
     for(*j = 0; *j < *rows_number; ++*j) // rows_number is inverse proportional 
             // to the number of threads 
     { 
      for(*k = 0; *k < *row_length; ++*k) // row_length is always the same 
      { 
       (*a + *j * *row_length)[*k] -= 2. * *k; 
      } 
     } 
    } 
    return NULL; 
} 

Also meine Frage ist: Warum bekomme ich nur 15% Speed-up statt 50%, wenn zwei Threads hier mit? Jede Hilfe oder Anregung wird geschätzt. Ich benutze 64-Bit Ubuntu Linux, Kernel 3.19.0-39-generisch, CPU Intel Core i5 4200M (zwei physikalische Kerne mit Multithreading), aber ich habe es auch auf zwei anderen Maschinen mit dem gleichen Ergebnis getestet.

EDIT: Wenn ich a[j*row_length + k] -= 2.; mit a[0] -= 2.; ersetzen, erhalte ich erwartete Geschwindigkeit-up:

./threads_test1 
Duration: 1823.689481 msec. 
./threads_test2 
Duration: 949.745232 msec. 

EDIT 2: Nun, wenn ich es mit a[k] -= 2.; ersetzt erhalte ich die folgende:

./threads_test1 
Duration: 1039.666979 msec. 
./threads_test2 
Duration: 1323.460080 msec. 

Diesen kann ich überhaupt nicht bekommen.

Answer 1

Sprechen Sie etwa 13% der Geschwindigkeit, aber was ist die Zeit für Ihre Kalkül-Funktion und nicht im Rest des Programms.

Sie könnten damit beginnen, nur die Zeit zu schätzen, die die Calcul-Methode ohne die Zeit der Thread-Verwaltung durchlaufen hat. Es ist möglich, dass Sie einen wichtigen Teil Ihrer Zeit in der Thread-Verwaltung verlieren. Das könnte die geringe Geschwindigkeit erklären, die Sie erhalten haben.

In anderen Teil, 50% der Geschwindigkeit mit 2 Fäden ist es ziemlich unmöglich zu erhalten.

Answer 2

Dies ist ein klassisches Problem, schalten Sie die i und j für Schleifen.

Sie durchlaufen zuerst die Spalten und in der inneren Schleife die Zeilen, das bedeutet, dass Sie viel mehr Cache-Fehler als nötig haben.

Meine Ergebnisse mit dem ursprünglichen Code (die erste Version ohne Polsterung):

$ ./matrix_test1 
Duration: 4620.799763 msec. 
$ ./matrix_test2 
Duration: 2800.486895 msec. 

(besser Verbesserung als Sie eigentlich)

Nachdem die for-Schleifen für i Schalten und j:

$ ./matrix_test1 
Duration: 1450.037651 msec. 
$ ./matrix_test2 
Duration: 728.690853 msec. 

Hier die 2-fache Beschleunigung.

EDIT: In der Tat ist das Original nicht , dass schlecht, weil der k-Index immer noch durchläuft die Reihe iterierenden Spalten, ist aber immer noch viel besser, die Zeile in der äußeren Schleife zu iterieren. Und wenn ich aufsteige, verarbeitest du immer weniger Gegenstände in der innersten Schleife, also ist es immer noch wichtig.

EDIT2: (entfernte die Blocklösung, weil es tatsächlich andere Ergebnisse erzeugte) - aber es sollte immer noch möglich sein, Blöcke zu verwenden, um die Cache-Leistung zu verbessern.