2019獨角獸企業(yè)重金招聘Python工程師標準>>>

Java Streams，第 4 部分: 從并發(fā)到并行

Java Streams 系列的第 4 期文章將解釋決定并行處理的有效性的因素，從歷史和技術(shù)角度分析它們。了解這些因素是最高效地使用 Streams 庫實現(xiàn)并行執(zhí)行的基礎(chǔ)，下一期文章 會重點介紹如何將這些原則直接應用于 Streams。

更多核心，而不是更快的核心

從 2002 年左右開始，芯片設(shè)計者用于實現(xiàn)性能指數(shù)級增長的技術(shù)開始枯竭。由于各種原因，進一步提高時鐘頻率變得不切實際，包括功耗和散熱，而且在每個周期完成更多工作的技術(shù)（ 指令級并行性 ）所帶來的收益也已開始出現(xiàn)滑坡。

摩爾定律 預言，可集成到一個晶片上的晶體管數(shù)量約每兩年翻一番。當芯片設(shè)計者 2002 年遇到頻率瓶頸 時，這并不是因為摩爾定律已失效；我們可以看到，晶體管數(shù)量仍然穩(wěn)定地呈指數(shù)級增長。不過，雖然利用這種不斷增加的晶體管預算來獲得更快核心的能力已失去作用，但芯片設(shè)計者仍能使用這種不斷增加的晶體管預算在單個晶片上放入更多核心。圖 1 通過來自英特爾處理器的數(shù)據(jù)演示了這種趨勢，這些數(shù)據(jù)標繪在一個對數(shù)標尺上。最頂部的（直）線表示晶體管數(shù)量的指數(shù)級增長，表示時鐘頻率、功耗和指令級并行性的線在 2002 年左右都表現(xiàn)出明顯的趨平狀態(tài)。

圖 1. 英特爾 CPU 的晶體管數(shù)量和 CPU 性能（圖像來源：Herb Sutter）

擁有更多核心可實現(xiàn)更高的功率效率（未被主動使用的核心可獨立地中斷電源），但這不一定等同于提供更高的程序性能 — 除非您可以保持所有核心都不停地執(zhí)行有用的工作。誠然，如今的芯片并沒有為我們提供摩爾定律所允許的核心數(shù) — 主要是因為如今的軟件無法富有成本效益地利用它們。

從并發(fā)到并行

幾乎在整個計算歷史中，并發(fā)性的目標都是大致相同的 （通過增加 CPU 利用率來提高性能），但技術(shù)（和性能度量）卻已發(fā)生改變。在單核系統(tǒng)時代，并發(fā)性主要依靠的是異步性— 允許某個活動在等待 I/O 完成期間讓出 CPU。異步性可提高響應速度（在后臺活動執(zhí)行期間不凍結(jié) UI）和吞吐量（在等待 I/O 完成期間允許另一個活動使用 CPU）。在一些并發(fā)性模型（例如 Actors and Communicating Sequential Processes [CSP]）中，并發(fā)性模型影響著程序結(jié)構(gòu)，但在大多數(shù)情況下（不論好壞），我們僅根據(jù)性能需要來使用并發(fā)性。

影響并行性的有效性的因素包括問題本身、解決問題所使用的算法、對任務(wù)分解和調(diào)度的運行時支持，以及數(shù)據(jù)集的大小和內(nèi)存位置。

隨著我們進入多核時代，并發(fā)性的主要應用是將工作負載分解為獨立的、粗粒度的任務(wù)（比如用戶請求），這樣做的目的在于通過同時處理多個請求來增加吞吐量。這一次，Java 庫獲得了一些工具，比如線程池 (thread pool)、信號量 (semaphore) 和 future，它們非常適合基于任務(wù)的并發(fā)性。

但是隨著核心數(shù)量的不斷增加，可能沒有足夠的 “自然發(fā)生的任務(wù)” 來讓所有核心一直處于繁忙狀態(tài)。隨著可用核心數(shù)超過任務(wù)數(shù)，另一個性能目標就變得很誘人：使用多個核心更快完成單個任務(wù)來減少延遲。不是所有任務(wù)都能通過這種分解來輕松處理；最適合的任務(wù)是數(shù)據(jù)密集型的查詢，其中的同一個操作會在大型的數(shù)據(jù)集上完成。

不幸的是，術(shù)語 并發(fā)性 和 并行性 沒有標準定義，它們常常被（錯誤地）交替使用。在過去，并發(fā)性描述的是程序的一個屬性（程序結(jié)構(gòu)所實現(xiàn)的合作計算活動的交互程度），而并行性是程序的一個執(zhí)行屬性，描述事件實際同時發(fā)生的程度。（根據(jù)此定義，并發(fā)性是并行性的潛在能力。）這種區(qū)別在真實的并發(fā)執(zhí)行主要停留在理論階段時很有用，但隨著時間的推移，有用性變得越來越低。

更多現(xiàn)代課程將并發(fā)性描述為正確、高效地控制對共享資源的訪問，而并行性指的是使用更多資源更快地解決問題。構(gòu)造線程安全的數(shù)據(jù)結(jié)構(gòu)屬于并發(fā)性范疇，通過鎖、事件、信號量、協(xié)同程序或軟件事務(wù)內(nèi)存 (STM) 等原語實現(xiàn)。另一方面，并行性使用分區(qū)或分片等技術(shù)來使多個活動處理一項任務(wù)，而沒有協(xié)調(diào)過程。

為什么這一區(qū)別很重要？畢竟，并發(fā)性和并行性的目標都是同時完成多件事。但是，應用這兩種技術(shù)的輕松程度有著很大差別。使用鎖等協(xié)調(diào)原語正確創(chuàng)建并發(fā)代碼很難、容易出錯且不自然。通過讓每個工作者擁有自己的問題部分來處理問題，從而正確創(chuàng)建并行代碼，這樣做相對更簡單、更安全且更自然。

并行性

盡管并行性的原理通常很簡單，但難點在于知道何時使用它。嚴格地講，并行性是一種優(yōu)化；它是一種為一次特定計算使用更多資源的選擇，以期更快獲得答案，而您始終有權(quán)選擇按順序執(zhí)行計算。不幸的是，使用更多資源并不能保證更快（甚至快速）獲得答案。此外，如果并行性消耗了額外的資源卻沒有為我們帶來收益（或負面收益），我們不應使用它。當然，收益高低取決于環(huán)境，所以沒有統(tǒng)一的答案。但是我們擁有各種工具，可幫助評估在給定情形中能否有效使用并行性：分析、度量和性能需求。

本文主要介紹分析（和探索）哪些計算種類可以很好地并行化，哪些不能。但是，作為經(jīng)驗規(guī)則，除非您有理由相信并行性會帶來提速，而且獲得的提速依據(jù)性能需求具有實際意義，否則會優(yōu)先使用順序執(zhí)行方法。（許多程序已足夠快，所以優(yōu)化它們所花的工作可更好地花在能創(chuàng)造更多價值的活動上，比如提高適用性或可靠性。）

可以用提速來度量并行性有效性，提速是并行運行時間與順序運行時間的比率。選擇并行性（假設(shè)它能帶來提速）是對注重時間而不是 CPU 和功率利用率的謹慎選擇。并行執(zhí)行完成的工作始終比順序執(zhí)行的多，因為除了解決問題之外，它還必須分解問題，創(chuàng)建和管理描述子問題的任務(wù)，分派和等待這些任務(wù)，合并它們的結(jié)果。所以并行執(zhí)行始終在順序執(zhí)行 “之后” 開始，希望通過規(guī)模經(jīng)濟來補償最初的落后。

要讓并行性成為更好的選擇，必須綜合考慮多個方面。首先我們需要一個允許采用并行解決方案的問題 — 不是所有問題都允許采用并行解決方案。然后，我們需要實現(xiàn)利用了內(nèi)在并行性的解決方案。我們需要確保用來實現(xiàn)并行性的技術(shù)沒有太多開銷，以至于浪費花在問題上的周期。而且我們還需要足夠的數(shù)據(jù)，以便可以實現(xiàn)獲得提速所需的規(guī)模經(jīng)濟。

利用并行性

不是所有問題都適合并行化。考慮以下問題：給定一個函數(shù) f，我們假設(shè)計算成本很高，將 g 定義如下：

g(0) = f(0)
g(n) = f( g(n-1) ), for n > 0

我們可以為 g 實現(xiàn)一個并行算法并度量它的提速，但我們不需要這么做；我們可以查看問題，而且立即就會發(fā)現(xiàn)它完全是順序的。為了看到此結(jié)果，我們可以采用稍微不同的方式重寫 g(n)：

g(n) = f( f( ... n times ... f(0) ... ) )

重寫之后，我們看到只有在 g(n-1) 計算完成后才能開始計算 g(n)。在計算 g(4) 的數(shù)據(jù)流依賴關(guān)系圖中，如圖 2 所示，g(n) 的每個值都依賴于前一個值 g(n-1)。

圖 2. 函數(shù) g 的數(shù)據(jù)流依賴關(guān)系圖

您可能忍不住得出這樣的判斷：問題源于 g(n) 是以遞歸方式定義的，但其實不然。考慮計算函數(shù) h(n) 的稍微不同的問題：

h(0) = f(0)
h(n) = f(n) + h(n-1)

如果編寫計算 h(n) 的比較明顯的實現(xiàn)，我們最終會得到一個類似圖 3 的數(shù)據(jù)流依賴關(guān)系圖，其中每個 h(n) 依賴于 h(n-1)。

圖 3. 函數(shù) h 的一種草率實現(xiàn)的數(shù)據(jù)流依賴關(guān)系圖

但是，如果以不同方式重寫 h(n)，就可以立即看到此問題可以通過并行性解決。我們可以獨立地計算每一項，然后對它們求和（這也允許并行性）：

h(n) = f(0) + f(1) + .. + f(n)

結(jié)果會得到圖 4 中所示的數(shù)據(jù)流依賴關(guān)系圖，其中每個 h(n) 均可獨立計算。

圖 4. 函數(shù) h 的數(shù)據(jù)流依賴關(guān)系圖

這些示例表明了兩點：首先，看起來類似的問題可能擁有完全不同的并行性可利用程度；第二，一個可利用并行性解決的問題的解決方案的 “明顯” 實現(xiàn)不一定會利用并行性。要獲得提速機會，需要同時滿足兩個條件。

分而治之

實現(xiàn)可利用的并行性的標準技術(shù)稱為遞歸分解 或分而治之。在此方法中，會反復將問題分解為許多子問題，直到子問題小到比按照順序解決更有意義；我們會并行解決子問題，然后組合子問題的各部分結(jié)果來獲得總結(jié)果。

清單 1 使用偽代碼演示了一個典型的分而治之解決方案，為并發(fā)執(zhí)行使用了一個假想的 CONCURRENT 原語。

清單 1.遞歸分解

R solve(Problem<R> problem) {if (problem.isSmall())return problem.solveSequentially();R leftResult, rightResult;CONCURRENT {leftResult = solve(problem.leftHalf());rightResult = solve(problem.rightHalf());}return problem.combine(leftResult, rightResult); }

遞歸分解很吸引人，因為它很簡單（在處理已遞歸定義的數(shù)據(jù)結(jié)構(gòu)（比如樹）時尤其如此）。類似清單 1 的并行代碼可跨眾多計算環(huán)境進行移植；它能夠使用一個核心或許多核心高效地處理數(shù)據(jù)，而且它不需要擔心協(xié)調(diào)對共享可變狀態(tài)的訪問帶來復雜性 — 因為沒有共享可變狀態(tài)。將問題分解為若干個子問題，安排每個問題僅訪問來自某個特定子問題的數(shù)據(jù)，這通常不需要進行線程間協(xié)調(diào)。

性能考慮因素

使用 清單 1 作為模型，我們現(xiàn)在可以繼續(xù)分析并行性可帶來優(yōu)勢的條件。通過分而治之方法引入了兩個額外的算法步驟（分解問題和組合部分結(jié)果），每個步驟或多或少適合并行性。另一個可能影響并行性能的因素是并行性原語本身的效率，我們對 清單 1 的偽代碼中假想的 CONCURRENT 機制進行了演示。其他兩個因素是數(shù)據(jù)集的屬性：數(shù)據(jù)集的大小和它的內(nèi)存位置。我們將依次查看每個條件。

一些問題（比如 “利用并行性” 部分的 g(n) 函數(shù)）完全不允許使用分解。甚至在問題允許采用分解時，分解可能也需要成本。（至少，分解一個問題涉及到創(chuàng)建子問題的描述。）例如，Quicksort 算法的分解步驟需要找到一個支點，也就是問題大小中的 O(n)，因為它涉及到檢查并（可能）更新所有數(shù)據(jù)。此需求比 “對一個元素數(shù)組求和” 這樣的問題的分解步驟的需求要高得多，后者的分解步驟為 O(1)— “對最高和最低指數(shù)求平均值。”此外，即使可以高效地分解問題，如果兩個子問題的大小非常不均勻，我們可能不會獲得太多可利用的并行性。

類似地，在解決兩個子問題時，必須組合結(jié)果。如果我們的問題是 “刪除重復元素”，步驟的組合需要合并兩個集合；如果我們想要獲得結(jié)果的一種平面表示，此步驟也為 O(n)。另一方面，如果我們的問題是 “對一個數(shù)組求和”，我們的組合步驟也是 O(1)— “添加兩個數(shù)”。

管理要并發(fā)執(zhí)行的任務(wù)可能涉及到多個可能的效率損失來源，比如將數(shù)據(jù)從一個線程轉(zhuǎn)交給另一個線程的內(nèi)在延遲，或者爭用共享數(shù)據(jù)結(jié)構(gòu)的風險。fork-join 框架（Java SE 7 中添加來管理細粒度、計算密集型任務(wù)）旨在最大限度減少并行分派中許多常見的低效性來源。java.util.stream 庫使用 fork-join 框架實現(xiàn)并行執(zhí)行。

最后，我們必須考慮數(shù)據(jù)。如果數(shù)據(jù)集很小，則很難獲得任何提速，原因是并行執(zhí)行會帶來啟動成本。類似地，如果數(shù)據(jù)集所在的內(nèi)存位置不佳（指針眾多的數(shù)據(jù)結(jié)構(gòu)，比如圖表，而不是數(shù)組），利用如今典型的內(nèi)存受限的系統(tǒng)執(zhí)行并行可能會導致許多線程等待來自緩存的數(shù)據(jù)，而不是有效使用核心來更快地計算答案。

這些因素中的每一個都有可能降低提速；在某些情況下，它們不僅會降低提速，甚至還會導致減速。

阿姆達爾定律

阿姆達爾定律描述計算的順序部分對可能的并行提速有何限制。大部分問題都有一定數(shù)量的工作無法并行化；這部分工作被稱為串行分數(shù) (serial fraction)。例如，如果將從一個數(shù)組將數(shù)據(jù)復制到另一個數(shù)組，復制過程可以并行化，但目標數(shù)組的分配（具有內(nèi)在的順序性）必須在發(fā)生任何復制之前執(zhí)行。

圖 5 展示了阿姆達爾定律的效果。各種曲線演示了此定律所允許的可能的最佳加速比，是如何隨著可獲得的處理器數(shù)量的變化的同時，對于不同的并行分數(shù)（串行分數(shù)的補集），阿姆達爾定律所允許的最大提速。舉例而言，如果并行碎片為 .5（一半的問題必須順序執(zhí)行）且有無限多個處理器可用，阿姆達爾定律會告訴我們，我們有望實現(xiàn)的最大提速為 2 倍。結(jié)果一目了然；即使我們可以通過并行化將可并行化部分的成本減少到 0，我們?nèi)杂幸话氲膯栴}要順序解決。

圖 5. 阿姆達爾定律（圖像來源：Wikimedia Commons）

阿姆達爾定律暗示的模型（工作的一些碎片必須完全順序地執(zhí)行，剩余部分可完美地并行化）過于簡單。不過，該模型仍對理解阻礙并行性的因素很有用。查明和減少串行碎片的能力，是能夠設(shè)計出更高效的并行算法的關(guān)鍵因素。

阿姆達爾定律的另一種解釋是：如果您有一臺 32 核的機器，對于您設(shè)置并行計算所花的每個周期，有 31 個周期不能應用來解決問題。而且如果您將問題拆分為兩個子問題，每個時鐘周期仍將浪費 30 個周期。只有當您拆分足夠的工作來讓所有處理器保持繁忙時，您才會獲得全速性能 — 而且如果您沒有足夠快地達到全速性能（或在此狀態(tài)停留足夠長時間），將很難獲得不錯的提速。

結(jié)束語

并行性是一種權(quán)衡，它使用更多計算資源來希望獲得提速。盡管從理論上講，我們使用 N 個核心可將問題解決速度提高 N 倍，但現(xiàn)實通常離此目標相距甚遠。影響并行性有效性的因素包括問題本身、解決問題所使用的算法、對任務(wù)分解和調(diào)度的運行時支持，以及數(shù)據(jù)集的大小和內(nèi)存位置。Java Streams 的 第 5 部分 會將這些考慮因素應用到 Streams 庫，并展示一些流管道如何（和為什么能）比其他管道更有效地實現(xiàn)并行化。

轉(zhuǎn)載于:https://my.oschina.net/CasparLi/blog/830417

總結(jié)

以上是生活随笔為你收集整理的Java Streams，第 4 部分: 从并发到并行的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。