自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

并行程序VS串行程序——優(yōu)化實錄

作者：Rosting
開發(fā) 開發(fā)工具
透過MPI寫成一個并行排序程序，但其實這是一個偽并行程序，其實質(zhì)還是一個串行程序。那么究竟該怎么對比他們呢？

　　在多核處理器、超級計算機日益普及的今天，程序員們怎能對并行程序“袖手旁觀”呢？

　　為了練手，我用MPI寫了一個并行排序程序，

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

　　使用MPI在各個進程之間進行通信，

　　1. 進程0生成隨機數(shù)，并且講數(shù)據(jù)分段，將各段數(shù)據(jù)分配給其他進程

　　2. 其他進程收到數(shù)據(jù)段，使用冒泡排序進行，發(fā)送回進程0

　　3. 進程0收到這些數(shù)據(jù)，通過歸并排序按順序整合起來。

　　下面是這個版本代碼，

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

　　自己寫出之后當然高興，不過程序經(jīng)過高手檢查之后，提出了一些問題。

　　最要命的是這個

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

　　這段程序徹底抹殺掉了我這個并行程序的光輝形象，因為這段煞有介事的并行程序，其實是一段串行程序。

　　屏幕前的高手應該看出來了吧，同一段程序的收發(fā)，都在同一段循環(huán)中。

　　也就意味著，不同段之間的收發(fā)是一個接著一個的。也就意味著，其他每個進程各自的排序也是一個接著一個進行的，并不會如我初衷并行排序。

　　想來，這段錯誤應該是并行程序小白們常犯的錯誤，所以我也很樂于把我做過的蠢事發(fā)出來給大家分享。前車之鑒，警鐘長鳴lol

　　改正之后的這段程序是這樣的，

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

　　同時程序的效率還可以提升，比如說把其他進程排序的算法換成快排什么的。

　　最后奉上優(yōu)化后的版本

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

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

[[50028]]

【編輯推薦】

  1. 微軟發(fā)布新版Windows 7及.NET 4軟件開發(fā)工具包
  2. 詳解.NET 4.0并行計算支持歷史
  3. 詳讀.NET 4.0環(huán)境配置
  4. 詳解.NET 4.0中異常處理方面的新特性
  5. 三方面詮釋.NET 4.0的新特性
責任編輯：彭凡 來源： 博客園
并行程序
相關(guān)推薦

2013-12-16 16:49:57

OpenMP

2013-12-16 16:58:47

OpenMP并行

2012-03-12 12:34:02

JavaF#

2010-06-03 19:28:02

Hadoop

2020-02-26 09:42:15

主存程序存儲器

2013-05-14 10:53:41

AIR Android真機運行

2016-03-28 10:00:09

Swift命令程序

2019-04-16 06:50:34

2023-03-31 08:44:55

Go開發(fā)命令

2021-04-21 07:53:12

JavaScript單行程序

2021-04-19 11:30:06

Java開發(fā)程序

2012-04-26 13:36:30

iPhone運行程序

2010-07-15 10:58:23

Perl命令行程序

2010-02-26 13:03:31

Python腳本語言

2022-02-04 22:05:19

JVM程序內(nèi)存模型

2011-09-19 19:21:54

linux

2013-05-14 10:41:31

2010-02-24 15:41:53

Python解釋器

2015-07-15 10:32:44

Node.js命令行程序

2013-10-31 15:47:29

CloudaApp
點贊
收藏

51CTO技術(shù)棧公眾號