Hybrid Parallel Execution Model for Logic-Based Specification Languages

The following sections are included:

• Contents

• List of Tables

• List of Figures

Software maintenance is a crucial phase for the longevity of any application. However, undiscovered errors in a requirements specification will result in maintenance costs exceeding ten times the original [95, 96]. Errors in the requirement phase can be reduced through validation and verification of the requirements specification. Many logic-based requirements specification languages have been developed to achieve these goals [9, 27, 37, 38, 47, 53, 54, 55, 56, 57, 58, 59, 67, 73, 77, 80, 82, 90, 91, 94]. Through the execution of the logic-based requirements specification, customers and developers can validate their disagreement or misunderstanding in the requirement phase. By reasoning over the logic-based requirements specification, developers can verify desired properties such as consistency, liveness and so on. Developers can also verify whether or not non-functional requirements specification describing the executional behavior of the specification have been satisfied. However, the execution and reasoning of logic-based requirements specification is very slow. An effective way to improve their performance is to execute and reason the logic-based requirements specification in parallel. In order to reach this goal, this book presents a hybrid parallel execution model for Horn-clause logic-based requirements specification languages such as FRORL [93]. This model is built on a static data dependency and mode analysis mechanism . Another application of the data dependency and mode analysis, a transformation system which transforms a logic-based specification into a procedural language program, is also discussed…

The following sections are included:

• Data Dependency Analysis

• OR-Parallelism

• AND-Parallelism

• Backtracking

The following sections are included:

• Non-monotonic Inheritance Expansion

• Static Data Dependency Analysis

• Automatic Transformation

• Hybrid AND-OR Parallel Execution

• Simplified OR-Parallel Model

• Backtracking Elimination

The following sections are included:

• Knowledge Representation through Object-Oriented Model

• The Modeling Primitives of FRORL
  • Object Frame
  • Activity Frame
  • Reserved Words

• Decomposition of a FRORL Requirements Specification
  • FRORL and its Non-monotonic Inheritance Mechanism
  • Transformation of FRORL into Horn-clause Logic-based Specification
  • Algorithms for Non-Monotonic Inheritance Handling

The following sections are included:

• Rewriting of a Logic-Based Specification
  • Equal-Introduction
  • Equal-Substitution
  • Decomposition
  • Simplification

• Data Dependency and Control Flow Analysis
  • Matrix Representation of Mode Information
  • Data Flow and Dependency Analysis Algorithm

The following sections are included:

• The Usage of Mode Information in the Parallel Model

• AND-OR Parallel Execution

• Synchronization in OR-Parallel Execution Model

• Calculation of the Currently Executable Predicate Set

• Hybrid Execution Algorithm

• Comparison with the Conventional BFS and DFS

• Advantages of the New Approach

• Analysis of Non-functional Requirements in the New Parallel Execution Model

The following sections are included:

• Execution Evaluation

• Communication Evaluation

• Criteria for Simulation and Evaluation

• A Simulator for Parallel Logic-based Specification Evaluation

• Experimental Results and Comparison
  • Simulation for Various Values of Error_Rate
  • Simulation for Values of Deep_Jumping_Distance
  • Simulation for Values of Deep_Jumping_Rate
  • Simulation for Values of Variable_Related_Rate
  • Simulation for Values of Nondeterminism_Rate

The following sections are included:

• Architecture of a Logic-based Specification Transformation System

• Determination of Control Sequence

• Data Type Generation and Procedural Function Formation
  • Rules-based Data Type Inference
  • Data Type Propagation Analysis and Generation
  • Data Type Analysis in a FRORL Specification
  • Procedural Program Generation

• Intelligent Backtracking for Transformation System

The following sections are included:

• Functional Requirements vs. Non-functional Requirements

• Issues in Non-functional Requirements

• Non-functional Requirements Modeling in FRORL

• Adjusting Non-functional Requirements

The following sections are included:

• References

• Index