falsesharing.cpp

#include <omp.h>
#include <iostream>
void sum(){
    int x,y;
    int i,j,k;
    /*
    Ta tablica w pamięci wygląda tak, zakładając linię pamięci 64 bajtów
    linia 1: 8B 8B 8B 8B 8B 8B 8B 8B
    linia 2: 8B 8B 8B 8B 8B 8B 8B 8B
    linia 3: 8B 8B 8B 8B 8B 8B 8B 8B
    itd.
    */
    long long table[40]; //każdy element ma 8 bajtów, bo long long
    x = 10000;
    y = 10000;
    int** A = new int*[x];
    for(i = 0; i < x; ++i){
        A[i] = new int[y];
    }

    for(i = 0; i < x; i++){
        for(j = 0; j < y; j++){
            A[i][j] = 1;
        }
    }
    omp_set_num_threads(2);
    long long suma = 0;
    double start,stop;
    for(k = 0; k < 10000; k++){
        start = omp_get_wtime();
        #pragma omp parallel
        {
            int id = omp_get_thread_num();
            table[k + id] = 0;
            #pragma omp for
            for(int i = 0; i < x; i++){
                for(int j = 0; j < y; j++){
                    //krok k, najpierw wątek 1: table[0], watęk 2: table[1]
                    //krok k+1, potem wątek 1: table[1], watęk 2: table[2]
                    //itd.
                    //Ponieważ wątki zapisują w tej samej linii, to muszą cały czas sięgać do tej samej linii, jeszcze raz, bo jest unieważniana
                    //W pewnym momencie dochodzimy do sytuacji, wątek 1: table[7], watęk 2: table[8]
                    // table[7] jest w pierwszej linii, table[8] jest w drugiej linii, wtedy nie ma false sharingu, i jest szybciej bo korzystają z pp
                    table[k + id] += A[i][j]; 
                }
            }
            #pragma omp atomic
            suma += table[k + id];
        }
        stop = omp_get_wtime();
        std::cout << "Sum: " << suma << std::endl;
        std::cout << "Elapsed time: " << (stop - start) << std::endl;
        suma = 0;
    }

    for(int i = 0; i < x; ++i){
        delete [] A[i];
    }
    delete [] A;
}

int main(){
    sum();
    return 0;
}