并行计算性能分析与模型概述

### 并行程序性能分析：执行时间与计算模型 #### 1. 并行执行时间分析 并行程序的并行执行时间受到多种因素的影响，具体如下： - **输入数据大小**：用 \(n\) 表示输入数据的大小，此外可能还受算法迭代次数、循环边界等因素影响。 - **处理器数量**：以 \(p\) 表示处理器的数量。 - **通信参数**：用于描述并行系统或通信库的通信特性。 对于特定的并行程序，其并行执行时间可以表示为关于 \(p\) 和 \(n\) 的函数 \(T(p, n)\)。下面通过并行标量积和矩阵 - 向量积的并行实现来具体分析。 ##### 1.1 并行标量积 并行标量积用于计算两个向量 \(a, b \in R^n\) 的标量值，即 \(a_j \cdot b_j\)（\(j = 1, \ldots, n\)）的和。在 \(p\) 个处理器上进行并行计算时，假设 \(n\) 能被 \(p\) 整除，即 \(n = r \cdot p\)（\(r \in N\)），且向量按块分布。处理器 \(P_k\) 存储元素 \(a_j\) 和 \(b_j\)（\(r \cdot (k - 1) + 1 \leq j \leq r \cdot k\)），并计算部分标量积 \(c_k\)： \[c_k = \sum_{j = r \cdot (k - 1) + 1}^{r \cdot k} a_j \cdot b_j\] 最后通过单累加操作得到最终结果 \(c = \sum_{k = 1}^{p} c_k\)。并行执行时间取决于计算时间和通信时间。假设执行一次算术运算需要 \(\alpha\) 个时间单位，向互连网络中的相邻处理器发送一个浮点值需要 \(\beta\) 个时间单位。部分标量积的并行计算时间为 \(2r\alpha\)。 单累加操作的时间取决于具体的互连网络，下面分别分析线性阵列和超立方体两种情况。 - **线性阵列**：在线性阵列中，单累加操作的最优根节点是中间节点，因为它与其他节点的距离不超过 \(p/2\)。每个节点在 \(\beta\) 时间内从左（或右）邻居获取一个值，在 \(\alpha\) 时间内将该值与本地值相加，并在下一步将结果发送到右（或左）邻居。通信时间为 \(\frac{p}{2}(\alpha + \beta)\)，总的并行执行时间为： \[T(p, n) = 2\frac{n}{p}\alpha + \frac{p}{2}(\alpha + \beta)\] 该函数表明，随着处理器数量 \(p\) 的增加，计算时间减少，但通信时间增加。通常，并行执行时间会随着 \(p\) 的增加而减少，直到通信开销的影响过大，然后并行执行时间又会增加。通过求导可以确定最优的 \(p\) 值，使并行执行时间最小。对 \(T(p)\) 求一阶导数： \[T'(p) = -\frac{2n\alpha}{p^2} + \frac{\alpha + \beta}{2}\] 令 \(T'(p) = 0\)，可得 \(p^* = \pm\sqrt{\frac{4n\alpha}{\alpha + \beta}}\)。二阶导数 \(T''(p) = \frac{4n\alpha}{p^3}\)，且 \(T''(p^*) > 0\)，说明 \(T(p)\) 在 \(p^*\) 处取得最小值。当 \(\beta > (4n - 1)\alpha\) 时，\(p^* < 1\)，此时应使用顺序程序。 - **超立方体**：对于 \(d\) 维超立方体（\(d = \log p\)），单累加操作可以使用生成树在 \(\log p\) 个时间步内完成。每个步骤发送数据和本地加法需要 \(\alpha + \beta\) 个时间单位，通信时间为 \(\log p(\alpha + \beta)\)，总的并行执行时间为： \[T(n, p) = \frac{2n\alpha}{p} + \log p \cdot (\alpha + \beta)\] 同样通过求导来确定最优的 \(p\) 值。一阶导数为： \[T'(p) = -\frac{2n\alpha}{p^2} + (\alpha + \beta)\frac{1}{p}\frac{1}{\ln 2}\] 令 \(T'(p) = 0\)，可得 \(p^* = \frac{2n\alpha \ln 2}{\alpha + \beta}\)。二阶导数 \(T''(p) = \frac{4n\alpha}{p^3} - \frac{1}{p^2}\frac{\alpha + \beta}{\ln 2}\)，且 \(T''(p^*) > 0\)，说明 \(T(p)\) 在 \(p^*\) 处取得最小值。这表明最优处理器数量随着 \(n\) 的增加而增加，且比线性阵列的增长速度更快，这是由于单累加操作的实现更快。 ##### 1.2 并行矩阵 - 向量积 矩阵 - 向量积 \(A \cdot b = c\)（\(A \in R^{n \times n}\)，\(b \in R^n\)）的并行实现可以采用矩阵 \(A\) 的行分布或列分布。假设 \(n\) 是处理器数量 \(p\) 的倍数，即 \(r = \frac{n}{p}\)，且执行一次算术运算需要 \(\alpha\) 个时间单位。 - **行分布实现**：处理器 \(P_k\) 存储矩阵 \(A\) 的第 \(r \cdot (k - 1) + 1 \leq i \leq r \cdot k\) 行，并计算结果向量 \(c\) 的元素 \(c_i\)： \[c_i = \sum_{j = 1}^{n} a_{ij} \cdot b_j\]