OpenMP takes longer than expected

Question

So, I am encountering some difficulties when using openMp. I am new and I don’t know what I am doing wrong. This is a project for one of my courses at the university, so I'm not looking for a solution, but rather for a hint or explanation.

The project must calculate the distance from the interference between two lines that belong to different sets (say, setA and setB). These two sets can contain 100,1000 or 10,000 lines, each of which consists of the same character length.

My problem is that although I have reduced the execution time of the parallel program, it still takes more time than the sequential algorithm.

So, I am attaching my codes to show what I have done so far.

serial code C.

void main(int argc,char **argv)
{

//initialize sets' number and string length
int m=atoi(argv[1]),n=atoi(argv[2]),I=atoi(argv[3]);
int i=0,j=0,l=0,TotalHammingDistance=0,count;

//creation of 2-dimentional matrices for setA and setB
char **setA = malloc(m * sizeof(char *)); // Allocate row pointers
for(i = 0; i < m; i++)
    setA[i] = malloc((I+1) * sizeof(char));  // Allocate each row separatel

char **setB = malloc(n * sizeof(char *)); // Allocate row pointers
for(i = 0; i < n; i++)
    setB[i] = malloc((I+1) * sizeof(char));  // Allocate each row separatel

// initialize matrices with random string (0 and 1)
for (i=0;i<m;i++){
    for(j=0;j<I;j++){
        setA[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
    }
    setA[i][I]='\0';
}

for (i=0;i<n;i++){
    for(j=0;j<I;j++){
        setB[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
    }
    setB[i][I]='\0';
}

//creation of m*n matrix to store all hamming distances and initialize it
int **HamDist = malloc(m * sizeof(int *)); // Allocate row pointers
for(i = 0; i < m; i++)
  HamDist[i] = malloc(n * sizeof(int));

for(i=0;i<m;i++){
    for(j=0;j<n;j++){
        HamDist[i][j]=0;
    }
}

clock_t start=clock();
//Calculate hamming distance for all combinations of the strings
for (i=0;i<m;i++){
    for(j=0;j<n;j++){
        count=0;
        for(l=0;l<=I;l++) {
            if (setA[i][l] != setB[j][l])
                count++;
        }
        HamDist[i][j]=count;
        TotalHammingDistance+=HamDist[i][j];
    }
}
clock_t end =clock();
double hamm_time=(double)(end-start)/CLOCKS_PER_SEC;

printf("\n|Total Hamming execution time= %f",hamm_time);
printf("\n\n*|The Total Hamming Distance is: %d\n",TotalHammingDistance );
} 

OpenMp C Code

void main(int argc,char **argv)
{
//initialize sets' number and string length
    int m=atoi(argv[1]),n=atoi(argv[2]),I=atoi(argv[3]);
     int i=0,j=0,TotalHammingDistance=0, tid,nthreads,chunk;

    //creation of 2-dimentional matrices for setA and setB      
    char **setA = malloc(m * sizeof(char *)); // Allocate row pointers
    for(i = 0; i < m; i++)
      setA[i] = malloc((I+1) * sizeof(char));  // Allocate each row separatel

    char **setB = malloc(n * sizeof(char *)); // Allocate row pointers
    for(i = 0; i < n; i++)
      setB[i] = malloc((I+1) * sizeof(char));  // Allocate each row separatel

    // initialize matrices with random string (0 and 1)
    for (i=0;i<m;i++){
        for(j=0;j<I;j++){
            setA[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
        }
        setA[i][I]='\0';
    }

    for (i=0;i<n;i++){
        for(j=0;j<I;j++){
            setB[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
        }
        setB[i][I]='\0';
    }

    //creation of m*n matrix to store all hamming distances and initialize it
    uint16_t **HamDist = malloc(m * sizeof(uint16_t *)); // Allocate row pointers
    for(i = 0; i < m; i++)
      HamDist[i] = malloc(n * sizeof(uint16_t));

    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            HamDist[i][j]=0;
        }
    }

    printf("\n HamDist set \n" );
    int count=0;
    clock_t start=clock();

    omp_set_num_threads(2);
    #pragma omp parallel shared(setA, setB,HamDist ) 
    {
        int k,p,l,count=0;
        #pragma omp for schedule(dynamic, 10000)        
        for (k=0;k<m;k++){
             for(p=0;p<n;p++){
                count=0;
                for(l=0;l<=I;l++){
                    if (setA[k][l] != setB[p][l]){
                        count++;
                    }
                }
                HamDist[k][p]=count;
            }
        }
    }

    clock_t end =clock();
    double per_time=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n|Total time for two sets= %f",per_time);

    /**/
    for (i=0;i<m;i++){
          for(j=0;j<n;j++){
              TotalHammingDistance+=HamDist[i][j];
          }
    }

printf("\n|Total execution time= %f",per_time);
printf("\n\n*|The Total Hamming Distance is: %d\n",TotalHammingDistance );
}

The execution time that I get is about 42.011104 for the openmp program and about 32.876482 for the sequential algorithm (m = n = 10000 and i = 100, where m, n describes the number of lines in each set, and I describes the length of the line)

I strongly believe that a parallel program should take less time to execute. Any idea?

Thanks in advance!

Answer 1

Measuring multiprocessor performance is a bit more complicated, but we can make a good approximation: "Does it work or not?" a time(1). If I do this with your code as it is (with GCC gcc-4.8.real (Ubuntu 4.8.5-2ubuntu1 ~ 14.04.1) 4.8.5 called using gcc -W -Wall -Wextra -O3 -fopenmp openmptest.c -o openmptest) I got

$ time ./openmptest 10000 10000 100

 HamDist set 

|Total time for two sets= 9.620011
|Total execution time= 9.620011

*|The Total Hamming Distance is: 1248788142

real    0m9.815s
user    0m9.700s
sys 0m0.116s

, , , . schedule(dynamic, 10000) Openmp ,

$ time ./openmptest 10000 10000 100
 HamDist set 

|Total time for two sets= 9.187761
|Total execution time= 9.187761

*|The Total Hamming Distance is: 1248788142

real    0m4.819s
user    0m9.265s
sys 0m0.112s

5/9 9/9. omp_set_num_threads(2) 4 ( ).

$ time ./openmptest 10000 10000 100
 HamDist set 

|Total time for two sets= 11.438243
|Total execution time= 11.438243

*|The Total Hamming Distance is: 1248788142

real    0m3.080s
user    0m11.540s
sys 0m0.104s

3/11 < 5/9 < 9/9. , , , OpenMP . omp_set_num_threads() .

, OpenMP . OpenMP - , , , @Davislor reduction .

: , count, , . . , .