c - 使用填充防止虚假共享

Question

我想计算一个大矩阵的总和，目前在使用多线程或仅使用一个线程时我没有看到性能提升。我认为问题与错误共享有关，但我还在我的结构中添加了一个填充。请看!

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

#define WIDTH 20000 
pthread_mutex_t mylock = PTHREAD_MUTEX_INITIALIZER;

struct split { // sizeof(split) = 24 
    int start; 
    int end; 
    int* matrix; 
    int i; 
    char padding[64 - 24]; //Padding the private sum variables     forces them into separate cache lines and removes false sharing. Assume cache line is 64 bytes
};

int ran(){ 
    return rand() % 21; 
}
int* createBigMatrix(){
    int* a = malloc(sizeof(int)* WIDTH * WIDTH);
    for (int i = 0; i < WIDTH * WIDTH; i ++){ 
        a[i] = ran(); // fill up the matrix with random numbers
    }
    return a;
}
static int finalSum;
void* partialSum(void* arg){ 
    struct split* a = arg;
    int totalSum = 0; // create local variable
    int i;
    for (i = a->start; i <= a->end; i ++){  
        totalSum += a->matrix[i];
    }
    pthread_mutex_lock(&mylock);
    finalSum += totalSum; // critical section
    pthread_mutex_unlock(&mylock);  
    free(a);

    return 0;
} 
int main(){ //-294925289
    int useMultiThreads = 1; // there is no difference between using one thread or 4 therads
    finalSum = 0;
    pthread_t thread_ids[4];  
    // i want a square matrix of npages width 
    int* c = createBigMatrix();  

    printf("%lu\n", sizeof(struct split));
    if (useMultiThreads){
        // split the tasks evenly amoung 4 threads
        // since there are 20,000x20,000, there must be 400,000,000 cells 
        int start[] = {0, 100000000, 200000000, 300000000};
        int end[] = {99999999, 199999999, 299999999, 399999999}; 
        // calculate sum
        for (int i = 0; i < 4; i ++){
            struct split* a = malloc(sizeof(struct split));
            a->start = start[i];
            a->end = end[i];
            a->matrix = c;
            pthread_create(thread_ids + i, NULL, partialSum, a);
        }

        for (int i = 0; i < 4; i ++){ // join em up
            pthread_join(thread_ids[i], NULL);
        }
    }
    else { // use single thread
        for (int i = 0; i <= 399999999; i ++){
            finalSum += c[i];
        }
    }

    printf("total sum is %d\n", finalSum);
/*
    real    0m4.871s
    user    0m4.844s
    sys     0m0.392s
*/ 
    free(c);
    return 0;
}

Answer 1

我看不到您的 struct 的填充与代码的性能有任何关系。真正的数据在指向的矩阵中。

您担心的是缺乏加速，这可能是因为您的代码完全受内存限制。也就是说，要执行求和，必须通过内存总线从内存中获取数据。 (您的矩阵太大，无法放入缓存。)也就是说，您的计算受内存总线带宽的限制，而内存总线由所有内核共享。

另请注意，您的代码不是以求和为主，而是以程序顺序部分中对 ran() 的调用为主。