基于OpenMP的并行Fortran程序數(shù)據(jù)競(jìng)爭(zhēng)靜態(tài)檢測(cè)方法

葛 優(yōu),金大海,宮云戰(zhàn)

(北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100876)

1 引 言

1.1 研究背景

隨著信息技術(shù)的跨越式發(fā)展,并行計(jì)算以及并行處理技術(shù)因?yàn)楦咝阅?、低成本的?yōu)點(diǎn),在當(dāng)今各行各業(yè)的軟件和系統(tǒng)中起到了舉足輕重的作用[1].在2021年的ISC21超算大會(huì)上,中國(guó)在TOP500的計(jì)算機(jī)數(shù)量位居首位,且系統(tǒng)峰值性能達(dá)到了125425.9TFlop/s.然而隨著并行計(jì)算機(jī)大規(guī)模的發(fā)展,故障和錯(cuò)誤層出不窮,系統(tǒng)的可靠性問(wèn)題亟待解決.

Fortran迄今為止仍是并行計(jì)算領(lǐng)域最流行的語(yǔ)言之一,但受限于其發(fā)明年代,最初的 Fortran 語(yǔ)言并不支持并行計(jì)算.而OpenMP作為可調(diào)用的并行庫(kù)和應(yīng)用程序編程接口,將Fortran語(yǔ)言擴(kuò)展為并行語(yǔ)言,它以其良好的靈活性和可移植性成為了共享存儲(chǔ)并行程序設(shè)計(jì)的工業(yè)標(biāo)準(zhǔn).然而,由于編寫(xiě)并行程序的復(fù)雜性以及運(yùn)行結(jié)果存在著難以重現(xiàn)和隨機(jī)性[2],都會(huì)造成程序中的數(shù)據(jù)競(jìng)爭(zhēng)故障,故障問(wèn)題很難通過(guò)運(yùn)行幾次程序發(fā)現(xiàn)并定位出來(lái).因此,如何準(zhǔn)確的檢測(cè)并行程序中數(shù)據(jù)競(jìng)爭(zhēng)故障,提高程序的穩(wěn)定性和可靠性,是本文研究的主要內(nèi)容.

1.2 研究意義

1.2.1 國(guó)內(nèi)外研究現(xiàn)狀

Atzeni等人提出的Archer[3]使用動(dòng)靜結(jié)合的數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)方法來(lái)進(jìn)行OpenMP數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè),它強(qiáng)制程序多次運(yùn)行來(lái)查找其中的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.Archer通過(guò)僅檢測(cè)程序中的并行部分,減少了基于pthread的TSAN-LLVM工具[4]的分析空間.由于Archer使用影子內(nèi)存來(lái)跟蹤每次內(nèi)存訪問(wèn),存在檢測(cè)的內(nèi)存需求和程序直接綁定的問(wèn)題.此外由于Archer使用Polly獲取函數(shù)的依賴和加載,在沒(méi)有依賴的情況下將一段代碼列入黑名單.對(duì)于循環(huán)嵌套等問(wèn)題,由于黑名單的存在,對(duì)缺陷檢測(cè)的準(zhǔn)確度大大降低.

Gu等人提出的ROMP[5]維護(hù)每次內(nèi)存訪問(wèn)的訪問(wèn)歷史,為隱式和顯式OpenMP任務(wù)構(gòu)建任務(wù)圖并分析并發(fā)事件.ROMP具有較高的準(zhǔn)確率和召回率,但它沒(méi)有對(duì)程序使用的所有動(dòng)態(tài)加載的共享庫(kù)進(jìn)行檢查.ThreadSanitizer[6]工具是基于Valgrid來(lái)檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題,它采用的happens-before的混合方法,并為共享內(nèi)存上的讀寫(xiě)操作維護(hù)鎖集.由于它需要維護(hù)影子內(nèi)存來(lái)存儲(chǔ)元數(shù)據(jù),而每次訪問(wèn)都需要影子內(nèi)存,因此其內(nèi)存需求會(huì)隨著線程之間的共享內(nèi)存量線性增長(zhǎng),檢測(cè)的運(yùn)行時(shí)間甚至?xí)笖?shù)增長(zhǎng).

Basupalli 等人提出的OMPVerify[7]是一種基于多面體模型的靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)工具,其工作在抽象語(yǔ)法樹(shù)層面上.OMPVerify檢測(cè)的核心是通過(guò)計(jì)算多面體減少依賴關(guān)系圖(PRDG),來(lái)推斷OpenMP并行區(qū)域中可能存在的真實(shí)依賴關(guān)系、讀寫(xiě)沖突以及過(guò)時(shí)的讀取問(wèn)題.但OMPVerify只能處理OMP并行的結(jié)構(gòu),并且對(duì)存在的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題沒(méi)有顯著的分類,因此檢測(cè)結(jié)果中存在的誤報(bào)問(wèn)題明顯較多.

LLOV[8]作為一種基于LLVM獨(dú)立中間表示的靜態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)工具.它使用多面體框架Polly,基于其中間表示在LLVM框架中實(shí)現(xiàn)快速、靜態(tài)的數(shù)據(jù)競(jìng)爭(zhēng)檢查.LLOV可以處理參數(shù)數(shù)組大小和循環(huán)邊界,并且其不依賴于運(yùn)行時(shí)的線程數(shù);但LLOV不支持OpenMP中用于同步和任務(wù)處理的制導(dǎo)指令,此外受多面體框架的影響,具有動(dòng)態(tài)控制流和不規(guī)則訪問(wèn)的程序不在LLOV分析范圍內(nèi).

現(xiàn)有的缺陷檢測(cè)工具對(duì)OpenMP并行程序的語(yǔ)言和語(yǔ)法特性進(jìn)行分析的不多,一些研究人員是通過(guò)多面體模型來(lái)檢測(cè)指定的OMP并行構(gòu)造進(jìn)行靜態(tài)檢測(cè)分析,與他們工作不同的是,本文是針對(duì)OpenMP并行程序的指令特性來(lái)對(duì)數(shù)據(jù)競(jìng)爭(zhēng)故障進(jìn)行分析,從而建立數(shù)據(jù)競(jìng)爭(zhēng)模型.因此本文方法對(duì)OpenMP制導(dǎo)指令的支持更健全和更準(zhǔn)確.

1.2.2 本文工作

本文的工作應(yīng)用數(shù)據(jù)流分析以及模型檢測(cè)理論,將數(shù)據(jù)競(jìng)爭(zhēng)抽象為一種故障模型,并根據(jù)基于OpenMP的Fortran并行程序的語(yǔ)言特性,對(duì)控制流圖進(jìn)行擴(kuò)展引入并行控制流圖,以及對(duì)并行區(qū)域的數(shù)據(jù)域進(jìn)行活躍變量及數(shù)據(jù)流計(jì)算,根據(jù)程序控制流節(jié)點(diǎn)上進(jìn)行狀態(tài)轉(zhuǎn)化來(lái)實(shí)現(xiàn)數(shù)據(jù)競(jìng)爭(zhēng)的檢測(cè).此法不對(duì)源程序運(yùn)行即可檢測(cè)出程序中的數(shù)據(jù)競(jìng)爭(zhēng)故障,并且能夠全面、有效、準(zhǔn)確的報(bào)告故障.

2 數(shù)據(jù)競(jìng)爭(zhēng)故障分析

2.1 數(shù)據(jù)競(jìng)爭(zhēng)故障

定義1.在程序內(nèi)的某段代碼區(qū)域產(chǎn)生并行區(qū)域P,假定P中存在著n(n>=2)個(gè)線程,若多個(gè)線程對(duì)P中的同一變量x進(jìn)行訪問(wèn),且有m(m>=1)個(gè)線程對(duì)x進(jìn)行寫(xiě)操作,則可能會(huì)發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.數(shù)據(jù)競(jìng)爭(zhēng)不會(huì)立即使程序崩潰,但這可能會(huì)導(dǎo)致程序在并行模式下產(chǎn)生不確定的結(jié)果.

在基于OpenMP的Fortran并行程序中,串行區(qū)域由主線程執(zhí)行,并行區(qū)域則是由線程組執(zhí)行[9].對(duì)于線程組中的線程來(lái)說(shuō)執(zhí)行的只是并行區(qū)域中的代碼部分,其操作的變量信息有一部分是與線程組中的其他線程共享的,另一部分則是其私有訪問(wèn)的,并且在這兩部分中由于存在著變量的使用從而產(chǎn)生潛在的定值引用關(guān)系,從而產(chǎn)生其并行程序中的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.

2.2 數(shù)據(jù)競(jìng)爭(zhēng)缺陷分類

2.2.1 循環(huán)攜帶數(shù)據(jù)依賴

循環(huán)攜帶數(shù)據(jù)依賴是指在并行區(qū)域P中,存在一個(gè)變量x,在線程t1的循環(huán)迭代中被讀取,在線程t2的循環(huán)迭代中被寫(xiě)入,而t1!=t2.循環(huán)攜帶數(shù)據(jù)依賴故障主要是在指令需要稍后更新的值時(shí)會(huì)發(fā)生.結(jié)合圖1分析,在程序中,循環(huán)嵌套應(yīng)該在第1行中是并行的,但標(biāo)記為并行的是第3行的內(nèi)部循環(huán),此處產(chǎn)生循環(huán)攜帶依賴問(wèn)題.因?yàn)樵诔绦虻牡?行,a(i,j-1)的讀取取決于在前一次迭代中對(duì)a(i,j)的寫(xiě)入.當(dāng)在串行執(zhí)行時(shí)毫無(wú)問(wèn)題,但在并行計(jì)算時(shí),不能獲取到a(i,j)處的未修改值,因此造成第4行產(chǎn)生一個(gè)數(shù)據(jù)競(jìng)爭(zhēng)故障.

2.2.2 未指定行為

OpenMP是建立在共享存儲(chǔ)結(jié)構(gòu)的計(jì)算機(jī)之上,線程間的全局變量和靜態(tài)變量是共享的,而局部變量是私有的[10].對(duì)于寫(xiě)入并行區(qū)域中的共享變量,變量的最終值是取決于最后一次迭代的寫(xiě)入,在串行情況下,這總是最后一次迭代,而在并行模式下,不能夠保證,因此會(huì)導(dǎo)致數(shù)據(jù)競(jìng)爭(zhēng)產(chǎn)生不確定的結(jié)果.

1)臨時(shí)變量私有故障

臨時(shí)變量私有故障是指并行區(qū)域內(nèi)的各個(gè)線程未對(duì)數(shù)據(jù)進(jìn)行私有備份,導(dǎo)致在并行區(qū)域多個(gè)線程可同時(shí)訪問(wèn)該數(shù)據(jù),產(chǎn)生不確定的結(jié)果.如圖2,在程序的第5行各個(gè)線程對(duì)變量x的值進(jìn)行更新,而循環(huán)的最后一次迭代沒(méi)能設(shè)置線程的私有備份x,導(dǎo)致最終的值不確定,在第5行產(chǎn)生一個(gè)數(shù)據(jù)競(jìng)爭(zhēng)故障.

圖2 具有臨時(shí)變量私有故障的示例Fig.2 Example with temporary variable private

2)全局變量專有故障

全局變量專有故障是指并行區(qū)域內(nèi)的線程未對(duì)全局?jǐn)?shù)據(jù)進(jìn)行專有拷貝,使其在多個(gè)并行區(qū)域之間保持連續(xù)性,導(dǎo)致多個(gè)線程同時(shí)訪問(wèn)該數(shù)據(jù),產(chǎn)生未知結(jié)果.如圖3,在程序的第2行和第3行聲明了全局變量counter、pcounter;在第5行只對(duì)變量pcounter進(jìn)行線程專有設(shè)置;第9行在并行區(qū)域多個(gè)線程對(duì)counter值進(jìn)行讀寫(xiě)操作,導(dǎo)致counter值的不確定性,因此第9行產(chǎn)生一個(gè)數(shù)據(jù)競(jìng)爭(zhēng)故障.

圖3 具有全局變量專有故障的示例Fig.3 Example with global variable exclusive

3)未定義的變量故障

未定義的變量故障是指該變量無(wú)有效的值,依賴于未定義變量值的使用導(dǎo)致未知結(jié)果產(chǎn)生.結(jié)合圖4分析,在程序的第1行變量b是private()指定的,此時(shí)變量未定義;在第5行時(shí),變量b被并行區(qū)域內(nèi)使用但b未被定義,導(dǎo)致變量i值的不確定,因此造成第5行產(chǎn)生一個(gè)數(shù)據(jù)競(jìng)爭(zhēng)故障.

圖4 具有未定義故障的示例Fig.4 Example with undefined

3 數(shù)據(jù)競(jìng)爭(zhēng)故障檢測(cè)框架

本文描述的是在課題組自主研發(fā)的缺陷檢測(cè)工具DTS[11]上的基于OpenMP的Fortran并行程序數(shù)據(jù)競(jìng)爭(zhēng)的故障檢測(cè),檢測(cè)框架如圖5所示.本文根據(jù)數(shù)據(jù)競(jìng)爭(zhēng)故障的分類,將數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題抽象為一種故障模式狀態(tài)機(jī),建立數(shù)據(jù)競(jìng)爭(zhēng)故障模型;之后根據(jù)并行程序的語(yǔ)法和語(yǔ)義特性,進(jìn)行并行程序建模; 最后將故障檢測(cè)問(wèn)題轉(zhuǎn)化為一個(gè)計(jì)算故障模式狀態(tài)機(jī)實(shí)例可能狀態(tài)集合的正向數(shù)據(jù)流問(wèn)題,沿著控制流節(jié)點(diǎn)通過(guò)判斷變量的讀寫(xiě)定值關(guān)系,迭代狀態(tài)機(jī)實(shí)例的狀態(tài)集合進(jìn)行數(shù)據(jù)競(jìng)爭(zhēng)故障的檢測(cè).故障檢測(cè)流程的關(guān)鍵技術(shù)如下所示:

圖5 數(shù)據(jù)競(jìng)爭(zhēng)故障檢測(cè)框架Fig.5 Data race detection framework

1)對(duì)源代碼進(jìn)行掃描,根據(jù)Fortran并行程序的語(yǔ)法和語(yǔ)義特性,構(gòu)建對(duì)應(yīng)的抽象語(yǔ)法樹(shù)和并行控制流圖,進(jìn)行并行程序建模;

2)通過(guò)多次遍歷抽象語(yǔ)法樹(shù),建立待分析程序的符號(hào)表.在符號(hào)表中存儲(chǔ)著標(biāo)記符的作用域信息、聲明使用信息等;

3)進(jìn)行并行數(shù)據(jù)流分析,計(jì)算并行區(qū)域內(nèi)特殊數(shù)據(jù)作用域涉及到的變量隱式引用和隱式定值關(guān)系,來(lái)確定并行區(qū)域中變量的讀寫(xiě)關(guān)系;

4)將數(shù)據(jù)競(jìng)爭(zhēng)故障抽象為一種模型,并建立這種模型的缺陷模式狀態(tài)機(jī),將模型描述文件載入到檢測(cè)引擎中;

5)在程序函數(shù)內(nèi)部為每個(gè)相關(guān)的句柄建立一個(gè)狀態(tài)機(jī)實(shí)例,通過(guò)在控制流圖上迭代狀態(tài)機(jī),利用相關(guān)算法計(jì)算狀態(tài)的轉(zhuǎn)變,完成對(duì)數(shù)據(jù)競(jìng)爭(zhēng)故障的檢測(cè).

4 Fortran并行程序建模

4.1 并行程序抽象語(yǔ)法樹(shù)構(gòu)建

由于Fortran程序?qū)崿F(xiàn)并行是在串行程序中添加OpenMP API來(lái)構(gòu)建的,而OpenMP作為并行語(yǔ)言,在語(yǔ)法上與Fortran是獨(dú)立的.并行程序中的編譯指導(dǎo)指令如OMP PARALLEL在構(gòu)建Fortran抽象語(yǔ)法樹(shù)時(shí)不會(huì)被解析生成抽象語(yǔ)法樹(shù)節(jié)點(diǎn)[12],僅僅對(duì)Fortran源程序構(gòu)建語(yǔ)法樹(shù)的方法是不能識(shí)別出并行區(qū)域的.因此,本小節(jié)提出了一種Fortran并行程序抽象語(yǔ)法樹(shù)的構(gòu)建方法.

4.1.1 抽象語(yǔ)法樹(shù)節(jié)點(diǎn)處理

對(duì)于Fortran程序的并行區(qū)域是根據(jù)OMP DO等編譯制導(dǎo)指令將指令包圍起來(lái)的串行區(qū)域并行化,制導(dǎo)指令只會(huì)將計(jì)算分散到不同線程中來(lái)加快執(zhí)行速度,不會(huì)影響Fortran程序的計(jì)算結(jié)果.因此對(duì)于Fortran代碼塊來(lái)說(shuō),若代碼塊的外側(cè)存在著一對(duì)制導(dǎo)指令,就可以確定這段代碼需要并行執(zhí)行.因此在抽象語(yǔ)法樹(shù)生成的節(jié)點(diǎn)中,確定Fortran代碼段與OMP制導(dǎo)指令的綁定關(guān)系,即可對(duì)并行程序的抽象語(yǔ)法樹(shù)進(jìn)行構(gòu)建和訪問(wèn).

1)基于ANTLR詞法語(yǔ)法解析器[13],對(duì)Fortran和OpenMP生成對(duì)應(yīng)的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)信息,在當(dāng)前節(jié)點(diǎn)中存儲(chǔ)其父結(jié)點(diǎn)及孩子節(jié)點(diǎn)信息.

2)對(duì)節(jié)點(diǎn)信息進(jìn)行拆分和讀取;根據(jù)節(jié)點(diǎn)關(guān)系特征,按照樹(shù)高從上到下逐層讀取語(yǔ)法樹(shù)節(jié)點(diǎn),每次都開(kāi)辟一個(gè)新的空間來(lái)存儲(chǔ)下一層節(jié)點(diǎn)的信息.

3)對(duì)節(jié)點(diǎn)信息進(jìn)行標(biāo)記;首先在抽象語(yǔ)法樹(shù)節(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)行號(hào)信息,然后按照行號(hào)確定Fortran與OpenMP節(jié)點(diǎn)間的關(guān)系,確定并行入口節(jié)點(diǎn)、并行出口節(jié)點(diǎn)以及并行區(qū)域Fortran起始和結(jié)束節(jié)點(diǎn).

4.1.2 基于鄰接表的節(jié)點(diǎn)訪問(wèn)算法構(gòu)建

根據(jù)上文的節(jié)點(diǎn)生成、節(jié)點(diǎn)存儲(chǔ)以及節(jié)點(diǎn)標(biāo)記,本文使用鄰接表作為重建抽象語(yǔ)法樹(shù)的存儲(chǔ)結(jié)構(gòu),通過(guò)鄰接表存儲(chǔ)串行和并行出入口節(jié)點(diǎn)來(lái)實(shí)現(xiàn)對(duì)Fortran并行程序的節(jié)點(diǎn)訪問(wèn)算法.

此算法基本思想為:首先利用鄰接表存儲(chǔ)并行抽象語(yǔ)法樹(shù)節(jié)點(diǎn)關(guān)聯(lián)信息,將并行區(qū)域起始節(jié)點(diǎn)的父節(jié)點(diǎn)作為鄰接表的鄰接數(shù)組,將對(duì)應(yīng)的OpenMP并行入口節(jié)點(diǎn)作為其鄰接表內(nèi)的鄰接關(guān)系.之后對(duì)語(yǔ)法樹(shù)節(jié)點(diǎn)訪問(wèn)時(shí),先遍歷鄰接數(shù)組,判斷訪問(wèn)的該節(jié)點(diǎn)是否在鄰接表中存在,如果存在即當(dāng)前節(jié)點(diǎn)為并行入口節(jié)點(diǎn),則訪問(wèn)其鄰接表內(nèi)對(duì)應(yīng)鄰接關(guān)系節(jié)點(diǎn)為其并行抽象語(yǔ)法樹(shù)的孩子節(jié)點(diǎn);否則根據(jù)深度優(yōu)先搜索直接訪問(wèn)其孩子節(jié)點(diǎn)信息.

4.2 并行控制流圖構(gòu)建

Fortran并行程序是由串行代碼塊和并行代碼塊交替組成的代碼區(qū)域,對(duì)于串行控制流圖來(lái)說(shuō),并不能表示因?yàn)镺penMP指導(dǎo)指令產(chǎn)生的并行區(qū)域,因此本小節(jié)提出了Fortran并行控制流圖來(lái)解決這一問(wèn)題.

算法.基于鄰接表的節(jié)點(diǎn)訪問(wèn)算法

輸入：鄰接表、抽象語(yǔ)法樹(shù)節(jié)點(diǎn)

輸出：抽象語(yǔ)法樹(shù)節(jié)點(diǎn)訪問(wèn)信息

1. begin:

2. createAdjacencyList(root);//鄰接表存儲(chǔ)節(jié)點(diǎn)關(guān)聯(lián)信息

3. ASTprogram_unit ast !=null

4. for all num in nunMap do //遍歷鄰接數(shù)組

5. if node==num.key then

6. root.astNodeAddChild(createTree(root,node),root.child);//節(jié)點(diǎn)信息添加到語(yǔ)法樹(shù)中

7. for all n in num.nodeList do //遍歷訪問(wèn)鄰接節(jié)點(diǎn)的鄰接鏈表

8. visitNodeInfo(n);

9. else if node is not in numMap.key then //鄰接數(shù)組中不存在當(dāng)前節(jié)點(diǎn)

10. root.astNodeAddChild(createTree(root,node),root.child);

11. for all i in node.getChildNum()do //遍歷訪問(wèn)該節(jié)點(diǎn)的孩子節(jié)點(diǎn)

12. visitNodeInfo(node.getChild(i))

13. end for

14. return ast //返回語(yǔ)法樹(shù)節(jié)點(diǎn)訪問(wèn)信息

15. end

4.2.1 Fortran并行控制流圖定義

定義2.設(shè)一個(gè)Fortran并行程序中存在N個(gè)并行代碼塊,那么該程序的并行控制流圖(PCFG),可表示為三元組{Gs,Gp,Ep}:

Ep定義為串行區(qū)域與并行區(qū)域控制流的邊集,是從串行區(qū)域進(jìn)入并行區(qū)域以及從并行區(qū)域離開(kāi)串行區(qū)域的特殊控制流.

4.2.2 Fortran并行控制流圖生成算法

在Fortran并行區(qū)中,一般包含任務(wù)共享結(jié)構(gòu),根據(jù)Fortran并行語(yǔ)法特征,主要將其分為兩類:一類是如OMP DO結(jié)構(gòu),每個(gè)線程對(duì)應(yīng)的串行控制流子圖相同,只是遍歷的循環(huán)的迭代空間不同;另一類則如OMP SECTIONS結(jié)構(gòu),對(duì)于任意兩個(gè)線程所對(duì)應(yīng)的串行控制流子圖不相同[14].

針對(duì)這兩種不同的任務(wù)共享結(jié)構(gòu),本文的并行控制流圖(PCFG)的生成算法基本思想為:首先根據(jù)語(yǔ)法樹(shù)節(jié)點(diǎn)確定并行標(biāo)志位和串行標(biāo)志位,通過(guò)訪問(wèn)標(biāo)志位來(lái)判斷當(dāng)前語(yǔ)句節(jié)點(diǎn)為串行或者并行控制流,之后根據(jù)語(yǔ)句結(jié)構(gòu)設(shè)計(jì)相應(yīng)的控制流子圖,最后將生成的控制流子圖寫(xiě)入并行控制流圖數(shù)據(jù)結(jié)構(gòu)中.對(duì)于并行區(qū)域,則需要根據(jù)任務(wù)共享結(jié)構(gòu)確定其相應(yīng)類型,來(lái)生成控制流子圖.

算法：并行控制流圖生成算法

輸入：控制流輔助結(jié)構(gòu)、抽象語(yǔ)法樹(shù)節(jié)點(diǎn)

輸出：并行控制流圖信息

1. begin:

2. gsFlag <-getFlagByParseTree(ast)//通過(guò)當(dāng)前語(yǔ)法樹(shù)節(jié)點(diǎn)確定是否訪問(wèn)串行標(biāo)志位

3. gpFlag <-getFlagByParseTree(ast)

4. if gsFlag==true then //語(yǔ)句節(jié)點(diǎn)為串行控制流

5. node <-createPcfgNode(ast)//創(chuàng)建控制流節(jié)點(diǎn)

6. gsi <-new CFG(ast,node.addEdge())//根據(jù)語(yǔ)句結(jié)

構(gòu)生成控制流子圖

7. gs.add(gsi);

8. visitNextStatement(ast)//訪問(wèn)下一條語(yǔ)句

9. else if gpFlag==true then //語(yǔ)句節(jié)點(diǎn)為并行控制流

10. shareFlag<-getShareStructFlag(ast)//確定節(jié)點(diǎn)的任務(wù)

共享結(jié)構(gòu)

11. if shareFlag==true then//并行區(qū)任務(wù)共享結(jié)構(gòu)相

同時(shí)

12. node <-createPcfgNode(ast)

13. gp.add(new CFG(ast,node.addEdge()));

14. else if shareFlag==false then

15. for all i in node.getThreadNum()do//遍歷并行區(qū)

域內(nèi)的線程數(shù)

16. ni <-createPcfgNode(ast)

17. gp[i] <-new CFG(ast,ni.addEdge())//為不

同線程創(chuàng)建串行控制流子圖

18. gp.add(gp[i]);

19. end for

20. visitNextStatement(ast)//訪問(wèn)下一條語(yǔ)句

21. end if

22. end

5 數(shù)據(jù)競(jìng)爭(zhēng)故障模式狀態(tài)機(jī)的設(shè)計(jì)

定義3.缺陷模式狀態(tài)機(jī)是描述存在有限個(gè)缺陷模式狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)計(jì)算模型,包括非空有限狀態(tài)集合S、輸入字母表Σ及轉(zhuǎn)移函數(shù)集合δ,S0是初始狀態(tài),為S的子集,其中δ:S×Σ→S.

在2.2節(jié)中討論的兩類數(shù)據(jù)競(jìng)爭(zhēng)缺陷,可以用圖6所示的缺陷模式狀態(tài)機(jī)來(lái)描述.它以被分析的函數(shù)為單元,針對(duì)并行區(qū)域內(nèi)調(diào)用的全局/局部變量創(chuàng)建狀態(tài)機(jī)實(shí)例,并通過(guò)對(duì)變量的讀寫(xiě)操作進(jìn)行跟蹤進(jìn)行缺陷報(bào)告.

圖6 數(shù)據(jù)競(jìng)爭(zhēng)缺陷模式狀態(tài)機(jī)Fig.6 Data race defect mode state machine

數(shù)據(jù)競(jìng)爭(zhēng)狀態(tài)機(jī)的狀態(tài)集合S設(shè)計(jì)為:{START,LOOP_DEPENDENCY,UNDEFINE,ERROR,END}.其中START狀態(tài)代表狀態(tài)機(jī)的唯一入口;END狀態(tài)代表結(jié)束狀態(tài);LOOP_DEPENDENCY狀態(tài)代表著當(dāng)前節(jié)點(diǎn)進(jìn)入到循環(huán)執(zhí)行的任務(wù)分擔(dān)域,其中的各個(gè)線程各自分擔(dān)其中一部分工作;UNDEFINE狀態(tài)代表著當(dāng)前節(jié)點(diǎn)內(nèi)的數(shù)據(jù)變量被設(shè)置為對(duì)并行部分的線程可見(jiàn)/私有;ERROR狀態(tài)代表當(dāng)前分析的節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)缺陷.

表1標(biāo)識(shí)了數(shù)據(jù)競(jìng)爭(zhēng)狀態(tài)轉(zhuǎn)換過(guò)程.

表1 數(shù)據(jù)競(jìng)爭(zhēng)的狀態(tài)轉(zhuǎn)換Table 1 State transition of data race

6 數(shù)據(jù)競(jìng)爭(zhēng)故障檢測(cè)算法

根據(jù)2.1節(jié)談到的兩種情況,可以看到這兩種情況主要是分為循環(huán)攜帶依賴和未指定行為.因此,下面將對(duì)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)算法分為循環(huán)攜帶依賴故障的檢測(cè)算法和未指定行為的檢測(cè)算法兩個(gè)部分來(lái)描述:

數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)算法所用到的定義如下:

N:控制流圖中所有節(jié)點(diǎn)的集合;

getEvaluationResults(node,xpath):通過(guò)Xpath檢索當(dāng)前程序中是否存在并行區(qū)域;

createSMInstance(var):變量var創(chuàng)建狀態(tài)機(jī)實(shí)例;

getState(var,n):獲得var在節(jié)點(diǎn)n上的狀態(tài),有START、LOOP_DEPENDENCY、UNDEFINE、ERROR、END;

addGen(state):添加新的狀態(tài)至gen[n];

in[n]:到達(dá)節(jié)點(diǎn)n之前的所有狀態(tài);

out[n]:到達(dá)節(jié)點(diǎn)n之后的所有狀態(tài);

gen[n]:到達(dá)節(jié)點(diǎn)n之后創(chuàng)建或迭代的所有狀態(tài).

6.1 循環(huán)攜帶依賴故障的檢測(cè)算法

以下是循環(huán)攜帶依賴故障檢測(cè)算法涉及到的幾個(gè)定義:

checkDependency(n):判斷當(dāng)前節(jié)點(diǎn)是否依靠并行區(qū)域的循環(huán)迭代次序,若為true,則說(shuō)明依靠,反之不依靠.

compareDependency(leftVar,rightVar):比較賦值操作的左右兩邊的變量操作是否存在著讀后寫(xiě)或者寫(xiě)后讀問(wèn)題.

此算法思想為:為程序中每個(gè)并行循環(huán)迭代變量創(chuàng)建故障狀態(tài)機(jī)實(shí)例,在并行控制流圖上根據(jù)狀態(tài)轉(zhuǎn)換條件進(jìn)行狀態(tài)的迭代,當(dāng)節(jié)點(diǎn)中的狀態(tài)為ERROR或END時(shí),則整個(gè)算法結(jié)束.

算法.循環(huán)攜帶依賴故障檢測(cè)算法

輸入：并行控制流圖、故障模式狀態(tài)機(jī)

輸出：報(bào)告數(shù)據(jù)競(jìng)爭(zhēng)

1. begin:

2. for node in getEvaluationResults(node,xpath)

3. do createDBStateInstance(n)

4. for each n in N do

5. do in[n]=out[n] !=null

6. visited=true

7. if visited then

8. for each n in N do

9. if n==entry then //當(dāng)前節(jié)點(diǎn)為控制流圖的入口節(jié)點(diǎn)

10. in[n]=state.getValue(START)

11. elseif checkLoop(n)

12. n.addGen(LOOP_DEPENDENCY);

13. detectLoopRace(n)//判斷節(jié)點(diǎn)是否存在數(shù)據(jù)依賴問(wèn)題

14. elseif checkUnDefined(n)&& IsAssignmentStmt(node)then

15. n.addGen(UNDEFINE);

16. end for

17. end

18. detectLoopRace:

19. begin:

20. if getState(node,n)=LOOP_DEPENDENCY &&checkDependency(n)then

21. if compareDependency(leftVar,rightVar)//判斷并行循環(huán)區(qū)域變量迭代的讀寫(xiě)依賴情況

22. n.addGen(ERROR);

23. report find Data Race //報(bào)告數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題

24. elseif !checkDependency(n)then

25. n.addGen(END);

26. end

27. end

6.2 未指定行為的檢測(cè)算法

對(duì)于Fortran并行程序來(lái)說(shuō),由于某些變量在進(jìn)入并行區(qū)后具有特殊的數(shù)據(jù)作用域?qū)傩訹15],如OMP PARALLEL PRIVATE(a),變量a被指定為并行區(qū)域中的私有屬性,即會(huì)在每個(gè)線程里定義新的同類型對(duì)象,取代原始變量.則對(duì)于a來(lái)說(shuō),在并行區(qū)域中產(chǎn)生的每個(gè)線程,都將擁有其值未定義的私有副本.因此本文使用基本數(shù)據(jù)流分析方式,求解并行程序的結(jié)果可能不正確.

6.2.1 并行數(shù)據(jù)流分析

定義4.隱式引用和隱式定值定義為并行區(qū)域中由OpenMP指令導(dǎo)致的潛在賦值操作引發(fā)的定值和引用關(guān)系.即對(duì)于一個(gè)共享變量,如果在并行區(qū)域中被聲明作為線程某種類型的私有變量,那么變量的共享版本值有可能會(huì)傳遞給線程中某一個(gè)私有副本,某一個(gè)私有副本的值也可能會(huì)傳遞給變量的共享版本.

并行數(shù)據(jù)流分析就是要在基本數(shù)據(jù)流分析的基礎(chǔ)上對(duì)隱式引用和隱式定值進(jìn)行分析和處理,使并行區(qū)域中存在隱式引用和隱式定值的代碼塊顯示地存儲(chǔ)在對(duì)應(yīng)變量的定義出現(xiàn)(DEF)集合和使用出現(xiàn)(USE)集合中[16],來(lái)確定并行區(qū)域中變量的讀寫(xiě)關(guān)系.

6.2.2 未指定行為的檢測(cè)算法

getSameParallel(node,samePath):判斷當(dāng)前控制流節(jié)點(diǎn)對(duì)應(yīng)的抽象語(yǔ)法樹(shù)中并行區(qū)域是否為相同任務(wù)共享結(jié)構(gòu);

isLocalScope(n):判斷當(dāng)前節(jié)點(diǎn)的符號(hào)表作用域;

此算法思想為:與循環(huán)攜帶依賴故障檢測(cè)算法一致,也是控制流圖迭代狀態(tài),但未指定行為中任務(wù)共享結(jié)構(gòu)分為兩種,要對(duì)串行控制流子圖相同與否進(jìn)行分類分析,此外在迭代過(guò)程中對(duì)于各個(gè)線程的變量進(jìn)行并行數(shù)據(jù)流分析,最終當(dāng)前控制流節(jié)點(diǎn)的讀寫(xiě)情況來(lái)確定是否含有數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.

算法.未指定行為檢測(cè)算法

輸入:并行控制流圖、故障模式狀態(tài)機(jī)

輸出:報(bào)告數(shù)據(jù)競(jìng)爭(zhēng)

1. begin:

2. for node in getEvaluationResults(node,xpath)

3. do createDBStateInstance(n)

4. for each n in N do

5. do in[n]=out[n] !=null

6. visited=true

7. if visited then //當(dāng)前節(jié)點(diǎn)位于控制流圖

8. isSame=getSameParallel(node,samePath)

9. if isSame←true &&isLocalScope(n)then

10. if checkUnDefined(n)then //并行區(qū)域串行控制流子圖相同時(shí)的情況

11. n.addGen(UNDEFINED)

12. goto detectUndefine

13. elseif checkSectionUndefined(n)then //并行區(qū)域串行控制流子圖不相同時(shí)的情況

14. n.addGen(UNDEFINED)

15. goto detectUndefine

16. end for

17. detectUndefine:

18. begin:

19. in[n]=∪p∈pred[n]out[p]//進(jìn)行數(shù)據(jù)流分析

20. old[n]=out[n]

21. out[n]=gen[n]∪(in[n]-kil([n]))

22. liveIn[n]=getParallelUseDef(out[n])//對(duì)并行線程副本的定義-使用關(guān)系進(jìn)行分析

23. if liveIn[n]={var:ERROR} then

24. report find Data Race

25. end

26. end

7 實(shí)驗(yàn)結(jié)果與分析

為了進(jìn)行實(shí)驗(yàn)評(píng)估,本文選擇了DataRaceBench Fortran 1.3.2 基準(zhǔn)測(cè)試集[17],可以系統(tǒng)和定量評(píng)估數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)工具的有效性.DataRaceBench Fortran是由166個(gè)微基準(zhǔn)內(nèi)核組成的,其中83個(gè)具有已知的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題,剩余83個(gè)不存在任何數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.

以運(yùn)用本文所提出的方法參與開(kāi)發(fā)的缺陷檢測(cè)系統(tǒng)(DTS)為工具進(jìn)行實(shí)驗(yàn),對(duì)DataRaceBench Fortran進(jìn)行檢測(cè),并與其他檢測(cè)工具進(jìn)行比較,表2為測(cè)試結(jié)果.

表2 不同工具檢測(cè)的最大競(jìng)爭(zhēng)數(shù)Table 2 Maximum number of races reported by different tools

表2中的TP表示能檢測(cè)到已存在的缺陷,FN表示未能檢測(cè)到已存在的缺陷,TN表示能檢測(cè)到不存在缺陷問(wèn)題,FP表示誤報(bào),不存在缺陷卻檢測(cè)到;誤報(bào)率表示本工具中檢測(cè)到的誤報(bào)缺陷數(shù)占所有不存在缺陷問(wèn)題總數(shù)的百分比.

根據(jù)表2中的實(shí)驗(yàn)對(duì)比數(shù)據(jù),可以看出運(yùn)用本方法的DTS與國(guó)際一流工具相比在數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)的準(zhǔn)確性上基本持平,尤其是DTS的平均誤報(bào)率僅為18.07%,比效果最好的ROMP 21.69%的誤報(bào)率低了3.62%,這說(shuō)明DTS能正確報(bào)出故障的效果是最好的,具有更好的檢測(cè)性能.

為了驗(yàn)證DTS檢測(cè)的穩(wěn)定性和精確性,對(duì)UP2D、NDYN、ParallelForest[18]等3個(gè)大型開(kāi)源項(xiàng)目進(jìn)行檢測(cè),表3為測(cè)試的結(jié)果.

表3 開(kāi)源項(xiàng)目測(cè)試結(jié)果Table 3 Open source project test results

IP表示檢測(cè)工具檢測(cè)到的數(shù)據(jù)競(jìng)爭(zhēng)故障,Defect表示IP中經(jīng)人工確認(rèn)后真實(shí)存在的數(shù)據(jù)競(jìng)爭(zhēng)故障,精確率是對(duì)預(yù)測(cè)結(jié)果的接近程度進(jìn)行度量,其表示為Defect個(gè)數(shù)占IP個(gè)數(shù)的百分比,較高的精確率表示該檢測(cè)工具通常會(huì)在存在數(shù)據(jù)競(jìng)爭(zhēng)時(shí)識(shí)別出數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題.運(yùn)用本方法的DTS檢測(cè)工具與ROMP檢測(cè)工具的測(cè)試結(jié)果進(jìn)行對(duì)比,圖3為對(duì)應(yīng)的結(jié)果.在所測(cè)的3個(gè)項(xiàng)目中,DTS經(jīng)人工確認(rèn)后的真實(shí)故障數(shù)為31個(gè),平均精確率為72.09%,而ROMP檢測(cè)出來(lái)的真實(shí)故障數(shù)為18個(gè),平均精確率為64.29%.從表3可以看出運(yùn)用本方法的DTS能夠檢測(cè)出更多的故障并且精確率更高,說(shuō)明本文提出的檢測(cè)方法是有效的,具有更好的精確性.

8 結(jié) 論

本文采用靜態(tài)分析方法檢測(cè) OpenMP并行Fortran程序中的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題,并通過(guò)所研發(fā)的測(cè)試工具來(lái)證明了本方法的可行性,同時(shí)實(shí)驗(yàn)數(shù)據(jù)也證明了本方法在數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)上的有效性.但通過(guò)實(shí)驗(yàn)數(shù)據(jù)也顯示了本方法并不能完全排除漏報(bào)和誤報(bào)問(wèn)題.通過(guò)分析,本文發(fā)現(xiàn)漏報(bào)問(wèn)題主要是由于有些數(shù)據(jù)競(jìng)爭(zhēng)故障沒(méi)有被歸類以及函數(shù)調(diào)用關(guān)系劃分不準(zhǔn)確造成的,而誤報(bào)問(wèn)題是由于并行數(shù)據(jù)流的分析不準(zhǔn)確造成的.今后的研究方向?qū)⒃谝韵?個(gè)方面改進(jìn):首先是進(jìn)一步總結(jié)數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題出現(xiàn)的情況,將其進(jìn)行更細(xì)致全面的抽象歸類;其次是對(duì)并行數(shù)據(jù)流進(jìn)行優(yōu)化以及變量進(jìn)行區(qū)間計(jì)算,盡量減少誤報(bào)和漏報(bào);最后是將此方法應(yīng)用于更多的故障檢測(cè)中去.