c - OpenMP 花费的时间比预期的要长

Question

因此，我在使用 openMp 时遇到了一些困难。我是初学者，我不知道自己做错了什么。这是我在大学的一门类(class)的项目，所以我不寻求解决方案，而是寻求提示或解释。

该项目是计算属于不同集合(比如 setA 和 setB)的 2 个字符串之间的汉明距离。这两组可能包含 100,1000 或 10000 个字符串，每个字符串都由相同长度的字符组成。

我的问题是，尽管我已经减少了并行程序的执行时间，但它仍然比串行算法花费更多的时间。

因此，我附上我的代码以显示我到目前为止所做的事情。

串行C代码。

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

//initialize sets' number and string's 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 代码

void main(int argc,char **argv)
{
//initialize sets' number and string's 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 );
}

对于 openmp 程序，我收到的执行时间约为 42.011104，而对于串行算法，我收到的执行时间约为 32.876482(m=n=10000 且 I=100，其中 m,n 描述了每个集合中的字符串数，I 是字符串长度)

我坚信并行程序应该花费更少的执行时间。 有什么想法吗？？

提前致谢!

Answer 1

测量多处理器性能有点复杂，但我们可以很好地近似“它是否有效？”使用 time(1)。如果我按原样使用您的代码(使用 GCC gcc-4.8.real (Ubuntu 4.8.5-2ubuntu1~14.04.1) 4.8.5 调用 gcc -W -Wall -Wextra -O3 -fopenmp openmptest .c -o openmptest) 我得到了

$ 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

其中，real 和 user 的值大致相同，也与普通版本大致相同。如果我完全删除 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(我这里有四个 CPU。)我得到

$ 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 您声明了两次，一次在循环之前，一次在循环内。你应该摆脱所有的警告。经常会在这几十条警告之间隐藏非常重要的信息。