一种改进的并发程序静态切片算法  

An Improved Algorithm for Static Slicing of Concurrent Programs

作　　者：肖健宇[1] 张德运[1] 陈海诠[1] 董皓[1] 

机构地区：[1]西安交通大学电子与信息工程学院

出　　处：《计算机工程》2006年第14期14-16,45,共4页Computer Engineering

基　　金：国家"863"计划基金(8633010503)

摘　　要：分析了Krinke切片算法对循环体内嵌套有线程的程序结构会产生切片不精确的现象,认为其原因是该算法对线程间数据依赖的定义过于粗糙,且对程序行为约束不够。该文提出一种新算法,在并发程序内部表示中,增加跨线程边界循环-承载数据依赖,并引入区域化执行证据约束程序行为。实例研究表明,该算法克服了Krinke算法的不精确现象。This paper proposes a algorithm for static slicing of concurrent programs. Based on the analysis of the fact that Krinke＇s slicing algorithm produces imprecise program slice for the program structure which has loops embedded with one or more threads, a conclusion is drawn that the reason for the impreciseness is that Krinke＇s data structure which threads program dependence graph and has over coarse definitions of data dependence relations between threads, The constraint puts on the execution path in concurrent program is too loose. An improved algorithm is proposed which added a new kind of data dependence relation between threads-loop carries data dependence crossing thread boundaries and introduces a new concept of regioned execution witness to further constrain the execution path. Examples show that the improved slicing algorithm could restrain the impreciseness of Krinke＇s.

关 键 词：静态程序切片 并发程序 切片算法 程序依赖图 执行证据 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]