并行计算的等效率度量与标准

"等效率度量标准-并行计算(中科大讲义)" 在并行计算领域，等效率度量标准是一种评估并行算法性能的重要指标。它关注的是随着处理器数量的增加，如何维持算法效率的稳定。这个概念由Kumar在1987年提出。等效率函数\( f_E(p) \)描述了问题规模\( W \)随着处理器数量\( p \)的变化关系，目的是在处理器增多时，通过调整问题规模来保持一定的算法效率\( E \)。 并行计算中，处理器的计算时间可以分为两部分：有用计算时间\( t_{ie} \)和额外开销时间\( t_{io} \)，后者包括通信、同步和空闲等待时间。整个系统上的并行算法运行时间\( T_p \)等于所有处理器的计算时间和开销时间之和，即\( T_p = t_{ie} + t_{io} \)。同时，问题规模\( W \)是最佳串行算法完成的计算量，且\( W = T_e \)（其中\( T_e \)是单处理器的最佳串行运行时间）。 等效率度量标准的关键在于，随着处理器\( p \)的增加，开销\( t_{io} \)通常也会增大，这会导致整体效率\( E \)下降，因为更多的资源被用于非计算任务。为了解决这个问题，我们需要通过增大问题规模\( W \)来抵消增加的开销，使得效率保持在一个期望的范围内。这样，等效率函数\( f_E(p) \)就成为了一个反映如何随着处理器数量的变化来调整问题规模以保持效率的数学表达式。 等效率度量标准在分析并行算法的可扩展性和优化时非常有用。在设计并行算法时，研究者会试图找到一个平衡点，使得即使在增加处理器数量时，算法的效率也能保持在一个理想的水平，从而充分利用硬件资源。 此外，中科大的课程内容涵盖了并行计算的多个方面，包括并行计算机系统结构模型、当代并行机系统（如SMP、MPP和Cluster）、并行计算性能评测、并行算法设计基础和技术、并行数值算法（如基本通信操作、稠密矩阵运算、线性方程组求解和快速傅里叶变换）、以及并行程序设计相关的基础、模型、分布式存储系统编程和设计环境与工具。这些内容旨在提供一个全面的并行计算学习框架，帮助学生理解和掌握并行计算的核心概念和技术。