高性能并行计算笔记

并行计算基础

粒度：在并行执行过程中，二次通讯之间每个处理机计算工作量大小的一个粗略描述。分为粗粒度、细粒度。

复杂性：在不考虑通讯开销的前提下，每个处理机上的计算量最大者，即为并行计算复杂性。

并行度：算法可以并行的程度。

加速比： $$ S_p(q)=\frac{T_s}{T_p(q)} $$ 效率： $$ E_p(q)=\frac{S_p(q)}{q} $$ Amdahl定律：假设串行计算所需要的时间$T_s=1$，$\alpha$是执行该计算所必须的串行部分所占的百分比，则有 $$ S_p(q)=\frac{1}{\alpha + \frac{1-\alpha}{q}} $$ Gustafson定律：假设并行计算所需要的时间$T_p=1$，$\alpha$是执行该并行计算所需的串行部分所占的百分比，则有 $$ S_p(q)=\frac{\alpha+(1-\alpha)\times q}{1} $$

矩阵乘并行计算

矩阵卷帘存储方式：对于一般$m\times n$分块矩阵和一般的处理机阵列$p\times q$，小块$A_{ij}$存放在处理机$P_{kl}(k=i\mod p,l=j\mod q)$中。

串行矩阵乘法：略，注意循环顺序。

行列分块算法：

$A_i,B_i,C_{i,j},j=0,1,…,p-1$存放在$P_i$中，这种存放方式使数据在处理机中不重复。由于使用$p$个处理机，每次每个处理机计算出一个$C_{i,j}$，计算$C$需要$p$次来完成。$C_{i,j}$的计算是按对角线进行的。

其中，C按行分块，处理机间传输B的分块：

行行分块算法：

$$ C_{i,*}=A_{i,*}B=\sum_{j=0}^{p-1}A_{i,j}B_{j,*} $$

其中，C按行分块，处理机间传送B的分块：

列行分块算法：

$$ C_{*,j}=\sum_{i=0}^{p-1}A_{*,i}B_{i,j} $$ C按列分块，处理机间通讯所传输的是计算的部分积：

列列分块算法：

$$ C_{*,j}=\sum_{i=0}^{p-1}A_{*,i}B_{i,j} $$ C按列分块，计算过程传送矩阵A的分块：

Cannon算法：

MPI学习笔记（四）：矩阵相乘的Cannon卡农算法 - 惊小呆520 - 博客园 (cnblogs.com)

主要的思路是A子矩阵横向循环传送，B子矩阵纵向循环传送。

子矩阵预重排：

LU分解

矩阵以一维卷帘方式存储，矩阵的第$i$列存放在$P_{i\mod p}$中。

迭代求解

Jacobi迭代法：每次使用上一轮的结果迭代求解直到收敛，易于并行。 $$ x^{(0)}=(x_1^{(0)},x_2^{(0)},…,x_n^{(0)})^T \ x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum_{j\neq i}^na_{ij}x_j^{(k)}),k=1,2,… $$ Gauss-Seidel迭代法：每次迭代都使用部分更新的数据，不易于并行。

FFT

内容量大，此文从略。