資訊專欄INFORMATION COLUMN
摘要：阿姆達(dá)爾定律定律是計(jì)算機(jī)科學(xué)中非常重要的定律。它定義了串行系統(tǒng)并行化后的加速比的計(jì)算公式和理論上線。需要從根本上修改程序的串行行為，提高系統(tǒng)內(nèi)可并行化的模塊比重，在此基礎(chǔ)上，合理增加并行處理器數(shù)量，才能以最小的投入，得到最大的加速比。
有關(guān)為什么要使用并行程序的問(wèn)題前面已經(jīng)進(jìn)行了簡(jiǎn)單的探討?？偟膩?lái)說(shuō)，最重要的應(yīng)該是處于兩個(gè)目的。
第一，為了獲得更好的性能；
第二，由于業(yè)務(wù)模型的需要，確實(shí)需要多個(gè)執(zhí)行實(shí)體。
在這里，我將更加關(guān)注第一種情況，也就是有關(guān)性能的問(wèn)題。將串行程序改造為并發(fā)程序，一般來(lái)說(shuō)可以提高程序的整體性能，但是究竟能提高多少，甚至說(shuō)究竟是否真的可以提高，還是一個(gè)需要研究的問(wèn)題。目前，主要有兩個(gè)定律對(duì)這個(gè)問(wèn)題進(jìn)行解答，一個(gè)是Amdahl定律，另外一個(gè)是Gustafson定律。
Amdahl(阿姆達(dá)爾)定律Amdahl定律是計(jì)算機(jī)科學(xué)中非常重要的定律。它定義了串行系統(tǒng)并行化后的加速比的計(jì)算公式和理論上線。
加速比定義：加速比 = 優(yōu)化前系統(tǒng)耗時(shí) / 優(yōu)化后系統(tǒng)耗時(shí)
所謂加速比就是優(yōu)化前耗時(shí)與優(yōu)化后耗時(shí)的比值。加速比越高，表明優(yōu)化效果越明顯。圖1.8顯示了Amdahl公式的推到過(guò)程，其中n表示處理器個(gè)數(shù)，T表示時(shí)間，T1表示優(yōu)化前耗時(shí)(也就是只有1個(gè)處理器時(shí)的耗時(shí))，Tn表示使用n個(gè)處理器優(yōu)化后的耗時(shí)。F是程序中只能串行執(zhí)行的比例。
根據(jù)這個(gè)公式，如果CPU處理器數(shù)量趨于無(wú)窮，那么加速比與系統(tǒng)的串行化比例成反比，如果系統(tǒng)中必須有50%的代碼串行執(zhí)行，那么系統(tǒng)的最大加速比為2。
假設(shè)有一個(gè)程序分為以下步驟執(zhí)行，每個(gè)執(zhí)行步驟花費(fèi)100個(gè)單位時(shí)間。其中，只有步驟2和步驟5可以并行，步驟1、3、4必須串行，如圖1.9所示。在全串行的情況下，系統(tǒng)合計(jì)耗時(shí)為500個(gè)單位時(shí)間。
若步驟2和步驟5并行化，假設(shè)在雙核處理器上，則有如圖1.10所示的處理流程。在這種情況下，步驟2和步驟5的耗時(shí)將為50個(gè)單位時(shí)間。故系統(tǒng)整體耗時(shí)為400個(gè)單位時(shí)間。根據(jù)加速比的定義有：
加速比 = 優(yōu)化前系統(tǒng)耗時(shí) / 優(yōu)化后系統(tǒng)耗時(shí) = 500/400 = 1.25
由于5個(gè)步驟中，3個(gè)步驟必須串行，因此其串行化比例為3/5=0.6，即 F = 0.6，且雙核處理器的處理器個(gè)數(shù)N為2。代入加速比公式得：
加速比 = 1/(0.6+(1-0.6)/2)=1.25
在極端情況下，假設(shè)并行處理器個(gè)數(shù)為無(wú)窮大，則有如圖1.11所示的處理過(guò)程。步驟2和步驟5的處理時(shí)間趨于0。即使這樣，系統(tǒng)整體耗時(shí)依然大于300個(gè)單位時(shí)間。使用加速比計(jì)算公式，N趨于無(wú)窮大，有加速比 = 1/F，且F=0.6，故有加速比=1.67。即加速比的極限為500/300=1.67。
由此可見(jiàn)，為了提高系統(tǒng)的速度，僅增加CPU處理的數(shù)量并不一定能起到有效的作用。需要從根本上修改程序的串行行為，提高系統(tǒng)內(nèi)可并行化的模塊比重，在此基礎(chǔ)上，合理增加并行處理器數(shù)量，才能以最小的投入，得到最大的加速比。
注意：根據(jù)Amdahl定律，使用多核CPU對(duì)系統(tǒng)進(jìn)行優(yōu)化，優(yōu)化的效果取決于CPU的數(shù)量，以及系統(tǒng)中串行化程序的比例。CPU數(shù)量越多，串行化比例越低，則優(yōu)化效果越好。僅提高CPU數(shù)量而不降低程序的串行化比例，也無(wú)法提高系統(tǒng)的性能。
阿姆達(dá)爾定律圖示為了更好地理解阿姆達(dá)爾定律，我會(huì)嘗試演示這個(gè)定定律是如何誕生的。
首先，一個(gè)程序可以被分割為兩部分，一部分為不可并行部分B，一部分為可并行部分1 – B。如下圖：
在頂部被帶有分割線的那條直線代表總時(shí)間 T(1)。
下面你可以看到在并行因子為2的情況下的執(zhí)行時(shí)間：
并行因子為3的情況：
舉個(gè)例子
一個(gè)業(yè)務(wù)會(huì)串行調(diào)用2個(gè)方法，m1，m2，m1耗時(shí)100ms，m2耗時(shí)400ms，m2內(nèi)部串行執(zhí)行了4個(gè)無(wú)依賴的任務(wù)，每個(gè)任務(wù)100ms，如下圖：
m2內(nèi)部的4個(gè)任務(wù)無(wú)依賴的，即可以并行進(jìn)行處理，4個(gè)任務(wù)同時(shí)并行，當(dāng)cpu數(shù)量大于等于4的時(shí)候，可以讓4個(gè)任務(wù)同時(shí)進(jìn)行，此時(shí)m2耗時(shí)最小，即100ms，cpu為2個(gè)的時(shí)候，同時(shí)只能夠執(zhí)行2個(gè)任務(wù)，其他2個(gè)任務(wù)處于等待cpu分配時(shí)間片狀態(tài)，此時(shí)m2耗時(shí)200ms；當(dāng)cpu超過(guò)4個(gè)的時(shí)候，或者趨于無(wú)限大的時(shí)候，m2耗時(shí)還是100ms，此時(shí)cpu數(shù)量再怎么增加對(duì)性能也沒(méi)有提升了，此時(shí)需要提升的是任務(wù)可以并行的數(shù)量。
從阿姆達(dá)爾定律可以看出，程序的可并行化部分可以通過(guò)使用更多的硬件（更多的線程或CPU）運(yùn)行更快。對(duì)于不可并行化的部分，只能通過(guò)優(yōu)化代碼來(lái)達(dá)到提速的目的。因此，你可以通過(guò)優(yōu)化不可并行化部分來(lái)提高你的程序的運(yùn)行速度和并行能力。你可以對(duì)不可并行化在算法上做一點(diǎn)改動(dòng)，如果有可能，你也可以把一些移到可并行化放的部分。
Gustafson定律Gustafson定律也試圖說(shuō)明處理器個(gè)數(shù)、串行化比例和加速比之間的關(guān)系，如圖1.12所示，但是Gustafson定律和Amdahl定律的角度不同。同樣，加速比都被定義為優(yōu)化前的系統(tǒng)耗時(shí)除以優(yōu)化后的系統(tǒng)耗時(shí)。
根據(jù)Gustafson定律，我們可以更容易地發(fā)現(xiàn)，如果串行化比例很小，并行化比例很大，那么加速比就是處理器的個(gè)數(shù)。只要不斷地累加處理器，就能獲得更快的速度。
Amdahl定律和Gustafson定律結(jié)論有所不同，并不是說(shuō)其中有個(gè)是錯(cuò)誤的，只是二者從不同的角度去看待問(wèn)題的結(jié)果，他們的側(cè)重點(diǎn)有所不同。
Amdahl強(qiáng)調(diào)：當(dāng)串行換比例一定時(shí)，加速比是有上限的，不管你堆疊多少個(gè)CPU參與計(jì)算，都不能突破這個(gè)上限。
Gustafson定律關(guān)系的是：如果可被并行化的代碼所占比例足夠大，那么加速比就能隨著CPU的數(shù)量線性增長(zhǎng)。
總的來(lái)說(shuō)，提升性能的方法?：想辦法提升系統(tǒng)并行的比例，同時(shí)增加CPU數(shù)量。
喜歡就關(guān)注我吧文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75907.html
摘要：方法由兩個(gè)參數(shù)，表示期望的值，表示要給設(shè)置的新值。操作包含三個(gè)操作數(shù)內(nèi)存位置預(yù)期原值和新值。如果處的值尚未同時(shí)更改，則操作成功。中就使用了這樣的操作。上面操作還有一點(diǎn)是將事務(wù)范圍縮小了，也提升了系統(tǒng)并發(fā)處理的性能。 這是java高并發(fā)系列第21篇文章。 本文主要內(nèi)容 從網(wǎng)站計(jì)數(shù)器實(shí)現(xiàn)中一步步引出CAS操作 介紹java中的CAS及CAS可能存在的問(wèn)題 悲觀鎖和樂(lè)觀鎖的一些介紹及數(shù)據(jù)庫(kù)...
摘要：有三種狀態(tài)運(yùn)行關(guān)閉終止。類類，提供了一系列工廠方法用于創(chuàng)建線程池，返回的線程池都實(shí)現(xiàn)了接口。線程池的大小一旦達(dá)到最大值就會(huì)保持不變，在提交新任務(wù)，任務(wù)將會(huì)進(jìn)入等待隊(duì)列中等待。此線程池支持定時(shí)以及周期性執(zhí)行任務(wù)的需求。 這是java高并發(fā)系列第19篇文章。 本文主要內(nèi)容 介紹Executor框架相關(guān)內(nèi)容 介紹Executor 介紹ExecutorService 介紹線程池ThreadP...
摘要：參考何去何從的并行計(jì)算忘記該死的并行并行程序的復(fù)雜性和亂序性，并行程序設(shè)計(jì)十分復(fù)雜?？膳碌默F(xiàn)實(shí)摩爾定律的失效單核上的晶體管數(shù)目達(dá)到極限。并發(fā)級(jí)別阻塞重入鎖無(wú)饑餓兩個(gè)線程優(yōu)先級(jí)不同，低優(yōu)先級(jí)的可能產(chǎn)生饑餓。 Chapter1 參考：https://github.com/chengbingh... 1.1何去何從的并行計(jì)算 1.1.1 忘記該死的并行并行程序的復(fù)雜性和亂序性，并行程序設(shè)計(jì)十...
摘要：我們需要先了解這些概念。在中，其表現(xiàn)在對(duì)于共享變量的某些操作，是不可分的，必須連續(xù)的完成。有序性有序性指的是程序按照代碼的先后順序執(zhí)行。 JMM(java內(nèi)存模型)，由于并發(fā)程序要比串行程序復(fù)雜很多，其中一個(gè)重要原因是并發(fā)程序中數(shù)據(jù)訪問(wèn)一致性和安全性將會(huì)受到嚴(yán)重挑戰(zhàn)。如何保證一個(gè)線程可以看到正確的數(shù)據(jù)呢？這個(gè)問(wèn)題看起來(lái)很白癡。對(duì)于串行程序來(lái)說(shuō)，根本就是小菜一碟，如果你讀取一個(gè)變量，這個(gè)...
摘要：無(wú)鎖無(wú)鎖的并行都是無(wú)障礙的，但不同的是無(wú)鎖的并發(fā)保證了必然有一個(gè)線程能夠在有限步驟內(nèi)離開(kāi)臨界區(qū)。有關(guān)并行的兩個(gè)重要定律未完待續(xù)實(shí)戰(zhàn)高并發(fā)程序設(shè)計(jì)第一章走入并行世界讀書(shū)筆記歡迎加入咖啡館的春天。 必須知道的幾個(gè)概念 同步（Synchronous）和異步（Asynchronous） 同步方法調(diào)用一旦開(kāi)始，調(diào)用者必須等待方法調(diào)用返回后才能繼續(xù)后續(xù)行為。異步方法調(diào)用更像一個(gè)消息傳遞，一旦開(kāi)始就...
閱讀 3068·2021-09-22 15:59
閱讀 1319·2021-08-30 09:46
閱讀 2281·2019-08-30 15:54
閱讀 2021·2019-08-26 12:15
閱讀 2547·2019-08-26 12:09
閱讀 1346·2019-08-26 11:57
閱讀 3344·2019-08-23 17:11
閱讀 1893·2019-08-23 15:59
