并行计算中的通讯与算法设计——以矩阵向量乘为例

"这篇内容是来自中国科学技术大学的并行计算讲义，涵盖了并行算法的通讯、并行计算的基础知识、并行计算机系统结构模型等多个主题。" 在并行计算领域，通讯是并行算法中至关重要的部分，它允许不同处理器间的数据交换，以实现并行计算的任务协同。在共享存储的多处理器系统中，通常使用`global read(X,Y)`和`global write(X,Y)`这样的操作来访问和修改全局内存中的数据。这两个操作允许所有处理器都能看到一致的内存视图，从而进行协作计算。 而在分布存储的多计算机系统中，由于数据分布在不同的计算节点上，通讯则依赖于`send(X,i)`和`receive(Y,j)`这样的消息传递机制。例如，在算法4.2中描述的分布存储多计算机上的矩阵向量乘法算法中，处理器通过发送和接收消息来协调计算过程。每个处理器首先计算其负责的子矩阵和向量的乘积，然后将结果累加到邻居处理器发送过来的结果上。这样的设计能够有效地将大规模计算任务分解到多个处理器上，提高计算效率。 并行计算的基础包括并行计算机系统结构模型和并行算法设计。从讲义的章节划分来看，第一篇主要介绍并行计算的基础知识，如并行计算机系统结构和性能评测；第二篇深入探讨并行算法的设计方法和技术；第三篇关注并行数值算法，包括基本通信操作、矩阵运算等；第四篇则讲解并行程序设计，涵盖从基础到分布式存储系统编程的各个层面。 并行计算机系统结构模型是理解并行计算的关键，它涉及到处理器之间的互连方式，如静态互联网络、动态互连网络以及标准互联网络。这些结构模型决定了数据如何在处理器之间高效地流动，对并行算法的效率和可扩展性有直接影响。 在实际应用中，设计并行算法时，需要考虑如何有效地分解任务、平衡负载，以及如何通过通讯机制协调各处理器的计算，以实现最佳性能。并行程序设计则涉及到编程模型的选择，如共享存储系统编程和分布式存储系统编程，以及使用各种并行程序设计环境和工具来简化开发过程。 这个讲义提供了并行计算的全面概述，从理论基础到实践技术，对于理解和掌握并行计算有着重要的指导意义。