分布式并行处理

武汉理工大学研究生课程论文课程名称分布式并行处理论文题目装箱问题的算法报告专业班级计算机应用1002班学生姓名李霞任课老师袁景凌2010 — 2011 学年第二学期装箱问题的算法报告一．实验环境Visual C++ 6.0，MPICH2二．实验目的（1）通过这次实验，更好的了解装箱问题算法的串行下次适应算法和并行下次适应算法及其思想，对这两个算法进行实现，并分析实验结果。

（2）在（1）的基础上，分析并行算法与串行算法的差别以及并行算法的优越性。

（3）最后通过分析装箱问题的几种算法，理解各种算法的思想及与其他算法相比的优越性。

三．实验内容装箱问题及其串行算法：经典的一维装箱问题(Bin Packing Problem)是指，给定n 件物品的序列12,,,n n L a a a =<> ，物品)1(n i a i ≤≤的大小]1,0()(∈i a s ，要求将这些物品装入单位容量1的箱子12,,,m B B B 中，使得每个箱子中的物品大小之和不超过1，并使所使用的箱子数目m 最小。

下次适应算法（Next Fit Algorithm ）是最早提出的、最简单的一个在线算法，[Joh73]首次仔细分析了下次适应算法的最坏情况性能。

下次适应算法维持一个当前打开的箱子，它依序处理输入物品，当物品到达时检查该物品能否放入这个当前打开的箱子中，若能则放入；否则把物品放入一个新的箱子中，并把这个新箱子作为当前打开的箱子。

算法描述如下： 串行下次适应算法输入：输入物品序列12,,,n L a a a =<> 。

输出：使用的箱子数目m ，各装入物品的箱子12,,,m P B B B =<> 。

procedure NextFit Begin（1）s (B ) = 1 /* 初始化当前打开的箱子B ，令B 已满 */ （2）m = 0 /* 使用箱子计数 */ （3）for i = 1 to n doif s (a i ) + s (B ) ≤ 1 then（i ） s (B ) = s (B ) + s (a i ) /* 把a i 放入B 中 */ else（i ） m = m + 1 /* 使用的箱子数加一 */ （ii ） B = B m /* 新打开箱子B m */ （iii ）s (B ) = s (a i ) /* 把a i 放入B 中 */end if end for End /* NextFit */装箱问题的并行算法：下次适应算法使用一遍扫描物品序列来实现，本身具有固有的顺序性，其时间复杂度为O(n)。

我们使用平衡树和倍增技术对其进行并行化。

首先利用前缀和算法建立一个链表簇，令A[i]为输入物品序列中第i件物品的大小,如果链表指针由A[j]指向A[k]，则表示A[j]+A[j+1]+…+A[k]>1且A[j]+A[j+1]+…+A[k-1]≤1；其后利用倍增技术计算以A[1]为头的链表的长度，而以A(1)为头的链表的长度即是下次适应算法所使用的箱子数目。

接下来利用在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节点恰好是下次适应算法在各箱子中放入的第一个物品的序号；最后，根据各箱子中放入的第一个物品的序号，使用二分法确定各物品所放入的箱子的序号。

并行下次适应算法输入：数组A[1,n]，其中A[i]为输入物品序列中第i个物品的大小。

输出：使用的箱子数目m，每个物品应放入的箱子序号数组B[1,n]。

procedure PNextFitBegin（1）调用求前缀和的并行算法计算F[j]= A[1]+A[2]+…+A[j]（2）for j = 1 to n pardo借助F[j]，使用二分法计算C[0,j]= max{k|A[j]+A[j+1]+…+A[k] ≤1} end for/* 以下（3）-（8），计算下次适应算法使用的箱子数目m */（3）C[0, n+1] = n（4）h = 0（5）for j=1 to n pardo E[0, j]=1 end for（6）while C[h,1] ≠n do（6.1）h = h + 1（6.2）for j = 1 to n pardoif C[h - 1, j] = n then（i）E[h, j] = E[h-1, j]（ii）C[h,j] = C[h - 1,j]else（i）E[h, j] = E[h - 1, j] + E[h - 1,C[h - 1, j] + 1]（ii）C[h, j] = C[h - 1,C[h - 1, j] + 1]end ifend forend while（7）height = h（8）m = E[height, 1]（9）/* 计算D[0, j]=第j个箱子中第一件物品在输入序列中的编号*/for h = height downto 0 dofor j = 1 to n / 2h pardo（i）if j = even then D[h,j] = C[h,D[h-1,j/2]]+1 endif（ii）if j = 1 then D[h,1] = 1 endif（iii）if j = odd > 1 then D[h,j] = D[h-1,[j+1]/2] endifend forend for（10）for j=1 to n pardo /* 计算B[j] = 第j个物品所放入的箱子序号*/使用二分法计算B[j] = max{ k | D[0,k] j , D[0,k+1] >j或者k = m } end forEnd /* PNextFit */四．实验结果五．实验小结装箱问题是NP问题,即在多项式时间内无法精确求解,一般采用近似算法,即启发式算法,这样可以迅速得到满意解,而不一定是最优解。

常见的算法：NF(Next Fit)近似算法，FF(First Fit)近似算法，FFD（First Fit Decreasing）近似算法，BF(best Fit),BFD(Best Fit Deceasing)等。

（1）下次适应算法（NF）：NF算法是最简单也是最早研究的一个算法，它的处理方法是始终维持一个当前打开的箱子，对于每一个要装入的物品，检查该物品是否可以放入当前打开的箱子，如果无法装入，则打开一个空箱子，装入该物品，以该箱子作为当前的箱子，由于每个物品在装入时，只有当前打开的箱子和空箱可以选择，这必然造成装箱的效率低下。

（2）首次适应算法(FF)：针对下次适应算法的缺陷，首次适应算法处理当前物品的时候，检查所有非空箱子，找到第一个能够放下当前物品的箱子并将该物品放入，否则则开启新的箱子。

（3）最佳适应算法(BF)：与首次适应算法类似，唯一的区别时当物品装箱时，不是直接装在第一个可装入的箱子中，而是装入在最适合该物体的箱子中，如果没有该箱子，则开启空箱。

首次适应算法和最佳适应算法有一个缺陷，即由于物品没有实现排序，则可能由于先装入小的物品，使大的物品在后来放入时无法装入，只得开启新的箱子，造成了空间的浪费，因此才有了这两种算法的改进算法。

（1）降序首次适应算法(FFD)：先对物品按降序排序，再按照首次适应算法进行装箱。

（2）降序最佳适应算法(BFD)：先对物品按降序排序，再按照最佳适应算法进行装箱。

这里要求采用BFD算法实现,由于装入的物品是动态的,这里要求用链表来实现,这里使用两个链表,一个是已使用的箱子链表,物体链表,其中物体链表要求降序排列,箱子链表要求按剩余空间升序排序,当物体装箱时,先在箱子链表中找可以放入的箱子,如果可以,则装入,如果仍有空间,则把该箱子重新排列,如果没有合适的箱子,则启用新的箱子,如有剩余,则把该箱子按序放入已装箱队列中.六．源代码#include <stdio.h>#include "math.h"#include "mpi.h"int forint ( float temp){int outint;if( temp >= (floor(temp) + 0.5))outint=floor(temp) + 1;elseoutint=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 group_size1,tmpp;FILE *fp;int lp1，h1,tmp1,lop1,high,mid,flag,fflag;int tmpd,d[100][100],height,m,td;int f[100][100],e[100][100], r[100]; /*output array*/float a[100], /* input array*/s[100],b[100][100],c[100][100],tmp;double starttime,endtime;MPI_Init ( &argc , &argv ); /* Initialze MPI. */starttime = MPI_Wtime(); /* 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( MPI_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 numberis %d\n",pnumber );group_size = pnumber+1;/*主进程:输入数组,输出结果*/if(my_rank == 0){printf ( "my_rank %d\n" ,my_rank );printf ( "Enter %d values(<=1):\n" , pnumber );fp=fopen("data1","rb");for(i = 1;i <= pnumber ; i++ ){fscanf(fp,"%f",&a[i]);if ( a[i] > 1){printf ( "input %fwrong!\n" , a[i] );i = i-1 ;}b[0][i] = a[i];}printf ( "input a[%d]:\n" , pnumber );for ( i = 1 ; i <= pnumber ; i++ ){printf ( "%f\n" , a[i] );}for ( i = 1; i <= pnumber ; i++ ){MPI_Send(&b[0][i],1,MPI_FLOAT,i,i,MPI_C OMM_WORLD);}tmp = log( pnumber ) / log(2);lp = forint( tmp);printf("lp= %d \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(&b[h-1][2*j-1],2,MPI_FLOAT,j,j +h*10,MPI_COMM_WORLD);}for( j = 1 ;j <= lop ; j++ ){MPI_Recv(&b[h][j],1,MPI_FLOAT,j,j+h*10+ 100,MPI_COMM_WORLD,&status);}}for ( i = 1 ; i <= pnumber ; i++ ){MPI_Recv(&c[0][i],1,MPI_FLOAT,i,0,MPI_ COMM_WORLD,&status);}for ( i = 1 ; i <= pnumber ; i++ ){MPI_Send(&c[0][1],pnumber,MPI_FLOAT,i, 1,MPI_COMM_WORLD);}for ( i = 1 ; i <= pnumber ; i++ ){MPI_Recv(&f[0][i],1,MPI_INT,i,0,MPI_CO MM_WORLD,&status);}for ( i = 1 ; i <= pnumber ; i++ ){MPI_Send(&f[0][1],pnumber,MPI_INT,i,2,M PI_COMM_WORLD);}MPI_Recv(&m,1,MPI_INT,1,0,MPI_COMM _WORLD,&status);for ( i = 1 ; i <= m ; i++ ){MPI_Recv(&d[0][i],1,MPI_INT,i,0,MPI_CO MM_WORLD,&status);printf("d 0 %d:%d\n",i,d[0][i]);}for ( i = 1 ; i <= pnumber ; i++ ){MPI_Send(&d[0][1],m,MPI_INT,i,1,MPI_CO MM_WORLD);}}/* 根据主进程传来的数据,计算,得出结果*/else{if ( my_rank <= pnumber ){/* 求前缀和c[0][j]<-a[1]+a[2]+...+a[j] */printf ( "my_rank %d\n" ,my_rank );MPI_Recv(&b[0][my_rank],1,MPI_FLOAT,0 ,my_rank,MPI_COMM_WORLD,&status);tmp1=1;i=0;for(;;){if ( tmp1 < my_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(&b[h1-1][2*my_rank-1],2,MPI_F LOAT,0,my_rank+h1*10,MPI_COMM_WO RLD,&status);b[h1][my_rank] =b[h1-1][2*my_rank-1]+b[h1-1][2*my_rank]; MPI_Send(&b[h1][my_rank],1,MPI_FLOAT, 0,my_rank+100+h1*10,MPI_COMM_WORL D);}for(h1=lp1-i;h1>=0;h1--){if ( my_rank == 1 ){c[h1][my_rank] =b[h1][my_rank] ;if ( h1 > 0 )MPI_Send(&c[h1][my_rank],1,MPI_FLOAT, my_rank*2,my_rank+h1*10,MPI_COMM_W ORLD);if ( h1 > 0 &&2*my_rank+1 < (group_size-1) )MPI_Send(&c[h1][my_rank],1,MPI_FLOAT, my_rank*2+1,my_rank+h1*10,MPI_COMM_ WORLD);}if ( my_rank % 2 == 0 ){MPI_Recv(&c[h1+1][my_rank/2],1,MPI_FL OAT,my_rank/2,my_rank/2+(h1+1)*10,MPI_ COMM_WORLD,&status);c[h1][my_rank] =c[h1+1][my_rank/2];if ( h1 > 0 )MPI_Send(&c[h1][my_rank],1,MPI_FLOAT, my_rank*2,my_rank+h1*10,MPI_COMM_W ORLD);if ( h1 > 0 &&my_rank*2+1 < (group_size-1) )MPI_Send(&c[h1][my_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(&c[h1+1][(my_rank-1)/2],1,MPI_ FLOAT,(my_rank-1)/2,(my_rank-1)/2+(h1+1) *10,MPI_COMM_WORLD,&status);c[h1][my_rank] =c[h1+1][(my_rank-1)/2] + b[h1][my_rank] ;if ( h1 > 0 )MPI_Send(&c[h1][my_rank],1,MPI_FLOAT, my_rank*2,my_rank+h1*10,MPI_COMM_W ORLD);if ( h1 > 0 &&my_rank*2+1 < (group_size-1) )MPI_Send(&c[h1][my_rank],1,MPI_FLOAT, my_rank*2+1,my_rank+h1*10,MPI_COMM_ WORLD);}}MPI_Send(&c[0][my_rank],1,MPI_FLOAT,0, 0,MPI_COMM_WORLD);/*借助c[0][j],计算f[0][j]<-max{k|a[j]+a[j+1]+...+a[k] <= 1}*/MPI_Recv(&c[0][1],group_size-1,MPI_FLO AT,0,1,MPI_COMM_WORLD,&status);c[0][0]=0;for ( i = 1 ; i <= group_size - my_rank ; i++ ){s[i] = c[0][my_rank+i-1] - c[0][my_rank-1] ;}if ( s[group_size-my_rank] <= 1 ) mid = group_size - my_rank ;else{for ( i = 1 ; i <=group_size - my_rank ; i++ ){if ( s[i] > 1 ) break ;}mid = i - 1 ;}f[0][my_rank] = mid +my_rank - 1 ;MPI_Send(&f[0][my_rank],1,MPI_INT,0,0,M PI_COMM_WORLD);/*计算下次适应算法使用的箱子数目m*/MPI_Recv(&f[0][1],group_size-1,MPI_INT,0 ,2,MPI_COMM_WORLD,&status);f[0][group_size] = group_size -1 ;h = 0 ;for ( i = 1 ; i < group_size ;i++ ){e[0][i] = 1 ;}fflag = 0 ;while ( fflag == 0 ){if ( h > 0 ){for ( j = 1 ; j <= group_size - 1 ; j++ ){MPI_Recv(&e[h][j],1,MPI_INT,j,j+h*1000,M PI_COMM_WORLD,&status);MPI_Recv(&f[h][j],1,MPI_INT,j,j+h*1000,M PI_COMM_WORLD,&status);}}if ( f[h][1] == group_size - 1 ){fflag=1 ;}else{h = h + 1 ;if ( f[h-1][my_rank] == group_size - 1 ){e[h][my_rank] = e[h-1][my_rank];f[h][my_rank]=f[h-1][my_rank];}else{t =f[h-1][my_rank] + 1 ;e[h][my_rank] = e[h-1][my_rank] + e[h-1][t] ;f[h][my_rank] = f[h-1][t] ;}for ( i = 1 ; i <group_size ; i++ ){MPI_Send(&e[h][my_rank],1,MPI_INT,i,my_ rank+h*1000,MPI_COMM_WORLD);MPI_Send(&f[h][my_rank],1,MPI_INT,i,my_ rank+h*1000,MPI_COMM_WORLD);}}}height=h;if ( my_rank == 1 ){m = e[height][1] ;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);}/*计算d[0][j]=第j个箱子中第一个物品在输入序列中的编号*/tmpd = 1 ;for ( h = height ; h >= 0 ; h-- ){if ( my_rank <= tmpd && my_rank <= m ){if ( my_rank == 1 ){d[h][1] = 1 ;MPI_Send(&d[h][1],1,MPI_INT,2,h*100+1, MPI_COMM_WORLD);}if ( my_rank % 2 == 0 ){MPI_Recv(&d[h+1][my_rank/2],1,MPI_INT, my_rank/2,(h+1)*100+my_rank/2,MPI_COM M_WORLD,&status);td =d[h+1][my_rank/2] ;d[h][my_rank] = f[h][td] + 1 ;if ( my_rank*2 <= tmpd*2 && my_rank*2 <= m ){MPI_Send(&d[h][my_rank],1,MPI_INT,my_r ank*2,h*100+my_rank,MPI_COMM_WORL D);}if ( my_rank*2 <= tmpd*2 && my_rank*2 - 1 <= m )MPI_Send(&d[h][my_rank],1,MPI_INT,my_r ank*2-1,h*100+my_rank,MPI_COMM_WOR LD);}if ( my_rank % 2 !=0&& my_rank > 1 ){MPI_Recv(&d[h+1][(my_rank+1)/2],1,MPI_I NT,(my_rank+1)/2,(h+1)*100+(my_rank+1)/2 ,MPI_COMM_WORLD,&status);d[h][my_rank] = d[h+1][(my_rank+1)/2] ;if ( my_rank*2 <= tmpd*2 && my_rank*2 <= m ){MPI_Send(&d[h][my_rank],1,MPI_INT,my_r ank*2,h*100+my_rank,MPI_COMM_WORL D);}if ( my_rank*2 <= tmpd*2 && my_rank*2-1 <= m )MPI_Send(&d[h][my_rank],1,MPI_INT,my_r ank*2-1,h*100+my_rank,MPI_COMM_WOR LD);}}tmpd = tmpd * 2 ;}if ( my_rank == 1 )MPI_Send(&m,1,MPI_INT,0,0,MPI_COMM _WORLD);if ( my_rank <= m ){MPI_Send(&d[0][my_rank],1,MPI_INT,0,0, MPI_COMM_WORLD);}/*计算r[j]=第j个物品所放入的箱子序号*/MPI_Recv(&d[0][1],m,MPI_INT,0,1,MPI_C OMM_WORLD,&status);if ( d[0][m] <= my_rank ){r[my_rank] = m ;}else{for ( i = 0 ; i <= m ; i++ ){if ( d[0][i] >my_rank ) break ;}r[my_rank] = i - 1 ;}printf ( "number %d goods put into box %d\n" , my_rank, r[my_rank] );}}endtime = MPI_Wtime();printf(" that tooks %fsecond!\n",endtime-starttime);MPI_Finalize();}。