Accession Number:

ADA061122

Title:

Real-Time Control Structures for Block Diagram Schemata.

Descriptive Note:

Master's thesis,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1978-08-01

Pagination or Media Count:

83.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE