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

并行计算

开发平台:

Unix_Linux

  1. /**本算法中处理器数目须小于图的顶点数**/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <malloc.h>
  5. #include <math.h>
  6. #include <mpi.h>
  7. /**使用动态分配的内存存储邻接矩阵,以下为宏定义**/
  8. #define A(i,j) A[i*N+j]
  9. /**以下为 N:顶点数  n:各处理器分配的顶点数  p:处理器数**/
  10. int N;
  11. int n;
  12. int p;
  13. int *D,*C;
  14. int *A;
  15. int temp;
  16. int myid;
  17. MPI_Status status;
  18. /**输出必要信息**/
  19. void print(int *P)
  20. {
  21.     int i;
  22.     if(myid==0)
  23.     {
  24.         for(i=0;i<N;i++)
  25.             printf("%d ",P[i]);
  26.         printf("n");
  27.     }
  28. }
  29. /**读入邻接矩阵**/
  30. void readA()
  31. {
  32.     char *filename;
  33.     int i,j;
  34.     printf("n");
  35.     printf("Input the vertex num:n");
  36.     scanf("%d",&N);
  37.     n=N/p;
  38.     if(N%p!=0) n++;
  39.     A=(int*)malloc(sizeof(int)*(n*p)*N);
  40.     if(A==NULL)
  41.     {
  42.         printf("Error when allocating memoryn");
  43.         exit(0);
  44.     }
  45.     printf("Input the adjacent matrix:n");
  46.     for(i=0;i<N;i++)
  47.         for(j=0;j<N;j++)
  48.             scanf("%d",&A(i,j));
  49.     for(i=N;i<n*p;i++)
  50.         for(j=0;j<N;j++)
  51.             A(i,j)=0;
  52. }
  53. /**处理器0广播特定数据**/
  54. void bcast(int *P)
  55. {
  56.     MPI_Bcast(P,N,MPI_INT,0,MPI_COMM_WORLD);
  57. }
  58. /**两者中取最小的数学函数**/
  59. int min(int a,int b)
  60. {
  61.     return(a<b?a:b);
  62. }
  63. /**为各顶点找最小的邻接超顶点,对应算法步骤(2.1)**/
  64. void D_to_C()
  65. {
  66.     int i,j;
  67.     for(i=0;i<n;i++)
  68.     {
  69.         C[n*myid+i]=N+1;
  70.         for(j=0;j<N;j++)
  71.             if((A(i,j)==1)&&(D[j]!=D[n*myid+i])&&(D[j]<C[n*myid+i]))
  72.         {
  73.             C[n*myid+i]=D[j];
  74.         }
  75.         if(C[n*myid+i]==N+1)
  76.             C[n*myid+i]=D[n*myid+i];
  77.     }
  78. }
  79. /**为各超顶点找最小邻接超顶点,对应算法步骤(2.2)**/
  80. void C_to_C()
  81. {
  82.     int i,j;
  83.     for(i=0;i<n;i++)
  84.     {
  85.         temp=N+1;
  86.         for(j=0;j<N;j++)
  87.             if((D[j]==n*myid+i)&&(C[j]!=n*myid+i)&&(C[j]<temp))
  88.         {
  89.             temp=C[j];
  90.         }
  91.         if(temp==N+1) temp=D[n*myid+i];
  92.         C[myid*n+i]=temp;
  93.     }
  94. }
  95. /**调整超顶点标识**/
  96. void CC_to_C()
  97. {
  98.     int i;
  99.     for(i=0;i<n;i++)
  100.         C[myid*n+i]=C[C[myid*n+i]];
  101. }
  102. /**产生新的超顶点,对应算法步骤(2.5)**/
  103. void CD_to_D()
  104. {
  105.     int i;
  106.     for(i=0;i<n;i++)
  107.         D[myid*n+i]=min(C[myid*n+i],D[C[myid*n+i]]);
  108. }
  109. /**释放动态内存**/
  110. void freeall()
  111. {
  112.     free(A);
  113.     free(D);
  114.     free(C);
  115. }
  116. /**主函数**/
  117. void main(int argc,char **argv)
  118. {
  119.     int i,j,k;
  120.     double l;
  121.     int group_size;
  122. /**以下变量用来记录运行时间**/
  123.     double starttime,endtime;
  124.     MPI_Init(&argc,&argv);
  125.     MPI_Comm_size(MPI_COMM_WORLD,&group_size);
  126.     MPI_Comm_rank(MPI_COMM_WORLD,&myid);
  127.     p=group_size;
  128.     MPI_Barrier(MPI_COMM_WORLD);
  129.     if(myid==0)
  130.         starttime=MPI_Wtime();
  131. /**处理器0读邻接矩阵**/
  132.     if(myid==0)
  133.         readA();
  134.     MPI_Barrier(MPI_COMM_WORLD);
  135.     MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD);
  136.     if(myid!=0)
  137.     {
  138.         n=N/p;
  139.         if(N%p!=0) n++;
  140.     }
  141.     D=(int*)malloc(sizeof(int)*(n*p));
  142.     C=(int*)malloc(sizeof(int)*(n*p));
  143.     if(myid!=0)
  144.         A=(int*)malloc(sizeof(int)*n*N);
  145. /**初始化数组D,步骤(1)**/
  146.     for(i=0;i<n;i++)
  147.         D[myid*n+i]=myid*n+i;
  148.     MPI_Barrier(MPI_COMM_WORLD);
  149.     MPI_Gather(&D[myid*n],n,MPI_INT,D,n,MPI_INT,0,MPI_COMM_WORLD);
  150.     bcast(D);
  151.     MPI_Barrier(MPI_COMM_WORLD);
  152. /**处理器0向其它处理器发送必要数据**/
  153.     if(myid==0)
  154.         for(i=1;i<p;i++)
  155.             MPI_Send(&A(i*n,0),n*N,MPI_INT,i,i,MPI_COMM_WORLD);
  156.     else
  157.         MPI_Recv(A,n*N,MPI_INT,0,myid,MPI_COMM_WORLD,&status);
  158.     MPI_Barrier(MPI_COMM_WORLD);
  159.     l=log(N)/log(2);
  160. /**主循环体:算法步骤(2)**/
  161.     for(i=0;i<l;i++)
  162.     {
  163.         if(myid==0) printf("Stage %d:n",i+1);
  164. /**算法步骤(2.1)**/
  165.         D_to_C();
  166.         MPI_Barrier(MPI_COMM_WORLD);
  167.         MPI_Gather(&C[n*myid],n,MPI_INT,C,n,MPI_INT,0,MPI_COMM_WORLD);
  168.         print(C);
  169.         bcast(C);
  170.         MPI_Barrier(MPI_COMM_WORLD);
  171. /**算法步骤(2.2)**/
  172.         C_to_C();
  173.         print(C);
  174.         MPI_Barrier(MPI_COMM_WORLD);
  175.         MPI_Gather(&C[n*myid],n,MPI_INT,C,n,MPI_INT,0,MPI_COMM_WORLD);
  176.         MPI_Gather(&C[n*myid],n,MPI_INT,D,n,MPI_INT,0,MPI_COMM_WORLD);
  177.         MPI_Barrier(MPI_COMM_WORLD);
  178. /**算法步骤(2.3)**/
  179.         if(myid==0)
  180.             for(j=0;j<n;j++)
  181.                 D[j]=C[j];
  182. /**算法步骤(2.4)**/
  183.         for(k=0;k<l;k++)
  184.         {
  185.             bcast(C);
  186.             CC_to_C();
  187.             MPI_Gather(&C[n*myid],n,MPI_INT,C,n,MPI_INT,0,MPI_COMM_WORLD);
  188.         }
  189.         bcast(C);
  190.         bcast(D);
  191. /**算法步骤(2.5)**/
  192.         CD_to_D();
  193.         MPI_Gather(&D[n*myid],n,MPI_INT,D,n,MPI_INT,0,MPI_COMM_WORLD);
  194.         print(D);
  195.         bcast(D);
  196.     }
  197.     if(myid==0) printf("Result: n");
  198.     print(D);
  199.     if(myid==0)
  200.     {
  201.         endtime=MPI_Wtime();
  202.         printf("The running time is %dn",endtime-starttime);
  203.     }
  204.     freeall();
  205.     MPI_Finalize();
  206. }