Real-Time Control Structures for Block Diagram Schemata.
Abstract
Block diagram schemata model computation systems in the context of an external environment. The environment imposes various constraints on the real-time performance of any implementation of a block diagram schemata. The model is used to provide precise definitions of real-time performance. The portion of the implementation that affects the real-time performance is called the control structure. This research investigates several strategies for synthesizing control structures to satisfy the external real-time specifications. The simplest strategy is to execute all the blocks in the diagram in some fixed order. Control structures of this type have been somewhat ignored for time critical applications. The synthesis problem is shown to be solvable in the sense that acyclic control structures do not need to be considered. A branch-and-bound synthesis algorithm is presented which requires exponential time in the worst case. Although no efficient synthesis algorithm was found, the conjecture that the problem is NP-complete is not proved.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1978
- Accession Number
- ADA061122
Entities
People
- Thomas Joseph Teixeira
Organizations
- Massachusetts Institute of Technology