An optimal static scheduling algorithm for hard real-time systems specified in prototyping language

Abstract

The Computer Aided Prototyping System ( CAPS ) and the Prototype System Description Language ( PSDL ) are tools that have been designed to aid in rapid prototyping. Within the framework of CAPS the Execution Support System (ESS) controls the execution of the prototype. The Static Scheduler is the component of the ESS which extracts and realizes critical timing constraints and precedence constraints for operators. The construction of a Static Scheduling Algorithm provides the foundation for handling hard real-time constraints during the execution of PSDL. The proposed work will be based on the theories of optimal sequencing through modular decomposition, as well as enumeration techniques. An optimal algorithm will provide the analyst with a definitive method for determining whether a given design can meet its hard real-time requirements.