并行程序VS串行程序——優化實錄
作者：Rosting
透過MPI寫成一個并行排序程序，但其實這是一個偽并行程序，其實質還是一個串行程序。那么究竟該怎么對比他們呢？
在多核處理器、超級計算機日益普及的今天，程序員們怎能對并行程序“袖手旁觀”呢？
為了練手，我用MPI寫了一個并行排序程序，
先介紹下我的第一個版本，大概的思路是：
使用MPI在各個進程之間進行通信，
1. 進程0生成隨機數，并且講數據分段，將各段數據分配給其他進程
2. 其他進程收到數據段，使用冒泡排序進行，發送回進程0
3. 進程0收到這些數據，通過歸并排序按順序整合起來。
下面是這個版本代碼，
- //MPI Hello World demo
- #include <mpi.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #defineN 30
- intmain(intargc, char** argv)
- {
- intprocessRank, processNum, t, data, num;
- intdataArr[N];
- intdataArrB[N];
- intpointer[100];
- intsecEnd[100];
- MPI_Status mpistat;
- MPI_Init(&argc, &argv);
- MPI_Comm_size(MPI_COMM_WORLD, &processNum);
- MPI_Comm_rank(MPI_COMM_WORLD, &processRank);
- printf("Yes, Sir! From process %i of %i ", processRank, processNum);
- if(processRank == 0)
- {
- srand(time(NULL));
- for(inti = 0;i <N; i++){
- dataArr[i] = rand()%1000;
- }
- printf("Original Array: ");
- for(inti = 0;i< N; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- puts("Distribute data to processes");
- for(inti = 1;i <processNum; i++){
- num = (N/(processNum-1));
- if(i == processNum -1)
- num = N - num * (processNum -2);
- ///distribute data to each process
- printf("Sending to process %d... ", i);
- MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);
- MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);
- ///gather the sorted data
- printf("Receiving from process %d... ", i);
- MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);
- ///prepare for merge, set the pointers
- pointer[i] = (N/(processNum-1)) * (i-1);
- secEnd[i] = pointer[i] + N/(processNum-1);
- if(i == processNum-1) secEnd[i] = N;
- }
- printf("Sorted Sections Array: ");
- for(inti = 0;i< N; i++){
- printf("%d ", dataArrB[i]);
- }
- puts("");
- ///merge the sorted sections
- puts("Merging...");
- for(inti = 0;i <N; i++){
- inttMin = 1;
- intmin = 10000;
- for(t = 1;t <processNum; t++){
- if(pointer[t] <secEnd[t] &&dataArrB[pointer[t]] <min){
- min = dataArrB[pointer[t]];
- tMin = t;
- }
- }
- dataArr[i] = dataArrB[pointer[tMin]];
- pointer[tMin]++;
- }
- ///output the results
- printf("Final Sorted Array: ");
- for(inti = 0;i< N; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- }
- else
- {
- //receieve the section
- MPI_Recv(&num, 1, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);
- MPI_Recv(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);
- printf("Received Original Array: ");
- for(inti = 0;i< num; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- //sort this section
- for(inti = 0;i <num -1;i++)
- for(intj = num-1;j>=i+1;j--)
- if(dataArr[j] <dataArr[j-1]){
- inttmp = dataArr[j];
- dataArr[j]= dataArr[j-1];
- dataArr[j-1] = tmp;
- }
- MPI_Send(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD);
- ///display
- printf("My Sorted Section: ");
- for(inti = 0;i< num; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- }
- MPI_Finalize();
- return0;
- }
自己寫出之后當然高興，不過程序經過高手檢查之后，提出了一些問題。
最要命的是這個
- for(inti = 1;i <processNum; i++){
- num = (N/(processNum-1));
- if(i == processNum -1)
- num = N - num * (processNum -2);
- ///distribute data to each process
- printf("Sending to process %d... ", i);
- MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);
- MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);
- ///gather the sorted data
- printf("Receiving from process %d... ", i);
- MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);
- ///prepare for merge, set the pointers
- pointer[i] = (N/(processNum-1)) * (i-1);
- secEnd[i] = pointer[i] + N/(processNum-1);
- if(i == processNum-1) secEnd[i] = N;
- }
這段程序徹底抹殺掉了我這個并行程序的光輝形象，因為這段煞有介事的并行程序，其實是一段串行程序。
屏幕前的高手應該看出來了吧，同一段程序的收發，都在同一段循環中。
也就意味著，不同段之間的收發是一個接著一個的。也就意味著，其他每個進程各自的排序也是一個接著一個進行的，并不會如我初衷并行排序。
想來，這段錯誤應該是并行程序小白們常犯的錯誤，所以我也很樂于把我做過的蠢事發出來給大家分享。前車之鑒，警鐘長鳴lol
改正之后的這段程序是這樣的，
- for(inti = 1;i <processNum; i++){
- num = (N/(processNum-1));
- if(i == processNum -1)
- num = N - num * (processNum -2);
- ///distribute data to each process
- printf("Sending to process %d... ", i);
- MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);
- MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);
- }
- for(inti = 1;i <processNum; i++){
- num = (N/(processNum-1));
- if(i == processNum -1)
- num = N - num * (processNum -2);
- ///gather the sorted data
- printf("Receiving from process %d... ", i);
- MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);
- ///prepare for merge, set the pointers
- pointer[i] = (N/(processNum-1)) * (i-1);
- secEnd[i] = pointer[i] + N/(processNum-1);
- if(i == processNum-1) secEnd[i] = N;
- }
同時程序的效率還可以提升，比如說把其他進程排序的算法換成快排什么的。
最后奉上優化后的版本
- //MPI Hello World demo
- #include <mpi.h>
- #include <stdio.h>
- #include <stdlib.h> //'qsort' is in it.
- #include <time.h>
- #include <map>
- #defineN 30
- intQuickSortCompareFun(constvoid*p1, constvoid*p2)
- {
- return*((constint*)p1) - *((constint*)p2);
- }
- intmain(intargc, char** argv)
- {
- intprocessRank, processNum, t, data, num;
- intdataArr[N];
- intdataArrB[N];
- intpointer[100];
- intsecEnd[100];
- MPI_Status mpistat;
- MPI_Init(&argc, &argv);
- MPI_Comm_size(MPI_COMM_WORLD, &processNum);
- MPI_Comm_rank(MPI_COMM_WORLD, &processRank);
- printf("Yes, Sir! From process %i of %i ", processRank, processNum);
- if(processRank == 0)
- {
- srand(time(NULL));
- for(inti = 0;i <N; i++){
- dataArr[i] = rand()%1000;
- }
- printf("Original Array: ");
- for(inti = 0;i< N; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- puts("Distribute data to processes");
- for(inti = 1;i <processNum; i++){
- num = (N/(processNum-1));
- if(i == processNum -1)
- num = N - num * (processNum -2);
- ///distribute data to each process
- printf("Sending to process %d... ", i);
- MPI_Send(&num, 1, MPI_INT, i, 55, MPI_COMM_WORLD);
- MPI_Send(&dataArr[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD);
- }
- for(inti = 1;i <processNum; i++){
- num = (N/(processNum-1));
- if(i == processNum -1)
- num = N - num * (processNum -2);
- ///gather the sorted data
- printf("Receiving from process %d... ", i);
- MPI_Recv(&dataArrB[(N/(processNum-1)) * (i-1)], num, MPI_INT, i, 55, MPI_COMM_WORLD, &mpistat);
- ///prepare for merge, set the pointers
- pointer[i] = (N/(processNum-1)) * (i-1);
- secEnd[i] = pointer[i] + N/(processNum-1);
- if(i == processNum-1) secEnd[i] = N;
- }
- printf("Sorted Sections Array: ");
- for(inti = 0;i< N; i++){
- printf("%d ", dataArrB[i]);
- }
- puts("");
- ///merge the sorted sections
- puts("Merging...");
- std::map<int, int>data2rank;
- for(t = 1;t <processNum; t++){
- if(pointer[t] <secEnd[t]){
- data2rank.insert(std::make_pair<int, int>(dataArrB[pointer[t]], t));
- pointer[t]++;
- }
- }
- for(inti = 0;i <N; i++){
- intdata = data2rank.begin()->first;
- intrank = data2rank.begin()->second;
- dataArr[i] = data;
- data2rank.erase(data2rank.begin());
- if(pointer[rank] <secEnd[rank])
- {
- data2rank.insert(std::make_pair<int, int>(dataArrB[pointer[rank]], rank));
- pointer[rank]++;
- }
- }
- ///output the results
- printf("Final Sorted Array: ");
- for(inti = 0;i< N; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- }
- else
- {
- //receieve the section
- MPI_Recv(&num, 1, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);
- MPI_Recv(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD, &mpistat);
- printf("Received Original Array: ");
- for(inti = 0;i< num; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- //sort this section
- qsort(dataArr, num, sizeof(int), QuickSortCompareFun);
- MPI_Send(&dataArr[0], num, MPI_INT, 0, 55, MPI_COMM_WORLD);
- ///display
- printf("My Sorted Section: ");
- for(inti = 0;i< num; i++){
- printf("%d ", dataArr[i]);
- }
- printf(" ");
- }
- MPI_Finalize();
- return0;
原文鏈接：http://www.cnblogs.com/rosting/archive/2011/11/16/2251892.html
【編輯推薦】
責任編輯：彭凡
來源：
博客園
