?? box.c
字號:
#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; else outint=floor(temp); return outint;}main ( argc, argv )int argc;char * argv[];{ MPI_Status status; int i, group_size, my_rank, pnumber, /* to store number of used slave processors */ h, lp, lop, j, t; int group_size1, /* number of rank*/ tmpp; FILE *fp; int lp1, h1, tmp1, lop1, high, mid, flag, fflag; int tmpd, d[100][100], height, m, /* number of box*/ 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 number is %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 %f wrong!\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_COMM_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_COMM_WORLD,&status); } for ( i = 1 ; i <= pnumber ; i++ ) { MPI_Send(&f[0][1],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(&d[0][i],1,MPI_INT,i,0,MPI_COMM_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_COMM_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_FLOAT,0,my_rank+h1*10,MPI_COMM_WORLD,&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_WORLD); } 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_WORLD); 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_FLOAT,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_WORLD); 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_WORLD); 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_FLOAT,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,MPI_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,MPI_COMM_WORLD,&status); MPI_Recv(&f[h][j],1,MPI_INT,j,j+h*1000,MPI_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_COMM_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_rank*2,h*100+my_rank,MPI_COMM_WORLD); } if ( my_rank*2 <= tmpd*2 && my_rank*2 - 1 <= m ) MPI_Send(&d[h][my_rank],1,MPI_INT,my_rank*2-1,h*100+my_rank,MPI_COMM_WORLD); } if ( my_rank % 2 !=0 && my_rank > 1 ) { 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); 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_rank*2,h*100+my_rank,MPI_COMM_WORLD); } if ( my_rank*2 <= tmpd*2 && my_rank*2-1 <= m ) MPI_Send(&d[h][my_rank],1,MPI_INT,my_rank*2-1,h*100+my_rank,MPI_COMM_WORLD); } } 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_COMM_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 %f second!\n",endtime-starttime); MPI_Finalize();}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -