并發程序內部表示及靜態切片算法的改進

肖健宇　張德運　鄭衛斌

摘要：通過分析Krinke切片算法對程序循環體內嵌套一個或多個線程結構會產生切片不精確現象，得出Krinke算法所基于的程序依賴圖對線程間數據的依賴關系定義得過于粗糙，且對并發程序執行行為的合法性約束不夠嚴格的結果．據此，提出一種新的并發程序依賴圖，引入跨線程邊界循環—承載數據依賴關系，并在此數據結構上改進了切片算法；引入區域化執行證據概念，進一步約束程序執行行為的合法性，并給出了添加跨線程邊界循環—承載數據依賴關系的算法及新的并發程序切片算法的偽代碼．實例分析與算法性能測試表明，改進的切片算法克服了Krinke算法的不精確現象，降低了時間開銷，改善了算法的可伸縮性。

關鍵詞：并發程序；程序依賴圖；循環—承載數據依賴；區域化執行證據

中圖分類號：TP311．1文獻標識碼：A文章編號：0253—987X(2005)12—1295—04