“并行程序依存性分析及应用”之原始创新论文

程京德

这是本人 1992 年和 1993 年的几篇论文，开创了“并行程序依存性分析及应用”这一新研究方向，是笔者研究室在这一研究方向上所有工作的初始基础。现将这几篇论文存放于此，一方面留作保存记录，另一方面提供给听课学生和有兴趣者获取。

顺便把论文概要翻译为中文如下：

Ada-Europe 92 论文： 本文提出并发程序中两种新的基本程序依存关系，称为同步依存性和通信依存性，以及 Ada 并行程序的一种新程序表示，称为任务依存网(TDN)。 任务依存网可以被用作 Ada 并行程序设计环境中的统一表示。

J. Cheng, “Task Dependence Net as a Representation for Concurrent Ada Programs,” in J. van Katwijk (Ed.), “Ada: Moving towards 2000, 11th Ada-Europe International Conference, Zandvoort, The Netherlands, June 1-5, 1992, Proceedings,” Lecture Notes in Computer Science, Vol. 603, pp. 150-164, Springer, June 1992.

Abstract： “This paper proposes two new types of basic program dependence in concurrent program, named the synchronization dependence and the communication dependence, and a new program representation for concurrent Ada programs, named the Task Dependence Net (TDN). The task dependence net can be used as a unified representation in a concurrent Ada programming environment.”

PDF: AdaTDN_AE92LNCS603.pdf

Ada Letters 论文： 最近，作者提出了存在于并发程序中的两种新的基本程序依存关系，称为同步依存性和通信依存性，以及一个称为任务依存网(TDN)的 Ada 并行程序的新程序表达，将通常的顺序程序的程序依存图扩展到 Ada 并行程序。 本文讨论在 Ada 软件开发活动中的任务依存网的一些潜在应用，包括程序理解、测试、排错、维护和复杂性度量。

J. Cheng, “The Task Dependence Net in Ada Software Development,” ACM Ada Letters, Vol. 12, No. 4, pp. 24-35, ACM Press, July/August 1992.

Abstract： “Recently, the author proposed two new types of basic program dependences in concurrent programs, named the synchronization dependence and the communication dependence, and a new program representation for concurrent Ada programs, named the Task Dependence Net (TDN), which extends the usual program dependence graph for sequential programs to the case of concurrent Ada programs. This article discusses some potential applications of the task dependence net in Ada software development activities including program understanding, testing, debugging, maintenance, and complexity measure/metrics.”

PDF: AdaTDN_AdaLettersXII4.pdf

AADEBUG 93 论文： 本文将最初为顺序程序提出和研究的切片概念扩展到并行程序，并提出了一种基于图论的、切割并发程序的方法。除了针对顺序程序提出和研究的通常的控制依存性和数据依存性，本文还提出并行程序中存在的三种新的原始程序依存关系，称为选择依存性、同步依存性和通信依存性。本文还提出了并行程序的一种新的程序表达，称为过程依存网(PDN)，它是一种弧分类的有向图，用于明确表示程序中的五种原始程序依存关系。基于此程序表达，关于切割并行程序的各种概念可以形式地被定义，并且并行程序的切片问题可以简单地归结为其 PDN 表达中的顶点可达性问题。

J. Cheng, “Slicing Concurrent Programs - A Graph-Theoretical Approach,” in P. A. Fritzson (Ed.), “Automated and Algorithmic Debugging, 1st International Workshop, AADEBUG ’93, Linkoping, Sweden, May 3-5, 1993, Proceedings,” Lecture Notes in Computer Science, Vol. 749, pp. 223-240, Springer, November 1993.

Abstract： “This paper extends the notion of slicing, which was originally proposed and studied for sequential programs, to concurrent programs and presents a graph-theoretical approach to slicing concurrent programs.  In addition to the usual control and data dependences proposed and studied for sequential programs, the paper introduces three new types of primary program dependences in concurrent programs, named the selection dependence, synchronization dependence, and communication dependence.  The paper also propose a new program representation for concurrent programs, named the Process Dependence Net (PDN), which is an arc-classified digraph to explicitly represent the five types of primary program dependences in the programs.  As a result, various notions about slicing concurrent programs can be formally defined based on the representation, and the problem of slicing a concurrent program can be simply reduced to a vertex reachability problem in its PDN representation.”

PDF: Slicing_AADEBUG93LNCS749.pdf

ICPP 93 论文： 本文提出了一些基于各种原始程序依存性定义的新度量指标，用于测量分布式程序的复杂性。由于不同的程序依存性反映了程序的不同属性，所以这些度量指标可以被用于从不同的角度来测量分布式程序的各种复杂性。

J. Cheng, “Dependence-Based Complexity Metrics for Distributed Programs,” Proceedings of the 22nd International Conference on Parallel Processing, Vol. 2, pp. 265-268, St.Charles, USA, CRC Press, August 1993.

Abstract： “This paper proposes some new metrics, which are defined based on various primary program dependences, for measuring complexity of distributed programs. Since different program dependences reflect different attributes of programs, the metrics can be used to measure various complexity of a distributed program from various viewpoints.”

PDF: PDN_ICPP93.pdf

ParCo 93 论文： 本文提出两个新的图论程序表达，可用于表达并行程序以及顺序程序中的控制流或数据流。本文还展示了它们在软件工程中的一些可能应用。

J. Cheng, “Nondeterministic Parallel Control-Flow/Definition-Use Nets and Their Applications,” in G. R.Joubert, D. Trystram, F. J. Prters, and D. J. Evans (Eds.), “Parallel Computing: Trends and Applications, Proceedings of the International Conference, ParCo93, Grenoble, France, 7-10 September 1993,” pp. 589-592, Elsevier B.V., May 1994.

Abstract： “This paper presents two new graph-theoretical program representations which can be used to represent control flows and/or data flows in concurrent programs as well as sequential programs. The paper also shows some possible applications of the representations in software engineering.”

PDF: NPDUN_PARCO93.pdf

COMPSAC 93 论文： 除了为顺序和集中式程序提出和研究的通常的控制和数据依存性之外，本文提出并行和分布式程序中存在的三种原始程序依存关系，命名为选择依存性、同步依存性和通信依存性，以及并行和分布式程序的一种新的程序表达，称为过程依存网(PDN)，它是一种弧分类的有向图，用于明确地表达程序中的五种原始程序依存关系。本文还介绍了该表达的一些应用。

J. Cheng, “Process Dependence Net of Distributed Programs and Its Applications in Development of Distributed Systems,” Proceedings of the 17th Annual International Computer Software and Applications Conference, pp. 231-240, Phoenix, USA, IEEE Computer Society Press, November 1993.

Abstract： “In addition to the usual control and data dependences proposed and studied for sequential and centralized programs, this paper introduces three new types of primary program dependences in concurrent and distributed programs, named the selection dependence, synchronization dependence, and communication dependence, and a new program representation for concurrent and distributed programs, named the Process Dependence Net (PDN), which is an arc-classified digraph to explicitly represent the five types of primary program dependences in the programs. The paper alsos hows some applications of the representation.”

PDF: PDN_COMPSAC93.pdf

ISSRE 93 论文： 本文为分布式程序提出了一些新的复杂性度量指标。这些度量指标是根据分布式程序中的多重控制流、多重数据流和各种原始程序依存关系的图论表达来定义的。它们可以用于从各种不同的角度来度量分布式程序的复杂性。

J. Cheng, “Complexity Metricsfor Distributed Programs,” Proceedings of the 4th International Symposium on Software Reliability Engineering, pp. 132-141, Denver, USA, IEEE Computer SocietyPress, November 1993.

Abstract： “This paper proposes some new complexity metrics for distributed programs. The metrics are defined based on graph-theoretical representations for multiple control flows, multipledata flows, and various primary program dependences in distributed programs. They can be used to measure the complexity of a distributed program from various different viewpoints.”

PDF: PDN_ISSRE93.pdf