并行计算：矩阵相乘的棋盘式算法解析

"这篇文档是关于矩阵相乘的并行算法设计的课程设计分析报告，由廖杰在2014年完成。报告探讨了如何利用并行处理技术，如MPI、OpenMP、MR，来优化大尺寸矩阵的乘法运算，特别是关注棋盘式分块划分的Cannon算法和Summa算法。" 在并行计算领域，矩阵相乘的并行算法是提升计算效率的关键。本报告的主要目标是让学生熟悉并行处理环境，掌握并行编程技巧，并运用这些技巧来解决实际问题。实验要求学生自动生成矩阵，使用并行处理技术进行编程，矩阵大小至少为1000*1000，并且以加速比作为评价性能的重要指标。 实验内容详细阐述了两种主要的矩阵划分策略：行列划分和棋盘划分。行列划分，也称为带状划分，将矩阵的行或列分为多个组，每个组分配给一个处理器。这种方法适合于处理器数量较少的情况，但并行度有限。相比之下，棋盘划分能够实现更高的并行度，特别是在大型矩阵乘法中。它将矩阵划分为子矩阵，每个子矩阵对应一个处理器，且处理器不持有完整的行或列。这种划分方式特别适用于二维处理器阵列，可以实现更高效的通信和计算。 Cannon算法是棋盘式划分的经典应用，它能处理相同尺寸的n*n矩阵，每个处理器处理n/p * n/p个元素，适用于处理器阵列为p*p的情况。然而，Cannon算法的局限在于其对矩阵尺寸的要求，限制了其在非方阵乘法中的应用。Summa算法则更加灵活，可以处理不同尺寸的m*l矩阵和l*n矩阵的乘法，提供了更大的灵活性。 算法原理部分，行划分法是一种简单的并行策略，其中主进程首先广播矩阵N给所有从进程，然后从进程各自计算其分配的矩阵M的部分行与N的乘积，最后将结果返回给主进程。这种方法简化了通信流程，但在大规模并行计算中可能因数据传输量大而效率降低。 这个课程设计通过矩阵相乘的并行算法，让学生深入理解并行计算的原理和实践，提高解决复杂计算问题的能力。并行处理技术如MPI、OpenMP、MR的应用，不仅能够加速计算速度，还能为大数据时代下的高性能计算提供解决方案。