Task Interdependencies in Design-to-Time Real-Time Scheduling

Abstract

Design-to-time is an approach to real-time scheduling in situations where multiple methods exist for many tasks that the system needs to solve. Often these methods will have relationships with one other, such as the execution of one method enabling the execution of another, or the use of a rough approximation by one method affecting the performance of a method that uses its result. Most previous work in the scheduling of real-time AI tasks has ignored these relationships. This paper presents an optimal design-to-time scheduler for particular kinds of relationships that occur in an actual AI application, and examines the performance of that scheduler in a simulation environment that models the tasks of that application. Introduction One of the major difficulties in the real-time scheduling of AI tasks is their lack of predictable durations. This difficulty occurs in non-AI systems, but it is especially prominent in AI problem-solving because of the inherent nondeterminism of most AI pr...