mpich

一、配置Linux集群

1. Linux系统：ubuntu-20.04.6-desktop-amd64

在Uuntu官方页面下载对应版本镜像 #### 2. 实验平台 :VMware® Workstation 16.2.5 在虚拟机中先安装好一台Ubuntu的虚拟机，内存最好为2G,磁盘为20G。 ### 二、实验环境搭建 #### 1.mpich环境配置 在Mpich官网下载mpich源码，本次实验使用的为4.2.1版本，在虚拟机上使用下载到本地

wget https://www.mpich.org/static/downloads/4.2.1/mpich-4.2.1.tar.gz

下载好后将其解压并修改安装位置

tar -zxvf mpich-4.2.1.tar.gz
cd mpich-4.2.1
./configure -prefix=/usr/local/mpich

随后对源码进行编译，也即安装mpich

make
sudo make install
````
<font size=6 color=red>注意:</font>此处会报错`error:No Fortran compiler`,此时需要在上面的配置命令中加入`--disable-fortran`，也即重新执行`./configure -prefix=/usr/local/mpich --disable-fortran`
安装完成后，需要将mpich加入到环境变量，执行
```sh
sudo vi /etc/profile
export PATH=/usr/local/mpich/bin:$PATH
export LD_LIBRARY_PATH=/usr/local/mpich/lib:$LD_LIBRARY_PATH
source /etc/profile

此时可对单机的mpich环境进行测试，进入到mpich目录下，运行官方计算圆周率pi的例子

cd /usr/local/mpich/examples/
mpiexec -n 10 ./cpi

若输出 则说明单机mpich环境配置成功 #### 2.多机通信ssh配置 为了实现集群间消息通信，mpich采用ssh来进行完成 首先安装并启动ssh

sudo apt-getinstallopenssh-server
/etc/init.d/ssh start

然后我们将当前机器在vmware中克隆一份，分别记为主机A，主机B。 在主机A上使用ssh-keygen -t rsa生成公钥，然后执行scp /home/A'sname/.ssh/id_rsa.pub B'name@B'sIP:/home/B'sname/.ssh/authorized_keys将A的公钥发送到B上，此时在A机上使用ssh免密登录B机了 配置完成机器间免密登录即可进行并行计算 ### 三、mpich并行计算 #### 1.配置集群环境 在相同的目录下，创建配置文件，如mf，里面存储各个主机的配置格式为: 用户名@IP:线程数 为了方便通信，还需在网络配置中进行修改，将IP对应地址进行注册 此时使用集群计算圆周率的例子，出现 即可说明集群配置成功 #### 2.使用奇偶排序实现并行计算 奇偶排序算法流程为:在奇数阶段，奇数位置与他前一个元素进行比较；在偶数阶段，奇数位置与他后一个元素进行比较。

for(int phase = 0; phase < n; phase++){
    if(phase % 2 == 0){        // 偶阶段，对0、1和2、3...等进行交换
        for(int i=0; i<n; i+=2){
            if(a[i-1] > a[i]){
                temp = a[i];
                a[i] = a[i-1];
                a[i-1] = temp;
            }
        }
    }
    else{                      // 奇阶段，对1、2和3、4...等进行交换 
        for(int i=1; i<n-1; i+=2){
            if(a[i] > a[i+1]){
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
}

将其进行并行的思想也很简单，将n*m个数据分发到n个进程中，每个进程含有m个数据，进程内部先进行排序，然后进程间再进行排序。 此处，进程内部的排序对于各个进程来说是并行的，而奇偶排序中，进程间的排序对于一个进程对之间是串行的，而对于其他的进程而言则是并行的。由此我们就得到了使用奇偶排序进行并行计算的理论。

并行算法思想:

1. 将各个进程中的数据用串行算法排序

2. 分奇偶阶段交换数据，每次交换数据的对象有所不同

3. 在交换数据过程中，首先需要进程通信，拿到对方进程的数据

4. 编号较小的进程保存两个进程中较小的一半数据，编号较大的进程保存两个进程中较大的一半数据

5. 重复奇偶阶段交换数据直至全局有序

算法代码实现:

#include<iostream>
#include<algorithm>
#include<random>
#include<time.h>
#include"mpi.h"
 
		//待排序的整型数量
 
using namespace std;
 
/*该函数用来获得某个阶段，某个进程的通信伙伴*/
int Get_Partner(int my_rank, int phase) {
	// 偶通信阶段，偶数为通信双方的较小进程
	if (phase % 2 == 0) {
		if (my_rank % 2 == 0) {
			return my_rank - 1;
		}
		else {
			return my_rank + 1;
		}
	}
	// 奇通信阶段，奇数为通信双方的较小进程
	else {
		if (my_rank % 2 == 0) {
			return my_rank + 1;
		}
		else {
			return my_rank - 1;
		}
	}
}
 
/*这个函数用来产生随机数，并分发至各个进程*/
void Get_Input(int A[], int local_n, int my_rank,int N) {
	int* a = NULL;
	// 主进程动态开辟内存，产生随机数，分发至各个进程
	if (my_rank == 0) {
		a = new int[N];
		srand((int)time(0));
		for (int i = 0; i < N; i++) {
			a[i] = rand() % 1000;
		}
		MPI_Scatter(a, local_n, MPI_INT, A, local_n, MPI_INT, 0, MPI_COMM_WORLD);
        // Sends data from one process to all other processes in a communicator
        // sendbuf
        // address of send buffer (choice)
        // sendcount
        // number of elements sent to each process (non-negative integer)
        // sendtype
        // data type of send buffer elements (handle)
        // recvcount
        // number of elements in receive buffer (non-negative integer)
        // recvtype
        // data type of receive buffer elements (handle)
        // root
        // rank of sending process (integer)
        // comm
        // communicator (handle)
		delete[] a;
	}
	// 其余进程接收随机数
	else {
		MPI_Scatter(a, local_n, MPI_INT, A, local_n, MPI_INT, 0, MPI_COMM_WORLD);
	}
}
 
/*该函数用来合并两个进程的数据，并取较小的一半数据*/
void Merge_Low(int A[], int B[], int local_n) {
	int* a = new int[local_n];		// 临时数组，倒腾较小的数据
	int p_a = 0, p_b = 0, i = 0;	//分别为A,B,a三个数组的指针
 
	// 这里不同担心数组越界，因为三个数组的大小是相等的
	while (i < local_n) {
		if (A[p_a] < B[p_b]) {
			a[i++] = A[p_a++];
		}
		else {
			a[i++] = B[p_b++];
		}
	}
	// 倒腾一下
	for (i = 0; i < local_n; i++) {
		A[i] = a[i];
	}
	delete[] a;
}
 
/*该函数用来合并两个进程的数据，并取较大的一半数据，与前面的Merge_Low函数类似*/
void Merge_High(int A[], int B[], int local_n) {
	int p_a = local_n - 1, p_b = local_n - 1, i = local_n - 1;
	int* a = new int[local_n];
	// 注意取最大值需要从后往前面取
	while (i >= 0) {
		if (A[p_a] > B[p_b]) {
			a[i--] = A[p_a--];
		}
		else {
			a[i--] = B[p_b--];
		}
	}
	for (i = 0; i < local_n; i++) {
		A[i] = a[i];
	}
	delete[] a;
}
 
/*这个函数用来输出排序后的数组*/
void Print_Sorted_Vector(int A[], int local_n, int my_rank,int N) {
	int* a = NULL;
	// 0号进程接收各个进程的A的分量，并输出至控制台
	if (my_rank == 0) {
		a = new int[N];
		MPI_Gather(A, local_n, MPI_INT, a, local_n, MPI_INT, 0, MPI_COMM_WORLD);
		for (int i = 0; i < N; i++) {
			cout << a[i] << "\t";
			if (i % 4 == 3) {
				cout << endl;
			}
		}
		cout << endl;
		delete[] a;
	}
	// 其余进程将y分量发送至0号进程
	else {
		MPI_Gather(A, local_n, MPI_INT, a, local_n, MPI_INT, 0, MPI_COMM_WORLD);
	}
}
 
int main(int argc, char *argv[]) {
	int local_n;	// 各个进程中数组的大小
	int* A, * B;	// A为进程中保存的数据，B为进程通信中获得的数据
	int comm_sz, my_rank, namelen;
    char processor_name[MPI_MAX_PROCESSOR_NAME];
    int N;
    N=atoi(argv[1]);
	MPI_Init(NULL, NULL);
 
	// 获得进程数和当前进程的编号
	MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    MPI_Get_processor_name(processor_name, &namelen);
	// 计算每个进程应当获得的数据量，动态开辟空间 
	local_n = N / comm_sz;
	A = new int[local_n];
	B = new int[local_n];
 
	// 随机产生数据并分发至各个进程
	Get_Input(A, local_n, my_rank,N);
    printf("Process %d of %d on %s: Sorting array...\n", my_rank, comm_sz, processor_name);//print message
	// 先有序化本地数据
	sort(A, A + local_n);
 
	// 定理：如果p个进程运行奇偶排序算法，那么p个阶段后，输入列表有序
	for (int i = 0; i < comm_sz; i++) {
		// 获得本次交换数据的进程号
		int partner = Get_Partner(my_rank, i);
		// 如果本次数据交换的进程号有效
		if (partner != -1 && partner != comm_sz) {
			// 与对方进程交换数据
			MPI_Sendrecv(A, local_n, MPI_INT, partner, 0, B, local_n, MPI_INT, partner, 0, MPI_COMM_WORLD, MPI_STATUSES_IGNORE);
			// 如果本进程号大于目标进程，就应该取值较大的部分
			if (my_rank > partner) {
				Merge_High(A, B, local_n);
			}
			// 否则应该取值较小的部分
			else {
				Merge_Low(A, B, local_n);
			}
		}
	}
    
    int *a = new int[N];
	MPI_Gather(A, local_n, MPI_INT, a, local_n, MPI_INT, 0, MPI_COMM_WORLD); // gather result
    if(my_rank==0) 
		{
            cout<<endl;
            for (int i = 0; i < N; i++) 
			{cout << a[i] << "\t";
            if (i % local_n == local_n-1) {
				cout << endl;
			}}}
    
	MPI_Finalize();// terminate the execution
	return 0;
}

其中我们在Get_Input中使用主进程来随机生成数据，并将数据分发到其他进程中；随后在各自的进程中调用sort来对进程内数据进行排序；然后使用merge函数来分别在奇偶阶段实现进程间的数据交换即排序；最终在排序结束后使用主进程0来接受并打印数据。最终程序运行如下