面向多線程程序的確定性并行關(guān)鍵技術(shù)研究.pdf

1、多核平臺的普及擴大了對多線程程序的需求，然而多線程程序的編寫、測試和調(diào)試一直是一個重大的研究挑戰(zhàn)。其中一個關(guān)鍵的挑戰(zhàn)是多線程程序的不確定性。程序可能會受到不確定線程交織的影響，產(chǎn)生不可預(yù)知的結(jié)果。確定性并行技術(shù)保證程序在相同的輸入下總是被執(zhí)行相同的線程交織，這極大地方便了多線程程序的調(diào)試，也使缺陷更容易重現(xiàn)。在確定性并行的多種實現(xiàn)方式中，基于運行時的確定性并行技術(shù)（即確定性執(zhí)行技術(shù)）可以兼容現(xiàn)有的不確定性代碼，因此成為當前的研究熱點。確

2、定性執(zhí)行技術(shù)又可以概括地分為強確定性執(zhí)行技術(shù)和弱確定性執(zhí)行技術(shù)。強確定性執(zhí)行技術(shù)允許程序有數(shù)據(jù)競爭，而弱確定性執(zhí)行技術(shù)只能保證無數(shù)據(jù)競爭程序的確定性。
　　然而當前確定性執(zhí)行技術(shù)仍然存在著實用性不強的問題。例如，強確定性執(zhí)行技術(shù)的開銷較大。弱確定性執(zhí)行技術(shù)雖然開銷較小，但是需要開發(fā)者預(yù)先消除程序的數(shù)據(jù)競爭。本文針對多線程程序開發(fā)階段和運行階段的不同特點，分別研究高效且具有良好可擴展性的強確定性執(zhí)技術(shù)和弱確定性執(zhí)行技術(shù)。
　　

3、1）靜態(tài)數(shù)據(jù)競爭檢測的誤報剔除技術(shù)。消除數(shù)據(jù)競爭是軟件開發(fā)階段的一項重要工作。靜態(tài)數(shù)據(jù)競爭檢測可以檢測出所有可能的數(shù)據(jù)競爭，這不但可以使弱確定性執(zhí)行技術(shù)的應(yīng)用成為可能，還可以輔助強確定性執(zhí)行系統(tǒng)減少插樁開銷。然而，與其他程序分析工具一樣，靜態(tài)數(shù)據(jù)競爭檢測也有較高的誤報率。造成誤報率過高的一個重要原因是靜態(tài)分析方法往往過于保守地估計一個線程所能訪問的內(nèi)存范圍。針對這個問題，我們提出線程例化（Thread Specialization）技術(shù)

4、。線程例化可以靜態(tài)地區(qū)分線程。通過在靜態(tài)時就確定線程的數(shù)量和每個線程的ID，我們可以將并行程序轉(zhuǎn)換成一個數(shù)據(jù)流和控制流都簡化的版本。在這個例化后的程序上進行靜態(tài)數(shù)據(jù)競爭檢測，我們將得到更精確的結(jié)果。為了進一步減少誤報，我們在線程例化的基礎(chǔ)上提出了三個優(yōu)化。懶惰調(diào)整（Lazy Adjusting）可以在數(shù)據(jù)流分析過程中延時調(diào)整動態(tài)多維數(shù)組的值；代碼段分析（Code Region Analysis）和階段分析（Phase Analysis）

5、可以剔除大部分原先因為忽視happens-before時序關(guān)系而造成的誤報。以上三個優(yōu)化的結(jié)合平均可以減少77.8％的誤報，同時可以減少57.9%的動態(tài)插樁點。
　　2）面向強確定性執(zhí)行的程序分析技術(shù)。強確定性執(zhí)行系統(tǒng)即使在有數(shù)據(jù)競爭存在的情況下也能保證確定性。當前，保證數(shù)據(jù)競爭確定性的一種常用方法是通過緩沖對共享內(nèi)存的訪問來隔離線程。但是緩沖所有共享訪存的開銷是相當大的。我們提出一種面向強確定性執(zhí)行的靜態(tài)分析技術(shù) DRDet。我

6、們認為不是所有對共享內(nèi)存的訪問都需要緩沖，事實上只需要緩沖與數(shù)據(jù)競爭有關(guān)的共享訪存。所謂的與數(shù)據(jù)競爭有關(guān)的共享訪存，包括所有可能的數(shù)據(jù)競爭，以及其他可能與這些數(shù)據(jù)競爭訪問相同變量的訪存操作。DRDet采用可靠的靜態(tài)數(shù)據(jù)競爭檢測工具來檢測所有可能的數(shù)據(jù)競爭，并通過別名分析找到其他與數(shù)據(jù)競爭有關(guān)的共享訪存。然而實驗顯示，別名分析的不精確性使得很大一部分共享訪存被標記為與數(shù)據(jù)競爭有關(guān)。緩沖這些訪存操作仍然會帶來很大的性能開銷。針對這個問題，

7、DRDet采用了兩個優(yōu)化來減少用于查詢別名分析的訪存數(shù)量。我們在一個經(jīng)典的強確定性執(zhí)行系統(tǒng)上實現(xiàn)了DRDet靜態(tài)分析。實驗結(jié)果表明，DRDet在保持確定性和可擴展性的前提下將該系統(tǒng)的執(zhí)行開銷降低了1.6倍。
　　3）無全局同步的弱確定性執(zhí)行技術(shù)?，F(xiàn)有的弱確定性執(zhí)行系統(tǒng)幾乎都會在程序執(zhí)行中引入額外的全局同步，影響了程序的性能和可擴展性。針對此問題，我們提出一種新的線程執(zhí)行模式——令牌自由模式（Token-Free Mode）。處在令

8、牌自由模式的線程會主動放棄得到的令牌，從而避免部分線程因為長時間占有令牌而造成其他線程等待。基于這種技術(shù)，我們實現(xiàn)了一個負載均衡的弱確定性運行時系統(tǒng)——LBDR（Load-Balanced Deterministic Runtime）。LBDR通過令牌自由模式來避免串行化，并且無需全局同步。實現(xiàn)結(jié)果表明，和經(jīng)典的弱確定性執(zhí)行系統(tǒng)Parrot相比，LBDR的性能提升了1.17倍。
　　4）面向流水線并行的確定性執(zhí)行技術(shù)?，F(xiàn)有的確定性

9、執(zhí)行系統(tǒng)在流水線并行程序上的效率普遍較低，主要的原因是確定性執(zhí)行會打亂流水線并行程序的負載均衡。針對這個問題，我們在 LBDR系統(tǒng)中為程序員提供了一種性能指導(dǎo)語句——同步自由區(qū)（Synchronization-Free Sections）。同步自由區(qū)可以以一種確定的方式把令牌從同步密集線程向非同步密集線程轉(zhuǎn)移。另外，針對流水線并行程序容易出現(xiàn)單線程執(zhí)行的情況，LBDR可以在不破壞確定性的前提下動態(tài)消除單線程區(qū)內(nèi)不必要的確定性調(diào)度操作。實