并行程序VS串行程序——优化实录

　　在多核处理器、超级计算机日益普及的今天，程序员们怎能对并行程序“袖手旁观”呢？

创新互联-专业网站定制、快速模板网站建设、高性价比镇平网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式镇平网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖镇平地区。费用合理售后完善，十年实体公司更值得信赖。

　　为了练手，我用MPI写了一个并行排序程序，

　　先介绍下我的第一个版本，大概的思路是：

　　使用MPI在各个进程之间进行通信，

　　1. 进程0生成随机数，并且讲数据分段，将各段数据分配给其他进程

　　2. 其他进程收到数据段，使用冒泡排序进行，发送回进程0

　　3. 进程0收到这些数据，通过归并排序按顺序整合起来。

　　下面是这个版本代码，

 
 
 
    
  
  
  
  1. 　　//MPI Hello World demo  
    2. 
  
  
  
  2. 　　#include   
    3. 
  
  
  
  3. 　　#include   
    4. 
  
  
  
  4. 　　#include   
    5. 
  
  
  
  5. 　　#include   
    6. 
  
  
  
  6. 　　#defineN 30  
    7. 
  
  
  
  7. 　　intmain(intargc, char** argv)  
    8. 
  
  
  
  8. 　　{  
    9. 
  
  
  
  9. 　intprocessRank, processNum, t, data, num;  
    10. 
  
  
  
  10. 　　intdataArr[N];  
    11. 
  
  
  
  11. 　　intdataArrB[N];  
    12. 
  
  
  
  12. 　　intpointer[100];  
    13. 
  
  
  
  13. 　　intsecEnd[100];  
    14. 
  
  
  
  14. 　　MPI_Status mpistat;  
    15. 
  
  
  
  15. 　　MPI_Init(&argc, &argv);  
    16. 
  
  
  
  16. 　　MPI_Comm_size(MPI_COMM_WORLD, &processNum);  
    17. 
  
  
  
  17. 　　MPI_Comm_rank(MPI_COMM_WORLD, &processRank);  
    18. 
  
  
  
  18. 　　printf("Yes, Sir! From process %i of %i ", processRank, processNum);  
    19. 
  
  
  
  19. 　　if(processRank == 0)  
    20. 
  
  
  
  20. 　　{  
    21. 
  
  
  
  21. 　　srand(time(NULL));  
    22. 
  
  
  
  22. 　　for(inti = 0;i 
  
  
  
  23. 　　dataArr[i] = rand()%1000;  
    24. 
  
  
  
  24. 　}  
    25. 
  
  
  
  25. 　　printf("Original Array: ");  
    26. 
  
  
  
  26. 　　for(inti = 0;i< N; i++){  
    27. 
  
  
  
  27. 　　printf("%d ", dataArr[i]);  
    28. 
  
  
  
  28. 　　}  
    29. 
  
  
  
  29. 　　printf(" ");  
    30. 
  
  
  
  30. 　　puts("Distribute data to processes");  
    31. 
  
  
  
  31. 　　for(inti = 1;i 
  
  
  
  32. 　　num = (N/(processNum-1));  
    33. 
  
  
  
  33. 　if(i == processNum -1)  
    34. 
  
  
  
  34. 　　num = N - num * (processNum -2);  
    35. 
  
  
  
  35. 　　///distribute data to each process  
    36. 
  
  
  
  36. 　　printf("Sending to process %d... ", i);  
    37. 
  
  
  
  37. 　　MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);  
    38. 
  
  
  
  38. 　　MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);  
    39. 
  
  
  
  39. 　　///gather the sorted data  
    40. 
  
  
  
  40. 　　printf("Receiving from process %d... ", i);  
    41. 
  
  
  
  41. 　　MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);  
    42. 
  
  
  
  42. 　　///prepare for merge, set the pointers  
    43. 
  
  
  
  43. 　　pointer[i] = (N/(processNum-1)) * (i-1);  
    44. 
  
  
  
  44. 　　secEnd[i] = pointer[i] + N/(processNum-1);  
    45. 
  
  
  
  45. 　　if(i == processNum-1) secEnd[i] = N;  
    46. 
  
  
  
  46. 　　}  
    47. 
  
  
  
  47. 　　printf("Sorted Sections Array: ");  
    48. 
  
  
  
  48. 　　for(inti = 0;i< N; i++){  
    49. 
  
  
  
  49. 　　printf("%d ", dataArrB[i]);  
    50. 
  
  
  
  50. 　　}  
    51. 
  
  
  
  51. 　　puts("");  
    52. 
  
  
  
  52. 　　///merge the sorted sections  
    53. 
  
  
  
  53. 　　puts("Merging...");  
    54. 
  
  
  
  54. 　　for(inti = 0;i 
  
  
  
  55. 　　inttMin = 1;  
    56. 
  
  
  
  56. 　　intmin = 10000;  
    57. 
  
  
  
  57. 　　for(t = 1;t 
  
  
  
  58. 　　if(pointer[t] 
  
  
  
  59. 　　min = dataArrB[pointer[t]];  
    60. 
  
  
  
  60. 　　tMin = t;  
    61. 
  
  
  
  61. 　　}  
    62. 
  
  
  
  62. 　　}  
    63. 
  
  
  
  63. 　　dataArr[i] = dataArrB[pointer[tMin]];  
    64. 
  
  
  
  64. 　　pointer[tMin]++;  
    65. 
  
  
  
  65. 　　}  
    66. 
  
  
  
  66. 　　///output the results  
    67. 
  
  
  
  67. 　　printf("Final Sorted Array: ");  
    68. 
  
  
  
  68. 　　for(inti = 0;i< N; i++){  
    69. 
  
  
  
  69. 　　printf("%d ", dataArr[i]);  
    70. 
  
  
  
  70. 　　}  
    71. 
  
  
  
  71. 　　printf(" ");  
    72. 
  
  
  
  72. 　　}  
    73. 
  
  
  
  73. 　　else 
    74. 
  
  
  
  74. 　　{  
    75. 
  
  
  
  75. 　　//receieve the section  
    76. 
  
  
  
  76. 　　MPI_Recv(&num, 1, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);  
    77. 
  
  
  
  77. 　　MPI_Recv(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);  
    78. 
  
  
  
  78. 　　printf("Received Original Array: ");  
    79. 
  
  
  
  79. 　　for(inti = 0;i< num; i++){  
    80. 
  
  
  
  80. 　　printf("%d ", dataArr[i]);  
    81. 
  
  
  
  81. 　　}  
    82. 
  
  
  
  82. 　　printf(" ");  
    83. 
  
  
  
  83. 　　//sort this section  
    84. 
  
  
  
  84. 　　for(inti = 0;i 
  
  
  
  85. 　　for(intj = num-1;j>=i+1;j--)  
    86. 
  
  
  
  86. 　　if(dataArr[j] 
  
  
  
  87. 　　inttmp = dataArr[j];  
    88. 
  
  
  
  88. 　　dataArr[j]= dataArr[j-1];  
    89. 
  
  
  
  89. 　　dataArr[j-1] = tmp;  
    90. 
  
  
  
  90. 　　}  
    91. 
  
  
  
  91. 　　MPI_Send(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD);  
    92. 
  
  
  
  92. 　　///display  
    93. 
  
  
  
  93. 　　printf("My Sorted Section: ");  
    94. 
  
  
  
  94. 　　for(inti = 0;i< num; i++){  
    95. 
  
  
  
  95. 　　printf("%d ", dataArr[i]);  
    96. 
  
  
  
  96. 　　}  
    97. 
  
  
  
  97. 　printf(" ");  
    98. 
  
  
  
  98. 　　}  
    99. 
  
  
  
  99. 　　MPI_Finalize();  
    100. 
  
  
  
  100. 　　return0;  
    101. 
  
  
  
  101. 　　} 
    102.

　　自己写出之后当然高兴，不过程序经过高手检查之后，提出了一些问题。

　　最要命的是这个

 
 
 
    
  
  
  
  1. 　　for(inti = 1;i 
  
  
  
  2. 　　num = (N/(processNum-1));  
    3. 
  
  
  
  3. 　　if(i == processNum -1)  
    4. 
  
  
  
  4. 　　num = N - num * (processNum -2);  
    5. 
  
  
  
  5. 　　///distribute data to each process  
    6. 
  
  
  
  6. 　　printf("Sending to process %d... ", i);  
    7. 
  
  
  
  7. 　　MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);  
    8. 
  
  
  
  8. 　　MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);  
    9. 
  
  
  
  9. 　　///gather the sorted data  
    10. 
  
  
  
  10. 　　printf("Receiving from process %d... ", i);  
    11. 
  
  
  
  11. 　　MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);  
    12. 
  
  
  
  12. 　　///prepare for merge, set the pointers  
    13. 
  
  
  
  13. 　　pointer[i] = (N/(processNum-1)) * (i-1);  
    14. 
  
  
  
  14. 　　secEnd[i] = pointer[i] + N/(processNum-1);  
    15. 
  
  
  
  15. 　　if(i == processNum-1) secEnd[i] = N;  
    16. 
  
  
  
  16. 　　} 
    17.

　　这段程序彻底抹杀掉了我这个并行程序的光辉形象，因为这段煞有介事的并行程序，其实是一段串行程序。

　　屏幕前的高手应该看出来了吧，同一段程序的收发，都在同一段循环中。

　　也就意味着，不同段之间的收发是一个接着一个的。也就意味着，其他每个进程各自的排序也是一个接着一个进行的，并不会如我初衷并行排序。

　　想来，这段错误应该是并行程序小白们常犯的错误，所以我也很乐于把我做过的蠢事发出来给大家分享。前车之鉴，警钟长鸣lol

　　改正之后的这段程序是这样的，

 
 
 
    
  
  
  
  1. 　　for(inti = 1;i 
  
  
  
  2. 　　num = (N/(processNum-1));  
    3. 
  
  
  
  3. 　　if(i == processNum -1)  
    4. 
  
  
  
  4. 　　num = N - num * (processNum -2);  
    5. 
  
  
  
  5. 　　///distribute data to each process  
    6. 
  
  
  
  6. 　　printf("Sending to process %d... ", i);  
    7. 
  
  
  
  7. 　　MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);  
    8. 
  
  
  
  8. 　　MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);  
    9. 
  
  
  
  9. 　　}  
    10. 
  
  
  
  10. 　　for(inti = 1;i 
  
  
  
  11. 　　num = (N/(processNum-1));  
    12. 
  
  
  
  12. 　　if(i == processNum -1)  
    13. 
  
  
  
  13. 　　num = N - num * (processNum -2);  
    14. 
  
  
  
  14. 　　///gather the sorted data  
    15. 
  
  
  
  15. 　　printf("Receiving from process %d... ", i);  
    16. 
  
  
  
  16. 　　MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);  
    17. 
  
  
  
  17. 　　///prepare for merge, set the pointers  
    18. 
  
  
  
  18. 　　pointer[i] = (N/(processNum-1)) * (i-1);  
    19. 
  
  
  
  19. 　　secEnd[i] = pointer[i] + N/(processNum-1);  
    20. 
  
  
  
  20. 　　if(i == processNum-1) secEnd[i] = N;  
    21. 
  
  
  
  21. 　　} 
    22.

　　同时程序的效率还可以提升，比如说把其他进程排序的算法换成快排什么的。

　　最后奉上优化后的版本

 
 
 
    
  
  
  
  1. 　　//MPI Hello World demo  
    2. 
  
  
  
  2. 　　#include   
    3. 
  
  
  
  3. 　　#include   
    4. 
  
  
  
  4. 　　#include  //'qsort' is in it.  
    5. 
  
  
  
  5. 　　#include   
    6. 
  
  
  
  6. 　　#include   
    7. 
  
  
  
  7. 　　#defineN 30  
    8. 
  
  
  
  8. 　　intQuickSortCompareFun(constvoid*p1, constvoid*p2)  
    9. 
  
  
  
  9. 　　{  
    10. 
  
  
  
  10. 　　return*((constint*)p1) - *((constint*)p2);  
    11. 
  
  
  
  11. 　　}  
    12. 
  
  
  
  12. 　　intmain(intargc, char** argv)  
    13. 
  
  
  
  13. 　　{  
    14. 
  
  
  
  14. 　　intprocessRank, processNum, t, data, num;  
    15. 
  
  
  
  15. 　　intdataArr[N];  
    16. 
  
  
  
  16. 　　intdataArrB[N];  
    17. 
  
  
  
  17. 　　intpointer[100];  
    18. 
  
  
  
  18. 　　intsecEnd[100];  
    19. 
  
  
  
  19. 　　MPI_Status mpistat;  
    20. 
  
  
  
  20. 　　MPI_Init(&argc, &argv);  
    21. 
  
  
  
  21. 　　MPI_Comm_size(MPI_COMM_WORLD, &processNum);  
    22. 
  
  
  
  22. 　　MPI_Comm_rank(MPI_COMM_WORLD, &processRank);  
    23. 
  
  
  
  23. 　　printf("Yes, Sir! From process %i of %i ", processRank, processNum);  
    24. 
  
  
  
  24. 　　if(processRank == 0)  
    25. 
  
  
  
  25. 　　{  
    26. 
  
  
  
  26. 　　srand(time(NULL));  
    27. 
  
  
  
  27. 　　for(inti = 0;i 
  
  
  
  28. 　　dataArr[i] = rand()%1000;  
    29. 
  
  
  
  29. 　　}  
    30. 
  
  
  
  30. 　　printf("Original Array: ");  
    31. 
  
  
  
  31. 　for(inti = 0;i< N; i++){  
    32. 
  
  
  
  32. 　　printf("%d ", dataArr[i]);  
    33. 
  
  
  
  33. 　　}  
    34. 
  
  
  
  34. 　　printf(" ");  
    35. 
  
  
  
  35. 　　puts("Distribute data to processes");  
    36. 
  
  
  
  36. 　　for(inti = 1;i 
  
  
  
  37. 　　num = (N/(processNum-1));  
    38. 
  
  
  
  38. 　　if(i == processNum -1)  
    39. 
  
  
  
  39. 　　num = N - num * (processNum -2);  
    40. 
  
  
  
  40. 　　///distribute data to each process  
    41. 
  
  
  
  41. 　　printf("Sending to process %d... ", i);  
    42. 
  
  
  
  42. 　　MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);  
    43. 
  
  
  
  43. 　　MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);  
    44. 
  
  
  
  44. 　　}  
    45. 
  
  
  
  45. 　　for(inti = 1;i 
  
  
  
  46. 　　num = (N/(processNum-1));  
    47. 
  
  
  
  47. 　if(i == processNum -1)  
    48. 
  
  
  
  48. 　　num = N - num * (processNum -2);  
    49. 
  
  
  
  49. 　　///gather the sorted data  
    50. 
  
  
  
  50. 　　printf("Receiving from process %d... ", i);  
    51. 
  
  
  
  51. 　　MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);  
    52. 
  
  
  
  52. 　　///prepare for merge, set the pointers  
    53. 
  
  
  
  53. 　　pointer[i] = (N/(processNum-1)) * (i-1);  
    54. 
  
  
  
  54. 　　secEnd[i] = pointer[i] + N/(processNum-1);  
    55. 
  
  
  
  55. 　　if(i == processNum-1) secEnd[i] = N;  
    56. 
  
  
  
  56. 　　}  
    57. 
  
  
  
  57. 　　printf("Sorted Sections Array: ");  
    58. 
  
  
  
  58. 　　for(inti = 0;i< N; i++){  
    59. 
  
  
  
  59. 　　printf("%d ", dataArrB[i]);  
    60. 
  
  
  
  60. 　　}  
    61. 
  
  
  
  61. 　　puts("");  
    62. 
  
  
  
  62. 　　///merge the sorted sections  
    63. 
  
  
  
  63. 　　puts("Merging...");  
    64. 
  
  
  
  64. 　　std::mapdata2rank;  
    65. 
  
  
  
  65. 　　for(t = 1;t 
  
  
  
  66. 　　if(pointer[t] 
  
  
  
  67. 　　data2rank.insert(std::make_pair(dataArrB[pointer[t]], t));  
    68. 
  
  
  
  68. 　　pointer[t]++;  
    69. 
  
  
  
  69. 　　}  
    70. 
  
  
  
  70. 　　}  
    71. 
  
  
  
  71. 　　for(inti = 0;i 
  
  
  
  72. 　　intdata = data2rank.begin()->first;  
    73. 
  
  
  
  73. 　　intrank = data2rank.begin()->second;  
    74. 
  
  
  
  74. 　　dataArr[i] = data;  
    75. 
  
  
  
  75. 　　data2rank.erase(data2rank.begin());  
    76. 
  
  
  
  76. 　　if(pointer[rank] 
  
  
  
  77. 　　{  
    78. 
  
  
  
  78. 　　data2rank.insert(std::make_pair(dataArrB[pointer[rank]], rank));  
    79. 
  
  
  
  79. 　　pointer[rank]++;  
    80. 
  
  
  
  80. 　　}  
    81. 
  
  
  
  81. 　　}  
    82. 
  
  
  
  82. 　　///output the results  
    83. 
  
  
  
  83. 　　printf("Final Sorted Array: ");  
    84. 
  
  
  
  84. 　　for(inti = 0;i< N; i++){  
    85. 
  
  
  
  85. 　　printf("%d ", dataArr[i]);  
    86. 
  
  
  
  86. 　　}  
    87. 
  
  
  
  87. 　　printf(" ");  
    88. 
  
  
  
  88. 　　}  
    89. 
  
  
  
  89. 　　else 
    90. 
  
  
  
  90. 　　{  
    91. 
  
  
  
  91. 　　//receieve the section  
    92. 
  
  
  
  92. 　　MPI_Recv(&num, 1, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);  
    93. 
  
  
  
  93. 　　MPI_Recv(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);  
    94. 
  
  
  
  94. 　　printf("Received Original Array: ");  
    95. 
  
  
  
  95. 　　for(inti = 0;i< num; i++){  
    96. 
  
  
  
  96. 　printf("%d ", dataArr[i]);  
    97. 
  
  
  
  97. 　　}  
    98. 
  
  
  
  98. 　　printf(" ");  
    99. 
  
  
  
  99. 　　//sort this section  
    100. 
  
  
  
  100. 　　qsort(dataArr, num, sizeof(int), QuickSortCompareFun);  
    101. 
  
  
  
  101. 　　MPI_Send(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD);  
    102. 
  
  
  
  102. 　　///display  
    103. 
  
  
  
  103. 　　printf("My Sorted Section: ");  
    104. 
  
  
  
  104. 　　for(inti = 0;i< num; i++){  
    105. 
  
  
  
  105. 　　printf("%d ", dataArr[i]);  
    106. 
  
  
  
  106. 　　}  
    107. 
  
  
  
  107. 　　printf(" ");  
    108. 
  
  
  
  108. 　　}  
    109. 
  
  
  
  109. 　　MPI_Finalize();  
    110. 
  
  
  
  110. 　return0; 
    111.

原文链接：http://www.cnblogs.com/rosting/archive/2011/11/16/2251892.html

【编辑推荐】

  1. 微软发布新版Windows 7及.NET 4软件开发工具包
  2. 详解.NET 4.0并行计算支持历史
  3. 详读.NET 4.0环境配置
  4. 详解.NET 4.0中异常处理方面的新特性
  5. 三方面诠释.NET 4.0的新特性

新闻标题：并行程序VS串行程序——优化实录
链接分享：http://www.shufengxianlan.com/qtweb/news24/138874.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

静态网站知识

同城分类信息

都江堰做网站　　 　定制级高端网站建设　　 　重庆移动网站建设　　 　边坡防护网　　 　腾讯香港虚拟主机　　 　网站推广　　 　成都谷歌推广　　 　成都网站建设　　 　seo推广公司　　 　南部网站建设　　 　成都免费做网站　　 　明安消防器材　　 　成都网站设计　　 　h5页面制作　　 　成都花箱　　 　主机租用　　 　广汉锦华建材　　 　重庆托管服务器　　 　成都网站制作　　 　网站收录