Program Dependence Theory of Concurrent Programs and Its Applications

1.我们提出了两个新的并发程序表示，命名为非确定性并行控制流网和非确定性并行定义使用网，并展示了如何使用它们来表示并发程序中的多个控制流和多个数据流，并发编程语言，如Ada，Occam 2，和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.