并行算法与性能

并行算法设计旨在寻求能够展现丰富并行性且通信开销低的计算方法，而性能分析则量化了它们如何有效地利用额外的处理器。

Definition

并行算法规定了多个处理器如何协同解决问题；其质量通过工作量（总操作数）和深度（最长依赖链）来衡量，并通过加速比和效率等性能指标来衡量使用p个处理器所带来的益处。

Scope

本主题涵盖了设计和分析并行算法的模型——最显著的是PRAM模型及其工作-深度分析——并行原语（如前缀和（扫描）、归约和排序）的设计，以及加速比、效率、成本最优性、等效率和Amdahl定律与Gustafson定律的性能框架。它为理解所有编程模型中的并行程序提供了分析基础。

Core questions

• 如何通过工作量和深度来表征问题的固有并行性？
• 加速比、效率和可扩展性如何定义和衡量？
• 问题的串行部分或增长如何决定其并行可扩展性？

Key theories

PRAM和工作-深度分析

PRAM模型将具有共享内存和同步步骤的并行机器理想化，支持对算法的工作量（总操作数）和深度（关键路径长度）进行分析，这两者共同限制了其可实现的并行时间。

加速比、效率和等效率

加速比衡量p个处理器解决问题快了多少，效率将其标准化到每个处理器，而等效率则表示问题规模必须如何随处理器数量增长以保持效率恒定，从而捕捉可扩展性。

Amdahl定律和Gustafson定律

Amdahl定律通过串行部分限制了固定规模的加速比，而Gustafson定律则观察到，随着机器扩展问题规模可以实现接近线性的加速比，共同构成了强扩展和弱扩展的框架。

Clinical relevance

工作-深度分析和扩展定律指导计算是否以及如何并行化，并预测其在大规模下的行为，为从排序和图核到大型模拟和机器学习训练等所有设计提供信息。

History

Amdahl在1967年的论点和Gustafson在1988年的反驳构成了加速比争论的框架；PRAM模型和工作-深度框架在20世纪80年代成熟，并在JaJa于1992年的著作以及Grama及其同事对可扩展性的分析中得到规范，为并行计算奠定了理论核心。

Debates

强扩展与弱扩展

Amdahl的强扩展观点（固定问题，更多处理器）预测收益递减，而Gustafson的弱扩展观点（随处理器数量增长问题规模）预测持续加速；哪种衡量标准是正确的取决于问题规模或解决时间是否固定。

Key figures

• Joseph JaJa
• Gene Amdahl
• John Gustafson
• Vipin Kumar

Seminal works

• jaja1992
• amdahl1967
• gustafson1988

Frequently asked questions

并行算法的工作量和深度有什么区别？

工作量是所有处理器执行的总操作数，而深度（或跨度）是最长依赖操作链的长度。深度限制了最佳可能的并行运行时间，而工作量与深度的比率表明了可用的并行度。