并行计算基础：复杂性度量与算法设计

"并行算法的复杂性度量-并行计算(中科大讲义)" 在并行计算领域，理解和度量并行算法的复杂性至关重要，因为它直接影响着算法的效率和适用性。串行算法的复杂性度量通常关注最坏情况下的复杂度（Worst-CASE Complexity）和期望复杂度（Expected Complexity），这些度量衡量的是算法在不同输入规模下执行所需的时间或资源。但在并行计算中，由于多处理器同时工作，我们还需要考虑新的复杂性度量指标。 首先，运行时间t(n)是并行算法的一个关键指标，它包括计算时间和通讯时间。计算时间步通常用来量化处理器执行基本操作的时间，而选路时间步则反映数据在处理器间传输所需的时间。n代表问题实例的输入规模，随着n的增长，算法的运行时间应尽可能保持低的增长率。 其次，处理器数p(n)也是一个重要的参数，它表示解决特定问题时使用的处理器数量。增加处理器可以提高并行算法的速度，但同时也可能引入更多的通信开销。 并行算法的成本c(n)综合了运行时间和处理器数，定义为c(n)=t(n)p(n)。这个指标旨在评估在给定硬件资源下解决问题的总代价，它不仅考虑了算法的执行速度，还考虑了硬件的使用效率。 总运算量W(n)是并行算法在求解问题过程中完成的总操作步数。这个度量关注的是算法的计算强度，即算法的计算密集程度。高总运算量可能意味着需要更多的计算资源，而优化算法的目标通常是降低这个量。 并行计算的内容涵盖了从并行计算机系统结构到并行算法设计的广泛领域。在结构方面，包括了并行计算机系统的互连网络，如静态互联网络、动态互连网络和标准互联网络，这些都是构建并行计算机系统的基础。而在算法设计方面，涉及到了并行算法设计的基础、一般设计方法和技术，以及并行数值算法，如基本通信操作、稠密矩阵运算和线性方程组的求解。此外，并行程序设计也占据了重要位置，包括并行程序设计模型、共享存储和分布存储系统编程，以及并行程序设计环境和工具的使用。 通过深入理解并行计算的这些基础知识和复杂性度量，可以设计出更高效、适应性强的并行算法，以满足现代科学和工程问题日益增长的计算需求。并行计算不仅仅是简单的任务分解，它涉及到系统架构、算法优化和编程模型等多个层面的综合考虑，是推动高性能计算发展的重要驱动力。