肖健宇 張德運(yùn) 鄭衛(wèi)斌
摘要:通過分析Krinke切片算法對(duì)程序循環(huán)體內(nèi)嵌套一個(gè)或多個(gè)線程結(jié)構(gòu)會(huì)產(chǎn)生切片不精確現(xiàn)象,得出Krinke算法所基于的程序依賴圖對(duì)線程間數(shù)據(jù)的依賴關(guān)系定義得過于粗糙,且對(duì)并發(fā)程序執(zhí)行行為的合法性約束不夠嚴(yán)格的結(jié)果.據(jù)此,提出一種新的并發(fā)程序依賴圖,引入跨線程邊界循環(huán)—承載數(shù)據(jù)依賴關(guān)系,并在此數(shù)據(jù)結(jié)構(gòu)上改進(jìn)了切片算法;引入?yún)^(qū)域化執(zhí)行證據(jù)概念,進(jìn)一步約束程序執(zhí)行行為的合法性,并給出了添加跨線程邊界循環(huán)—承載數(shù)據(jù)依賴關(guān)系的算法及新的并發(fā)程序切片算法的偽代碼.實(shí)例分析與算法性能測(cè)試表明,改進(jìn)的切片算法克服了Krinke算法的不精確現(xiàn)象,降低了時(shí)間開銷,改善了算法的可伸縮性。
關(guān)鍵詞:并發(fā)程序;程序依賴圖;循環(huán)—承載數(shù)據(jù)依賴;區(qū)域化執(zhí)行證據(jù)
中圖分類號(hào):TP311.1文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):0253—987X(2005)12—1295—04