并行计算：棋盘划分与矩阵-向量乘法

"棋盘划分的矩阵-向量乘法是一种在并行计算环境中优化矩阵运算的方法，常见于大规模数值计算。此方法来源于中国科学技术大学的讲义，旨在提高计算效率，尤其适用于处理大型矩阵。" 这篇讲义讨论了如何通过棋盘划分策略将矩阵-向量乘法任务分解到多个处理器上，以实现并行计算。具体来说，棋盘划分是将一个大的n×n矩阵分割成p个子矩阵（或称为“块”），每个子矩阵对应一个处理器Pi,i，其中Pij用来存放原矩阵的ai,j元素。对于理想情况p=n²，算法步骤如下： 1. 每个处理器Pi,i将存储在其内的向量元素xi广播到所有与其相邻的处理器Pj,i（即同一列的其他处理器）。 2. 接着，处理器按照行方向执行乘法-加法操作，并累加结果。最后一列的处理器Pi,n-1将收集并积累全部结果，得到最终的向量yi。 当p小于n²时，处理器会形成一个二维网格结构，算法中的广播操作会涉及到X中相应的少于n²/p个分量。在此过程中，计算时间Tp(CT)分为三部分：首先，将X中相应分量放入Pi,i的通信时间；其次，按列进行一次到多次广播的时间；最后，按行进行单点积累的时间。 讲义还涵盖了并行计算的更广泛主题，包括并行计算的基础知识，如并行计算机系统结构模型，当代并行机系统（如SMP、MPP和Cluster），以及并行计算性能评测。此外，它深入探讨了并行算法的设计，包括设计基础、一般设计方法、基本设计技术和过程。在并行数值算法部分，讲义讨论了基本通信操作、稠密矩阵运算、线性方程组求解和快速傅里叶变换。最后，它涵盖了并行程序设计，包括基础概念、编程模型以及在共享和分布式存储系统中的编程实践，以及并行程序设计环境和工具。 这种方法不仅提高了计算速度，还减少了计算资源的闲置，是并行计算领域中优化大规模计算任务的关键技术之一。通过理解并掌握这种棋盘划分的矩阵-向量乘法，可以有效地应用于解决科学与工程问题中的高复杂度计算需求。