并发程序切片方法综述

随着实际应用对并发软件需求的不断增加,并发程序的应用越来越广,程序切片的研究不再仅仅局限于顺序程序,并发程序切片的研究也越来越多.但是由于并发程序执行的不确定性,并发程序切片的研究还有许多问题有待解决.文中介绍了当前主要的几种并发程序切片方法及其主要特性,并对这些切片方法进行了比较分析,结果表明并发程序切片的效率和精度都达到理想的目标是不可能的,只能是在两者之间的均衡,最后简要介绍了并发程序切片的应用.     

改进的基于逆向流分析的C程序切片算法

为解决切片算法时空开销太大的问题, 提出一种改进的基于逆向流的静态切片算法。只需通过分析控制依赖, 获得程序整体框架, 再从切片点开始基于逆向控制流从里向外扩张式扫描,在扫描中不断获得只与切片相关的数据依赖, 以此得到程序切片。该算法减少了计算控制流的工作量, 避免计算谓词依赖集的过程, 减少了存储资源开销, 提高了切片的效率。     

基于多线程归并排序算法设计

为解决传统递归方式的归并排序算法串行执行效率低的问题, 使用数据依赖关系分析方法对归并排序算法进行并行性分析。通过分析发现算法本身具有并行的特征, 在多核处理器下使用OpenMp编译制导语句对算法进行直接并行化处理。在数据量较大的情况下, 为了使算法执行的速度更快, 在多核处理器系统中设置多个线程, 并将序列分成多个组, 每个线程操作一组数据, 最后对多个局部有序的结果进行逐一合并。实验验证结果表明, 该并行化算法可使执行速度提高50%以上。     

基于控制流的多线程程序的静态切片算法

介绍一种基于控制流的多线程程序的静态切片算法, 该算法的主要思想是在构造多线程程序依赖图的同时保留程序的控制流信息, 利用这些信息能 够判断出程序中的多线程可实现路径, 从而提高多线程程序静态切片的精度和效率. 最后给出一个多线程切片的实例.     

Java语言中的线程同步互斥研究

在介绍操作系统中引入多线程的原因后,介绍了Java语言中的多线程机制和编程实现方案,介绍了线程同步互斥机制,并用经典操作系统进程同步互斥算法实现程序,演示如何编写Java并发程序。     

并发程序模型的可信性研究

讨论基于交替计算模式的并发程序执行行为的可信性问题。通过比较共享变量程序的交替计算与实际重叠执行，对并发程序的执行过程进行粒度分析－首先提出了种粒度细化、求精方法，限制单个原子转换包含的临界事件数目；继而引入一种限制临界引用（ＬＣＲ）条件，进上步限制每一与语名相关的转换至多执行一次临界引用；对任一程序，通过转换算法将其转化为与之等价的ＬＣＲ程序，且ＬＣＲ程序的交替计算结果与实际的重叠执行结果一致的     

应用XSL验证XML的函数依赖

为了增加语义,把关系数据库理论中的函数依赖概念引入到XML约束中.由于XML的层次结构,XML函数依赖的描述与验证比关系模型要复杂得多.就两种函数依赖类型给出了一个基于XML样式单语言(XSL)的验证算法.对于XML文档实例,应用该算法实现的XSLT程序,可以直接由Web浏览器打开,并显示出是否满足给定的函数依赖的验证结果.     

应用XSL验证XML的函数依赖

为了增加语义,把关系数据库理论中的函数依赖概念引入到XML约束中.由于XML的层次结构,XML函数依赖的描述与验证比关系模型要复杂得多.就两种函数依赖类型给出了一个基于XML样式单语言(XSL)的验证算法.对于XML文档实例,应用该算法实现的XSLT程序,可以直接由Web浏览器打开,并显示出是否满足给定的函数依赖的验证结果.     

一种基于函数依赖图的构件抽取方法

结合程序切片技术,文中提出了一种基于函数依赖图的构件抽取方法.先讨论函数依赖图中的几种依赖关系及其表示方法,再对由源码分析所得的函数依赖图进行切片操作得到依赖子图,并结合源码生成最终切片代码,即为构件抽取的结果.此基础上,提出一种基于函数依赖图的内聚度和耦合度的计算方法,以便从软件度量的角度来评价切片代码(构件)的质量.实验表明利用文中的构件抽取方法生成的切片代码较精简,且具有较高的运行效率.     

一种应用代价评估的推测多线程路径预测方法

推测多线程技术对于自动并行化非规则程序是有效的,然而基于控制流图和分支预测方法的线程划分方法,不可避免地受到划分路径上存在的控制依赖和数据依赖制约.针对现有的路径预测方法在考虑控制依赖影响的同时却不能有效地综合考虑数据依赖影响的问题,提出一种新的基于代价评估的路径预测方法,通过引入数据依赖模型,综合评估控制和数据依赖两种影响因素,寻求一条具有近似最小推测开销的推测划分路径.实验结果表明,文中提出的路径预测方法能够计算出代价更小的推测划分路径,并取得了更好的加速比性能,总体上系统可以得到2.43%的加速比性能提升.     

Slicing Java generic programs using generic system dependence graph

The existing slicing algorithms do not consider parameterized types in generic programs, so they are not suitable for generic programs. To solve this problem, this paper presents a generic system dependence graph for Java generic programs based on the traditional system dependence graph to express dependences for parameterized type information. A novel slicing criterion and slicing algorithm for generic programs is proposed. The slices computed by the algorithm can help to understand relations between concepts and types for generic programs and can express the features of generic programs better. Biography: CHEN Lin (1979–), male, Ph.D. candidate, research direction: program analysis and refactoring.     

Dependence analysis based on dynamic slicing for debugging

Dynamic program slicing is an effective technique for narrowing the errors to the relevant parts of a program when debugging. Given a slicing criterion, the dynamic slice contains only those statements that actually affect the variables in the slicing criterion. This paper proposes a dynamic slicing method based on static dependence analysis. It uses the program dependence graph and other static information to reduce the information needed to be traced during program execution. Thus, the efficiency is dramatically improved while the precision is not depressed. The slicing criterion is modified to fit for debugging. It consists of filename and the line number at which the statement is.     

基于抽象实现结构图的数据流方程切片方法

提出在PASCAL抽象实现结构图上,采用数据流方程算法实现程序切片的自动化.该方法将过程蓝图的抽象实现结构图引入静态过程内切片领域,实现了程序表示形式与程序切片处理形式的统一,避免了传统方法产生控制流图的需要,简化了切片处理过程,提高了切片处理效率,并直观地反映了切片后的程序变化.     

Dynamic slicing of object-oriented programs

Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in programP that may effect the value of variablev at some pointp, and a dynamic slice consists only of statements that influence the value of variable occurrence for specific program inputs. In this paper, we concern the problem of dynamic slicing of object-oriented programs which, to our knowledge, has not been addressed in the literatures. To solve this problem, we present the dynamic object-oriented dependence graph (DODG) which is an arc-classified digraph to explicitly represent various dynamic dependence between statement instances for a particular execution of an object-oriented program. Based on the DODG, we present a two-phase backward algorithm for computing a dynamic slice of an object-oriented program.     

顺序程序任务并行性的识别

探讨了任务并行性识别中任务执行条件的导出，利用任务给点间的相关性（包括数据相关和控制相关）就可求出并行执行条件．提出了层次任务图模型下直接生成优化任务执行条件的算法，省去了后控树及控制相关图（ＣＤＧ）的产生，其过程简单且比较高效．     

过程间的程序分片技术

程序分片在程序理解、调试、维护、测试和集成等许多领域都有广泛的应用.过程间的程序分片是分片技术的难点之一.在总结了现有的过程间分片技术基础之上,重点介绍了具有代表性的图形可达性算法.