一种改进的用于并发程序静态切片的程序依赖图

分析了Krinke切片算法，发现当对程序循环体内嵌套有一个或多个线程的结构时会产生切片不精确的现象．原因是Krinke算法的数据结构所定义的线程间数据依赖关系过于粗糙，相应的切片算法对程序执行路径的合法性约束不够严格。提出一种改进的并发程序依赖图，引入跨线程边界循环一承载数据依赖关系。给出了添加跨线程边界循环一承载数据依赖关系的算法。实例分析表明，作用在新的并发程序依赖图上的切片算法克服了Krinke算法的切片不精确现象。

An Improved Program Dependence Graph for Static Slicing Concurrent Programs

Data structure for static slicing algorithm of concurrent programs was studied. Based on the analysis of the fact that Krinke's slicing algorithm produced imprecise slice for the program structure which has loops embedded with threads, a conclusion was drawn that the reason for the impreciseness was that Krinke's data structure had over coarse definitions of data dependence relations between threads, and the associated algorithm had an unduly loose constraint on the execution paths. An improved threaded program dependence graph was proposed which introduced a new dependence relation of loop-carried data dependence crossing thread boundaries. The algorithm adding loop-carried data dependence relations crossing thread boundaries was given. Examples showed that the slicing algorithm based on the new data structure could restrain the impreciseness of Krinke's.