OpenMP 花费的时间比预期的要长
OpenMP takes more time than expected
所以,我在使用 openMp 时遇到了一些困难。我是初学者,我不知道自己做错了什么。这是我在大学的一门课程的项目,所以我不寻求解决方案,而是寻求提示或解释。
该项目是计算属于不同集合(比如 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]='[=10=]';
}
for (i=0;i<n;i++){
for(j=0;j<I;j++){
setB[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
}
setB[i][I]='[=10=]';
}
//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]='[=11=]';
}
for (i=0;i<n;i++){
for(j=0;j<I;j++){
setB[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
}
setB[i][I]='[=11=]';
}
//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是字符串长度)
我坚信并行程序应该花费更少的执行时间。
有什么想法吗??
提前致谢!
测量多处理器性能有点复杂,但我们可以用 time(1)
很好地近似 "Does it work or not?"。如果我按原样使用您的代码(使用 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 的默认设置运行良好。 Fine-tuning OpenMP 本身就是一门科学,但是例如@Davislor 关于使用 reduction
的评论似乎是一个很好的开始。
顺便说一句:你也有很多警告,其中之一是关于阴影 count
你声明了两次,一次在循环之前,一次在循环内。你应该摆脱所有的警告。经常发生的是,在这几十个警告之间隐藏了一个非常重要的信息。
所以,我在使用 openMp 时遇到了一些困难。我是初学者,我不知道自己做错了什么。这是我在大学的一门课程的项目,所以我不寻求解决方案,而是寻求提示或解释。
该项目是计算属于不同集合(比如 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]='[=10=]';
}
for (i=0;i<n;i++){
for(j=0;j<I;j++){
setB[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
}
setB[i][I]='[=10=]';
}
//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]='[=11=]';
}
for (i=0;i<n;i++){
for(j=0;j<I;j++){
setB[i][j]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"[rand() % 62];
}
setB[i][I]='[=11=]';
}
//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是字符串长度)
我坚信并行程序应该花费更少的执行时间。 有什么想法吗??
提前致谢!
测量多处理器性能有点复杂,但我们可以用 time(1)
很好地近似 "Does it work or not?"。如果我按原样使用您的代码(使用 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 的默认设置运行良好。 Fine-tuning OpenMP 本身就是一门科学,但是例如@Davislor 关于使用 reduction
的评论似乎是一个很好的开始。
顺便说一句:你也有很多警告,其中之一是关于阴影 count
你声明了两次,一次在循环之前,一次在循环内。你应该摆脱所有的警告。经常发生的是,在这几十个警告之间隐藏了一个非常重要的信息。