Cannon算法与并行矩阵相乘

该文档是关于矩阵相乘的并行算法设计的课程设计分析报告，主要探讨了行列划分和棋盘划分两种并行计算策略，包括Cannon算法和Summa算法，并简述了算法原理。 在并行计算领域，矩阵相乘是一个经典问题，其并行化能够显著提高计算效率。本报告首先介绍了两种矩阵划分方法： 1. **行列划分**：这种方法将矩阵按照行或列进行均匀分割，分配给各个处理器。例如，对于一个8×8的矩阵，可以将其划分为1×4或4×1的分块矩阵，每个处理器处理2行（或2列）的数据。这种划分方式适合于处理器数量小于矩阵维度的情况。 2. **棋盘划分**：也称为Cannon算法，它将矩阵划分为棋盘状，每个处理器处理(n/p)×(n/p)大小的子矩阵，其中n是矩阵的维度，p是处理器的数量。棋盘划分的优势在于可以利用二维处理器网格进行并行计算，使得通信和计算能够同步进行。同时，报告提到了另一种棋盘式算法——Summa算法，它能处理不同尺寸的矩阵，比Cannon算法更具通用性。 接着，报告详细阐述了两种算法的原理： - **行划分法**：这是一种简单的并行策略，主进程分配矩阵M，从进程计算各自分配到的行与矩阵N的乘积，最后主进程收集所有结果。这种方法中，矩阵M根据进程数量被分成块，最后一块可能不规则，因为它包含未整除的行。 - **Cannon算法**：Cannon算法的核心是利用二维处理器网格，通过循环移动矩阵块使其对齐，以便进行匹配的块乘法。每个处理器只处理一对可以直接相乘的块，这样可以实现并行计算所有必要的乘法操作。 最后，Summa算法引入了秩nb的修正，即将矩阵分解为nb大小的列块和行块进行相乘。广播操作通过逻辑处理器行环或列环的流水线传输实现，这允许计算和通信的重叠，提高了并行效率。 总结来说，这份报告深入探讨了矩阵相乘的并行算法，特别是行列划分和棋盘划分的策略，以及Cannon算法和Summa算法的实现细节，对于理解并行计算在处理大规模矩阵运算中的应用具有重要意义。