box.c
上传用户:hhyinxing
上传日期:2013-09-10
资源大小:833k
文件大小:12k
源码类别:

并行计算

开发平台:

Unix_Linux

  1. #include <stdio.h>
  2. #include "math.h"
  3. #include "mpi.h"
  4. int forint ( float temp)
  5. {
  6.     int outint;
  7.     if( temp >= (floor(temp) + 0.5))
  8.         outint=floor(temp) + 1;
  9.     else
  10.         outint=floor(temp);
  11.     return outint;
  12. }
  13. main ( argc, argv )
  14. int argc;
  15. char * argv[];
  16. {
  17.     MPI_Status status;
  18.     int     i,
  19.         group_size,
  20.         my_rank,
  21.         pnumber,                                  /* to store number of used slave processors */
  22.         h,
  23.         lp,
  24.         lop,
  25.         j,
  26.         t;
  27.     int     group_size1,                          /* number of rank*/
  28.         tmpp;
  29.     FILE    *fp;
  30.     int     lp1,
  31.         h1,
  32.         tmp1,
  33.         lop1,
  34.         high,
  35.         mid,
  36.         flag,
  37.         fflag;
  38.     int     tmpd,
  39.         d[100][100],
  40.         height,
  41.         m,                                        /* number of box*/
  42.         td;
  43.     int     f[100][100],
  44.         e[100][100],
  45.         r[100];                                   /*output array*/
  46.     float   a[100],                               /* input array*/
  47.         s[100],
  48.         b[100][100],
  49.         c[100][100],
  50.         tmp;
  51.     double starttime,endtime;
  52.     MPI_Init ( &argc , &argv );                   /* Initialze MPI. */
  53.     starttime = MPI_Wtime();
  54.                                                   /* Get the number of rank. */
  55.     MPI_Comm_size ( MPI_COMM_WORLD , &group_size1 );
  56.     MPI_Comm_rank ( MPI_COMM_WORLD , &my_rank );  /* get id of rank*/
  57. /*if the number of slave processor is less than 2,Abort!*/
  58.     if ( group_size1 < 3 )
  59.     {
  60.         printf ( "not enough processor!n" );
  61.         MPI_Abort ( MPI_COMM_WORLD,99 );
  62.     }
  63. /* calculate the number of use slave processor and the size of input array*/
  64.     tmpp = 1;
  65.     for ( i = 1 ; ; i++ )
  66.     {
  67.         tmpp = tmpp * 2;
  68.         if ( tmpp > group_size1 - 1 ) break ;
  69.     }
  70.     pnumber = (int)( tmpp / 2 );
  71.     printf ( "processor number is %dn",pnumber );
  72.     group_size = pnumber+1;
  73. /*主进程:输入数组,输出结果*/
  74.     if(my_rank == 0)
  75.     {
  76.         printf ( "my_rank %dn" , my_rank );
  77.         printf ( "Enter %d values(<=1):n" , pnumber );
  78.         fp=fopen("data1","rb");
  79.         for(i = 1;i <= pnumber ; i++ )
  80.         {
  81.             fscanf(fp,"%f",&a[i]);
  82.             if ( a[i] > 1)
  83.             {
  84.                 printf ( "input %f wrong!n" , a[i] );
  85.                 i = i-1 ;
  86.             }
  87.             b[0][i] = a[i];
  88.         }
  89.         printf ( "input a[%d]:n" , pnumber );
  90.         for ( i = 1 ; i <= pnumber ; i++ )
  91.         {
  92.             printf ( "%fn" , a[i] );
  93.         }
  94.         for ( i = 1; i <= pnumber ; i++ )
  95.         {
  96.             MPI_Send(&b[0][i],1,MPI_FLOAT,i,i,MPI_COMM_WORLD);
  97.         }
  98.         tmp = log( pnumber ) / log(2);
  99.         lp = forint( tmp);
  100.         printf("lp= %d n",lp);
  101.         tmp = 1 ;
  102.         for ( h = 1;h <= lp ; h++ )
  103.         {
  104.             tmp = tmp * 2 ;
  105.             lop =(int)( pnumber / tmp  );
  106.             for ( j = 1 ;j <= lop ; j++ )
  107.             {
  108.                 MPI_Send(&b[h-1][2*j-1],2,MPI_FLOAT,j,j+h*10,MPI_COMM_WORLD);
  109.             }
  110.             for( j = 1 ;j <= lop ; j++ )
  111.             {
  112.                 MPI_Recv(&b[h][j],1,MPI_FLOAT,j,j+h*10+100,MPI_COMM_WORLD,&status);
  113.             }
  114.         }
  115.         for ( i = 1 ; i <= pnumber ; i++ )
  116.         {
  117.             MPI_Recv(&c[0][i],1,MPI_FLOAT,i,0,MPI_COMM_WORLD,&status);
  118.         }
  119.         for ( i = 1 ; i <= pnumber ; i++ )
  120.         {
  121.             MPI_Send(&c[0][1],pnumber,MPI_FLOAT,i,1,MPI_COMM_WORLD);
  122.         }
  123.         for ( i = 1 ; i <= pnumber ; i++ )
  124.         {
  125.             MPI_Recv(&f[0][i],1,MPI_INT,i,0,MPI_COMM_WORLD,&status);
  126.         }
  127.         for ( i = 1 ; i <= pnumber ; i++ )
  128.         {
  129.             MPI_Send(&f[0][1],pnumber,MPI_INT,i,2,MPI_COMM_WORLD);
  130.         }
  131.         MPI_Recv(&m,1,MPI_INT,1,0,MPI_COMM_WORLD,&status);
  132.         for ( i = 1 ; i <= m ; i++ )
  133.         {
  134.             MPI_Recv(&d[0][i],1,MPI_INT,i,0,MPI_COMM_WORLD,&status);
  135.             printf("d 0 %d:%dn",i,d[0][i]);
  136.         }
  137.         for ( i = 1 ; i <= pnumber ; i++ )
  138.         {
  139.             MPI_Send(&d[0][1],m,MPI_INT,i,1,MPI_COMM_WORLD);
  140.         }
  141.     }
  142. /* 根据主进程传来的数据,计算,得出结果*/
  143.     else
  144.     {
  145.         if ( my_rank <= pnumber )
  146.         {
  147. /* 求前缀和 c[0][j]<-a[1]+a[2]+...+a[j] */
  148.             printf ( "my_rank %dn" , my_rank );
  149.             MPI_Recv(&b[0][my_rank],1,MPI_FLOAT,0,my_rank,MPI_COMM_WORLD,&status);
  150.             tmp1=1;
  151.             i=0;
  152.             for(;;)
  153.             {
  154.                 if ( tmp1 < my_rank )
  155.                 {
  156.                     i++;
  157.                     tmp1 = tmp1 * 2 ;
  158.                 }
  159.                 else break ;
  160.             }
  161.             tmp = log( group_size-1 ) / log(2);
  162.             lp1 = forint ( tmp );
  163.             for(h1=1;h1<=lp1-i;h1++)
  164.             {
  165.                 MPI_Recv(&b[h1-1][2*my_rank-1],2,MPI_FLOAT,0,my_rank+h1*10,MPI_COMM_WORLD,&status);
  166.                 b[h1][my_rank] = b[h1-1][2*my_rank-1]+b[h1-1][2*my_rank];
  167.                 MPI_Send(&b[h1][my_rank],1,MPI_FLOAT,0,my_rank+100+h1*10,MPI_COMM_WORLD);
  168.             }
  169.             for(h1=lp1-i;h1>=0;h1--)
  170.             {
  171.                 if ( my_rank == 1 )
  172.                 {
  173.                     c[h1][my_rank] = b[h1][my_rank] ;
  174.                     if ( h1 > 0 )
  175.                         MPI_Send(&c[h1][my_rank],1,MPI_FLOAT,my_rank*2,my_rank+h1*10,MPI_COMM_WORLD);
  176.                     if ( h1 > 0 && 2*my_rank+1 < (group_size-1) )
  177.                         MPI_Send(&c[h1][my_rank],1,MPI_FLOAT,my_rank*2+1,my_rank+h1*10,MPI_COMM_WORLD);
  178.                 }
  179.                 if ( my_rank % 2 == 0 )
  180.                 {
  181.                     MPI_Recv(&c[h1+1][my_rank/2],1,MPI_FLOAT,my_rank/2,my_rank/2+(h1+1)*10,MPI_COMM_WORLD,&status);
  182.                     c[h1][my_rank] = c[h1+1][my_rank/2];
  183.                     if ( h1 > 0 )
  184.                         MPI_Send(&c[h1][my_rank],1,MPI_FLOAT,my_rank*2,my_rank+h1*10,MPI_COMM_WORLD);
  185.                     if ( h1 > 0 && my_rank*2+1 < (group_size-1) )
  186.                         MPI_Send(&c[h1][my_rank],1,MPI_FLOAT,my_rank*2+1,my_rank+h1*10,MPI_COMM_WORLD);
  187.                 }
  188.                 if ( my_rank % 2 != 0 && my_rank > 1 )
  189.                 {
  190.                     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);
  191.                     c[h1][my_rank] = c[h1+1][(my_rank-1)/2] + b[h1][my_rank] ;
  192.                     if ( h1 > 0 )
  193.                         MPI_Send(&c[h1][my_rank],1,MPI_FLOAT,my_rank*2,my_rank+h1*10,MPI_COMM_WORLD);
  194.                     if ( h1 > 0 && my_rank*2+1 < (group_size-1) )
  195.                         MPI_Send(&c[h1][my_rank],1,MPI_FLOAT,my_rank*2+1,my_rank+h1*10,MPI_COMM_WORLD);
  196.                 }
  197.             }
  198.             MPI_Send(&c[0][my_rank],1,MPI_FLOAT,0,0,MPI_COMM_WORLD);
  199. /*借助c[0][j],计算f[0][j]<-max{k|a[j]+a[j+1]+...+a[k] <= 1}*/
  200.             MPI_Recv(&c[0][1],group_size-1,MPI_FLOAT,0,1,MPI_COMM_WORLD,&status);
  201.             c[0][0]=0;
  202.             for ( i = 1 ; i <= group_size - my_rank ; i++ )
  203.             {
  204.                 s[i] = c[0][my_rank+i-1] - c[0][my_rank-1] ;
  205.             }
  206.             if ( s[group_size-my_rank] <= 1 ) mid = group_size - my_rank ;
  207.             else
  208.             {
  209.                 for ( i = 1 ; i <= group_size - my_rank ; i++ )
  210.                 {
  211.                     if ( s[i] > 1 )  break ;
  212.                 }
  213.                 mid = i - 1 ;
  214.             }
  215.             f[0][my_rank] = mid + my_rank - 1 ;
  216.             MPI_Send(&f[0][my_rank],1,MPI_INT,0,0,MPI_COMM_WORLD);
  217. /*计算下次适应算法使用的箱子数目 m*/
  218.             MPI_Recv(&f[0][1],group_size-1,MPI_INT,0,2,MPI_COMM_WORLD,&status);
  219.             f[0][group_size] = group_size - 1 ;
  220.             h = 0 ;
  221.             for ( i = 1 ; i < group_size ; i++ )
  222.             {
  223.                 e[0][i] = 1 ;
  224.             }
  225.             fflag = 0 ;
  226.             while ( fflag == 0 )
  227.             {
  228.                 if ( h > 0 )
  229.                 {
  230.                     for ( j = 1 ; j <= group_size - 1 ; j++ )
  231.                     {
  232.                         MPI_Recv(&e[h][j],1,MPI_INT,j,j+h*1000,MPI_COMM_WORLD,&status);
  233.                         MPI_Recv(&f[h][j],1,MPI_INT,j,j+h*1000,MPI_COMM_WORLD,&status);
  234.                     }
  235.                 }
  236.                 if ( f[h][1] == group_size - 1 )
  237.                 {
  238.                     fflag=1 ;
  239.                 }
  240.                 else
  241.                 {
  242.                     h = h + 1 ;
  243.                     if ( f[h-1][my_rank] == group_size - 1 )
  244.                     {
  245.                         e[h][my_rank] = e[h-1][my_rank];
  246.                         f[h][my_rank]=f[h-1][my_rank];
  247.                     }
  248.                     else
  249.                     {
  250.                         t = f[h-1][my_rank] + 1 ;
  251.                         e[h][my_rank] = e[h-1][my_rank] + e[h-1][t] ;
  252.                         f[h][my_rank] = f[h-1][t] ;
  253.                     }
  254.                     for ( i = 1 ; i < group_size ; i++ )
  255.                     {
  256.                         MPI_Send(&e[h][my_rank],1,MPI_INT,i,my_rank+h*1000,MPI_COMM_WORLD);
  257.                         MPI_Send(&f[h][my_rank],1,MPI_INT,i,my_rank+h*1000,MPI_COMM_WORLD);
  258.                     }
  259.                 }
  260.             }
  261.             height=h;
  262.             if ( my_rank == 1 )
  263.             {
  264.                 m = e[height][1] ;
  265.                 for ( i = 2 ; i < group_size ; i++ )
  266.                 {
  267.                     MPI_Send(&m,1,MPI_INT,i,2,MPI_COMM_WORLD);
  268.                 }
  269.             }
  270.             else
  271.             {
  272.                 MPI_Recv(&m,1,MPI_INT,1,2,MPI_COMM_WORLD,&status);
  273.             }
  274. /*计算d[0][j]=第j个箱子中第一个物品在输入序列中的编号*/
  275.             tmpd = 1 ;
  276.             for ( h = height ; h >= 0 ; h-- )
  277.             {
  278.                 if ( my_rank <= tmpd && my_rank <= m )
  279.                 {
  280.                     if ( my_rank == 1 )
  281.                     {
  282.                         d[h][1] = 1 ;
  283.                         MPI_Send(&d[h][1],1,MPI_INT,2,h*100+1,MPI_COMM_WORLD);
  284.                     }
  285.                     if ( my_rank % 2 == 0 )
  286.                     {
  287.                         MPI_Recv(&d[h+1][my_rank/2],1,MPI_INT,my_rank/2,(h+1)*100+my_rank/2,MPI_COMM_WORLD,&status);
  288.                         td = d[h+1][my_rank/2] ;
  289.                         d[h][my_rank] = f[h][td] + 1 ;
  290.                         if ( my_rank*2 <= tmpd*2 && my_rank*2 <= m )
  291.                         {
  292.                             MPI_Send(&d[h][my_rank],1,MPI_INT,my_rank*2,h*100+my_rank,MPI_COMM_WORLD);
  293.                         }
  294.                         if ( my_rank*2 <= tmpd*2 && my_rank*2 - 1 <= m )
  295.                             MPI_Send(&d[h][my_rank],1,MPI_INT,my_rank*2-1,h*100+my_rank,MPI_COMM_WORLD);
  296.                     }
  297.                     if ( my_rank % 2 !=0 && my_rank > 1 )
  298.                     {
  299.                         MPI_Recv(&d[h+1][(my_rank+1)/2],1,MPI_INT,(my_rank+1)/2,(h+1)*100+(my_rank+1)/2,MPI_COMM_WORLD,&status);
  300.                         d[h][my_rank] = d[h+1][(my_rank+1)/2] ;
  301.                         if ( my_rank*2 <= tmpd*2 && my_rank*2 <= m )
  302.                         {
  303.                             MPI_Send(&d[h][my_rank],1,MPI_INT,my_rank*2,h*100+my_rank,MPI_COMM_WORLD);
  304.                         }
  305.                         if ( my_rank*2 <= tmpd*2 && my_rank*2-1 <= m )
  306.                             MPI_Send(&d[h][my_rank],1,MPI_INT,my_rank*2-1,h*100+my_rank,MPI_COMM_WORLD);
  307.                     }
  308.                 }
  309.                 tmpd = tmpd * 2 ;
  310.             }
  311.             if ( my_rank == 1 ) MPI_Send(&m,1,MPI_INT,0,0,MPI_COMM_WORLD);
  312.             if ( my_rank <= m )
  313.             {
  314.                 MPI_Send(&d[0][my_rank],1,MPI_INT,0,0,MPI_COMM_WORLD);
  315.             }
  316. /*计算r[j]=第j个物品所放入的箱子序号*/
  317.             MPI_Recv(&d[0][1],m,MPI_INT,0,1,MPI_COMM_WORLD,&status);
  318.             if ( d[0][m] <= my_rank )
  319.             {
  320.                 r[my_rank] = m ;
  321.             }
  322.             else
  323.             {
  324.                 for ( i = 0 ; i <= m ; i++ )
  325.                 {
  326.                     if ( d[0][i] > my_rank ) break ;
  327.                 }
  328.                 r[my_rank] = i - 1 ;
  329.             }
  330.             printf ( "number %d goods put into box %dn" , my_rank, r[my_rank] );
  331.         }
  332.     }
  333.     endtime = MPI_Wtime();
  334.     printf(" that tooks %f second!n",endtime-starttime);
  335.     MPI_Finalize();
  336. }