Scheduling parallel real-time tasks that allow imprecise results

Abstract

Imprecise computation and parallel processing are two techniques for avoiding timing faults and tolerating hardware faults in hard real-time systems. When a result of the desired quality cannot be produced in time, hard real-time systems can produce an intermediate result of acceptable quality by imprecise computation, reduce the response time of the result by parallel processing, or both, to avoid timing faults. To mask hardware faults, a real-time task is replicated into several copies which are executed on distinct processing elements. The imprecise computation technique provides hard real-time systems with flexible functionality by trading off the quality of the result produced by a task with the amount of the computational resources required to produce it and thus enables the systems to reduce their computational loads in case of hardware faults. These two techniques permit the performance of hard real-time systems to remain predictable and to degrade gracefully.

This thesis describes efficient algorithms for scheduling two different task models on multiprocessors. Both task models support the imprecise computation technique whereby each task is logically decomposed into a hard task and a soft task. The hard task must be completed before the deadline to produce an acceptable result. The soft task refines the result produced by the hard task until the deadline. In the parallelizable task model, each task may be decomposed into concurrent subtasks which are processed simultaneously by multiple processing elements. The overhead associated with concurrent processing is assumed to be a linear function of the degree of parallelism. The scheduling algorithm for this model is optimal, if the multiprocessing overhead is indeed a linear function of the degree of parallelism. In the replicated task model, the replicas of a task must be assigned to distinct processing elements. The performance of the scheduling algorithms for this model is evaluated by stochastic analysis and computer simulations.