Hiệu suất nhỏ tăng khi sử dụng nhiều luồng

Question

Tôi đã triển khai phương pháp đa luồng Jordan-Gauss để giải quyết hệ thống tuyến tính và thấy rằng chạy trên hai luồng chỉ mất khoảng 15% ít hơn thời gian chạy trên một chuỗi thay vì 50% lý tưởng. Vì vậy, tôi đã viết một chương trình đơn giản sao chép này. Ở đây tôi tạo một ma trận 2000x2000 và cung cấp 2000/THREADS_NUM dòng cho mỗi luồng để thực hiện một số phép tính với chúng.

#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; 
} 

đây làm thế nào tôi biên dịch nó:

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 

Bây giờ khi tôi chạy tôi nhận được:

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

Có nghĩa là chương trình 2 sợi chạy nhanh hơn so với sợi đơn 13%, thậm chí mặc dù không có sự đồng bộ giữa các luồng và chúng không chia sẻ bất kỳ bộ nhớ nào. Tôi tìm thấy câu trả lời này: https://stackoverflow.com/a/14812411/5647501 và nghĩ rằng đây có thể là một số vấn đề với bộ nhớ cache của bộ xử lý, vì vậy tôi đã thêm phần đệm, nhưng kết quả vẫn giữ nguyên. Tôi đã thay đổi mã của mình như sau:

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; 
} 

Vì vậy, câu hỏi của tôi là: tại sao tôi chỉ nhận được 15% tốc độ thay vì 50% khi sử dụng hai chủ đề ở đây? Bất kỳ trợ giúp hoặc gợi ý nào sẽ được đánh giá cao. Tôi đang chạy Ubuntu Linux 64 bit, hạt nhân 3.19.0-39-chung, CPU Intel Core i5 4200M (hai lõi vật lý với đa luồng), nhưng tôi cũng đã thử nghiệm trên hai máy khác có cùng kết quả.

EDIT: Nếu tôi thay a[j*row_length + k] -= 2.; với a[0] -= 2.;, tôi nhận được tốc độ tăng dự kiến:

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

EDIT 2: Bây giờ, khi tôi đã thay thế nó với a[k] -= 2.; tôi nhận được như sau:

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

Điều này tôi không thể hiểu được.

Answer 1

Bạn có nói khoảng 13% tốc độ tăng không, nhưng thời gian trôi qua trên fonction tính toán của bạn và không nằm trong phần còn lại của chương trình.

Bạn có thể bắt đầu ước tính chỉ thời gian trôi qua trên phương pháp tính toán mà không cần thời gian quản lý luồng. Có thể bạn mất một phần quan trọng trong thời gian quản lý luồng. Điều đó có thể giải thích tốc độ nhỏ mà bạn thu được.

Trong phần khác, 50% tăng tốc với 2 luồng hoàn toàn không thể có được.

Answer 2

Đây là vấn đề kinh điển, chuyển i và j thành vòng lặp.

Bạn đang lặp qua các cột đầu tiên và trong vòng lặp bên trong, bạn xử lý các hàng, điều đó có nghĩa là bạn có nhiều bộ nhớ cache bị thiếu hơn mức cần thiết.

kết quả của tôi với mã gốc (phiên bản đầu tiên mà không cần đệm):

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

(cải thiện tốt hơn so với bạn thực sự)

Sau khi chuyển đổi cho các vòng lặp for i và j:

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

Ở đây tăng tốc 2 lần.

EDIT: Trong thực tế, bản gốc không phải là rằng xấu vì chỉ mục k vẫn đi qua các cột lặp lại hàng, nhưng vẫn tốt hơn nhiều để lặp lại hàng trong vòng lặp bên ngoài. Và khi tôi tăng lên, bạn đang xử lý các mặt hàng ít hơn và ít hơn trong vòng lặp bên trong nhất, do đó, nó vẫn còn quan trọng.

EDIT2: (đã xóa giải pháp chặn vì nó thực sự tạo ra các kết quả khác nhau) - nhưng vẫn có thể sử dụng các khối để cải thiện hiệu suất bộ nhớ cache.