Program Dependence Theory of Concurrent Programs and Its Applications

1. 我们提出了两种新的并发程序表示，分别命名为非确定性并行控制流网络和非确定性并行定义使用网络，并展示了如何使用它们来表示用并发编程语言（如Ada、Occam2和SR.2）编写的并发程序中的多个控制流和多个数据流。除了通常提出并研究的顺序程序的控制和数据依赖关系外，我们还在并发程序中引入了三种新的主要程序依赖关系，即选择依赖关系、同步依赖关系和通信依赖关系，并为并发程序提出了两种新的程序表示形式，即进程依赖网和进程影响网。它们是弧分类的有向图，以显式地表示程序中主要程序依赖的五种类型。我们还展示了这些表示的一些应用，包括并发程序理解、优化、测试、调试、维护和复杂性度量。我们开发了一组工具，将并发程序转换为它们的非确定性并行控制流网络、非确定性并行定义使用网络、进程依赖网络和程序影响网络。我们将最初为顺序程序提出和研究的切片概念扩展到并发程序，并采用图论方法对并发程序进行切片。我们为并发程序提出了一些新的复杂性指标，并对其中的一部分进行了评估。

1. We proposed two new representations for concurrent programs, named the nondeterministic parallel control-flow net and nondeterministic parallel definition-use net, and showed how to use them to represent multiple control flows and multiple data flows in concurrent programs written in concurrent programing languages such as Ada, Occam2, and SR.2. In addition to the usual control and data dependencies proposed and studied for sequential programs, we introduced three new types of primary program dependencies in concurrent programs, named the selection dependence, synchronization dependence, and communication dependence and proposed two new program representations for concurrent programs, named the process dependence net and the process influence net, which are arc-classified digraphs to explicitly represent the five types of primary program dependencies in the programs. We also showed some applications of the representations including concurrent program understanding, optimization, testing, debugging, maintenance, and complexity measurement.3. We developed a group of tools to transform concurrent programs into their nondeterministic parallel control-flow nets, nondeterministic parallel definition-use nets, process dependence nets, and program influence nets.4. We extended the notion of slicing, which was originally proposed and studied for sequential programs, to concurrent programs and a graph-theoretical approach to slicing concurrent programs.5. We proposed a number of new complexity metrics for concurrent programs and evaluated a part of them.