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

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

Improvement of Static Slicing Algorithm and Internal Representation of Concurrent Program

Based on the analysis that Krinke's slicing algorithm produced imprecise result for the program cycle body embedded with one or more threads,from which a conclusion was drawn that the reason for the imprecision was that the dependence relation of the relied graph to thread data was defined too coarsely and the constraint of the validity of execution behavior in concurrent program was unduly loose.Upon which,a novel relied graph of concurrent program was proposed,a dependence relation of loop-carried data across thread boundaries was introduced and an improved slicing algorithm was also proposed,in which a new concept of regional execution evidence was introduced to further constrain the validity of execution behavior in concurrent program.The algorithm added the dependence relations of loop-carried data across thread boundaries and the pseudo codes of slicing algorithm of concurrent program were given.Algorithm performance test and instances analysis show that the improved slicing algorithm can overcome the Krinke's imprecision,decreases overhead time and ameliorates scalability.