connect.c
资源名称:mpi.zip [点击查看]
上传用户:hhyinxing
上传日期:2013-09-10
资源大小:833k
文件大小:5k
源码类别:
并行计算
开发平台:
Unix_Linux
- /**本算法中处理器数目须小于图的顶点数**/
- #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
- #include <math.h>
- #include <mpi.h>
- /**使用动态分配的内存存储邻接矩阵,以下为宏定义**/
- #define A(i,j) A[i*N+j]
- /**以下为 N:顶点数 n:各处理器分配的顶点数 p:处理器数**/
- int N;
- int n;
- int p;
- int *D,*C;
- int *A;
- int temp;
- int myid;
- MPI_Status status;
- /**输出必要信息**/
- void print(int *P)
- {
- int i;
- if(myid==0)
- {
- for(i=0;i<N;i++)
- printf("%d ",P[i]);
- printf("n");
- }
- }
- /**读入邻接矩阵**/
- void readA()
- {
- char *filename;
- int i,j;
- printf("n");
- printf("Input the vertex num:n");
- scanf("%d",&N);
- n=N/p;
- if(N%p!=0) n++;
- A=(int*)malloc(sizeof(int)*(n*p)*N);
- if(A==NULL)
- {
- printf("Error when allocating memoryn");
- exit(0);
- }
- printf("Input the adjacent matrix:n");
- for(i=0;i<N;i++)
- for(j=0;j<N;j++)
- scanf("%d",&A(i,j));
- for(i=N;i<n*p;i++)
- for(j=0;j<N;j++)
- A(i,j)=0;
- }
- /**处理器0广播特定数据**/
- void bcast(int *P)
- {
- MPI_Bcast(P,N,MPI_INT,0,MPI_COMM_WORLD);
- }
- /**两者中取最小的数学函数**/
- int min(int a,int b)
- {
- return(a<b?a:b);
- }
- /**为各顶点找最小的邻接超顶点,对应算法步骤(2.1)**/
- void D_to_C()
- {
- int i,j;
- for(i=0;i<n;i++)
- {
- C[n*myid+i]=N+1;
- for(j=0;j<N;j++)
- if((A(i,j)==1)&&(D[j]!=D[n*myid+i])&&(D[j]<C[n*myid+i]))
- {
- C[n*myid+i]=D[j];
- }
- if(C[n*myid+i]==N+1)
- C[n*myid+i]=D[n*myid+i];
- }
- }
- /**为各超顶点找最小邻接超顶点,对应算法步骤(2.2)**/
- void C_to_C()
- {
- int i,j;
- for(i=0;i<n;i++)
- {
- temp=N+1;
- for(j=0;j<N;j++)
- if((D[j]==n*myid+i)&&(C[j]!=n*myid+i)&&(C[j]<temp))
- {
- temp=C[j];
- }
- if(temp==N+1) temp=D[n*myid+i];
- C[myid*n+i]=temp;
- }
- }
- /**调整超顶点标识**/
- void CC_to_C()
- {
- int i;
- for(i=0;i<n;i++)
- C[myid*n+i]=C[C[myid*n+i]];
- }
- /**产生新的超顶点,对应算法步骤(2.5)**/
- void CD_to_D()
- {
- int i;
- for(i=0;i<n;i++)
- D[myid*n+i]=min(C[myid*n+i],D[C[myid*n+i]]);
- }
- /**释放动态内存**/
- void freeall()
- {
- free(A);
- free(D);
- free(C);
- }
- /**主函数**/
- void main(int argc,char **argv)
- {
- int i,j,k;
- double l;
- int group_size;
- /**以下变量用来记录运行时间**/
- double starttime,endtime;
- MPI_Init(&argc,&argv);
- MPI_Comm_size(MPI_COMM_WORLD,&group_size);
- MPI_Comm_rank(MPI_COMM_WORLD,&myid);
- p=group_size;
- MPI_Barrier(MPI_COMM_WORLD);
- if(myid==0)
- starttime=MPI_Wtime();
- /**处理器0读邻接矩阵**/
- if(myid==0)
- readA();
- MPI_Barrier(MPI_COMM_WORLD);
- MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD);
- if(myid!=0)
- {
- n=N/p;
- if(N%p!=0) n++;
- }
- D=(int*)malloc(sizeof(int)*(n*p));
- C=(int*)malloc(sizeof(int)*(n*p));
- if(myid!=0)
- A=(int*)malloc(sizeof(int)*n*N);
- /**初始化数组D,步骤(1)**/
- for(i=0;i<n;i++)
- D[myid*n+i]=myid*n+i;
- MPI_Barrier(MPI_COMM_WORLD);
- MPI_Gather(&D[myid*n],n,MPI_INT,D,n,MPI_INT,0,MPI_COMM_WORLD);
- bcast(D);
- MPI_Barrier(MPI_COMM_WORLD);
- /**处理器0向其它处理器发送必要数据**/
- if(myid==0)
- for(i=1;i<p;i++)
- MPI_Send(&A(i*n,0),n*N,MPI_INT,i,i,MPI_COMM_WORLD);
- else
- MPI_Recv(A,n*N,MPI_INT,0,myid,MPI_COMM_WORLD,&status);
- MPI_Barrier(MPI_COMM_WORLD);
- l=log(N)/log(2);
- /**主循环体:算法步骤(2)**/
- for(i=0;i<l;i++)
- {
- if(myid==0) printf("Stage %d:n",i+1);
- /**算法步骤(2.1)**/
- D_to_C();
- MPI_Barrier(MPI_COMM_WORLD);
- MPI_Gather(&C[n*myid],n,MPI_INT,C,n,MPI_INT,0,MPI_COMM_WORLD);
- print(C);
- bcast(C);
- MPI_Barrier(MPI_COMM_WORLD);
- /**算法步骤(2.2)**/
- C_to_C();
- print(C);
- MPI_Barrier(MPI_COMM_WORLD);
- MPI_Gather(&C[n*myid],n,MPI_INT,C,n,MPI_INT,0,MPI_COMM_WORLD);
- MPI_Gather(&C[n*myid],n,MPI_INT,D,n,MPI_INT,0,MPI_COMM_WORLD);
- MPI_Barrier(MPI_COMM_WORLD);
- /**算法步骤(2.3)**/
- if(myid==0)
- for(j=0;j<n;j++)
- D[j]=C[j];
- /**算法步骤(2.4)**/
- for(k=0;k<l;k++)
- {
- bcast(C);
- CC_to_C();
- MPI_Gather(&C[n*myid],n,MPI_INT,C,n,MPI_INT,0,MPI_COMM_WORLD);
- }
- bcast(C);
- bcast(D);
- /**算法步骤(2.5)**/
- CD_to_D();
- MPI_Gather(&D[n*myid],n,MPI_INT,D,n,MPI_INT,0,MPI_COMM_WORLD);
- print(D);
- bcast(D);
- }
- if(myid==0) printf("Result: n");
- print(D);
- if(myid==0)
- {
- endtime=MPI_Wtime();
- printf("The running time is %dn",endtime-starttime);
- }
- freeall();
- MPI_Finalize();
- }