有声读物,欢乐颂第一季免费阅读,绝色狂妃仙魅小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

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

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

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比鎮(zhèn)平網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式鎮(zhèn)平網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋鎮(zhèn)平地區(qū)。費(fèi)用合理售后完善，十年實(shí)體公司更值得信賴。

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

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

　　使用MPI在各個(gè)進(jìn)程之間進(jìn)行通信，

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

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

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

　　下面是這個(gè)版本代碼，

 
 
 
  
  
  　　//MPI Hello World demo  
  
  
  　　#include   
  
  
  　　#include   
  
  
  　　#include   
  
  
  　　#include   
  
  
  　　#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 
  
  
  
　　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 
  
  
  
　　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 
  
  
  
　　inttMin = 1;  
  
  
  　　intmin = 10000;  
  
  
  　　for(t = 1;t 
  
  
  
　　if(pointer[t] 
  
  
  
　　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 
  
  
  
　　for(intj = num-1;j>=i+1;j--)  
  
  
  　　if(dataArr[j] 
  
  
  
　　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;  
  
  
  　　}

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

　　最要命的是這個(gè)

 
 
 
  
  
  　　for(inti = 1;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;  
  
  
  　　}

　　這段程序徹底抹殺掉了我這個(gè)并行程序的光輝形象，因?yàn)檫@段煞有介事的并行程序，其實(shí)是一段串行程序。

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

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

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

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

 
 
 
  
  
  　　for(inti = 1;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 
  
  
  
　　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;  
  
  
  　　}

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

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

 
 
 
  
  
  　　//MPI Hello World demo  
  
  
  　　#include   
  
  
  　　#include   
  
  
  　　#include  //'qsort' is in it.  
  
  
  　　#include   
  
  
  　　#include   
  
  
  　　#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 
  
  
  
　　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 
  
  
  
　　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 
  
  
  
　　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::mapdata2rank;  
  
  
  　　for(t = 1;t 
  
  
  
　　if(pointer[t] 
  
  
  
　　data2rank.insert(std::make_pair(dataArrB[pointer[t]], t));  
  
  
  　　pointer[t]++;  
  
  
  　　}  
  
  
  　　}  
  
  
  　　for(inti = 0;i 
  
  
  
　　intdata = data2rank.begin()->first;  
  
  
  　　intrank = data2rank.begin()->second;  
  
  
  　　dataArr[i] = data;  
  
  
  　　data2rank.erase(data2rank.begin());  
  
  
  　　if(pointer[rank] 
  
  
  
　　{  
  
  
  　　data2rank.insert(std::make_pair(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

【編輯推薦】

微軟發(fā)布新版Windows 7及.NET 4軟件開發(fā)工具包
詳解.NET 4.0并行計(jì)算支持歷史
詳讀.NET 4.0環(huán)境配置
詳解.NET 4.0中異常處理方面的新特性
三方面詮釋.NET 4.0的新特性

新聞標(biāo)題：并行程序VS串行程序——優(yōu)化實(shí)錄
文章地址：http://m.fisionsoft.com.cn/article/dhghoeh.html

新聞中心

其他資訊