《多核与GPU编程：工具、方法及实践》----1.5 并行程序性能的预测与测量
本節書摘來自華章出版社《多核與GPU編程：工具、方法及實踐》一書中的第1章，第1.5節， 作 者 Multicore and GPU Programming: An Integrated Approach［阿聯酋］杰拉西莫斯·巴拉斯（Gerassimos Barlas） 著，張云泉 賈海鵬 李士剛 袁良 等譯， 更多章節內容可以訪問云棲社區“華章計算機”公眾號查看。
1.5 并行程序性能的預測與測量
構建并行程序要比串行程序更具挑戰性。并行程序程序員需要解決諸如共享資源訪問、負載均衡（即，將計算負載分配到所有計算資源上來最小化執行時間）以及程序終止（即，以協調方式暫停程序）等相關問題。
編寫并行程序應該首先確定并行能否提升程序性能，加速問題的解決。并行程序的開發成本決定了程序員不可能簡單地實現多個并行版本，通過測試找出最佳和最差版本，來評估項目的可行性。雖然對于最簡單的問題，這個方法可能是可行的。但是即使能夠這樣，如果能夠確定一個先驗的最佳開發路徑，并按照這個路徑進行并行開發，是非常有利的。
并行程序的開發始于其對應的串行版本。雖然這看起來有些矛盾，但是我們需要回答這些問題：如果沒有一個對應的串行程序版本，我們如何知道并行程序對性能的提升？我們需要一個基準性能，而這個基準性能只能從串行程序中獲得。此外，我們如何判定并行程序執行結果的正確性？當然，這并不是說串行程序的執行結果肯定是正確的，但是串行程序能夠更容易獲得正確的執行結果。
當然，串行算法及相關程序的開發也可以提供一些該程序是否能夠并行化的信息。這是很關鍵的，因為我們需要回答關于并行程序的可行性及成本效益的幾個問題：
程序中最耗時的子程序在哪里？這是最應該并行化的部分。
這些子程序一旦被確定后，并假設是可以并行化的。那么，期望的性能提升是多少?
這里需要澄清一個問題：并行所需的串行程序并不是能夠解決相同問題的任意程序。它必須能夠并行化。例如，如果需要對數據進行并行排序，那么最適合的串行實現為桶排序算法。桶排序算法的串行實現可以幫助我們預測并行實現的性能，并能夠指出算法中最耗時的部分。雖然快速排序的串行實現可以提供基準性能信息，但是它不能回答上面提到的兩個問題。
一旦實現串行版本后，我們可以利用性能分析工具（profiler）來回答上面兩個問題。性能分析工具可以收集程序的調用頻率、執行時間以及內存使用等信息。性能分析工具使用許多不同技術來執行這些任務。其中，最常用的技術如下：
程序插樁（instrumentation）：修改將要進行性能分析的程序代碼以便收集信息。例如，在每條指令執行之前增加一個專用計數器。雖然這可以提供非常精確的信息，但同時會增加程序的執行時間。除此之外，該技術需要重新編譯目標程序。
采樣（sampling）：定期中斷目標程序以便查詢正在執行的函數。顯然，該技術不能提供同程序插樁一樣的精確信息，但是目標程序不需要重新編譯，且執行時間也不會發生大的變化。
valgrind程序分析工具集包含了一個基于程序插樁技術的性能分析工具。該工具在執行性能分析操作之前進行程序插樁操作，這意味著不需要用戶干預。下面是該工具使用的一個例子：
其中，./bucketsort 1000000為目標程序和程序參數。
該工具的輸出是一個命名為callgrind.out的文件，該文件包含了分析結果。該結果可以通過前端程序（如kcachegrind）進行可視化。圖1-10為可視化結果。
當然，相關領域的經驗和知識可以允許程序員無須對串行程序進行性能分析，就可以確定串行程序中需要并行化的熱點。
然而，性能分析工具可以回答第二個問題：并行程序可以提供多少潛在的性能提升。傳統上，這可以通過近似數學模型實現，該數學模型允許我們捕捉將要執行的計算的本質問題。通過對串行程序執行性能分析操作，可以提供這些數學模型的參數。接下來的一節將討論Amdahl定律，該定律即使上述的簡單模型。
除數學模型的性能預測之外，必須要對并行程序進行實際測試，這主要有兩個原因：正確性和性能。并行程序的正確性必須要進行驗證。并行程序可以以不確定的方式執行，因為時間可能會影響計算結果。當然，并行程序一般會消除這個不良特性。此外，測試可以暴露并行程序初始設計的弱點以及需要解決的性能問題。
正確測試并行程序的方法如下。
除非特殊說明，否則需要測試并行程序的整體執行時間。如果串行程序只有一部分并行化，可僅針對這部分進行加速比和效率計算。然而，整體運行時間可用來檢測并行方案對整體性能的影響，并判斷其成本效益。例如，假設一個程序僅僅有10%的部分進行了并行化，即使這部分的加速比為100倍。如果該程序的串行版本的運行時間為100秒，那么并行版本的運行時間也高于90秒。
性能結果應該是多次執行時間的平均值，可能包括標準偏差。執行次數因問題而異。例如，如果對一個執行時間為3天的應用程序執行100次，顯然是不現實的。然而，只運行3次求平均值會產生不可靠的統計數據。因此，需要一個謹慎的平衡。
去除“異常值”。即，在計算平均值時，需要去除過大或者過小的性能結果。這是因為這些結果通常表示執行異常（例如，訪存越界或者計算機的負載發生了變化）。然而，需要重點對不利結果做出解釋而不是簡單去除。
可擴展性是非常重要的。所以，需要測試不同輸入規模及不同計算平臺大小下的性能結果（理想情況下，需要覆蓋真實應用場景的所有情況）。
性能測試時的輸入應該從小到大，但應該都包括真實應用場景中的問題規模（如果這個規模可以確定）。
當使用多核計算平臺時，并行程序開啟的線程或者進程數量不應超過可用的硬件提供的計算內核的數目。超線程是一個特例，因為這個技術使操作系統認為處理器的計算內核數目是實際值的兩倍。然而，這些邏輯計算內核并不具備真正計算內核的計算能力。所以，雖然操作系統認為這些內核是有效的（例如，有8個計算內核），但是相對應的硬件資源不存在，這樣對可擴展性的分析是不利的。理想情況下，當測試可擴展性時，應該關閉超線程，或者開啟的線程數目不要超過實際的物理內核數。
下一節討論的兩個定律可在不需要對并行程序進行實現和測試的前提下，預測并行程序性能。盡管已證明Amdahl定律是有缺陷的，但是它依然有影響力。
1.5.1 Amdahl定律
1967年，Gene Amdahl定義了一個簡單的實驗思想來獲取并行程序的可能
性能收益。Amdahl假設：
我們有一個在單CPU上執行時間為T的串行程序。
該串行程序可并行的比例為α，其中0≤α≤1。同時，串行處理剩余的1–α部分。
并行執行沒有通信開銷，并且并行部分可以平均分配到多個CPU上執行。這個假設適應于多核CPU架構，因為在這種架構下，所有計算內核共享內存。
基于這些假設，在N個計算節點上能夠獲得的加速比上限是：
（1-5）
因為我們忽略了所有任務劃分/通信/協調開銷。所以，如果設定N →∞，式（1-5）定義的可能最大加速比是：
（1-6）
式（1-6）非常重要，它通過簡單、容易記憶的方式解決了一個非常復雜的問題：并行程序對于問題的解決可以帶來多少性能提升？同時，式（1-6）采用了完全抽象的方式，不依賴于具體的計算平臺，僅與問題的特性相關，即α。
圖1-11顯示了在α取不同值的情況下，Amdahl定律的性能預測。這是非常引人注意的，因為預測的加速比受到了嚴格限制。即使α是一個比較好的值，加速比依然很低。例如當α = 0.9時，無論使用多少個處理器，加速比不可能超過10。
同樣的情況也出現在圖1-12中的效率曲線中。即使α = 95%，效率也會有較大幅度的降低。
Amdahl定律有一個非常有意思的結果，這可能是該定律產生的原因。Amdahl定律是在小型機出現的時代發布的。與大型機相比，小型機便宜但計算性能差。一個問題出現了：哪個是加速問題解決的最佳投資？是昂貴但計算性能高的大型機還是便宜但計算性能低的小型機呢？
用“蟻群與象群”這個比喻來描述這個兩難的問題，產生的結果是沒有疑問的。基于這個假設的數學證明如下：假設有一個應用程序，在單個高性能CPU A上執行的時間為TA，在單個較低性能CPU B上執行的時間為TB。那么，根據執行時間，CPU A要比CPU B快r=TB/TA倍。如果我們購買NB個性能較低的CPU B，相對于單個高性能CPU A，我們可能達到的最高加速比為：
（1-7）
如果NB無限大，我們可以得到的加速比上限為：
（1-8）
這就意味著加速比不會超過1。
（1-9）
所以，當 α = 90%且 r = 10時，最佳的解決方案是使用單個昂貴但性能高的CPU，而不是使用多個便宜但性能低的CPU。
問題是這個結果與高性能計算的現實并不一致。2014年6月公布的全球超級計算機Top 500排行榜中，由幾萬到上百萬個桌面級處理器的計算內核（其中，排第1名的中國“天河二號”擁有3 120 000個計算內核）構成的超級計算機是主流的。如果蟻群獲取了勝利，說明我們的方法存在缺陷。這將在下一節討論。
1.5.2 Gustafson-Barsis定律
Amdahl定律是錯誤的，因為已經反復證明它無法解釋現實數據：并行程序經常超過預期的加速比限制。
最終，在Amdahl定律發布20年后，Gustafson 和 Barsis開始以一種更為恰當的方式進行問題測試。
并行計算平臺并不是僅僅加速串行程序的執行。它可以處理更大的問題。所以，我們應該測試當使用串行計算平臺來處理并行計算平臺處理的相同問題時，串行計算平臺該如何處理。而不是測試并行程序相對于串行程序的性能加速比。
假設：
有一個并行應用程序，在N個CPU上執行的時間為T。
該應用程序在所有計算機上運行的時間占總運行時間的比例為：0 ≤ α ≤ 1，剩下的1 – α需要串行處理。
在串行計算機上解決該問題所需要的總時間為：
（1-10）
因為原并行計算部分現在需要串行處理。
加速比如下：
（1-11）
對應的效率如下：
（1-12）
當N無限大時，效率的下限是α。
圖1-13顯示了這種情況下的加速比曲線，它是圖1-11的一個變種。當不考慮通信開銷時，其結果確實過于樂觀，但這正是潛力所在。
圖1-14中的效率曲線依然非常不錯。即使當α = 50%時，在16個CPU上的效率也沒有低于50%。這也太異想天開了。即使是極易并行的程序，當N不斷增大時，通信開銷會成為加速比和效率降低的一個重要因素。通常情況下，能夠獲得90%的效率就已經是非常不錯的成就了。
習題
1.研究全球超級計算機性能排名中的Top 10，指出這些超級計算機：
運行什么操作系統？
由多少個CPU/GPU構成？
總內存是多少？
用于編程的軟件工具是什么？
2.AMD和NVIDIA的頂級GPU包含多少個計算內核？這些芯片的峰值性能是多少GFlop？
3.世界上最強大的超級計算機性能會有兩個值：Rpeak和Rmax，單位都是TFlo/s（每秒進行多少百萬億次浮點計算）。為什么要這樣做？從Rpeak到Rmax，性能降低的因素是什么？有沒有可能達到Rpeak？
4.一個串行應用程序中，有20%的比例必須串行執行，現需要實現3倍的性能提升。為實現這個目標，需要多少個CPU？如果要實現5倍的加速比，需要多少個CPU？
5.一個運行在5臺計算機上的并行程序中，有10%的并行部分。相對于在一個計算機上的串行執行，加速比是多少？如果我們想將加速比提升兩倍，需要多少個CPU？
7.使用合并排序算法實現一個簡單的排序程序，該程序用來對大規模（比如107）32位的整型數據進行排序。輸入和輸出數據存儲在文件中，所以I/O操作為該應用程序的串行部分。盡管合并排序算法不能在任意多個處理器上平均分配計算負載，但該算法依然被認為是非常適合并行執行的排序算法。假設計算負載能夠平均分配。應用程序可并行部分的運行時間占整體運行時間的比例為α，該值通過性能分析工具（如gprof 或者valgrind）獲得。使用這個值來預測合并排序程序的加速比。
α依賴于輸入規模嗎？如果依賴，你該如何修改預測值及對應的圖形說明？
8.一個并行程序在10個CPU上執行，執行時間為串行執行總時間的15%。我們應該使用性能為多少的CPU，才能保證串行運行時間和并行運行時間相同？
總結
以上是生活随笔為你收集整理的《多核与GPU编程：工具、方法及实践》----1.5 并行程序性能的预测与测量的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《Adobe Illustrator C
- 下一篇： 《Splunk智能运维实战》——3.6