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

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

1 引 言

1.1 研究背景

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

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

1.2 研究意義

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

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

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

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

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

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

1.2.2 本文工作

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

2 數(shù)據(jù)競爭故障分析

2.1 數(shù)據(jù)競爭故障

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

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

2.2 數(shù)據(jù)競爭缺陷分類

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

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

2.2.2 未指定行為

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

1)臨時變量私有故障

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

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

2)全局變量專有故障

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

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

3)未定義的變量故障

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

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

3 數(shù)據(jù)競爭故障檢測框架

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

圖5 數(shù)據(jù)競爭故障檢測框架Fig.5 Data race detection framework

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

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

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

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

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

4 Fortran并行程序建模

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

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

4.1.1 抽象語法樹節(jié)點處理

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

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

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

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

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

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

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

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

Fortran并行程序是由串行代碼塊和并行代碼塊交替組成的代碼區(qū)域,對于串行控制流圖來說,并不能表示因為OpenMP指導(dǎo)指令產(chǎn)生的并行區(qū)域,因此本小節(jié)提出了Fortran并行控制流圖來解決這一問題.

算法.基于鄰接表的節(jié)點訪問算法

輸入：鄰接表、抽象語法樹節(jié)點

輸出：抽象語法樹節(jié)點訪問信息

1. begin:

2. createAdjacencyList(root);//鄰接表存儲節(jié)點關(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é)點信息添加到語法樹中

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

8. visitNodeInfo(n);

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

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

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

12. visitNodeInfo(node.getChild(i))

13. end for

14. return ast //返回語法樹節(jié)點訪問信息

15. end

4.2.1 Fortran并行控制流圖定義

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

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

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

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

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

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

輸入：控制流輔助結(jié)構(gòu)、抽象語法樹節(jié)點

輸出：并行控制流圖信息

1. begin:

2. gsFlag <-getFlagByParseTree(ast)//通過當(dāng)前語法樹節(jié)點確定是否訪問串行標(biāo)志位

3. gpFlag <-getFlagByParseTree(ast)

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

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

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

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

7. gs.add(gsi);

8. visitNextStatement(ast)//訪問下一條語句

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

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

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

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

同時

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)//訪問下一條語句

21. end if

22. end

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

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

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

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

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

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

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

6 數(shù)據(jù)競爭故障檢測算法

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

數(shù)據(jù)競爭檢測算法所用到的定義如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出：報告數(shù)據(jù)競爭

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é)點為控制流圖的入口節(jié)點

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

11. elseif checkLoop(n)

12. n.addGen(LOOP_DEPENDENCY);

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

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ū)域變量迭代的讀寫依賴情況

22. n.addGen(ERROR);

23. report find Data Race //報告數(shù)據(jù)競爭問題

24. elseif !checkDependency(n)then

25. n.addGen(END);

26. end

27. end

6.2 未指定行為的檢測算法

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

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

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

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

6.2.2 未指定行為的檢測算法

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

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

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

算法.未指定行為檢測算法

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

輸出:報告數(shù)據(jù)競爭

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é)點位于控制流圖

8. isSame=getSameParallel(node,samePath)

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

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

11. n.addGen(UNDEFINED)

12. goto detectUndefine

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

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])//對并行線程副本的定義-使用關(guān)系進(jìn)行分析

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

24. report find Data Race

25. end

26. end

7 實驗結(jié)果與分析

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

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

表2 不同工具檢測的最大競爭數(shù)Table 2 Maximum number of races reported by different tools

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

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

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

表3 開源項目測試結(jié)果Table 3 Open source project test results

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

8 結(jié) 論

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