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

An Improved Program Dependence Graph for Static Slicing Concurrent Programs

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

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

出　　处：《微电子学与计算机》2006年第1期6-10,共5页Microelectronics & Computer

基　　金：国家"863"网络安全管理与测评技术(863-301-05-03)

摘　　要：分析了KRINKE切片算法,发现当对程序循环体内嵌套有一个或多个线程的结构时会产生切片不精确的现象,原因是KRINKE算法的数据结构所定义的线程间数据依赖关系过于粗糙,相应的切片算法对程序执行路径的合法性约束不够严格。提出一种改进的并发程序依赖图,引入跨线程边界循环-承载数据依赖关系。给出了添加跨线程边界循环-承载数据依赖关系的算法。实例分析表明,作用在新的并发程序依赖图上的切片算法克服了KRINKE算法的切片不精确现象。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 depen- dence relation of loop-carried data dependence crossing thread boundaries. The algorithm adding loop-carried data de- pendence 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.

关 键 词：静态程序切片.并发程序 程序依赖图 循环-承载数据依赖 

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