Hardware Reference
In-Depth Information
The
average error
on the task set is defined as
n
=
w
i
i
,
i
=1
where
w
i
is the relative importance of
τ
i
in the task set. An error
i
>
0 means that a
portion of subtask
O
i
has been discarded in the schedule at the expense of the quality
of the result produced by task
τ
i
, but for the benefit of other mandatory subtasks that
can complete within their deadlines.
In this model, a schedule is said to be
feasible
if every mandatory subtask
M
i
is com-
pleted within its deadline. A schedule is said to be
precise
if the average error
on
the task set is zero. In a precise schedule, all mandatory and optional subtasks are
completed within their deadlines.
As an illustrative example, let us consider a set of jobs
shown in Fig-
ure 9.31a. Note that this task set cannot be precisely scheduled; however, a feasible
schedule with an average error of
=4can be found, and it is shown in Figure 9.31b.
In fact, all mandatory subtasks finish within their deadlines, whereas not all optional
subtasks are able to complete. In particular, a time unit of execution is subtracted from
O
1
, two units from
O
3
, and one unit from
O
5
. Hence, assuming that all tasks have an
importance value equal to one (
w
i
=1), the average error on the task set is
=4.
{
J
1
,...,J
n
}
For a set of periodic tasks, the problem of deciding the best level of quality com-
patible with a given load condition can be solved by associating each optional part
of a task a reward function
R
i
(
σ
i
), which indicates the reward accrued by the task
when it receives
σ
i
units of service beyond its mandatory portion. This problem has
been addressed by Aydin et al. [AMMA01], who presented an optimal algorithm that
maximizes the weighted average of the rewards over the task set.
Note that in the absence of a reward function, the problem can easily be solved by
using a compression algorithm like the elastic approach. In fact, once, the new task
utilizations
U
i
are computed, the new computation times
C
i
that lead to a given desired
load can easily be computed from the periods as
C
i
=
T
i
U
i
.
Finally, if an algorithm cannot be executed in an incremental fashion or it cannot be
aborted at any time, a task can be provided with multiple versions, each characterized
by a different quality of performance and execution time. Then, the value
C
i
can be
used to select the task version having the computation time closer to, but smaller than
C
i
.
Search WWH ::
Custom Search