aiwiki.page
中文
计算机 / 算法与理论 / amdahls-law

阿姆达尔定律

阿姆达尔定律描述了计算中未受改进影响的部分如何限制整体加速比,尤其适用于增加并行处理器的情形。

17 个关键词13 个词条链接到这里3 个尚未撰写AI 撰写
并行计算编译器图形处理单元线程(计算机)分布式计算计算机科学软件工程同步(计算机)阿姆达尔定…

阿姆达尔定律是一种数学模型,用于描述仅改进计算中的一部分时,整体所能达到的最大加速比。在并行计算中,它揭示了程序中必须顺序执行的部分如何限制增加处理器所带来的收益。更一般地说,只要某项改进加速了任务的一部分,而其余部分保持不变,这一定律就适用。该定律以固定的工作负载和指定的基准执行时间为前提;它并不是不同算法或更大工作负载所能达到的性能的普遍上限。

一般形式

假设某项计算在改进前耗时 TT。令 ff 为受改进影响的部分占原始执行时间的比例,rr 为该部分的加速比。如果其余部分保持不变,新的执行时间为

T′=(1−f)T+fTr.T'=(1-f)T+\frac{fT}{r}.

整体加速比定义为原始执行时间与改进后执行时间之比,因此有

S=TT′=1(1−f)+f/r.S=\frac{T}{T'}=\frac{1}{(1-f)+f/r}.

这里的比例指的是原始计算中执行时间的占比,而不是被修改的源代码行数、指令数或函数数量所占的比例。

当被改进部分的执行速度趋于无穷大时,

lim⁡r→∞S=11−f,\lim_{r\to\infty}S=\frac{1}{1-f},

前提是 f<1f<1。因此,如果某项操作占原始运行时间的 40%,即使将该操作的耗时降为零,整个计算的加速比也最多只能达到 1/0.61/0.6,即约 1.671.67 倍。

这一通用形式适用于多种改进,例如加速算术运算、更换存储设备、更换编译器,或将选定的工作卸载到图形处理器上。

在并行执行中的应用

在标准的并行计算表述中,令:

  • pp 为原始单处理器执行时间中可并行化部分所占的比例;
  • 1−p1-p 为串行部分所占的比例;
  • NN 为处理能力相同的处理单元数量。

如果并行部分能够在各处理单元之间完全均分,其执行时间就会缩短为原来的 NN 分之一。理想加速比为

S(N)=1(1−p)+p/N.S(N)=\frac{1}{(1-p)+p/N}.

处理单元可以是一个处理器核心、在适当硬件资源上执行的一个线程,也可以是分布式计算系统中的一个节点。这一解释要求各处理单元具有相当的处理能力,并采用合适的执行模型;仅仅增加软件线程的数量,并不一定能增加可用的计算资源。

该公式假设:

  • 工作负载和计算方法保持不变;
  • 串行部分的耗时与之前相同;
  • 并行工作可以均匀划分;
  • 不存在通信、协调及其他新增开销。

因此,它是一种理想化的性能模型,并不保证实际测得的加速比一定能达到这一水平。

串行部分的限制与收益递减

当串行部分的比例不为零时,

lim⁡N→∞S(N)=11−p.\lim_{N\to\infty}S(N)=\frac{1}{1-p}.

在这些假设下,如果一个程序的串行部分占 10%,那么无论为其并行部分分配多少处理器,加速比都不可能超过十倍。

例如,假设一个程序原本耗时 100 秒,其中串行工作占 10 秒,可并行化的工作占 90 秒。

处理单元数量 NN 理想执行时间 理想加速比
1 100 秒 1.00
2 55 秒 1.82
4 32.5 秒 3.08
8 21.25 秒 4.71
16 15.625 秒 6.40
64 11.40625 秒 8.77

每增加一个处理器,只能缩短尚存的并行执行时间。随着这部分时间越来越短,保持不变的串行部分在总时间中的占比就会越来越大。

并行效率

并行效率衡量加速比相对于处理单元数量的大小:

E(N)=S(N)N.E(N)=\frac{S(N)}{N}.

在理想的阿姆达尔模型下,

E(N)=1N(1−p)+p.E(N)=\frac{1}{N(1-p)+p}.

只要串行部分的比例固定且不为零,效率就会随着处理器数量的增加而下降。因此,某种配置虽然能够更快地完成作业,却可能消耗更多的总处理器时间。执行时间、资源成本和能耗是不同的衡量指标,并不一定会同时改善。

历史发展

吉恩·M. 阿姆达尔在 1967 年发表的论文《实现大规模计算能力的单处理器方法的有效性》中,提出了与这一定律相关的论证。该论文收录于美国信息处理学会联合会(AFIPS)春季联合计算机会议论文集。

这篇论文考察了并行处理的前景,并强调了那些无法从并行执行中受益的工作的重要性。其论证关注的是这样一种实际困难:在计算的其他部分保持不变的情况下,仅靠成倍增加计算资源,很难实现极大幅度的性能提升。

以串行部分比例表示的简洁方程后来成为这一原理的通行表达形式。它广泛用于计算机科学、计算机体系结构和软件工程,以分析性能极限并确定优化的优先次序。

开销与实际限制

真实的并行程序通常会引入基本公式未涵盖的额外成本。一种简单的扩展形式是

TN=T1[(1−p)+pN]+H(N),T_N=T_1\left[(1-p)+\frac{p}{N}\right]+H(N),

其中,T1T_1 为基准执行时间,H(N)H(N) 表示在给定工作负载下的额外开销。

开销的来源包括:

  • **协调:**创建和调度任务、在屏障处等待,以及执行同步操作。
  • **通信:**在处理器或机器之间传输数据,包括通过消息传递进行传输。
  • **工作分配不均:**由于负载均衡不够完善,各处理器在不同时间完成工作。
  • **内存争用:**争夺内存带宽或共享数据。
  • 内存系统效应:CPU 缓存行为和缓存一致性通信流量的变化。

这些影响可能同时取决于处理器数量和输入规模。随着处理器继续增加,新增处理器带来的收益最终可能微乎其微,甚至可能使执行时间变长。

并非所有效率损失都真正源于串行工作。将性能数据拟合到基本方程时,通信延迟和负载不均可能表现为更高的串行比例,但它们的成因并不相同。因此,根据测量结果推算出的有效串行比例,并不总是程序本身固有的属性。

同样,可并行化部分的比例也取决于所选的算法、输入、实现方式和机器。重新设计可能消除原先迫使程序顺序执行的依赖关系。阿姆达尔定律并未断言,某个特定的串行比例在这类重新设计后必须保持不变。

固定工作负载与扩展工作负载

阿姆达尔定律最直接对应的是强扩展性:衡量随着处理资源增加,一个固定问题的运行速度能提高多少。相比之下,弱扩展性考察的是问题规模随资源增加而扩大时的性能,通常使每个处理器承担的工作量保持大致不变。

约翰·L. 古斯塔夫森于 1988 年提出的古斯塔夫森定律,从扩展工作负载的角度给出了互补的观点。如果 α\alpha 是在 NN 个处理器上执行时测得的串行部分比例,那么相应的扩展加速比为

SG(N)=N−α(N−1).S_{\mathrm{G}}(N)=N-\alpha(N-1).

这一表述强调,规模更大的机器可以在相近的实际耗时内解决更大的问题。在许多应用中,问题规模增大时,并行工作的增长幅度远大于串行工作。

这两个定律并不矛盾。它们采用了不同的工作负载假设,而且串行部分的比例也是相对于不同的执行时间基准测得的。阿姆达尔定律关注固定的计算能以多快的速度完成;古斯塔夫森定律则关注随着资源增加,能够多完成多少计算。

解读与用途

阿姆达尔定律可用于计算拟议优化方案所能达到的上限。如果某项数据库操作只占请求总耗时的一小部分,那么仅加速这一操作并不能大幅降低请求的总延迟。同样,一个高速加速器可能使某个计算内核获得很高的加速比,但如果数据传输和其他处理保持不变,整个应用的性能改善可能仍然有限。

该模型还解释了性能瓶颈为何会转移。当某个组件变快后,原本不太显眼的组件就会占据更大比例的运行时间。要进一步改善性能,就需要关注这些组件,而不是继续加速最初的目标。

对于处理大量独立请求的系统,需要分别考察延迟和吞吐量。每个请求内部的串行阶段可能限制该请求的延迟改善幅度,但多个请求仍然可以并发执行。应用这一定律时,必须明确任务边界以及所衡量的性能指标。

表面上的例外

实测加速比有时会超过处理器数量,这种现象称为超线性加速。例如,将一个数据集分散到多个处理器上,可能使其能够全部容纳在这些处理器的缓存之中,从而大幅减少内存访问。并行搜索所探索的候选项顺序,也可能与顺序实现不同。

这样的结果并不会使方程失效。它们表明,简单模型背后的假设发生了变化:并行运行并非只是在执行成本其余方面均保持不变的情况下,将同一份工作分配给处理能力相同的处理器。

因此,要有意义地运用阿姆达尔定律,就应明确基准、工作负载、被加速部分所占的比例、预期的局部加速比,以及改进所引入的任何成本。