分布式并行處理

1、學(xué)生學(xué)號(hào)104972101493 論文成績(jī)武漢理工大學(xué)研究生課程論文課程名稱 分布式并行處理 論文題目 裝箱問題的算法報(bào)告 專業(yè)班級(jí) 計(jì)算機(jī)應(yīng)用1002班 學(xué)生姓名 李 霞 任課老師 袁景凌 2010 2011 學(xué)年 第 二 學(xué)期裝箱問題的算法報(bào)告一實(shí)驗(yàn)環(huán)境Visual C+ 6.0，MPICH2二實(shí)驗(yàn)?zāi)康模?）通過這次實(shí)驗(yàn)，更好的了解裝箱問題算法的串行下次適應(yīng)算法和并行下次適應(yīng)算法及其思想，對(duì)這兩個(gè)算法進(jìn)行實(shí)現(xiàn)，并分析實(shí)驗(yàn)結(jié)果。（2）在（1）的基礎(chǔ)上，分析并行算法與串行算法的差別以及并行算法的優(yōu)越性。（3）最后通過分析裝箱問題的幾種算法，理解各種算法的思想及與其他算法相比的優(yōu)越性。三實(shí)驗(yàn)內(nèi)容

2、裝箱問題及其串行算法：經(jīng)典的一維裝箱問題(Bin Packing Problem)是指，給定件物品的序列，物品的大小，要求將這些物品裝入單位容量1的箱子中，使得每個(gè)箱子中的物品大小之和不超過1，并使所使用的箱子數(shù)目最小。下次適應(yīng)算法（Next Fit Algorithm）是最早提出的、最簡(jiǎn)單的一個(gè)在線算法，Joh73首次仔細(xì)分析了下次適應(yīng)算法的最壞情況性能。下次適應(yīng)算法維持一個(gè)當(dāng)前打開的箱子，它依序處理輸入物品，當(dāng)物品到達(dá)時(shí)檢查該物品能否放入這個(gè)當(dāng)前打開的箱子中，若能則放入；否則把物品放入一個(gè)新的箱子中，并把這個(gè)新箱子作為當(dāng)前打開的箱子。算法描述如下：串行下次適應(yīng)算法輸入：輸入物品序列。輸出：

3、使用的箱子數(shù)目m，各裝入物品的箱子。procedure NextFitBegin（1）s(B) = 1/* 初始化當(dāng)前打開的箱子B，令B已滿 */（2）m = 0 /* 使用箱子計(jì)數(shù) */（3）for i = 1 to n doif s(ai) + s(B) 1 then（i） s(B) = s(B) + s(ai) /* 把a(bǔ)i放入B中 */else（i） m = m + 1/* 使用的箱子數(shù)加一 */（ii） B = Bm/* 新打開箱子Bm */（iii）s(B) = s(ai)/* 把a(bǔ)i放入B中 */end ifend forEnd /* NextFit */裝箱問題的并行算法：下次

4、適應(yīng)算法使用一遍掃描物品序列來實(shí)現(xiàn)，本身具有固有的順序性，其時(shí)間復(fù)雜度為O(n)。我們使用平衡樹和倍增技術(shù)對(duì)其進(jìn)行并行化。首先利用前綴和算法建立一個(gè)鏈表簇，令A(yù)i為輸入物品序列中第件物品的大小,如果鏈表指針由Aj指向Ak，則表示Aj+Aj+1+Ak>1且Aj+Aj+1+Ak-1£1；其后利用倍增技術(shù)計(jì)算以A1為頭的鏈表的長(zhǎng)度，而以A(1)為頭的鏈表的長(zhǎng)度即是下次適應(yīng)算法所使用的箱子數(shù)目。接下來利用在上一步驟中產(chǎn)生的中間數(shù)據(jù)反向建立一棵二叉樹，使該二叉樹的葉節(jié)點(diǎn)恰好是下次適應(yīng)算法在各箱子中放入的第一個(gè)物品的序號(hào)；最后，根據(jù)各箱子中放入的第一個(gè)物品的序號(hào)，使用二分法確定各物品所放入

5、的箱子的序號(hào)。并行下次適應(yīng)算法輸入：數(shù)組A1,n，其中Ai為輸入物品序列中第i個(gè)物品的大小。輸出：使用的箱子數(shù)目m，每個(gè)物品應(yīng)放入的箱子序號(hào)數(shù)組B1,n。procedure PNextFitBegin（1）調(diào)用求前綴和的并行算法計(jì)算Fj= A1+A2+Aj（2）for j = 1 to n pardo借助Fj，使用二分法計(jì)算C0,j= maxk|Aj+Aj+1+Ak £1end for/* 以下（3）-（8），計(jì)算下次適應(yīng)算法使用的箱子數(shù)目m */（3）C0, n+1 = n（4）h = 0（5）for j=1 to n pardo E0, j=1 end for（6）while C

6、h,1 ¹ n do（6.1）h = h + 1（6.2）for j = 1 to n pardoif Ch - 1, j = n then（i）Eh, j = Eh-1, j（ii）Ch,j = Ch - 1,jelse（i）Eh, j = Eh - 1, j + Eh - 1,Ch - 1, j + 1（ii）Ch, j = Ch - 1,Ch - 1, j + 1end ifend forend while（7）height = h（8）m = Eheight, 1（9）/* 計(jì)算D0, j=第j個(gè)箱子中第一件物品在輸入序列中的編號(hào) */for h = height downt

7、o 0 dofor j = 1 to n / 2h pardo（i）if j = even then Dh,j = Ch,Dh-1,j/2+1 endif（ii）if j = 1 then Dh,1 = 1 endif（iii）if j = odd > 1 then Dh,j = Dh-1,j+1/2 endifend forend for（10）for j=1 to n pardo /* 計(jì)算Bj = 第j個(gè)物品所放入的箱子序號(hào) */使用二分法計(jì)算Bj = max k | D0,k £j , D0,k+1 >j 或者k = m end forEnd /* PNextFi

8、t */四實(shí)驗(yàn)結(jié)果五實(shí)驗(yàn)小結(jié)裝箱問題是NP問題,即在多項(xiàng)式時(shí)間內(nèi)無法精確求解,一般采用近似算法,即啟發(fā)式算法,這樣可以迅速得到滿意解,而不一定是最優(yōu)解。常見的算法：NF(Next Fit)近似算法，F(xiàn)F(First Fit)近似算法，F(xiàn)FD（First Fit Decreasing）近似算法，BF(best Fit),BFD(Best Fit Deceasing)等。（1）下次適應(yīng)算法（NF）：NF算法是最簡(jiǎn)單也是最早研究的一個(gè)算法，它的處理方法是始終維持一個(gè)當(dāng)前打開的箱子，對(duì)于每一個(gè)要裝入的物品，檢查該物品是否可以放入當(dāng)前打開的箱子，如果無法裝入，則打開一個(gè)空箱子，裝入該物品，以該箱子作為當(dāng)

9、前的箱子，由于每個(gè)物品在裝入時(shí)，只有當(dāng)前打開的箱子和空箱可以選擇，這必然造成裝箱的效率低下。（2）首次適應(yīng)算法(FF)：針對(duì)下次適應(yīng)算法的缺陷，首次適應(yīng)算法處理當(dāng)前物品的時(shí)候，檢查所有非空箱子，找到第一個(gè)能夠放下當(dāng)前物品的箱子并將該物品放入，否則則開啟新的箱子。（3）最佳適應(yīng)算法(BF)：與首次適應(yīng)算法類似，唯一的區(qū)別時(shí)當(dāng)物品裝箱時(shí)，不是直接裝在第一個(gè)可裝入的箱子中，而是裝入在最適合該物體的箱子中，如果沒有該箱子，則開啟空箱。首次適應(yīng)算法和最佳適應(yīng)算法有一個(gè)缺陷，即由于物品沒有實(shí)現(xiàn)排序，則可能由于先裝入小的物品，使大的物品在后來放入時(shí)無法裝入，只得開啟新的箱子，造成了空間的浪費(fèi)，因此才有了這兩

10、種算法的改進(jìn)算法。（1）降序首次適應(yīng)算法(FFD)：先對(duì)物品按降序排序，再按照首次適應(yīng)算法進(jìn)行裝箱。（2）降序最佳適應(yīng)算法(BFD)：先對(duì)物品按降序排序，再按照最佳適應(yīng)算法進(jìn)行裝箱。這里要求采用BFD算法實(shí)現(xiàn),由于裝入的物品是動(dòng)態(tài)的,這里要求用鏈表來實(shí)現(xiàn),這里使用兩個(gè)鏈表,一個(gè)是已使用的箱子鏈表,物體鏈表,其中物體鏈表要求降序排列,箱子鏈表要求按剩余空間升序排序,當(dāng)物體裝箱時(shí),先在箱子鏈表中找可以放入的箱子,如果可以,則裝入,如果仍有空間,則把該箱子重新排列,如果沒有合適的箱子,則啟用新的箱子,如有剩余,則把該箱子按序放入已裝箱隊(duì)列中.六源代碼#include <stdio.h>#

11、include "math.h"#include "mpi.h"int forint ( float temp) int outint; if( temp >= (floor(temp) + 0.5) outint=floor(temp) + 1; else outint=floor(temp); return outint;main ( argc, argv )int argc;char * argv; MPI_Status status; int i，group_size,my_rank, pnumber，h，lp，lop,j,t; int g

12、roup_size1,tmpp; FILE *fp; int lp1，h1,tmp1,lop1,high,mid,flag,fflag; int tmpd,d100100,height,m,td; int f100100,e100100, r100; /*output array*/ float a100, /* input array*/ s100,b100100,c100100,tmp;double starttime,endtime; MPI_Init ( &argc , &argv ); /* Initialze MPI. */ starttime = MPI_Wtim

13、e(); /* Get the number of rank. */ MPI_Comm_size ( MPI_COMM_WORLD , &group_size1 ); MPI_Comm_rank ( MPI_COMM_WORLD , &my_rank ); /* get id of rank*/*if the number of slave processor is less than 2,Abort!*/ if ( group_size1 < 3 ) printf ( "not enough processor!n" ); MPI_Abort ( M

14、PI_COMM_WORLD,99 ); /* calculate the number of use slave processor and the size of input array*/ tmpp = 1; for ( i = 1 ; ; i+ ) tmpp = tmpp * 2; if ( tmpp > group_size1 - 1 ) break ; pnumber = (int)( tmpp / 2 ); printf ( "processor number is %dn",pnumber ); group_size = pnumber+1;/*主進(jìn)程:

15、輸入數(shù)組,輸出結(jié)果*/ if(my_rank = 0) printf ( "my_rank %dn" , my_rank ); printf ( "Enter %d values(<=1):n" , pnumber ); fp=fopen("data1","rb"); for(i = 1;i <= pnumber ; i+ ) fscanf(fp,"%f",&ai); if ( ai > 1) printf ( "input %f wrong!n"

16、, ai ); i = i-1 ; b0i = ai; printf ( "input a%d:n" , pnumber ); for ( i = 1 ; i <= pnumber ; i+ ) printf ( "%fn" , ai ); for ( i = 1; i <= pnumber ; i+ ) MPI_Send(&b0i,1,MPI_FLOAT,i,i,MPI_COMM_WORLD); tmp = log( pnumber ) / log(2); lp = forint( tmp); printf("lp= %d

17、 n",lp); tmp = 1 ; for ( h = 1;h <= lp ; h+ ) tmp = tmp * 2 ; lop =(int)( pnumber / tmp ); for ( j = 1 ;j <= lop ; j+ ) MPI_Send(&bh-12*j-1,2,MPI_FLOAT,j,j+h*10,MPI_COMM_WORLD); for( j = 1 ;j <= lop ; j+ ) MPI_Recv(&bhj,1,MPI_FLOAT,j,j+h*10+100,MPI_COMM_WORLD,&status); for

18、( i = 1 ; i <= pnumber ; i+ ) MPI_Recv(&c0i,1,MPI_FLOAT,i,0,MPI_COMM_WORLD,&status); for ( i = 1 ; i <= pnumber ; i+ ) MPI_Send(&c01,pnumber,MPI_FLOAT,i,1,MPI_COMM_WORLD); for ( i = 1 ; i <= pnumber ; i+ ) MPI_Recv(&f0i,1,MPI_INT,i,0,MPI_COMM_WORLD,&status); for ( i = 1

19、; i <= pnumber ; i+ ) MPI_Send(&f01,pnumber,MPI_INT,i,2,MPI_COMM_WORLD); MPI_Recv(&m,1,MPI_INT,1,0,MPI_COMM_WORLD,&status); for ( i = 1 ; i <= m ; i+ ) MPI_Recv(&d0i,1,MPI_INT,i,0,MPI_COMM_WORLD,&status); printf("d 0 %d:%dn",i,d0i); for ( i = 1 ; i <= pnumber ;

20、 i+ ) MPI_Send(&d01,m,MPI_INT,i,1,MPI_COMM_WORLD); /* 根據(jù)主進(jìn)程傳來的數(shù)據(jù),計(jì)算,得出結(jié)果*/ else if ( my_rank <= pnumber ) /* 求前綴和 c0j<-a1+a2+.+aj */ printf ( "my_rank %dn" , my_rank ); MPI_Recv(&b0my_rank,1,MPI_FLOAT,0,my_rank,MPI_COMM_WORLD,&status); tmp1=1; i=0; for(;) if ( tmp1 < m

21、y_rank ) i+; tmp1 = tmp1 * 2 ; else break ; tmp = log( group_size-1 ) / log(2); lp1 = forint ( tmp ); for(h1=1;h1<=lp1-i;h1+) MPI_Recv(&bh1-12*my_rank-1,2,MPI_FLOAT,0,my_rank+h1*10,MPI_COMM_WORLD,&status); bh1my_rank = bh1-12*my_rank-1+bh1-12*my_rank; MPI_Send(&bh1my_rank,1,MPI_FLOAT,

22、0,my_rank+100+h1*10,MPI_COMM_WORLD); for(h1=lp1-i;h1>=0;h1-) if ( my_rank = 1 ) ch1my_rank = bh1my_rank ; if ( h1 > 0 ) MPI_Send(&ch1my_rank,1,MPI_FLOAT,my_rank*2,my_rank+h1*10,MPI_COMM_WORLD); if ( h1 > 0 && 2*my_rank+1 < (group_size-1) ) MPI_Send(&ch1my_rank,1,MPI_FLOAT

23、,my_rank*2+1,my_rank+h1*10,MPI_COMM_WORLD); if ( my_rank % 2 = 0 ) MPI_Recv(&ch1+1my_rank/2,1,MPI_FLOAT,my_rank/2,my_rank/2+(h1+1)*10,MPI_COMM_WORLD,&status); ch1my_rank = ch1+1my_rank/2; if ( h1 > 0 )MPI_Send(&ch1my_rank,1,MPI_FLOAT,my_rank*2,my_rank+h1*10,MPI_COMM_WORLD); if ( h1 &g

24、t; 0 && my_rank*2+1 < (group_size-1) ) MPI_Send(&ch1my_rank,1,MPI_FLOAT,my_rank*2+1,my_rank+h1*10,MPI_COMM_WORLD); if ( my_rank % 2 != 0 && my_rank > 1 ) MPI_Recv(&ch1+1(my_rank-1)/2,1,MPI_FLOAT,(my_rank-1)/2,(my_rank-1)/2+(h1+1)*10,MPI_COMM_WORLD,&status); ch1my_ra

25、nk = ch1+1(my_rank-1)/2 + bh1my_rank ; if ( h1 > 0 ) MPI_Send(&ch1my_rank,1,MPI_FLOAT,my_rank*2,my_rank+h1*10,MPI_COMM_WORLD); if ( h1 > 0 && my_rank*2+1 < (group_size-1) ) MPI_Send(&ch1my_rank,1,MPI_FLOAT,my_rank*2+1,my_rank+h1*10,MPI_COMM_WORLD); MPI_Send(&c0my_rank,1,

26、MPI_FLOAT,0,0,MPI_COMM_WORLD);/*借助c0j,計(jì)算f0j<-maxk|aj+aj+1+.+ak <= 1*/ MPI_Recv(&c01,group_size-1,MPI_FLOAT,0,1,MPI_COMM_WORLD,&status); c00=0; for ( i = 1 ; i <= group_size - my_rank ; i+ ) si = c0my_rank+i-1 - c0my_rank-1 ; if ( sgroup_size-my_rank <= 1 ) mid = group_size - my_r

27、ank ; else for ( i = 1 ; i <= group_size - my_rank ; i+ ) if ( si > 1 ) break ; mid = i - 1 ; f0my_rank = mid + my_rank - 1 ; MPI_Send(&f0my_rank,1,MPI_INT,0,0,MPI_COMM_WORLD);/*計(jì)算下次適應(yīng)算法使用的箱子數(shù)目 m*/ MPI_Recv(&f01,group_size-1,MPI_INT,0,2,MPI_COMM_WORLD,&status); f0group_size = group

28、_size - 1 ; h = 0 ; for ( i = 1 ; i < group_size ; i+ ) e0i = 1 ; fflag = 0 ; while ( fflag = 0 ) if ( h > 0 ) for ( j = 1 ; j <= group_size - 1 ; j+ ) MPI_Recv(&ehj,1,MPI_INT,j,j+h*1000,MPI_COMM_WORLD,&status); MPI_Recv(&fhj,1,MPI_INT,j,j+h*1000,MPI_COMM_WORLD,&status); if

29、( fh1 = group_size - 1 ) fflag=1 ; else h = h + 1 ; if ( fh-1my_rank = group_size - 1 ) ehmy_rank = eh-1my_rank; fhmy_rank=fh-1my_rank; else t = fh-1my_rank + 1 ; ehmy_rank = eh-1my_rank + eh-1t ; fhmy_rank = fh-1t ; for ( i = 1 ; i < group_size ; i+ ) MPI_Send(&ehmy_rank,1,MPI_INT,i,my_rank+

30、h*1000,MPI_COMM_WORLD); MPI_Send(&fhmy_rank,1,MPI_INT,i,my_rank+h*1000,MPI_COMM_WORLD); height=h; if ( my_rank = 1 ) m = eheight1 ; for ( i = 2 ; i < group_size ; i+ ) MPI_Send(&m,1,MPI_INT,i,2,MPI_COMM_WORLD); else MPI_Recv(&m,1,MPI_INT,1,2,MPI_COMM_WORLD,&status); /*計(jì)算d0j=第j個(gè)箱子中

31、第一個(gè)物品在輸入序列中的編號(hào)*/ tmpd = 1 ; for ( h = height ; h >= 0 ; h- ) if ( my_rank <= tmpd && my_rank <= m ) if ( my_rank = 1 ) dh1 = 1 ; MPI_Send(&dh1,1,MPI_INT,2,h*100+1,MPI_COMM_WORLD); if ( my_rank % 2 = 0 ) MPI_Recv(&dh+1my_rank/2,1,MPI_INT,my_rank/2,(h+1)*100+my_rank/2,MPI_COMM_WORLD,&status); td = dh+1my_rank/2 ; dhmy_rank = fhtd + 1 ; if ( my_rank*2 <= tmpd*2 && my_rank*2 <= m ) MPI_Send(&dhmy_rank,1,MPI_INT,my_rank*2,h*100+my_rank,MPI_COMM_WORLD); if ( my_rank*2 <= tmpd*2 && my_rank*2 - 1 <= m ) MPI_Send(&dhmy_rank,1