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

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

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

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

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

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

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

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

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

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