基础知识
并行计算三大定律
-
阿姆达尔定律 (Amdahl’s Law, 1967)
记 α ∈ [0, 1] 是某任务无法并行处理部分所占的比例. 假设该任务的工作 量固定，则对任意 n 个处理器，相比于 1 个处理器，能够取得的加速比 满足:S(n) < 1/α. -
古斯塔法森定律 (Gustafson’s Law, 1988）
记 α ∈ [0, 1] 是某任务无法并行处理部分所占的比例. 假设该任务的工作 量可以随着处理器个数缩放，从而保持处理时间固定. 则对任意 n 个处 理器，相比于 1 个处理器，能够取得的加速比 S′(n) 不存在上界. -
孙-倪定律 (Sun-Ni’s Law, 1990)
记 α ∈ [0, 1] 是某任务无法并行处理部分所占的比例. 假设该任务的可并 行部分随着处理器个数 n 按照因子 G(n) 缩放，则对任意 n，相比于 1 个处理器，能够取得的加速比 S∗(n) 满足
S∗(n)= α+(1−α)G(n) / α + (1 − α)G(n)/n