ABSTRACT
Meeting deadline constraints is of paramount importance in real-time systems. Sometimes, it is not possible to schedule all the tasks to meet their deadlines, a situation that occurs quite often when the system is overloaded. In situations like this, it is often more desirable to complete some portions of every task rather than giving up completely the processing of some tasks. The Imprecise Computation Model was introduced [1-3] to allow for the trade-off of the quality of computations in favor of meeting the deadline constraints. In this model, a task is logically decomposed into two subtasks, mandatory and optional. The mandatory subtask of each task is required to be completed by its deadline, while the optional subtask can be left unfinished. If a task has an unfinished optional subtask, it incurs an error equal to the execution time of its unfinished portion. The Imprecise Computation Model is designed to model an iterative algorithm, where the task initially spends some time for initialization (the mandatory subtask) and then iterates to improve the quality of the solution (the optional subtask). Since the optional subtask corresponds to iterations to improve the quality of the solution, it can be left unfinished and still obtain a solution with a somewhat inferior quality. In this way, we can trade off the quality of the computation in favor of meeting the deadline constraints.
