Two important laws about parallelism

This article excerpts from   Ge Yiming The teacher's 《 actual combat java High concurrency Programming 》 A Book . I took it off because I thought it was well written

Transform the serial program into Concurrent Program , Generally speaking, it can improve the overall performance of the program , But how much can it be improved , Even if it can really improve , It's still a problem to be studied . at present , There are two main laws that answer this question , One is Amdahl The laws of , The other is Gustafson The laws of .

1.Amdahl The laws of

Amdahl Laws are very important laws in computer science . It defines the calculation formula and theory of the speedup ratio of the serial system after parallelization .

Speedup definition ：

                    Speedup ratio = System time before optimization / After optimization, the system takes time

The so-called speedup ratio is the ratio of time consumption before optimization to time consumption after optimization . The higher the acceleration ratio , The more obvious the optimization effect is . chart 1-1 by Amdahl Formula derivation process , among n Represents the number of processors ,T Time ,T1 Time consuming before optimization （ It's just 1 Time spent on processors ）,Tn Said the use of n Time to optimize processors .F Is the proportion of a program that can only be executed serially .

chart 1-1

According to this formula , If cpu The number of processors tends to be infinite , Then the speedup ratio is inversely proportional to the serialization ratio of the system , If the system has to have 50% The code is executed serially , Then the maximum acceleration ratio of the system is 2.

Suppose there is a program that is executed in the following steps , Cost per execution step 100 Unit time . among , There are only steps 2 And steps 5 It can be done in parallel , step 1、3、4 It has to be serial , Pictured 1-2 Shown . In the case of full serial , The total time of the system is 500 Unit time .

chart 1-2

If the steps are 2 And steps 5 Parallelization , Suppose on a dual core processor , As shown in the picture 1-3 The processing flow shown in . under these circumstances , step 2 And steps 5 It will take time for 50 Unit time . Therefore, the overall time consumption of the system is 400 Unit time . According to the definition of acceleration ratio ：

Speedup ratio = System time before optimization / After optimization, the system takes time = 500 / 400 = 1.25

chart 1-3

because 5 In one step ,3 Must be serial , Therefore, the serialization ratio is 3/5 = 0.6, namely F=0.6, And the number of dual core processors N by 2. Substituting the acceleration ratio formula, we get ：

Speedup ratio = 1/(0.6+(1-0.6) /2) = 1.25

In extreme cases , Suppose the number of parallel processors is infinite , Is shown in figure 1-4 Process shown . step 2 And steps 5 The implementation of tends to 0. Even so, the overall system still takes more time than 300 Unit time . Use the acceleration ratio formula ,N Towards infinity , There's an acceleration ratio = 1 / F, And F = 0.6, So there's an acceleration ratio = 1.67. The limit of the acceleration ratio is 500/300 = 1.67

chart 1-4

thus it can be seen , In order to improve the speed of the system , Just add CPU The number of processors doesn't necessarily work . The serial behavior of the program needs to be fundamentally modified , Increase the proportion of parallelizable modules in the system , On this basis , Reasonably increase the number of parallel processors , With the least investment , Get the maximum acceleration ratio .

according to Amdahl The laws of , Use multi-core CPU Optimize the system , The effect of optimization depends on CPU The number of , And the proportion of serialized programs in the system .CPU The more the number of , The lower the serialization ratio , The better the optimization effect . Only improve CPU Number without reducing the serialization ratio of programs , It doesn't improve system performance .

2.Gustafson The laws of

Gustafson The law also attempts to account for the number of processors 、 The relationship between serialization ratio and speedup ratio , Pictured 2-1 Shown , however Gustafson The law and Amdahl The angle of the law is different . Again , The speedup ratio is defined as the system time before optimization divided by the system time after optimization .

chart 2-1 Gustafson Derivation process

You can see , Because of the different angles of penetration ,Gustafson The formula of the law and Amdahl The formula of the law is quite different .

from Gustafson In the law , We can find it easier , If the serialization ratio is small , The proportion of parallelization is very large , So the speedup is the number of processors . Just keep accumulating processors , You can get faster .

3. Whether they contradict each other

Amdahl The law and Gustafson The conclusion of the law is different , Does this mean that one of the two theories is wrong ？ It's not , The difference between the two is actually the result of these two laws examining the same objective fact from different angles , Their focus is different .

Take an example from life , Driving in a car 60km On the way , It took you an hour , Driving 30km. No matter how fast you drive next , You can't reach the whole journey 90km/h Average speed of . chart 3-1 It explains the reason very well .

chart 3-1  Amdahl The partial focus of the law

Solution graph 3-1 The equation of , You will find that if you want to achieve 90km/h The speed of , So you start with AB The midpoint reaches B The dot time will be a negative number , This is obviously not a reasonable conclusion . actually , If the first half of the journey 30km You used it for an hour , So even if you go from the midpoint to B Point at the speed of light , also The overall average speed can only be maintained at 60km/h.

in other words Amdahl emphasize ： When the serialization ratio is fixed , There is an upper limit to the speedup , No matter how many you stack CPU Participate in calculation , Can't break the upper limit ！

and Gustafson The starting point of the law is different , Yes Gustafson According to the law , No matter you're from A How slow is it to start , Just give you enough time and distance , As long as your late speed is a little faster than expected , You can always adjust the average speed very close to that expectation . such as , You want to reach average speed 90km/h, Even before 30km Your speed is only 30km/h , You just need to reach the speed at the back 91km/h, Give you enough time and distance , One day we can increase the average speed to very close 90km/h.

therefore ,Gustafson The law is concerned with ： If the proportion of code that can be serialized is large enough , So the acceleration ratio can be adjusted with CPU The number of linear growth .

So these two laws are not contradictory . In extreme terms , If there is no parallelizable code in the system （ namely F=1）, So for these two laws , The acceleration ratio is 1 . conversely , If the proportion of parallelizable code in the system reaches 100%, So the acceleration ratio of these two laws is n （ Number of processors ）.

 

 
---------------------
author ：Mr.LiJiaHao
source ：CSDN
original text ：https://blog.csdn.net/codeHaoHao/article/details/90286873
Copyright notice ： This is the author's original article , Please attach a link to the blog post ！
Content analysis By：CSDN,CNBLOG One click reprint plugin for blog posts