阿姆达尔定律
阿姆达尔定律可以用来计算处理器平行运算之后效率提升的能力。阿姆达尔定律因 Gene Amdal 在 1967 年提出这个定律而得名。绝大多数使用并行或并发系统的开发者有一种并发或并行可能会带来提速的感觉,甚至不知道阿姆达尔定律。不管怎样,了解阿姆达尔定律还是有用的。
我会首先以算术的方式介绍阿姆达尔定律定律,然后再用图表演示一下。
阿姆达尔定律定义
一个程序(或者一个算法)可以按照是否可以被并行化分为下面两个部分:
- 可以被并行化的部分
- 不可以被并行化的部分
假设一个程序处理磁盘上的文件。这个程序的一小部分用来扫描路径和在内存中创建文件目录。做完这些后,每个文件交个一个单独的线程去处理。扫描路径和创建文件目录的部分不可以被并行化,不过处理文件的过程可以。
程序串行(非并行)执行的总时间我们记为 T。时间 T 包括不可以被并行和可以被并行部分的时间。不可以被并行的部分我们记为 B。那么可以被并行的部分就是 T-B。下面的列表总结了这些定义:
- T = 串行执行的总时间
- B = 不可以并行的总时间
- T- B = 并行部分的总时间
从上面可以得出:
T = B + (T – B)
首先,这个看起来可能有一点奇怪,程序的可并行部分在上面这个公式中并没有自己的标识。然而,由于这个公式中可并行可以用总时间 T 和 B(不可并行部分)表示出来,这个公式实际上已经从概念上得到了简化,也即是指以这种方式减少了变量的个数。
T- B 是可并行化的部分,以并行的方式执行可以提高程序的运行速度。可以提速多少取决于有多少线程或者多少个 CPU 来执行。线程或者 CPU 的个数我们记为 N。可并行化部分被执行的最快时间可以通过下面的公式计算出来:
(T – B ) / N
或者通过这种方式
(1 / N) * (T – B)
维基中使用的是第二种方式。
根据阿姆达尔定律,当一个程序的可并行部分使用 N 个线程或 CPU 执行时,执行的总时间为:
T(N) = B + ( T – B ) / N
T(N)指的是在并行因子为 N 时的总执行时间。因此,T(1)就执行在并行因子为 1 时程序的总执行时间。使用 T(1)代替 T,阿姆达尔定律定律看起来像这样:
T(N) = B + (T(1) – B) / N
表达的意思都是是一样的。
一个计算例子
为了更好的理解阿姆达尔定律,让我们来看一个计算的例子。执行一个程序的总时间设为 1。程序的不可并行化占 40%,按总时间 1 计算,就是 0.4,可并行部分就是 1–0.4=0.6.
在并行因子为 2 的情况下,程序的执行时间将会是:
T(2) = 0.4 + ( 1 - 0.4 ) / 2
= 0.4 + 0.6 / 2
= 0.4 + 0.3
= 0.7
在并行因子为 5 的情况下,程序的执行时间将会是:
T(5) = 0.4 + ( 1 - 0.4 ) / 5
= 0.4 + 0.6 / 6
= 0.4 + 0.12
= 0.52
阿姆达尔定律图示
为了更好地理解阿姆达尔定律,我会尝试演示这个定定律是如何诞生的。
首先,一个程序可以被分割为两部分,一部分为不可并行部分 B,一部分为可并行部分 1–B。如下图:
在顶部被带有分割线的那条直线代表总时间 T(1)。
下面你可以看到在并行因子为 2 的情况下的执行时间:
并行因子为 3 的情况:
优化算法
从阿姆达尔定律可以看出,程序的可并行化部分可以通过使用更多的硬件(更多的线程或 CPU)运行更快。对于不可并行化的部分,只能通过优化代码来达到提速的目的。因此,你可以通过优化不可并行化部分来提高你的程序的运行速度和并行能力。你可以对不可并行化在算法上做一点改动,如果有可能,你也可以把一些移到可并行化放的部分。
优化串行分量
如果你优化一个程序的串行化部分,你也可以使用阿姆达尔定律来计算程序优化后的执行时间。如果不可并行部分通过一个因子 O 来优化,那么阿姆达尔定律看起来就像这样:
T(O, N) = B / O + (1 - B / O) / N
记住,现在程序的不可并行化部分占了 B / O 的时间,所以,可并行化部分就占了 1 - B / O 的时间。
如果 B 为 0.1,O 为 2,N 为 5,计算看起来就像这样:
T(2,5) = 0.4 / 2 + (1 - 0.4 / 2) / 5
= 0.2 + (1 - 0.4 / 2) / 5
= 0.2 + (1 - 0.2) / 5
= 0.2 + 0.8 / 5
= 0.2 + 0.16
= 0.36
运行时间 vs. 加速
到目前为止,我们只用阿姆达尔定律计算了一个程序或算法在优化后或者并行化后的执行时间。我们也可以使用阿姆达尔定律计算加速比(speedup),也就是经过优化后或者串行化后的程序或算法比原来快了多少。
如果旧版本的程序或算法的执行时间为 T,那么增速比就是:
Speedup = T / T(O , N);
为了计算执行时间,我们常常把 T 设为 1,加速比为原来时间的一个分数。公式大致像下面这样:
Speedup = 1 / T(O,N)
如果我们使用阿姆达尔定律来代替 T(O,N),我们可以得到下面的公式:
Speedup = 1 / ( B / O + (1 - B / O) / N)
如果 B = 0.4, O = 2, N = 5, 计算变成下面这样:
Speedup = 1 / ( 0.4 / 2 + (1 - 0.4 / 2) / 5)
= 1 / ( 0.2 + (1 - 0.4 / 2) / 5)
= 1 / ( 0.2 + (1 - 0.2) / 5 )
= 1 / ( 0.2 + 0.8 / 5 )
= 1 / ( 0.2 + 0.16 )
= 1 / 0.36
= 2.77777 ...
上面的计算结果可以看出,如果你通过一个因子 2 来优化不可并行化部分,一个因子 5 来并行化可并行化部分,这个程序或算法的最新优化版本最多可以比原来的版本快 2.77777 倍。
测量,不要仅是计算
虽然阿姆达尔定律允许你并行化一个算法的理论加速比,但是不要过度依赖这样的计算。在实际场景中,当你优化或并行化一个算法时,可以有很多的因子可以被考虑进来。
内存的速度,CPU 缓存,磁盘,网卡等可能都是一个限制因子。如果一个算法的最新版本是并行化的,但是导致了大量的 CPU 缓存浪费,你可能不会再使用 xN 个 CPU 来获得 xN 的期望加速。如果你的内存总线(memory bus),磁盘,网卡或者网络连接都处于高负载状态,也是一样的情况。
我们的建议是,使用阿姆达尔定律定律来指导我们优化程序,而不是用来测量优化带来的实际加速比。记住,有时候一个高度串行化的算法胜过一个并行化的算法,因为串行化版本不需要进行协调管理(上下文切换),而且一个单个的 CPU 在底层硬件工作(CPU 管道、CPU 缓存等)上的一致性可能更好。
相关推荐
计算机系统结构(2012年春)-基本概念CPI阿姆达尔定律.ppt
使用场景:本资源主要用于辅助系统分析师的软考;适用人群:系分备考者、产品经历、软件开发等,也适用于有...内容概要:各系统的性能评价,以及阿姆达尔定律常考内容;其他:思维导图的方式介绍知识点,标注重点和示例
阿姆达尔的法律探索者 来自同名的阿姆达尔定律计算器的源代码和测试html页面。 或者只是在您的浏览器中。 (使用jQuery 2.x,因此不支持IE 6,7,8)
由于混合结构的特殊性,分析了传统的阿姆达尔定律,将其推广到混合结构中。针对FMM算法中近程计算部分在multi-GPU CPU混合结构中存在的任务均衡以及通信延时等问题,在混合结构阿姆达尔定律的指导下,提出了多GPU...
示例: 阿姆达尔定律 阿姆斯特朗公理 阿帕网 埃尔布朗基 埃尔米特函数 安全标号 安全操作系统 安全策略 安全措施 安全等级 安全电子交易 安全功能评估 安全过滤器 安全...
《计算机系统结构》复习提纲 第一章复习题1、计算机发展的历史,最早的计算机是电子管...5、掌握阿姆达尔定律。6、什么是峰值性能、持续性能?持续性能有哪几种表示方法。列出它们的计算公式,并比较它们的优缺点。
Xilinx官方翻译的...另外,读者 需要对基本的计算机架构有所熟悉,例如流水线(pipeline),加速,阿姆达尔定律(Amdahl's Law)。以寄存器传输级(RTL)为基础FPGA设计知识并不是必需的,但会对理解本书有所帮助。
阿姆达尔定律是一个公式,它显示了可以通过增加系统资源来实现的计算任务的潜在加速。通常用于并行计算中,它可以预测增加处理器数量的实际好处,这受程序的可并行性限制。 最好用一个例子说明。如果程序由两部分...
1. 记住阿姆达尔定律: Ahmdal's rule funccost是函数func运行时间百分比,funcspeedup是你优化函数的运行的系数。 所以,如果你优化了函数TriangleIntersect执行40%的运行时间,使它运行快了近两倍,而你...
使用Python和CUDA进行动手GPU编程必将步入正轨:您将首先学习如何应用阿姆达尔定律,使用代码分析器来识别Python代码中的瓶颈,并设置合适的GPU编程环境。 然后,您将看到如何“查询” GPU的功能以及如何在GPU自身...
UIBK PS并行系统(703078,2021) 该存储库包含完成2021年夏季学期并行编程实验室练习所需的材料,包括作业单和任何相关材料。...加速,阿姆达尔定律,测量 2021-03-23 顺序性能,缓存效果,pthread并行性 2021-04-13
《计算机组成与体系结构:性能设计(原书第8版)》是介绍当代计算机体系主流技术和最新...性能评估:扩充了对性能评估的讨论,增加了对基准程序和阿姆达尔定律的分析。汇编语言:增加了一个关于汇编语言和汇编器的新附录。