MPI计算全局总和（树形与蝶形）

1. 内容

​ 编写一个MPI程序，分别采用树形和蝶形通信结构计算全局总和。首先计算通信域comm_sz的进程数是2的幂的特殊情况，若能够正确运行，改变该程序使其适用于comm_sz中任意进程数目的值。

2. 代码如下：

2.1 树形结构计算全局总和

​ 在树形结构中，先将多个数分成若干部分求和，再通过树形结构将局部和相加，最后求得的和在线程0中

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <mpi.h> #include <string> #include <cstring> #include <cstdlib> #include <fstream> #include <cmath> #include <algorithm> #include <iostream> #include <random> using namespace std; const int numall = 100000; //要求和的数的数目 int ceil_log2(int n) { return ceil(log(n) / log(2)); } int tree_add(int argc, char **argv){ //生成numall个数字 int data[numall]; for (int i = 0; i < numall; i++) { data[i] = rand() % 100; } //MPI multi thread int comm_sz; int my_rank; MPI_Init(NULL, NULL); MPI_Comm_size(MPI_COMM_WORLD, &comm_sz); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); //串行求和，用于验证是否正确 if (my_rank == 0) { int test_sum = 0; for (int i = 0; i < numall; i++) { test_sum += data[i]; } cout << "求得的和应为: " << test_sum << endl; } //分派数字 int local_n = numall / comm_sz; //每个线程被分配到的数字的数目 if (numall %comm_sz > my_rank) local_n += 1; int local_init_index = my_rank * local_n; if (my_rank == numall % comm_sz) local_init_index = my_rank * (local_n + 1); if (numall%comm_sz < my_rank) local_init_index = (numall / comm_sz + 1)*(numall%comm_sz) + (my_rank - numall % comm_sz)*local_n; //对每个线程分配的数进行求和 int local_sum = 0; for (int i = 0; i < local_n; i++) { local_sum += data[local_init_index + i]; } //cout << my_rank << ": " << local_sum << endl; MPI_Barrier(MPI_COMM_WORLD); //将每个线程求得的局部和进行求和 int k = ceil_log2(comm_sz); for (int i = 0; i < k; i++) { for (int j = int(pow(2,i)); j < comm_sz; j += int(pow(2, i + 1))) { int send_p = j; int recv_p = send_p - int(pow(2, i)); if (my_rank == recv_p) { //接收数据并求和 int recv_sum = 0; MPI_Recv(&recv_sum, 1, MPI_INT, send_p, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE); local_sum += recv_sum; } else if(my_rank==send_p){ //发送数据 MPI_Send(&local_sum, 1, MPI_INT, recv_p, 0, MPI_COMM_WORLD); } } MPI_Barrier(MPI_COMM_WORLD); } if (my_rank == 0) cout << local_sum << endl; MPI_Finalize(); return 0; }

2.2 蝶形结构计算全局总和

​ 与树形结构不同的一点是，最后求得的和在每个线程中都存在

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <mpi.h> #include <string> #include <cstring> #include <cstdlib> #include <fstream> #include <cmath> #include <algorithm> #include <iostream> #include <random> using namespace std; const int numall = 8; //要求和的数的数目 int ceil_log2(int n) { return ceil(log(n) / log(2)); } int main(int argc, char **argv) { //生成numall个数字 int data[numall] = {0,1,2,3,4,5,6,7}; //for (int i = 0; i < numall; i++) { // data[i] = rand() % 100; //} //MPI multi thread int comm_sz; int my_rank; MPI_Init(NULL, NULL); MPI_Comm_size(MPI_COMM_WORLD, &comm_sz); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); //串行求和，用于验证是否正确 if (my_rank == 0) { int test_sum = 0; for (int i = 0; i < numall; i++) { test_sum += data[i]; } cout << "求得的和应为: " << test_sum << endl; } //分派数字 int local_n = numall / comm_sz; //每个线程被分配到的数字的数目 if (numall %comm_sz > my_rank) local_n += 1; int local_init_index = my_rank * local_n; if (my_rank == numall % comm_sz) local_init_index = my_rank * (local_n + 1); if (numall%comm_sz < my_rank) local_init_index = (numall / comm_sz + 1)*(numall%comm_sz) + (my_rank - numall % comm_sz)*local_n; //对每个线程分配的数进行求和 int local_sum = 0; for (int i = 0; i < local_n; i++) { local_sum += data[local_init_index + i]; } //cout << my_rank << ": " << local_sum << endl; MPI_Barrier(MPI_COMM_WORLD); //将每个线程求得的局部和进行求和，蝶形 int k = ceil_log2(comm_sz); for (int i = 0; i < k; i++) { for (int j = 0; j < comm_sz; j += int(pow(2, i + 1))) { for (int k = 0; k < (1 << i); k++) { int px = j+k; int py = (1 << i) + px; if (px >= comm_sz || py >= comm_sz)break; if (px == my_rank) { int recv_sum = 0; MPI_Send(&local_sum, 1, MPI_INT, py, 0, MPI_COMM_WORLD); MPI_Recv(&recv_sum, 1, MPI_INT, py, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE); local_sum += recv_sum; } else if (py == my_rank) { int recv_sum = 0; MPI_Send(&local_sum, 1, MPI_INT, px, 0, MPI_COMM_WORLD); MPI_Recv(&recv_sum, 1, MPI_INT, px, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE); local_sum += recv_sum; } } } cout << my_rank << ": " << local_sum << endl; MPI_Barrier(MPI_COMM_WORLD); } //cout << my_rank << ": " << local_sum << endl; if (my_rank == 0) cout << local_sum << endl; MPI_Finalize(); return 0; }

3. 树形结构与蝶形结构比较

​ 蝶形结构主要用于分布式系统中，每个进程都希望获得所有数的和，即每个进程都希望能得到最后的结果。而树形结构的话只是将部分和集中，最后只有0号进程能获得所有数字的总和。