Hardware Reference
In-Depth Information
9.4.4
SERVICE ADAPTATION
A third method for coping with a permanent overload condition is to reduce the load
by decreasing the task computation times. This can be done only if the tasks have been
originally designed to trade performance with computational requirements. When
tasks use some incremental algorithm to produce approximated results, the precision
of results is related to the number of iterations, and thus with the computation time.
In this case, an overload condition can be handled by reducing the quality of results,
aborting the remaining computation if the quality of the current results is acceptable.
The concept of imprecise and approximate computation has emerged as a new ap-
proach to increasing flexibility in dynamic scheduling by trading computation accu-
racy with timing requirements. If processing time is not enough to produce high-
quality results within the deadlines, there could be enough time for producing ap-
proximate results with a lower quality. This concept has been formalized by many
authors [LNL87, LLN87, LLS
+
91, SLC91, LSL
+
94, Nat95] and specific techniques
have been developed for designing programs that can produce partial results.
In a real-time system that supports imprecise computation, every task
τ
i
is decom-
posed into a
mandatory
subtask
M
i
and an
optional
subtask
O
i
. The mandatory sub-
task is the portion of the computation that must be done in order to produce a result
of acceptable quality, whereas the optional subtask refines this result [SLCG89]. Both
subtasks have the same arrival time
a
i
and the same deadline
d
i
as the original task
τ
i
;
however,
O
i
becomes ready for execution when
M
i
is completed. If
C
i
is the worst-
case computation time associated with the task, subtasks
M
i
and
O
i
have computation
times
m
i
and
o
i
, such that
m
i
+
o
i
=
C
i
. In order to guarantee a minimum level
of performance,
M
i
must be completed within its deadline, whereas
O
i
can be left
incomplete, if necessary, at the expense of the quality of the result produced by the
task.
It is worth noting that the task model used in traditional real-time systems is a special
case of the one adopted for imprecise computation. In fact, a hard task corresponds to
a task with no optional part (
o
i
=0), whereas a soft task is equivalent to a task with
no mandatory part (
m
i
=0).
In systems that support imprecise computation, the
error
i
in the result produced by
τ
i
(or simply the error of
τ
i
) is defined as the length of the portion of
O
i
discarded in
the schedule. If
σ
i
is the total processor time assigned to
O
i
by the scheduler, the error
of task
τ
i
is equal to
i
=
o
i
−
σ
i
.
Search WWH ::
Custom Search