分块矩阵相乘算法详解-并行计算

"这篇文档是关于单处理机上分块矩阵相乘算法的，主要源自《并行计算——结构·算法·编程》一书的修订版，由陈国良编著。书中详细介绍了如何在单处理机上实现分块矩阵乘法，并探讨了并行计算的概念、结构和编程技术。该算法将矩阵乘法任务分解为子矩阵的乘加运算，以提高计算效率。" 在单处理机上执行分块矩阵相乘算法，主要是为了减少大型矩阵乘法中的计算复杂度。传统的矩阵乘法算法需要执行 \( n^3 \) 次乘加运算，而分块矩阵乘法将大矩阵分成 \( q \times q \) 的子矩阵，每个子矩阵大小为 \( \frac{n}{q} \times \frac{n}{q} \)。算法执行 \( q^3 \) 次子矩阵乘法，每次子矩阵乘法需要 \( \left(\frac{n}{q}\right)^3 \) 次乘加运算，因此总乘加次数仍为 \( n^3 \)。 具体步骤如下： 1. **分块**：将两个输入矩阵 \( A \) 和 \( B \) 分成 \( p \times p \) 个子矩阵 \( A_{ij} \) 和 \( B_{ij} \)，每个子矩阵大小为 \( \frac{n}{p} \times \frac{n}{p} \)。 2. **计算**：在单处理机上，使用嵌套循环来遍历每个子矩阵对，将 \( C \) 矩阵对应的子矩阵初始化为零，然后对每个子矩阵执行乘加操作，即 \( C_{ij} = C_{ij} + A_{ik} \cdot B_{kj} \)，这里 \( k \) 是遍历的子矩阵索引。 3. **并行化**：如果使用 \( p \) 个处理器，每个处理器负责计算一个 \( C_{ij} \) 块。为了计算 \( C_{ij} \)，处理器需要广播 \( A \) 矩阵的相应子矩阵到同一行的所有处理器，同时广播 \( B \) 矩阵的子矩阵到同一列的所有处理器。完成通信后，处理器可以并行执行乘加运算。 并行计算中，当分块乘法在 \( p \) 个处理器的超立方体上执行时，考虑到通信时间和计算时间。通信时间大约为 \( 2(t_{slogp}+t_wn^{2p(p-1)}) \)，而计算时间为 \( p \times \left(\frac{n}{p}\right)^3 \)。这个模型展示了如何通过并行处理减小计算时间，提高效率。 此算法和相关内容对于理解和实现并行计算的高效算法，特别是在数值计算领域，如线性代数中的矩阵运算，具有重要意义。它也适用于计算机科学教育，作为面向21世纪课程教材的一部分，旨在培养学生的并行计算思维和编程能力。