有关并行的两个重要定律

本文介绍了将串行程序改造成并发程序性能提升问题的两个定律。Amdahl定律定义了串行系统并行化后的加速比计算公式和理论上限,指出提高系统速度需提高可并行化模块比重。Gustafson定律从不同角度说明三者关系,若串行化比例小,加速比随处理器个数增加。二者并不矛盾。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

本文摘自 葛一鸣 老师的《实战java高并发程序设计》一书。因为觉得写得好就摘下来了

将串行程序改造成并发程序,一般来说可以提高程序的整体性能,但是究竟能提升多少,甚至说究竟是否真的可以提高,还是一个需要研究的问题。目前,主要有两个定律对这个问题进行解答,一个是Amdahl定律,另一个是Gustafson定律。

1.Amdahl定律

Amdahl定律是计算机科学中非常重要的定律。它定义了串行系统并行化后的加速比的计算公式和理论上线

加速比定义:

                    加速比 = 优化前系统耗时 / 优化后系统耗时

所谓加速比就是优化前的耗时与优化后耗时的比值。加速比越高,表明优化效果越明显。图1-1 为Amdahl公式推导过程,其中 n 表示处理器个数,T 表示时间,T1 表示优化前耗时(也就是只有 1 个处理器时的耗时),Tn 表示使用 n 个处理器优化后的耗时。F 是程序中只能串行执行的比例。

图 1-1

根据这个公式,如果 cpu 处理器数量趋于无穷,那么加速比与系统的串行化比例成反比,如果系统中必须有 50% 的代码串行执行,那么系统的最大加速比为 2。

假设有一个程序分为以下步骤执行,每个执行步骤花费 100 个单位时间。其中,只有步骤 2 和步骤 5 可以并行,步骤 1、3、4必须串行,如图1-2 所示。在全串行的情况下,系统合计耗时为500个单位时间。

图 1-2

若将步骤 2和步骤 5并行化,假设在双核处理器上,则有如图 1-3所示的处理流程。在这种情况下,步骤 2和步骤 5的耗时将为 50个单位时间。故系统整体耗时为400个单位时间。根据加速比定义有:

加速比 = 优化前系统耗时 / 优化后系统耗时 = 500 / 400 = 1.25

图 1-3

由于 5个步骤中,3个必须串行,因此串行化比例为 3/5 = 0.6,即 F=0.6,且双核处理器的处理器个数N为2.代入加速比公式得:

加速比 = 1/(0.6+(1-0.6) /2) = 1.25

在极端的情况下,假设并行处理器个数无限大,则如图 1-4所示处理过程。步骤 2和步骤 5的执行实现趋于0。即使这样整体系统耗时依然大于300个单位时间。使用加速比公式,N趋于无穷大,有加速比 = 1 / F,且F = 0.6,故有加速比 = 1.67。即加速比的极限为 500/300 = 1.67

图 1-4

由此可见,为了提高系统的速度,仅增加CPU处理器的数量并不一定能起到有效的作用。需要从根本上修改程序的串行行为,提高系统内可并行化的模块比重,在此基础上,合理增加并行处理器数量,才能以最小的投入,得到最大的加速比。

根据Amdahl 定律,使用多核CPU 对系统进行优化,优化的效果取决于CPU的数量,以及系统中串行化程序的比例。CPU 数量越多,串行化比例越低,则优化效果越好。仅提高CPU 数量而不降低程序的串行化比例,也无法提高系统性能。

2.Gustafson定律

Gustafson 定律也试图说明处理器个数、串行化比例和加速比之间的关系,如图2-1所示,但是Gustafson 定律和Amdahl 定律的角度不同。同样,加速比都被定义为优化前的系统耗时除以优化后的系统耗时。

图2-1 Gustafson推导过程

可以看到,由于切入角度的不同,Gustafson 定律的公式和Amdahl 定律的公式截然不同。从Gustafson 定律中,我们可以更容易的发现,如果串行化比例很小,并行化比例很大,那么加速比就是处理器的个数。只要不断地累加处理器,就能获得更快的速度。

3.是否相互矛盾

Amdahl 定律和Gustafson 定律的结论不同,这是不是说明这两个理论之间有一个是错误的呢?其实不然,两者的差异其实是因为这两个定律对同一个客观事实从不同的角度去审视的结果,他们的侧重点有所不同。

举一个生活中的例子,一辆汽车行驶在60km的路上,你花了一个小时,行驶了30km。无论接下来开多快,整个路程你都不可能达到90km/h的平均速度。图3-1很好的说明了原因。

图3-1  Amdahl 定律的偏重点

求解图3-1的方程,你会发现如果想要达到90km/h的时速,那么你从AB中点到达B点的时间会是一个负数,这显然不是一个合理的结论。实际上,如果前半程 30km你使用了一小时,那么即使你从中点到B点使用光速,也 只能把整体的平均时速维持在 60km/h。

也就是说Amdahl 强调:当串行化比例一定时,加速比是有上限的,不管你堆叠多少CPU参与计算,都不能突破上限!

而Gustafson定律的出发点与之不同,对Gustafson定律来说,不管你从A点出发的速度有多慢,只要给你足够的时间和距离,只要你后期的速度比期望快那么一点点,你总是可以把平均速度调整到非常接近那个期望值的。比如,你想要达到均速90km/h,即使在前30km 你的时速只有30km/h ,你只要在后面的速度达到91km/h,给你足够的时间和距离,总有一天可以把均速提高到非常接近90km/h。

因此,Gustafson 定律关心的是:如果可被串行化的代码所占比例足够大,那么加速比就能随着CPU的数量线性增长。

所以这两个定律并不矛盾。从极端的角度来说,如果系统中没有可被并行化的代码(即 F=1),那么对于这两个定律,其加速比都是1 。反之,如果系统中可被并行化代码的比例达到100%,那么这两个定律得到的加速比都是n (处理器个数)。

 

 

 

 

### 回答1: RKF45(Runge-Kutta-Fehlberg)算法是一种数值积分方法,用于解决常微分方程组。它是由Runge-Kutta法和Fehlberg法演变而来,旨在在保证精度的同时尽可能地降低计算复杂度。 要用C语言实现RKF45算法,你需要了解以下几点: 1. 常微分方程的基本概念和表示方法。 2. Runge-Kutta法的原理和实现方法。 3. Fehlberg法的原理和实现方法。 首先,你需要定义一个函数来表示待求解的常微分方程组。这个函数应该接受两个参数:当前时间和状态变量的值,并返回每个状态变量的导数。 然后,你需要实现RKF45算法的主体部分。这部分包括计算K1~K6和y1~y6的过程。在计算过程中,你需要调用你定义的函数来计算每个状态变量的导数。 最后,你需要实现一个循环来按照RKF45算法的步骤迭代地计算状态变量的值。在循环中,你需要根据当前时间、状态变量的值和K1~K6和y1~y6的值来计算下一个时刻的状态变量的值。 示例代码如下 ### 回答2: RKF45算法是一种常用的数值计算方法,用于求解常微分方程组的初始值问题。在C语言中,可以通过编写函数来实现该算法。 首先,需要包含头文件<math.h>和<stdio.h>,并定义常数和变量。其中常数包括步长h,误差限制tolerance,以及系数表,变量包括初值y0和初始步长h。 然后,编写函数rkf45,该函数的参数包括表示微分方程系统的函数指针func,初始值y0,自变量t0,结束点te,初始步长h,以及误差限制tolerance。 函数中,首先计算系数表,并初始化其他变量。然后使用循环来迭代求解微分方程组。在迭代过程中,根据系数表和当前条件,计算下一步的近似解yi,以及相应的步长h。然后比较当前步长与目标步长的差值,对步长进行调整。 最后,将结果打印出来。 以下是一个示例实现: ```c #include <stdio.h> #include <math.h> #define h 0.1 // 步长 #define tolerance 1e-6 // 误差限制 // 定义微分方程组 void func(double t, double *y, double *f) { f[0] = y[1]; f[1] = -2 * y[0]; } // RKF45算法函数实现 void rkf45(void (*func)(double, double*, double*), double y0[], double t0, double te, double h, double tolerance) { double t = t0; double y[2]; double f[2]; double k1[2], k2[2], k3[2], k4[2], k5[2], k6[2]; double R; // 初始化 double h_act = h; for (int i = 0; i < 2; i++) { y[i] = y0[i]; } // 迭代求解 while (t < te) { // 计算k1 func(t, y, f); for (int i = 0; i < 2; i++) { k1[i] = h_act * f[i]; } // 计算k2 double t2 = t + 1/4.0 * h_act; for (int i = 0; i < 2; i++) { y[i] = y0[i] + 1/4.0 * k1[i]; } func(t2, y, f); for (int i = 0; i < 2; i++) { k2[i] = h_act * f[i]; } // 计算k3 double t3 = t + 3/8.0 * h_act; for (int i = 0; i < 2; i++) { y[i] = y0[i] + 3/32.0 * k1[i] + 9/32.0 * k2[i]; } func(t3, y, f); for (int i = 0; i < 2; i++) { k3[i] = h_act * f[i]; } // 计算k4 double t4 = t +12/13.0 * h_act; for (int i = 0; i < 2; i++) { y[i] = y0[i] + 1932/2197.0 * k1[i] - 7200/2197.0 * k2[i] + 7296/2197.0 * k3[i]; } func(t4, y, f); for (int i = 0; i < 2; i++) { k4[i] = h_act * f[i]; } // 计算k5 double t5 = t + h_act; for (int i = 0; i < 2; i++) { y[i] = y0[i] + 439/216.0 * k1[i] - 8 * k2[i] + 3680/513.0 * k3[i] - 845/4104.0 * k4[i]; } func(t5, y, f); for (int i = 0; i < 2; i++) { k5[i] = h_act * f[i]; } // 计算k6 double t6 = t +1/2.0 * h_act; for (int i = 0; i < 2; i++) { y[i] = y0[i] - 8/27.0 * k1[i] + 2 * k2[i] - 3544/2565.0 * k3[i] + 1859/4104.0 * k4[i] - 11/40.0 * k5[i]; } func(t6, y, f); for (int i = 0; i < 2; i++) { k6[i] = h_act * f[i]; } // 计算下一步的近似解yi+1 for (int i = 0; i < 2; i++) { y0[i] = y0[i] + 25/216.0 * k1[i] + 1408/2565.0 * k3[i] + 2197/4104.0 * k4[i] - 1/5.0 * k5[i]; } // 计算下一步的步长 R = fabs(1/360.0 * k1[0] - 128/4275.0 * k3[0] - 2197/75240.0 * k4[0] + 1/50.0 * k5[0] + 2/55.0 * k6[0]) / h_act; if (R <= tolerance) { t += h_act; printf("t: %.6f, y: %.6f\n", t, y0[0]); } // 调整步长 h_act = 0.9 * h_act * pow(tolerance / R, 1/5.0); if (h_act > h) { h_act = h; } } } int main() { double y0[2] = {0.0, 1.0}; // 初值 double t0 = 0.0; // 初始点 double te = 1.0; // 结束点 rkf45(func, y0, t0, te, h, tolerance); return 0; } ``` 以上是一个基于C语言的RKF45算法的示例实现,该实现通过迭代求解微分方程组,并输出结果。在实际使用时,可以根据实际问题进行相应的修改和优化。 ### 回答3: RKF45算法是一种常用的常微分方程数值解法,用于求解初始值问题。下面是一个用C语言实现RKF45算法的简单示例代码: 首先,我们需要定义一个函数,该函数表示待解的常微分方程。假设我们要解的方程为dy/dx = f(x, y),其中f(x, y)是某个已知的函数。 ```c #include <stdio.h> // 待解的常微分方程 dy/dx = f(x, y) double f(double x, double y){ return x * x + y; } // RKF45算法的实现 void RKF45(double x0, double y0, double h, double xi){ double x = x0; double y = y0; while(x < xi){ double k1 = h * f(x, y); double k2 = h * f(x + h/4, y + k1/4); double k3 = h * f(x + 3*h/8, y + 3*k1/32 + 9*k2/32); double k4 = h * f(x + 12*h/13, y + 1932*k1/2197 - 7200*k2/2197 + 7296*k3/2197); double k5 = h * f(x + h, y + 439*k1/216 - 8*k2 + 3680*k3/513 - 845*k4/4104); double k6 = h * f(x + h/2, y - 8*k1/27 + 2*k2 - 3544*k3/2565 + 1859*k4/4104 - 11*k5/40); double R = fabs(k1/360 - 128*k3/4275 - 2197*k4/75240 + k5/50 + 2*k6/55) / h; // 根据误差限定步长 if(R <= 1e-6){ x += h; y += 25/216*k1 + 1408/2565*k3 + 2197/4104*k4 - k5/5; } h *= 0.9 * pow(1e-6 / R, 0.2); } printf("x = %lf, y = %lf\n", x, y); } int main(){ double x0 = 0; // 初始x值 double y0 = 0; // 初始y值 double h = 0.1; // 初始步长 double xi = 1; // 目标x值 RKF45(x0, y0, h, xi); return 0; } ``` 在上述代码中,函数RKF45实现了RKF45算法,计算了在给定初始x和y值的情况下,从x = x0到x = xi的解。在函数中,我们使用while循环来反复更新x和y的值,直到x达到目标值xi为止。在每次迭代中,我们计算各个k值,并根据k值计算出误差R,若误差在给定的阈值范围内,则按照RKF45算法的公式更新x和y的值,并根据误差调整步长h。 在主函数中,我们给定了初始x和y值,初始步长h和目标x值xi,并调用RKF45函数求解。最后,我们输出x和y的值。 需要注意的是,上述示例代码只是RKF45算法的实现示例,具体的求解函数f(x, y)需要根据具体问题进行定义。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值