并行程序设计实验报告

陈翊辉

SA19011116

[toc]

公共部分

并行求和

蝶式求和

并行算法描述

蝶形运算是并行计算中一种基本的方法，快速傅里叶变换就通常使用蝶形运算，而蝶形求和也是最简单的蝶形计算，可以使$2^n$个处理器经过$n$步得到全和。其并行算法如下：

输入：n个数，每个处理器上各有一个，n是2的幂，n=2^M
输出：n个数的和，每个处理器上都有
Begin
  for k=1 to m do
      计算对应处理器号t
      按蝶形计算向对应处理器t发送自己的部分和（第一次是初始数）
      按蝶形计算从对应处理器t接收部分和并加到自己部分和（第一次是初始数）
  end for
End

其中对应处理器号t计算

base = 2 ** k;
group = rank / base;
offset = rank % base;
target = (group % 2 ? group - 1 : group + 1) * base + offset;

MPI实现

在蝶形运算中，共有$log_2n$步，每一步需要每个处理器给对应处理器发送，并从对应处理器接收，如果都先发或先收则必定造成死锁，这里用简单的rank和target比较判断，也可以考虑异步收发或者用MPI_Sendrecv。

核心MPI代码

for (int i = 0; i < steps; ++i) {
    int group = rank / base;
    int offset = rank % base;
    int target = (group % 2 ? group - 1 : group + 1) * base + offset;
    if (rank < target) {
      MPI_Send(reinterpret_cast<void*>(&send), 1, MPI_INT, target, target, MPI_COMM_WORLD);
      MPI_Recv(reinterpret_cast<void*>(&recv), 1, MPI_INT, target, rank, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    } else {
      MPI_Recv(reinterpret_cast<void*>(&recv), 1, MPI_INT, target, rank, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      MPI_Send(reinterpret_cast<void*>(&send), 1, MPI_INT, target, target, MPI_COMM_WORLD);
    }
    send += recv;
    base *= 2;
  }

完整代码见附件

性能结果

问题规模	任务数	总运行时间(sec)
4	4	0.021
8	8	0.025
16	16	0.020
32	32	0.168
64	64（跨机器）	0.397
128	128（跨机器）	0.447

二叉树求和

并行算法描述

二叉树求和使$2^n$个处理器经过$2n$步得到全和，前$n$步是树上的归约求和过程，后$n$步是发送结果过程。其并行算法如下：

输入：n个数，每个处理器上各有一个，n是2的幂，n=2^M
输出：n个数的和，每个处理器上都有
Begin
  for k=1 to m do
      叶子结点向根节点发送部分和（第一次是初始数）
      根结点求和，根结点继续下一轮，非根结点结束
  end for
  for k=1 to m do
      根结点向两个孩子结点发送全和
  end for
End

二叉树根的选取可以任意，一种比较简单的二叉树构建方法是按处理器编号0,1;2,3;...;构建，每次编号小的作为根结点，然后进行下一轮运算。

MPI实现

一种比较简单的确定二叉树方法是按处理器编号0,1;2,3;...;构建，每次编号小的作为根结点，然后进行下一轮运算。比如开始时，所有结点都参与，即mod1=0的参与，mod2=0的作为根结点；第2步，mod2=0的参与，mod4=0的作为根结点......发送结果时反过来。

根结点和非根节点一个收，一个发，只需要用最简单的MPI_Send和MPI_Recv即可。

核心MPI代码

  int base = 1;
  for (int i = 0; i < steps; ++i) {
    if (rank % base == 0) {
      int b = base * 2;
      if (rank % b == 0) { // recv
        MPI_Recv(&recv, 1, MPI_INT, rank + base, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      } else { // send
        MPI_Send(&send, 1, MPI_INT, rank - base, 0, MPI_COMM_WORLD);
      }
    }
    send += recv;
    base *= 2;
  }
  base /= 2;
  for (int i = 0; i < steps; ++i) {
    if (rank % base == 0) {
      int b = base * 2;
      if (rank % b == 0) { // recv
        MPI_Send(&send, 1, MPI_INT, rank + base, 0, MPI_COMM_WORLD);
      } else { // send
        MPI_Recv(&send, 1, MPI_INT, rank - base, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      }
    }
    base /= 2;
  }

完整代码见附件

性能结果

问题规模	任务数	总运行时间(sec)
4	4	0.022
8	8	0.013
16	16	0.048
32	32	0.156
64	64（跨机器）	0.394
128	128（跨机器）	0.466

FOX矩阵乘法

并行算法描述

和其他并行矩阵乘法类似，FOX矩阵乘法基本原理也是矩阵分块乘法，不同的是使用了不同的矩阵块传送策略。

输入：n*n矩阵A，n*n矩阵B，初始时A和B分成p个子矩阵，处理器P[i,j]存有块A[i,j]和B[i,j](q * q = p，处理器编号0,0;0,1;...;q-1,q-1)
输出：n*n矩阵C，每个处理器P[i,j]存有块C[i,j]
Begin
  for k = 1 to q do
      处理器P[i,(i+k) mod q]向所在行广播其A子块
      各处理器将接收到的A子块和自己的B子块进行矩阵乘，并加到结果部分和
      B子块向上循环移动
  end for
End

MPI实现

MPI实现主要有几个部分：

矩阵A和B读取和分发，由进程0完成
运算过程
- 广播A子块
- 部分和矩阵乘
- B子块循环移动
矩阵C的接收，输出

其中读取，输出，部分矩阵乘虽然是比较基础的操作，但考虑到有广播分发，和接收的操作，需要考虑其数据摆放（layout）。

输入数据矩阵A和B按正常顺序放在文本文件中。

如果直接按顺序读入内存，则在散播子块时比较不方便，因为每一子块的内存不是连续的，这样要么需要再申请一块内存搬动数据，要么就需要分部分传输每个子块。因而考虑读入时就按子块连续的方式存放。

比如4*4矩阵，分到4个处理器，读入数据摆放如下，这样直接使用一个MPI_Scatter就可完成子块分发。

在运算前，需要将处理器按行和列分到不同的通信域中，因为处理器初始的编号是一维的，而算法需要二维的编号，并且一些在行内，列内的操作也需要各自的通信域。

运算过程中，广播A子块使用MPI_Bcast，在行通信域内广播

B子块的循环移动，可以使用MPI_Sendrecv，每个处理器的源是下一行，目标是上一行（环形考虑）

矩阵C的接收和矩阵AB的分发正好相反，使用MPI_Gather汇集到0处理器上，这时接收到的C矩阵不是正常顺序，需要根据一定的顺序输出。

核心MPI代码

数据摆放变换，矩阵乘法

class MatWrap {
 private:
  float* data_;
  int n_;

 public:
  MatWrap() {}
  MatWrap(float* data, int n) : data_(data), n_(n) {}
  float* operator[](size_t n) const { return data_ + n * n_; }
  float* split_map(int sqrt_q, int i, int j) const {
    int sub_n = n_ / sqrt_q;
    return data_ + (i / sub_n * sqrt_q + j / sub_n) * sub_n * sub_n +
           i % sub_n * sub_n + j % sub_n;
  }
  friend void MatMultAdd(const MatWrap& a, const MatWrap& b, MatWrap& c);
};
void MatMultAdd(const MatWrap& a, const MatWrap& b, MatWrap& c) {
  assert(a.n_ == b.n_);
  assert(a.n_ == c.n_);
  int n = a.n_;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) {
        c[i][j] += a[i][k] * b[k][j];
      }
    }
  }
}

完整代码见附件

并行计算部分

  // broadcast sub matrix
  MPI_Scatter(mat_a, sub_n * sub_n, MPI_FLOAT, sub_mat_a, sub_n * sub_n,
              MPI_FLOAT, 0, MPI_COMM_WORLD);
  MPI_Scatter(mat_b, sub_n * sub_n, MPI_FLOAT, sub_mat_b, sub_n * sub_n,
              MPI_FLOAT, 0, MPI_COMM_WORLD);
  // split comm in col and row
  MPI_Comm col_world, row_world;
  int col_rank = rank % sqrt_q;
  int row_rank = rank / sqrt_q;
  MPI_Comm_split(MPI_COMM_WORLD, col_rank, row_rank, &col_world);
  MPI_Comm_split(MPI_COMM_WORLD, row_rank, col_rank, &row_world);
  // compute
  for (int i = 0; i < sqrt_q; ++i) {
    // broadcast sub_a
    int send_root = (row_rank + i) % sqrt_q;
    if (col_rank == (row_rank + i) % sqrt_q) {
      memcpy(sub_mat_comm, sub_mat_a, sub_n * sub_n * sizeof(float));
    }
    MPI_Bcast(sub_mat_comm, sub_n * sub_n, MPI_FLOAT, send_root, row_world);
    // calculate sub mat gemm
    MatMultAdd(sub_comm, sub_b, sub_c);
    // swap sub_b
    MPI_Sendrecv_replace(
        sub_mat_b, sub_n * sub_n, MPI_FLOAT, (row_rank + sqrt_q - 1) % sqrt_q,
        1, (row_rank + 1) % sqrt_q, 1, col_world, MPI_STATUS_IGNORE);
  }
  // gather result
  MPI_Gather(sub_mat_c, sub_n * sub_n, MPI_FLOAT, mat_c, sub_n * sub_n,
             MPI_FLOAT, 0, MPI_COMM_WORLD);

性能结果

问题规模	并行数	总运行时间(sec)
128	1	0.123
256	4	0.288
512	16	0.784
1024	64	4.856

问题规模	并行数	总运行时间(sec)	加速比
512	1	2.551	1.00
512	4	1.099	2.32
512	16	0.784	3.25
512	64	1.248	2.04

参数服务器系统

并行算法描述

设系统中总计有N个进程，其中P个进程作为参数服务器进程，而Q个进程作为工作进程（N = P + Q，且 0 < P << Q）。工作进程和服务器进程的互动过程如下：

第i个工作进程首先产生一个随机数，发送给第i%P个参数服务器进程。然后等待并接收它对应的参数服务器进程发送更新后的数值，之后，再产生随机数，再发送……。
每个参数服务器进程等待并接收来自它对应的所有工作进程的数据，在此之后，经通信，使所有的参数服务器获得所有工作进程发送数据的平均值。

每个参数服务器发送该平均值给它对应的所有工作进程，然后再等待……

do while true
工作进程i产生随机数
i mod p参数服务器接收进程i的随机数
所有服务器通信计算所有数据平均值
参数服务器发送平均值给工作进程
end do

MPI实现

为了方便各种通信，需要划分通信域：

所有服务器之间的域：服务器间通信，计算平均值
服务器和各自负责的工作进程的域：服务器接收随机数，发送平均值

划分好通信域之后就比较简单了，

服务器从每个工作进程接收随机数

因为最终只需要计算一个平均值，并且要等待每个工作进程，直接使用MPI的归约操作 MPI_Reduce，其中的操作MPI_SUM，这样每个服务器都有着负责的工作进程的数字的和。

所有服务器通信计算平均值这里需要每个服务器都获得所有工作进程的平均，而现在每个服务器只有自己负责工作进程的部分和，考虑使用MPI_Allreduce，其中的操作仍为MPI_SUM，这时每个服务器都有所有工作进程的和，再除以工作进程数即可获得进程的平均数。
服务器发送平均值给工作进程每个服务器把平均数广播给工作进程即可。

核心MPI代码

  // server or client
  int SorC = rank >= SERVER_NUM;
  MPI_Comm serverClient, service;
  MPI_Comm_split(MPI_COMM_WORLD, SorC, -1, &serverClient);
  int service_num = rank % SERVER_NUM;
  MPI_Comm_split(MPI_COMM_WORLD, service_num, SorC, &service);
  int service_rank;
  MPI_Comm_rank(service, &service_rank);
  // start
  float value;
  float sum;
  for (int i = 0; i < LOOP; ++i) {
    if (SorC) { // client
      value = dis(gen);
      // printf("c:%d, %d, %f\n", rank, service_rank, value);
    } else { // server
      value = 0;
    }
    MPI_Reduce(&value, &sum, 1, MPI_FLOAT, MPI_SUM, 0, service);
    if (!SorC) {
      // printf("s:%d, %d, %f\n", rank, service_rank, sum);
      MPI_Allreduce(&sum, &value, 1, MPI_FLOAT, MPI_SUM, serverClient);
      value /= (size - SERVER_NUM);
      // printf("s:%d, %d, %f\n", rank, service_rank, value);
    }
    MPI_Bcast(&value, 1, MPI_FLOAT, 0, service);
    // printf("c:%d, %f\n", rank, value);
  }

完整代码见附件

性能结果

交换次数	服务器数	工作进程数	总运行时间(sec)
1024	1	8	0.036
1024	2	16	0.087
1024	4	24	0.268
1024	4	32	0.292

交换次数	服务器数	工作进程数	总运行时间(sec)	加速比
1024	1	64	0.441	-
1024	2	64	1.496	-
1024	4	64	0.714	-
1024	8	64	0.684	-

从结果上看，当工作进程数增加时，服务器成比例增加也难以保证总运行时间，因为每次运行需要所有服务器间通信一次。

而当工作进程数固定下，增加服务器数并不能使服务时间线性下降，服务器为1时是一个特例，因为服务器间不再需要通信。因而在服务器负载均衡时，尽量减少服务器间的通信，有时不均衡的微服务设计会好于非常均匀的负载均衡。

个人实验

问题描述

LSTM长短时记忆

长短期记忆（英语：Long Short-Term Memory，LSTM）是一种时间递归神经网络（RNN），论文首次发表于1997年。由于独特的设计结构，LSTM适合于处理和预测时间序列中间隔和延迟非常长的重要事件。LSTM可以应用在语音识别，机器翻译，自然语言处理，手写识别等机器学习应用。

串行算法描述

计算公式

$$ it=\text{sigmoid}(W{ii}xt+b{ii}+W{hi}h{(t-1)}+b_{hi})\ ft=\text{sigmoid}(W{if}xt+b{if}+W{hf}h{(t-1)}+b_{hf})\ gt=\text{tanh}(W{ig}xt+b{ig}+W{hc}h{(t-1)}+b_{hg})\ ot=\text{sigmoid}(W{io}xt+b{io}+W{ho}h{(t-1)}+b_{ho})\ c_t=ft\cdot c{(t-1)}+i_t\cdot g_t\ h_t=o_t\cdot \text{tanh}(c_t) $$

对于上面公式的矩阵乘加计算，使用增广矩阵形式，化为矩阵乘。 $$ it=\text{sigmoid}(W{ii}xt+W{hi}h_{(t-1)})\ ft=\text{sigmoid}(W{if}xt+W{hf}h_{(t-1)})\ gt=\text{tanh}(W{ig}xt+W{hc}h_{(t-1)})\ ot=\text{sigmoid}(W{io}xt+W{ho}h_{(t-1)})\ c_t=ft\cdot c{(t-1)}+i_t\cdot g_t\ h_t=o_t\cdot \text{tanh}(c_t) $$

串行伪代码

输入：增广输入向量x[1..T]，增广矩阵形式权值W_ii,W_if,W_ig,W_io
输出：预测向量h[1..T]
for t = 1 to T
    i[t] = sigmoid(W_ii * x[t] + W_hi * h[t-1])
    f[t] = sigmoid(W_if * x[t] + W_hf * h[t-1])
    g[t] = tanh(W_ig * x[t] + W_hc * h[t-1])
    o[t] = sigmoid(W_io * x[t] + W_ho * h[t-1])
    c[t] = f[t] .* c[t-1] + i[t] .* g[t]
    h[t] = o[t] .* tanh(c[t])    
end for

并行算法描述

PCAM设计

1）划分

从功能上看，上面算法中主要可分为it,ft,gt,ot,ct,ht

从任务负载来看，上面算法中运行时间比重较大的是矩阵乘加运算——it,ft,gt和ot的工作量相同，而ct,ht的工作量稍少。

在每个矩阵乘加运算中，可以按照分块矩阵乘法对矩阵乘加进一步划分。

2）通信

计算it,ft,gt,ot需要xt,ht-1，而ct需要ft,it,gt，ht需要ot,ct

3）组合

考虑ct,ht工作量较少，且需要传输较多数据，将ct,ht和it合并

4）映射

it,ct,ht; ft; gt; ot分别放在4个处理机上，这时这4个处理机任务量非常接近，且此时传输数据量较少。

而it,ct,ht; ft; gt; ot各自计算矩阵乘时，再将矩阵分块，分配到各自通信域中的处理机上。

依赖关系分析

从上面公式和串行伪代码来看，依赖关系非常明显，输出$c_t,ht$流依赖于$c{(t-1)},f_t,g_t,i_t,o_t$，而$i_t,f_t,g_t,ot$又六依赖于$h{(t-1)}$，对于这种随时间的迭代计算，不同时间$t$之间不能并行计算，因而考虑$i_t,f_t,g_t,o_t$可以并行计算，而在$i_t,f_t,g_t,o_t$内有矩阵乘加计算，也可以使用分块矩阵的并行计算。

MPI+OpenMP设计

对于LSTM的各个时间点的计算，无法并行

对于LSTM的一个时间点内的计算，考虑在同一个节点上使用MPI分为$i_t,f_t,g_t,o_t$4个部分在4个节点上计算，需要广播$xt,h{(t-1)}$，最后由0号节点收集结果，再在0号节点上计算$c_t,h_t$

$i_t,f_t,g_t,o_t$每个部分内的矩阵乘法使用OpenMP计算

MPI+OpenMP实现

矩阵乘，矩阵加，激活，OpenMP实现

void MatrixMult(float *a, float *b, float *c, int n, bool init = false) {
  #pragma omp parallel for num_threads(OMP_THREADS)
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (init) {
        c[i * n + j] = 0.0f;
      }
      for (int k = 0; k < n; ++k) {
        c[i * n + j] += a[i * n + k] * b[k * n + j];
      }
    }
  }
}

void MatrixDot(float *a, float *b, float *c, int n) {
  #pragma omp parallel for num_threads(OMP_THREADS)
  for (int i = 0; i < n * n; ++i) {
    c[i] = a[i] * b[i];
  }
}

void MatrixAdd(float *a, float *b, float *c, int n) {
  #pragma omp parallel for num_threads(OMP_THREADS)
  for (int i = 0; i < n * n; ++i) {
    c[i] = a[i] + b[i];
  }
}

void tanh(float *x, float *y, int n) {
  #pragma omp parallel for num_threads(OMP_THREADS)
  for (int i = 0; i < n; ++i) {
    y[i] = std::tanh(x[i]);
  }
}

void sigmoid(float *x, float *y, int n) {
  #pragma omp parallel for num_threads(OMP_THREADS)
  for (int i = 0; i < n; ++i) {
    y[i] = 1.0f / (1.0f + std::exp(-x[i]));
  }
}

随时间迭代计算，MPI实现

  // computing
  for (int i = 0; i < seq_len; ++i) {
    // broadcast x
    if (rank == 0) {
      memcpy(sub_x, x + i * n * n, n * n * sizeof(float));
    }
    MPI_Bcast(sub_x, n * n, MPI_FLOAT, 0, MPI_COMM_WORLD);
    // broadcast h
    if (i == 0) {
      for (int i = 0; i < n * n; ++i) {
        sub_h[i] = 0.0f;
      }
    } else {
      MPI_Bcast(sub_h, n * n, MPI_FLOAT, 0, MPI_COMM_WORLD);
    }
    // matrix multply
    MatrixMult(sub_w, sub_x, ifgo, n, true);
    MatrixMult(sub_w + n * n, sub_h, ifgo, n);
    // active
    if (rank == 2) {
      tanh(ifgo, ifgo, n * n);
    } else {
      sigmoid(ifgo, ifgo, n * n);
    }
    // gather result
    if (rank == 0) {
      MPI_Recv(ft, n * n, MPI_FLOAT, 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      MPI_Recv(gt, n * n, MPI_FLOAT, 2, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      MPI_Recv(ot, n * n, MPI_FLOAT, 3, 3, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    } else if (rank == 1) {
      MPI_Send(ifgo, n * n, MPI_FLOAT, 0, 1, MPI_COMM_WORLD);
    } else if (rank == 2) {
      MPI_Send(ifgo, n * n, MPI_FLOAT, 0, 2, MPI_COMM_WORLD);
    } else if (rank == 3) {
      MPI_Send(ifgo, n * n, MPI_FLOAT, 0, 3, MPI_COMM_WORLD);
    }
    // compute ct ht
    if (rank == 0) {
      MatrixDot(ft, c, c, n);
      MatrixDot(ifgo, gt, gt, n);
      MatrixAdd(c, gt, c, n);
      tanh(c, sub_h, n * n);
      MatrixDot(ot, sub_h, sub_h, n);
      memcpy(h + i * n * n, sub_h, n * n * sizeof(float));
    }
  }

完整代码见附件

性能结果

问题规模	OpenMP线程数	总运行时间(sec)
64	1	0.492
128	2	1.725
256	4	6.681
512	8	46.498

问题规模	OpenMP线程数	总运行时间(sec)	加速比
256	1	19.848	1.00
256	2	11.068	1.79
256	4	7.162	2.77
256	8	6.252	3.17

分组实验

章	15	19	22
算法程序数	4	2	2
分到的程序号	1	1	1
分到的程序	closure	gauss	fft

closure-MPI

性能结果

1 | 问题规模 | MPI进程数 | 总运行时间(sec) | | -------- | --------- | --------------- | | 64 | 1 | 0.122 | | 128 | 4 | 0.267 | | 256 | 16 | 0.276 | | 512 | 64 | 4.923 | 2

问题规模	MPI进程数	总运行时间(sec)	加速比
256	1	1.014	1.00
256	4	0.811	1.25
256	16	1.396	0.72
256	64	4.923	0.21

改进

优化了数据传输，使用MPI_Bcast, MPI_Scatter, MPI_Gather替换了for-MPI_Send-MPI_Recv
使用管道重定向输入输出
自动化性能测试脚本

完整代码见附件

closure-Hybrid-omp-mpi

MPI+OpenMP实现

原有程序为MPI行划分实现，很难再在行内新增OpenMP并行。因而考虑重新设计并行方案。closure运算的本质是布尔矩阵乘，因而考虑使用分块并行矩阵乘法，使用MPI分块并行矩阵乘法，在每个子矩阵块乘法再使用OpenMP行划分矩阵并行乘法。

核心代码

void MatMultAdd(const MatWrap& a, const MatWrap& b, MatWrap& c) {
  assert(a.n_ == b.n_);
  assert(a.n_ == c.n_);
  int n = a.n_;
#pragma omp parallel for num_threads(OMP_THREADS)
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) {
        c[i][j] = static_cast<bool>(c[i][j] + a[i][k] * b[k][j]);
      }
    }
  }
}

  for (int k = 0; k <= std::log2f(n); ++k) {
    for (int i = 0; i < sub_n; ++i) {
      for (int j = 0; j < sub_n; ++j) {
        sub_c[i][j] = 0;
      }
    }
    // broadcast sub matrix
    MPI_Scatter(mat_a, sub_n * sub_n, MPI_INT, sub_mat_a, sub_n * sub_n,
                MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Scatter(mat_a, sub_n * sub_n, MPI_INT, sub_mat_b, sub_n * sub_n,
                MPI_INT, 0, MPI_COMM_WORLD);
    // split comm in col and row
    MPI_Comm col_world, row_world;
    int col_rank = rank % sqrt_q;
    int row_rank = rank / sqrt_q;
    MPI_Comm_split(MPI_COMM_WORLD, col_rank, row_rank, &col_world);
    MPI_Comm_split(MPI_COMM_WORLD, row_rank, col_rank, &row_world);
    // compute
    for (int i = 0; i < sqrt_q; ++i) {
      // broadcast sub_a
      int send_root = (row_rank + i) % sqrt_q;
      if (col_rank == (row_rank + i) % sqrt_q) {
        memcpy(sub_mat_comm, sub_mat_a, sub_n * sub_n * sizeof(int));
      }
      MPI_Bcast(sub_mat_comm, sub_n * sub_n, MPI_INT, send_root, row_world);
      // calculate sub mat gemm
      MatMultAdd(sub_comm, sub_b, sub_c);
      // swap sub_b
      MPI_Sendrecv_replace(
          sub_mat_b, sub_n * sub_n, MPI_INT, (row_rank + sqrt_q - 1) % sqrt_q,
          1, (row_rank + 1) % sqrt_q, 1, col_world, MPI_STATUS_IGNORE);
    }
    // gather result
    MPI_Gather(sub_mat_c, sub_n * sub_n, MPI_INT, mat_a, sub_n * sub_n, MPI_INT,
               0, MPI_COMM_WORLD);
    // print result
    if (rank == 0) {
      MatWrap mc(mat_a, n);
      printf("loop:%d\n", k);
      mc.print(true, sqrt_q);
    }
  }

完整代码见附件

性能结果

问题规模	OpenMP线程数	MPI进程数	总运行时间(sec)	加速比
64	1	1	0.122	1.00
64	2	1	0.090	1.36
64	4	1	0.067	1.82
256	1	4	1.255	1.00
256	2	4	0.834	1.50
256	4	4	0.647	1.94

gauss-MPI

性能结果

问题规模	任务数	总运行时间	分发数据时间	并行计算时间
512	1	0.387903	0.112848	0.275056
1024	2	1.265614	0.335754	0.929859
2048	4	4.077509	1.161536	2.915974
4096	8	19.073884	4.172863	14.901021
8192	16	100.614923	16.937205	83.677718

问题规模	任务数	总运行时间	分发数据时间	并行计算时间	加速比
2048	1	5.461998	1.217323	4.244675	1.00
2048	2	4.983760	1.240886	3.742874	1.13
2048	4	4.045694	1.148780	2.896914	1.47
2048	8	4.017666	1.161650	2.856016	1.49
2048	16	4.135822	1.286142	2.849679	1.48

改进

使用Python，numpy生成输入数据
重定向输出，使用管道重定向输出
自动化性能测试脚本

完整代码见附件

fft-MPI

性能结果

1 | 问题规模 | MPI进程数 | 总运行时间(sec) | | -------- | --------- | --------------- | | 512 | 1 | 0.036836 | | 1024 | 2 | 0.073674 | | 2048 | 4 | 0.148747 | | 4096 | 8 | 0.347353 | 2

问题规模	MPI进程数	总运行时间(sec)	加速比
4096	1	2.323001	1.00
4096	2	1.162240	2.00
4096	4	0.605259	3.84
4096	8	0.349958	6.64

改进

使用Python，numpy生成输入数据
重定向输出，使用管道重定向输出
自动化性能测试脚本
修改了输入数量规模上限

完整代码见附件

report.md 27 KB 고유링크 히스토리 Raw

并行程序设计实验报告

公共部分

并行求和

蝶式求和

并行算法描述

MPI实现

核心MPI代码

性能结果

二叉树求和

并行算法描述

MPI实现

核心MPI代码

性能结果

FOX矩阵乘法

并行算法描述

MPI实现

核心MPI代码

性能结果

参数服务器系统

并行算法描述

MPI实现

核心MPI代码

性能结果

个人实验

问题描述

LSTM长短时记忆

串行算法描述

计算公式

串行伪代码

并行算法描述

PCAM设计

依赖关系分析

MPI+OpenMP设计

MPI+OpenMP实现

矩阵乘，矩阵加，激活，OpenMP实现

随时间迭代计算，MPI实现

性能结果

分组实验

closure-MPI

性能结果

改进

closure-Hybrid-omp-mpi

MPI+OpenMP实现

核心代码

性能结果

gauss-MPI

性能结果

改进

fft-MPI

性能结果

改进

report.md 27 KB

고유링크 히스토리 Raw