Program Dependence Theory of Concurrent Programs and Its Applications

点击翻译按钮获取中文摘要

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.