程序靜態(tài)分析技術(shù)被廣泛應(yīng)用于計(jì)算機(jī)程序設(shè)計(jì)與開發(fā)的諸多環(huán)節(jié),包括錯(cuò)誤檢測、代碼優(yōu)化、測試等�；贑FL（Context-Free Language）可達(dá)的過程間程序靜態(tài)分析是一種具有較高通用意義的過程間靜態(tài)分析方法,該方法本質(zhì)上是一種圖的可達(dá)性計(jì)算問題。盡管程序靜態(tài)分析方面的研究取得了很多進(jìn)展,但是由于硬件資源和傳統(tǒng)方法的限制,單機(jī)計(jì)算已難以支撐日益增長大規(guī)模圖數(shù)據(jù)的高效處理,從而導(dǎo)致了靜態(tài)分析方法的性能低效且可擴(kuò)展性較低。因此對(duì)大規(guī)�，F(xiàn)代軟件進(jìn)行復(fù)雜的過程間分析仍然具有挑戰(zhàn)性。針對(duì)大規(guī)模程序靜態(tài)分析性能低效和可擴(kuò)展性低的問題,本文提出了一種基于分布式圖計(jì)算模型的高效可擴(kuò)展的并行化大規(guī)模程序靜態(tài)分析方法,并設(shè)計(jì)實(shí)現(xiàn)了高效可擴(kuò)展的分布式大規(guī)模程序靜態(tài)分析系統(tǒng)。本文的主要研究工作和貢獻(xiàn)點(diǎn)如下:（1）將基于CFL可達(dá)的程序靜態(tài)分析問題抽象為大規(guī)模圖計(jì)算問題,基于數(shù)據(jù)并行框架研究設(shè)計(jì)了一種新型的并行化傳遞閉包算法和Join-Process-Filter計(jì)算模型,基于該算法和計(jì)算模型,設(shè)計(jì)實(shí)現(xiàn)了一個(gè)分布式離線全量程序靜態(tài)分析系統(tǒng),分別提出了算法級(jí)和系統(tǒng)級(jí)優(yōu)化,并設(shè)計(jì)了具有壓縮效果的數(shù)據(jù)結(jié)構(gòu)。（2... 

【文章來源】：南京大學(xué)江蘇省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：87 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖２－３?Ｓｐａｒｋ生態(tài)系統(tǒng)組件??

第三章離線全量程序靜態(tài)分析方法與并行化算法??用圖的形式表達(dá)可達(dá)關(guān)系傳遞規(guī)則，則圖中的邊即為可達(dá)關(guān)系的體現(xiàn)。傳遞??閉包公式３－１分別對(duì)應(yīng)圖３－１中可達(dá)關(guān)系的三種傳遞方式，其中ｘ?＝?ｙ上ｚ即為一??組邊對(duì)。??匚?ｃ／ｌ?＜Ａ?３??＾?ｃ??ａ）?ｅ?ｓ?ｂ）?Ｃ?ｃ／Ｚ?ｃ）?Ｃ?ｃ／Ｚ?乃??圖３－１可達(dá)關(guān)系傳遞規(guī)則的圖表現(xiàn)形式??邊對(duì)模型的提出，為數(shù)據(jù)并行化算法設(shè)計(jì)提供了有利條件：將邊對(duì)以中間節(jié)??點(diǎn)（節(jié)點(diǎn)ｙ即是邊對(duì)ｘ＾ｙ三ｚ的中間節(jié)點(diǎn)）為核心進(jìn)行存儲(chǔ)，由于產(chǎn)生式的右部??不超過兩個(gè)符號(hào)，中間節(jié)點(diǎn)通過對(duì)入邊（ｉｎｃｏｍｉｎｇｅｄｇｅ）和出邊（ｏｕｔｇｏｉｎｇｅｄｇｅ）??的收集，可以獨(dú)立完成可達(dá)關(guān)系的傳遞，不必依賴別的節(jié)點(diǎn)的計(jì)算結(jié)果，因此可??以并行化執(zhí)行每個(gè)中間節(jié)點(diǎn)的標(biāo)簽匹配任務(wù)，即多個(gè)中間節(jié)點(diǎn)同時(shí)對(duì)自己的“左??鄰右舍”進(jìn)行符合產(chǎn)生式的可達(dá)關(guān)系傳遞。??３．１．２?串行?Ｗｏｒｋｌｉｓｔ?算法??從３．１．１節(jié)可達(dá)關(guān)系的傳遞方式可以看出，傳遞閉包是動(dòng)態(tài)更新的，每次向??傳遞閉包中添加可達(dá)關(guān)系，都有可能觸發(fā)新的可達(dá)關(guān)系的生成，這是一個(gè)迭代更??新的過程。??Ｗｏｒｋｌｉｓｔ算法是一種基于搜索的可達(dá)性計(jì)算的算法［２２］［３６］。它的主要工作流??程如下：使用ｗｏｒｋｌｉｓｔ存儲(chǔ)計(jì)算中的頂點(diǎn)和以它為終點(diǎn)的路徑信息

頂點(diǎn)和目標(biāo)頂點(diǎn)進(jìn)行分區(qū)，即通過對(duì)邊的復(fù)制，解除中間節(jié)點(diǎn)的邊集共享問題。??這樣做可以使邊同時(shí)完成雙向的路徑傳遞，實(shí)現(xiàn)標(biāo)簽匹配操作的并行化。復(fù)制操??作如圖３－２所示：??ＡＢＣ??？?，?＾??ｘ?ｙ?ｚ?ｗ??復(fù)制ｙ－＞ｚ??ａ?Ｂ?２?￣?ｅ?▲??？?＾＾??Ｘ?ｙ?ｚ?ｙ?Ｚ?Ｗ??圖３－２通過復(fù)制解除中間節(jié)點(diǎn)的依賴關(guān)系??具有相同源或目標(biāo)頂點(diǎn)（鍵）的邊被放在與圖３－４框中矩形相對(duì)應(yīng)的相同分??區(qū)中。分區(qū)內(nèi)部計(jì)算是并行執(zhí)行的，提高了并行效率和資源利用率。??ｊｏｉｎ和ｆｉｌｔｅｒ操作的并行化基于上述分區(qū)完成。??３．２．２數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)??分區(qū)中邊集（包括待計(jì)算邊集ＩＶ和原傳遞閉包ＴＣ的邊）被處理為以頂點(diǎn)為??鍵，與頂點(diǎn)相連的邊集為值的ｋｅｙ－ｖａｌｕｅ形式，這是離線系統(tǒng)實(shí)現(xiàn)中的基本數(shù)據(jù)??結(jié)構(gòu)。需要注意的是，為了算法能及時(shí)收斂和避免冗余計(jì)算，每個(gè)鍵值對(duì)中，只??１９??


本文編號(hào)：2960022