分布式chap-4
第四章 性能
指标（加速比和效率）
- 运行时间（执行时间）
- 加速
- 效率
- 可扩展性
- 便携性、编程能力等等
超线性加速表达式
- 固有串行计算 σ(n)
- 潜在并行计算 (n)
- 并行开销 κ(n,p)
加速比
Ts：串行时间
Tp：并行时间
效率
Ep = Sp/p
阿姆达尔定律
实例：
局限性：忽略了并行的开销，高估了可实现的加速
回顾：
将问题大小视为常数
显示执行时间如何随着处理器数量的增加而减少
其他角度
我们经常使用更快的计算机来解决更大的问题实例
让我们将时间视为常数，并允许问题规模随着处理器数量的增加而增加
古斯塔夫定律
阿姆达尔和古斯塔夫都忽略了并行开销，所以有另一个定律
Karp-Flatt
将并行开销包含考虑，并检测加速模型中忽略的其他开销
- 进程启动时间
- 进程同步时间
- 不平衡的工作量
- 结构开销
等效率指标
- 并行系统：在并行计算机上执行的并行程序
- 并行系统的可扩展性：衡量其随着处理器数量增加而提高性能的能力
- 可扩展的系统在添加处理器时保持效率
- 等效率：衡量可扩展性的方法
等效率推导步骤
- 从加速公式开始
- 计算总开销
- 假设效率保持不变
- 确定顺序执行时间和开销之间的关系
可扩展性功能
- 假设等效率关系为 n >= f(p)
- 令 M(n) 表示大小为 n 的问题所需的内存
- M(f(p))/p 显示每个处理器的内存使用量必须如何增加才能保持相同的效率
- 我们称 M(f(p))/p 为可伸缩性函数
可扩展性函数的含义
- 为了在增加 p 时保持效率，我们必须增加 n
- 受可用内存限制的最大问题大小，在 p 中是线性的
- 可扩展性函数显示每个处理器的内存使用量必须如何增长才能保持效率
- 可扩展性函数常数意味着并行系统是完全可扩展的
复杂度例子
- 串行算法复杂度 T(n,1) = (n)
- 并行算法
- 计算复杂度 = (n/p)
- 通信复杂度 = (log p)
- 并行开销 T0(n,p) = (p log p)
弗洛伊德算法
- 顺序时间复杂度：(n3)
- 并行计算时间：(n3/p)
- 并行通信时间：(n2log p)
- 并行开销：T0(n,p) = (pn2log p)
- 等效率关系 n3 C(p n2 log p) n C p log p
M(n) = n2
并行系统可扩展性差 
有限差分
- 每次迭代的顺序时间复杂度：(n2)
- 每次迭代的并行通信复杂度：(n/p)
- 并行开销：(n p)
- 等效率关系 n2 Cnp n C p
M(n) = n2 - 该算法具有完美的可扩展性
