基于分布式圖計算的大規(guī)模程序靜態(tài)分析算法與系統(tǒng)
發(fā)布時間：2021-01-06 05:36
程序靜態(tài)分析技術(shù)被廣泛應用于計算機程序設(shè)計與開發(fā)的諸多環(huán)節(jié),包括錯誤檢測、代碼優(yōu)化、測試等�；贑FL（Context-Free Language）可達的過程間程序靜態(tài)分析是一種具有較高通用意義的過程間靜態(tài)分析方法,該方法本質(zhì)上是一種圖的可達性計算問題。盡管程序靜態(tài)分析方面的研究取得了很多進展,但是由于硬件資源和傳統(tǒng)方法的限制,單機計算已難以支撐日益增長大規(guī)模圖數(shù)據(jù)的高效處理,從而導致了靜態(tài)分析方法的性能低效且可擴展性較低。因此對大規(guī)�，F(xiàn)代軟件進行復雜的過程間分析仍然具有挑戰(zhàn)性。針對大規(guī)模程序靜態(tài)分析性能低效和可擴展性低的問題,本文提出了一種基于分布式圖計算模型的高效可擴展的并行化大規(guī)模程序靜態(tài)分析方法,并設(shè)計實現(xiàn)了高效可擴展的分布式大規(guī)模程序靜態(tài)分析系統(tǒng)。本文的主要研究工作和貢獻點如下:（1）將基于CFL可達的程序靜態(tài)分析問題抽象為大規(guī)模圖計算問題,基于數(shù)據(jù)并行框架研究設(shè)計了一種新型的并行化傳遞閉包算法和Join-Process-Filter計算模型,基于該算法和計算模型,設(shè)計實現(xiàn)了一個分布式離線全量程序靜態(tài)分析系統(tǒng),分別提出了算法級和系統(tǒng)級優(yōu)化,并設(shè)計了具有壓縮效果的數(shù)據(jù)結(jié)構(gòu)。（2...
【文章來源】：南京大學江蘇省 211工程院校 985工程院校 教育部直屬院校
【文章頁數(shù)】：87 頁
【學位級別】：碩士
【部分圖文】：
圖２－３?Ｓｐａｒｋ生態(tài)系統(tǒng)組件??
第三章離線全量程序靜態(tài)分析方法與并行化算法??用圖的形式表達可達關(guān)系傳遞規(guī)則，則圖中的邊即為可達關(guān)系的體現(xiàn)。傳遞??閉包公式３－１分別對應圖３－１中可達關(guān)系的三種傳遞方式，其中ｘ?＝?ｙ上ｚ即為一??組邊對。??匚?ｃ／ｌ?＜Ａ?３??＾?ｃ??ａ）?ｅ?ｓ?ｂ）?Ｃ?ｃ／Ｚ?ｃ）?Ｃ?ｃ／Ｚ?乃??圖３－１可達關(guān)系傳遞規(guī)則的圖表現(xiàn)形式??邊對模型的提出，為數(shù)據(jù)并行化算法設(shè)計提供了有利條件：將邊對以中間節(jié)??點（節(jié)點ｙ即是邊對ｘ＾ｙ三ｚ的中間節(jié)點）為核心進行存儲，由于產(chǎn)生式的右部??不超過兩個符號，中間節(jié)點通過對入邊（ｉｎｃｏｍｉｎｇｅｄｇｅ）和出邊（ｏｕｔｇｏｉｎｇｅｄｇｅ）??的收集，可以獨立完成可達關(guān)系的傳遞，不必依賴別的節(jié)點的計算結(jié)果，因此可??以并行化執(zhí)行每個中間節(jié)點的標簽匹配任務(wù)，即多個中間節(jié)點同時對自己的“左??鄰右舍”進行符合產(chǎn)生式的可達關(guān)系傳遞。??３．１．２?串行?Ｗｏｒｋｌｉｓｔ?算法??從３．１．１節(jié)可達關(guān)系的傳遞方式可以看出，傳遞閉包是動態(tài)更新的，每次向??傳遞閉包中添加可達關(guān)系，都有可能觸發(fā)新的可達關(guān)系的生成，這是一個迭代更??新的過程。??Ｗｏｒｋｌｉｓｔ算法是一種基于搜索的可達性計算的算法［２２］［３６］。它的主要工作流??程如下：使用ｗｏｒｋｌｉｓｔ存儲計算中的頂點和以它為終點的路徑信息
頂點和目標頂點進行分區(qū)，即通過對邊的復制，解除中間節(jié)點的邊集共享問題。??這樣做可以使邊同時完成雙向的路徑傳遞，實現(xiàn)標簽匹配操作的并行化。復制操??作如圖３－２所示：??ＡＢＣ??？?，?＾??ｘ?ｙ?ｚ?ｗ??復制ｙ－＞ｚ??ａ?Ｂ?２?￣?ｅ?▲??？?＾＾??Ｘ?ｙ?ｚ?ｙ?Ｚ?Ｗ??圖３－２通過復制解除中間節(jié)點的依賴關(guān)系??具有相同源或目標頂點（鍵）的邊被放在與圖３－４框中矩形相對應的相同分??區(qū)中。分區(qū)內(nèi)部計算是并行執(zhí)行的，提高了并行效率和資源利用率。??ｊｏｉｎ和ｆｉｌｔｅｒ操作的并行化基于上述分區(qū)完成。??３．２．２數(shù)據(jù)結(jié)構(gòu)設(shè)計??分區(qū)中邊集（包括待計算邊集ＩＶ和原傳遞閉包ＴＣ的邊）被處理為以頂點為??鍵，與頂點相連的邊集為值的ｋｅｙ－ｖａｌｕｅ形式，這是離線系統(tǒng)實現(xiàn)中的基本數(shù)據(jù)??結(jié)構(gòu)。需要注意的是，為了算法能及時收斂和避免冗余計算，每個鍵值對中，只??１９??
本文編號：2960022
【文章來源】：南京大學江蘇省 211工程院校 985工程院校 教育部直屬院校
【文章頁數(shù)】：87 頁
【學位級別】：碩士
【部分圖文】：
圖２－３?Ｓｐａｒｋ生態(tài)系統(tǒng)組件??
第三章離線全量程序靜態(tài)分析方法與并行化算法??用圖的形式表達可達關(guān)系傳遞規(guī)則，則圖中的邊即為可達關(guān)系的體現(xiàn)。傳遞??閉包公式３－１分別對應圖３－１中可達關(guān)系的三種傳遞方式，其中ｘ?＝?ｙ上ｚ即為一??組邊對。??匚?ｃ／ｌ?＜Ａ?３??＾?ｃ??ａ）?ｅ?ｓ?ｂ）?Ｃ?ｃ／Ｚ?ｃ）?Ｃ?ｃ／Ｚ?乃??圖３－１可達關(guān)系傳遞規(guī)則的圖表現(xiàn)形式??邊對模型的提出，為數(shù)據(jù)并行化算法設(shè)計提供了有利條件：將邊對以中間節(jié)??點（節(jié)點ｙ即是邊對ｘ＾ｙ三ｚ的中間節(jié)點）為核心進行存儲，由于產(chǎn)生式的右部??不超過兩個符號，中間節(jié)點通過對入邊（ｉｎｃｏｍｉｎｇｅｄｇｅ）和出邊（ｏｕｔｇｏｉｎｇｅｄｇｅ）??的收集，可以獨立完成可達關(guān)系的傳遞，不必依賴別的節(jié)點的計算結(jié)果，因此可??以并行化執(zhí)行每個中間節(jié)點的標簽匹配任務(wù)，即多個中間節(jié)點同時對自己的“左??鄰右舍”進行符合產(chǎn)生式的可達關(guān)系傳遞。??３．１．２?串行?Ｗｏｒｋｌｉｓｔ?算法??從３．１．１節(jié)可達關(guān)系的傳遞方式可以看出，傳遞閉包是動態(tài)更新的，每次向??傳遞閉包中添加可達關(guān)系，都有可能觸發(fā)新的可達關(guān)系的生成，這是一個迭代更??新的過程。??Ｗｏｒｋｌｉｓｔ算法是一種基于搜索的可達性計算的算法［２２］［３６］。它的主要工作流??程如下：使用ｗｏｒｋｌｉｓｔ存儲計算中的頂點和以它為終點的路徑信息
頂點和目標頂點進行分區(qū)，即通過對邊的復制，解除中間節(jié)點的邊集共享問題。??這樣做可以使邊同時完成雙向的路徑傳遞，實現(xiàn)標簽匹配操作的并行化。復制操??作如圖３－２所示：??ＡＢＣ??？?，?＾??ｘ?ｙ?ｚ?ｗ??復制ｙ－＞ｚ??ａ?Ｂ?２?￣?ｅ?▲??？?＾＾??Ｘ?ｙ?ｚ?ｙ?Ｚ?Ｗ??圖３－２通過復制解除中間節(jié)點的依賴關(guān)系??具有相同源或目標頂點（鍵）的邊被放在與圖３－４框中矩形相對應的相同分??區(qū)中。分區(qū)內(nèi)部計算是并行執(zhí)行的，提高了并行效率和資源利用率。??ｊｏｉｎ和ｆｉｌｔｅｒ操作的并行化基于上述分區(qū)完成。??３．２．２數(shù)據(jù)結(jié)構(gòu)設(shè)計??分區(qū)中邊集（包括待計算邊集ＩＶ和原傳遞閉包ＴＣ的邊）被處理為以頂點為??鍵，與頂點相連的邊集為值的ｋｅｙ－ｖａｌｕｅ形式，這是離線系統(tǒng)實現(xiàn)中的基本數(shù)據(jù)??結(jié)構(gòu)。需要注意的是，為了算法能及時收斂和避免冗余計算，每個鍵值對中，只??１９??
本文編號：2960022
本文鏈接：http://sikaile.net/kejilunwen/ruanjiangongchenglunwen/2960022.html
最近更新
教材專著
