并发程序内部表示及静态切片算法的改进

肖健宇　张德运　郑卫斌

摘要：通过分析Krinke切片算法对程序循环体内嵌套一个或多个线程结构会产生切片不精确现象，得出Krinke算法所基于的程序依赖图对线程间数据的依赖关系定义得过于粗糙，且对并发程序执行行为的合法性约束不够严格的结果．据此，提出一种新的并发程序依赖图，引入跨线程边界循环—承载数据依赖关系，并在此数据结构上改进了切片算法；引入区域化执行证据概念，进一步约束程序执行行为的合法性，并给出了添加跨线程边界循环—承载数据依赖关系的算法及新的并发程序切片算法的伪代码．实例分析与算法性能测试表明，改进的切片算法克服了Krinke算法的不精确现象，降低了时间开销，改善了算法的可伸缩性。

关键词：并发程序；程序依赖图；循环—承载数据依赖；区域化执行证据

中图分类号：TP311．1文献标识码：A文章编号：0253—987X(2005)12—1295—04