#include<iostream> #include"mpi.h" #include<stdlib.h> using namespace std; int main(int argc,char *argv[]) { int len,num[1000],id,numprocs,namelen,*recvbuf; char processor_name[MPI_MAX_PROCESSOR_NAME]; double t1,t2; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&id); MPI_Get_processor_name(processor_name,&namelen); if(id==0) { cout<<"请输入数列长度(最多为1000)"; cin>>len; for(int i=0;i<len;i++) cin>>num[i]; for(int i=1;i<numprocs;i++) { MPI_Send(&len,1,MPI_INT,i,1,MPI_COMM_WORLD); MPI_Send(num,len,MPI_INT,i,2,MPI_COMM_WORLD); } } else { MPI_Recv(&len,1,MPI_INT,0,1,MPI_COMM_WORLD,&status); MPI_Recv(num,len,MPI_INT,0,2,MPI_COMM_WORLD,&status); } MPI_Barrier(MPI_COMM_WORLD);//同步,可要可不要 t1=MPI_Wtime(); int min=2147483647,k,start,end;//k记录每个进程要处理的数据个数,start记录每个进程从第几个数据开始处理 k=len/numprocs; start=k*id; if(id==numprocs-1)//最后一个进程处理数据多一些 k+=len%numprocs; end=start+k; for(int i=start;i<end;i++) if(num[i]<min) min=num[i]; if(id==0) { recvbuf=(int*)malloc(numprocs*sizeof(int)); } //将所有进程的min聚集到0号进程中 MPI_Gather(&min,1,MPI_INT,recvbuf,1,MPI_INT,0,MPI_COMM_WORLD); if(id==0) { int min=2147483647; for(int i=0;i<numprocs;i++) { if((*recvbuf)<min) min=*recvbuf; recvbuf++; } cout<<"最小值为"<<min<<endl; } t2=MPI_Wtime(); cout<<"进程"<<id<<"计算耗时"<<(t2-t1)*1000<<"毫秒"<<endl<<endl; MPI_Finalize(); return 0; }
MPI程序:
#include <stdio.h> #include <mpi.h> #include <math.h> #include <stdlib.h> #include <time.h> #include <memory.h> int **A, **B, **C; //C=A*B int *a, *b, *c; //各个进程的缓冲区 int n; //矩阵的行列数 int np; //每个进程控制的小矩阵的行列数 MPI_Status status; int p, rank; //进程个个数、当前进程的编号,笛卡尔进程编号 int *tempa, *tempb; void ProduceABC(); //在根处理器中随机生成矩阵AB,数值在0-10之间;初始化矩阵C void PrintABC(); //输出结果 void ScatterAB(); // 分发矩阵AB中的元素到各个进程中 void MainProcess(); //cannon算法的主过程 void collectC(); //收集结果矩阵C void Mutiply(); //矩阵相乘 void Printab(); void Printc(); int main(int argc, char *argv[]) { int i; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &p); MPI_Comm_rank(MPI_COMM_WORLD, &rank); // printf( "Hello world from process %d of %d\n", rank, p ); if (rank == 0) { printf("请输入矩阵的行列数n = "); fflush(stdout); scanf("%d", &n); printf("\n"); } MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); // n = atoi(argv[1]); np = n / (int) sqrt(p); a = (int *) malloc(np * np * sizeof(int)); b = (int *) malloc(np * np * sizeof(int)); c = (int *) malloc(np * np * sizeof(int)); memset(c, 0, np * np * sizeof(int)); //Printc(); tempa = (int *) malloc(np * np * sizeof(int)); tempb = (int *) malloc(np * np * sizeof(int)); if (rank == 0) { //在根处理器中为矩阵ABC分配空间 A = (int **) malloc(n * sizeof(int *)); B = (int **) malloc(n * sizeof(int *)); C = (int **) malloc(n * sizeof(int *)); for (i = 0; i < n; i++) { A[i] = (int *) malloc(n * sizeof(int)); B[i] = (int *) malloc(n * sizeof(int)); C[i] = (int *) malloc(n * sizeof(int)); } ProduceABC(); //在根处理器中随机生成矩阵AB,数值在0-10之间;初始化矩阵C ScatterAB(); // 分发矩阵AB中的元素到各个进程中 } else { MPI_Recv(a, np * np, MPI_INT, 0, 1, MPI_COMM_WORLD, &status); MPI_Recv(b, np * np, MPI_INT, 0, 2, MPI_COMM_WORLD, &status); } MainProcess(); //cannon算法的主过程 if (rank == 0) { collectC(); //收集结果矩阵C PrintABC(); //输出结果 for (i = 0; i < n; i++) { free(A[i]); free(B[i]); free(C[i]); } free(A); free(B); free(C); } else { MPI_Send(c, np * np, MPI_INT, 0, 1, MPI_COMM_WORLD); } free(a); free(b); free(c); free(tempa); free(tempb); //MPI_Barrier(MPI_COMM_WORLD); MPI_Finalize(); return 0; } void ProduceABC() //在根处理器中随机生成矩阵AB { int i, j; srand((unsigned int) time(NULL)); /*设随机数种子 */ /*随机生成A,B,并初始化C*/ for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { A[i][j] = (int) (rand() / (double) RAND_MAX * 10); B[i][j] = (int) (rand() / (double) RAND_MAX * 10); C[i][j] = 0; } } } void PrintABC() //输出结果 { int i, j; printf("矩阵A如下:\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) printf("%6d", A[i][j]); printf("\n"); } printf("\n"); printf("矩阵B如下:\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) printf("%6d", B[i][j]); printf("\n"); } printf("\n"); printf("矩阵C如下:\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) printf("%6d", C[i][j]); printf("\n"); } printf("\n"); } void ScatterAB() // 分发矩阵AB中的元素到各个进程中 { int imin, imax, jmin, jmax; int sp; int i, j, k, m; for (k = 0; k < p; k++) { /*计算相应处理器所分得的矩阵块在总矩阵中的坐标范围 */ sp = (int) sqrt(p); imin = (k / sp) * np; imax = imin + np - 1; jmin = (k % sp) * np; jmax = jmin + np - 1; /*rank=0的处理器将A,B中的相应块拷至tempa,tempb,准备向其他处理器发送 */ m = 0; for (i = imin; i <= imax; i++) { for (j = jmin; j <= jmax; j++) { tempa[m] = A[i][j]; tempb[m] = B[i][j]; m++; } } /*根处理器将自己对应的矩阵块从tempa,tempb拷至a,b */ if (k == 0) { memcpy(a, tempa, np * np * sizeof(int)); memcpy(b, tempb, np * np * sizeof(int)); } else { /*根处理器向其他处理器发送tempa,tempb中相关的矩阵块 */ MPI_Send(tempa, np * np, MPI_INT, k, 1, MPI_COMM_WORLD); MPI_Send(tempb, np * np, MPI_INT, k, 2, MPI_COMM_WORLD); } } } void MainProcess() //cannon算法的主过程 { MPI_Comm comm; //笛卡尔结构通讯器 int crank; int dims[2], periods[2], coords[2]; int source, dest, up, down, right, left; int i; dims[0] = dims[1] = (int) sqrt(p); periods[0] = periods[1] = 1; MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, 1, &comm); MPI_Comm_rank(comm, &crank); MPI_Cart_coords(comm, crank, 2, coords); MPI_Cart_shift(comm, 1, -1, &right, &left); // printf("crank = %d right = %d left = %d\n", crank, right, left); MPI_Cart_shift(comm, 0, -1, &down, &up); // printf("crank = %d up = %d down = %d\n", crank, up, down); MPI_Cart_shift(comm, 1, -coords[0], &source, &dest); // printf("crank = %d source = %d dest = %d\n", crank, source, dest); MPI_Sendrecv_replace(a, np * np, MPI_INT, dest, 1, source, 1, comm, &status); MPI_Cart_shift(comm, 0, -coords[1], &source, &dest); MPI_Sendrecv_replace(b, np * np, MPI_INT, dest, 1, source, 1, comm, &status); Mutiply(); //矩阵相乘 // printf("rank = %d\n", rank);Printab();Printc(); for (i = 1; i < dims[0]; i++) { MPI_Sendrecv_replace(a, np * np, MPI_INT, left, 1, right, 1, comm, &status); MPI_Sendrecv_replace(b, np * np, MPI_INT, up, 1, down, 1, comm, &status); Mutiply(); //矩阵相乘 // printf("i = %d rank = %d\n",i, rank);Printab();Printc(); } MPI_Comm_free(&comm); } void collectC() //收集结果矩阵C { int i, j, k, s, m; int imin, imax, jmin, jmax; int sp = (int) sqrt(p); /* 根处理器中的c赋给总矩阵C */ for (i = 0; i < np; i++) { for (j = 0; j < np; j++) C[i][j] = c[i * np + j]; } for (k = 1; k < p; k++) { /*根处理器从其他处理器接收相应的分块c */ MPI_Recv(c, np * np, MPI_INT, k, 1, MPI_COMM_WORLD, &status); // printf("rank = %d\n", k);Printc(); imin = (k / sp) * np; imax = imin + np - 1; jmin = (k % sp) * np; jmax = jmin + np - 1; /*将接收到的c拷至C中的相应位置,从而构造出C */ for (i = imin, m = 0; i <= imax; i++, m++) { for (j = jmin, s = 0; j <= jmax; j++, s++) C[i][j] = c[m * np + s]; } } } void Mutiply() //矩阵相乘 { int i, j, k; for (i = 0; i < np; i++) for (j = 0; j < np; j++) for (k = 0; k < np; k++) c[i * np + j] += a[i * np + k] * b[k * np + j]; } void Printab() //输出结果 { int i; printf("矩阵a如下:\n"); for (i = 0; i < np * np; i++) printf("%6d", a[i]); printf("\n"); printf("\n"); printf("矩阵b如下:\n"); for (i = 0; i < np * np; i++) printf("%6d", b[i]); printf("\n"); printf("\n"); } void Printc() { int i; printf("矩阵c如下:\n"); for (i = 0; i < np * np; i++) printf("%6d", c[i]); printf("\n"); printf("\n"); }
OpenMP:
#include <omp.h> #include <stdio.h> #include <time.h> #define NN 2000 int a[NN][NN], b[NN][NN]; long long c[NN][NN]; void solve(int n, int num_thread) { int i, j, t, k, time; clock_t startTime, endTime; long long sum; omp_set_num_threads(num_thread); for(i=0;i<n;i++)//对矩阵a和矩阵b进行初始化 { t=i+1; for(j=0;j<n;j++) { a[i][j]=t++; b[i][j]=1; } } startTime=clock(); sum=0; #pragma omp parallel shared(a,b,c) private(i,j,k) { #pragma omp for schedule(dynamic) for(i=0;i<n;i++) { for(j=0;j<n;j++) { c[i][j]=0; for(k=0;k<n;k++) { c[i][j]+=a[i][k]*b[k][j]; } } } } for(i=0;i<n;i++)for(j=0;j<n;j++) sum+=c[i][j]; endTime=clock(); time=endTime-startTime; printf("sum=%lld time=%dms\n",sum,time); } int main() { int n, num_thread; while(scanf("%d%d",&n,&num_thread)!=EOF) { solve(n,num_thread); } return 0; }
void MPI_Alltoall_a(int rank,int size,int tag){ int index,source; char message[100]; char buffers[ProNum][100]; char buffer[10]; MPI_Status status; strcpy(message,"Hello,the message is from process "); snprintf(buffer,10,"%d",rank); strcat(message,buffer); for(index=0;index<size;index++){ MPI_Send(message,strlen(message), MPI_CHAR, index, tag, MPI_COMM_WORLD); } printf("There are %d processes in the group.\n",size); for(source=0;source<size;source++){ MPI_Recv(buffers[source],100, MPI_CHAR,source, tag, MPI_COMM_WORLD, &status); printf("Process %d received %s\n",rank,buffers[source]); } }
对于n皇后问题(即n个皇后分布在nn的棋盘上,棋盘的每一行、列以及两条对角线上均最多只能有一个皇后),设计一个通用的并行算法,并用MPI编程实现之 <file cpp> #include<iostream> #include<fstream> #include <mpi.h> using namespace std; #define N 8 void outPut(const int & size,int * array,ofstream & file)输出到文件 { for(int i = 0 ; i < size ; i) { file<<array[i]<<" "; } file<<endl; } bool isContact(const int &deep, const int * const &array)//判断对角线上是否有冲突 { int temp; for(int i = 1 ; i < deep+1 ; i++) { temp = array[deep-i]; if(array[deep] -i == temp
for(int i = 0 ; i < size ; i++)//从第到第个,判断是否还有没用过并且没有冲突的数据 { if(!flags[i])//判断是否被用过,这里使用的是按内容寻址的方式 {
array[deep] = i;//如果i没有被使用过,那么现在使用i if(deep !=0)//不是第一行的元素要判断对角线上是否有冲突 { if(isContact(deep,array))//判断对角线是否有冲突,主要deep是层次 continue;//如果有冲突,继续循环,寻找下一个试探点 } flags[i] = 1;//目前第i个点可用,这里进行标记,第i个点已经被占用了 if(deep == size-1)//当深度为,就是找到了一个序列,满足八皇后要求了 { outPut(size,array,file);//将结果输出到文件 count++;//次数加一 } else//没有找全所有的棋子 { range(size,deep+1,flags,array,count,file);//进一步递归调用,完成没完成的棋子 array[deep] = -1;//递归回来,要恢复原状,以备下次继续递归到新的序列 } flags[i] = 0;//恢复标志 } }
} void mpirange(const int & size,int * &flags,int * &array,const int &myId)mpi开启递归调用 { ofstream file; file.open(“temp.txt”,std::ios::out | std::ios::app);输出的文件,每个进程都以追加的方式存放数据 flags = new int[N];两个数据结构,flags用来存储位置是否被占用信息 array = new int[N];存储第i行的棋子放的位置 memset(flags,0,sizeof(int)N);赋初值 memset(array,-1,sizeof(int)N); flags[myId] = 1;第i个进程执行第一行为i的计算 array[0] = myId; int count = 0 ;计数为 int totalCount = 0;总计数为 range(N,1,flags,array,count,file);开始递归 MPIReduce(&count,&totalCount,1,MPIINT,MPISUM,0,MPICOMMWORLD);规约所有递归结构 if(myId == 0)主进程输出计算结果 cerr«totalCount«endl; file.close(); } int _tmain(int argc, char* argv[]) { int size; int myId; ofstream file; MPIInit(&argc,&argv);初始化mpi MPICommsize(MPICOMMWORLD,&size);获取开启的进程数量 MPICommrank(MPICOMMWORLD,&myId);获取当前进程的id号 int *flags;标记 int *array;存放棋盘次序 file.open(“temp.txt”);用来清空文件–采用一次打开然后关闭文件,仅仅是在计算前,清空文件中原有的内容,后面文件打开均采用追加的方式 file.close(); mpirange(N,flags,array,myId);开始递归计算 MPI_Finalize();计算终止 return 0; } </file> 运行结果: