Vermeiden Sie falsche Freigabe mit Padding

Question

Ich möchte die Summe einer großen Matrix berechnen und ich sehe derzeit keine Leistungsverbesserungen, wenn ich mehrere Threads oder nur einen einzigen verwenden. Ich denke, das Problem bezieht sich auf die falsche Freigabe, aber ich habe auch eine Auffüllung meiner Struktur hinzugefügt. Bitte guck dir das an!

#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

ich nicht auch immer der Polsterung Ihrer struct sehen sollte mit der Leistung Ihres Codes zu tun haben. Die realen Daten befinden sich in der Matrix, auf die verwiesen wird.

Um was geht es Ihnen, der Mangel an Beschleunigung, dies ist wahrscheinlich aufgrund der Tatsache, dass Ihr Code vollständig Speicher gebunden ist. Das heißt, um die Summe durchzuführen, müssen die Daten aus dem Speicher über den Speicherbus abgerufen werden. (Ihre Matrix ist viel zu groß, um in den Cache zu passen.) Das heißt, Ihre Berechnung ist an die Bandbreite Ihres Speicherbusses gebunden, die von allen Ihren Kernen gemeinsam genutzt wird.

Beachten Sie auch, dass Ihr Code nicht durch die Summe, sondern durch die Aufrufe an ran(), die im sequentiellen Teil des Programms sind, dominiert.