An environment for imprecise computations
Jane W. Liu, David L. Hull · 2000
The imprecise computation technique is a way to enhance the robustness and scheduling flexibility of a real-time system. It is based on the observation that in a hard real-time system, it is often better for a task to produce an approximate result by the task's deadline than to produce an exact result late. We call a task that can trade execution time and other resources for result quality in this way a flexible task. An flexible application is made up of flexible tasks. The results of the flexible tasks in a flexible application depend on each other: when the input quality of a task goes down, the task's output quality goes down as well unless the task spends extra time or resources to maintain its output quality. Conversely, when a task's input quality goes up, it can conserve time and resources and still maintain its output quality. This thesis is concerned with the problem of providing operating system support to flexible real-time applications with end-to-end deadlines and of integrating checkpointing and rollback recovery with flexible applications as a means to increase the availability and dependability of real-time systems. This thesis makes the following contributions: (1) It describes a model for representing flexible real-time applications as a composition of components tasks, and characterizes how quality of service of a task depends on both the task's input quality and resource usage. (2) It introduces an architecture, called the Imprecise Computation Environment, for executing flexible applications based on this flexible application model. (3) It describes an efficient algorithm for quality of service management in flexible applications. This algorithm allocates the processor time available for an application to each task in the application to maximize the output quality of the application as a whole.