用户工具

站点工具


01-基础学习:课程:mpi

并行计算试题

1.利用MPI编写并行程序实现在含n个整数的数列中找出其最小值

#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;
}

运行结果:

2. 分别编写MPI和OpenMP程序,实现两个n*n的矩阵相乘

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;
}

3. 用MPI_Send和MPI_Recv简单的编写一段代码来实现MPI_alltoall的功能

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]);
        }
}

4. n皇后问题

对于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> 运行结果:

01-基础学习/课程/mpi.txt · 最后更改: 2020/04/07 06:34 由 annhe