Exploiting Approximations in Real-Time Scheduling

In real-time systems, to provide timing guarantees, pessimistic worst-case bounds are traditionally assumed for computation and communication tasks. In practice, tighter bounds can be established by allowing computation or communication to be dropped or to execute in an approximate or imprecise manner. This creates a fundamental tradeoff between tightness of bounds and degradations in application quality. In this chapter, we present scheduling of computation and communication tasks as a quality optimization problem in terms of computation and communication budget assignments for systems with independent and dependent tasks. For independent tasks, traditional mixed-criticality (MC) systems can be extended to derive the precision of low-criticality tasks such that combined quality degradation is minimized while satisfying schedule admissibility. For dependent tasks, we describe approaches to find an optimized mapping, scheduling, and budgeting of task graphs that maximizes overall quality while meeting end-to-end real-time constraints. We evaluate our proposed approaches on both artificial and real-world task sets and compare them to traditional solutions that do not allow for approximations.