并行计算：带状与棋盘划分的效率对比

"这篇讲义来自中国科学技术大学，主题是并行计算，涵盖了并行计算的基础、算法设计、数值算法和程序设计等多个方面。讲义中对比了带状划分和棋盘划分在处理网孔链接时的运行时间，指出棋盘划分在效率上优于带状划分。" 并行计算是一种利用多处理器或多个计算资源同时处理任务的计算方式，旨在提高计算速度和解决复杂问题。在并行计算领域，有效的任务划分和数据分布对于优化计算性能至关重要。讲义中提到了两种不同的任务划分策略——带状划分和棋盘划分，并通过网孔链接的例子进行了比较。 带状划分（Strip Partitioning）通常将问题空间沿一个方向连续地分割成多个条带，每个处理器负责处理一个条带内的任务。这种划分方式适用于数据有明显连续性的场景，但可能在处理器间通信时产生较高的开销，因为相邻条带间的通信频繁。 棋盘划分（Checkerboard Partitioning）则是将问题空间划分为交替的二维格子，每个处理器负责处理一部分交错的格子。这种方式减少了相邻处理器间的数据交换，从而可能降低通信延迟，提高整体效率。在网孔链接的例子中，棋盘划分显示出了比带状划分更快的运行时间。 并行计算的结构、算法和编程是并行计算学科的三大核心组成部分。讲义中详细介绍了并行计算机系统，包括SMP（对称多处理器）、MPP（大规模并行处理）和Cluster（集群）等架构，以及并行计算性能评测的标准和方法。此外，还深入讨论了并行算法设计的基础和一般方法，如并行化的基本设计技术，如任务分解、数据分区、负载均衡等。 在数值算法部分，讲义涵盖了基本通信操作、稠密矩阵运算、线性方程组求解和快速傅里叶变换等关键内容。在并行程序设计中，讲解了基础理论、编程模型，以及在共享存储和分布式存储系统中的编程实践，还提到了并行程序设计环境和工具的应用。 总结起来，这篇讲义为读者提供了一个全面的并行计算学习框架，从系统结构到算法设计，再到实际编程，旨在帮助读者理解和掌握并行计算的关键概念和技术，特别强调了带状和棋盘划分这两种策略在并行计算中的应用和效率差异。