Algorithms for Scheduling Real-Time Tasks with Input Error and End-to-End Deadlines.
AbstractThis paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task
INTRODUCTION
HARD real-time system contains tasks which must
produce logically correct results within certain timing
constraints. In a system where the processing times of tasks
transient overloads may be unavoidable. A hard real-time
system must remain robust and maintain an acceptable
level of performance under a transient overload. The
imprecise-computation technique [1], [2], [3], [4], [5] was
introduced as a way to deal with transient overloads. The
technique is motivated by the fact that one can often trade
off precision for timeliness. It prevents missed deadlines
and provides graceful degradation during a transient
overload by ensuring that an approximate result of acceptable
quality is available whenever the exact result cannot be
obtained in time.
The imprecise-computation model used in previous
studies [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14],
[15] assumes that the quality of a task's result depends
solely on the time spent by the task to produce the result.
Specifically, the input of each task is free of error. If a task
terminates prematurely, the result produced by it contains
an error that is a nondecreasing function of the processing
time of the unexecuted portion. While this model adequately
characterizes many real-time applications, there are
several others that it does not. Examples include video
compression, speech recognition, and radar tracking. In
these applications, the quality of a result produced by a
task depends also on the quality of the input of the task.
When the results produced by some tasks are used as inputs
by other tasks, the decision on how much of each task
to complete by what time in order for the set of dependent
tasks to produce a good overall result should not be made
by considering each task independently from the others.
In addition, previous studies on imprecise computation
focus on the case where the timing constraints of each task
are given. However, the timing constraints that can be derived
directly from high-level requirements are typically
not that of individual tasks, but rather are timing constraints
of sets of tasks. We call such timing constraints end-
to-end timing constraints. The end-to-end timing constraints
over each set of tasks must be met. In contrast, the individual
tasks in the set do not have any specific timing con-
straints, other than those imposed by the end-to-end timing
constraints. Thus, we have the freedom to advance and
postpone the executions of individual tasks. This freedom
gives us an added dimension in the tradeoff between result
quality and timing requirements.
In this paper, we extend the imprecise-computation
model to account for input error as well as the end-to-end
nature of the timing constraints. According to this model,
tasks which jointly support a function of the system are
dependent. The amount of time required to complete a successor
task depends on the quality of the result produced
by its predecessor task. Each set of dependent tasks forms a
composite task. Composite tasks are independent of each
other. The ready time and deadline of each composite task
are the end-to-end timing constraints of the component
tasks in it. We describe in this paper a two-level approach
to scheduling composite tasks. At the high level, the scheduler
determines the total amount of time budgeted to each
composite task in order for all the composite tasks to meet
their deadlines. At the low level, the scheduler distributes
the time budgeted for each composite task to its component
tasks so as to minimize its output error. The high-level
scheduler can use one of several existing algorithms for
scheduling independent tasks with precise inputs to determine
the time budgets of the composite tasks. We describe
here several heuristic algorithms which the low-level
scheduler can use to distribute time to component tasks.
The remainder of this paper is organized as follows: Section
2 provides the background information needed for Section
3, which describes the extended imprecise-computation
. W.-c. Feng and J.W.-S. Liu are with the Department of Computer Science,
University of Illinois at Urbana-Champaign, Urbana, IL 61801.
E-mail: {feng, janeliu}@cs.uiuc.edu.
Manuscript received Sept. 9, 1994.
Recommended for acceptance by A.C. Shaw.
For information on obtaining reprints of this article, please send e-mail to:
transse@computer.org, and reference IEEECS Log Number S95622.
A
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 2, FEBRUARY 1997
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 2 / 14
model. Section 4 quantifies the effect of input error on the
processing time requirements and result quality of dependent
component tasks. Section 5 presents a set of heuristic
scheduling algorithms which attempt to optimize the overall
result quality of each composite task. Section 6 presents the
performance of these algorithms. Lastly, Section 7 summarizes
our results and presents future work.
Our model is built on the imprecise-computation model used
in previous studies [3], [4], [5], [6], [7], [8], [9], [10], [11], [12],
[13], [14], [15] which characterizes the workload on a real-time
system as a set of preemptable tasks
Each task T i is logically decomposed into a mandatory part M i
followed by an optional part O i and has the following rational
parameters:
. ready time r i . The time at which task T i is available for
execution,
. deadline d i . The time by which task T must produce a
result
. processing time p i . The amount of processor time required
to execute the task T i to completion,
. mandatory processing time the amount of processor
time required to execute the mandatory part M i to
completion, and
. optional processing time . The amount of processor time
required to execute the optional part O i to completion.
The mandatory part M i must execute to completion in order
to produce an acceptable and usable result. The task T i
meets its deadline if its mandatory part completes by its
deadline. The optional part O can only execute after the
mandatory part M completes. The optional part may be
terminated before it has completed, if necessary, so that the
task and other tasks can meet their deadlines.
Our attention is confined to uniprocessor systems. We let
f denote the amount of processor time that is assigned to
execute the task T i , according to a given schedule. A scheduling
algorithm works correctly if it never schedules a task
before its ready time and if the total time f i it assigns to
every task T i is no less than the mandatory processing time
be the amount of time remaining, after
the mandatory part M i completes, for the execution of the
optional part O i . s i may be less than Hereafter, by a
scheduling algorithm, we mean a correct algorithm, and by
a schedule, we mean a valid schedule in which
We call a schedule in which every task T is assigned m i or
more units of time before its deadline a feasible schedule.
When the assigned processor time f i equals p i , or equivalently
, the task T is said to be precisely scheduled.
Otherwise if f i < p i , the last portion of T with processing time
is discarded. In a valid schedule, p i - f i , which is equal
to equal to or less than o . We call the
amount of discarded work and
f
for
the fraction of discarded work. 1
never in the range
the value of F in this range is irrelevant; it is assumed
to have the value of one for the sake of convenience.
Most existing algorithms [3], [4], [5], [7], [8], [9], [10],
[11], [12], [13], [14], [15] for scheduling tasks with optional
parts assume that the tasks are monotone. As a monotone
task executes longer, the quality of its results improves.
Hence, these algorithms seek schedules in which the fraction
of discarded work (or some function of this fraction) of
each task is as small as possible. Specific performance metrics
commonly used by existing algorithms include
weighted average of the fractions of discarded work, sum
of the fractions of discarded work, maximum fraction of
discarded work, and number of discarded optional tasks.
The high-level scheduler described later in this paper
makes use of Algorithm G described in [5]. This optimal off-line
algorithm finds preemptive schedules of independent
tasks in which the maximum fraction of discarded work
among all tasks is as small as possible. This algorithm in turn
uses the optimal algorithm, developed earlier by Shih et al.
[11], for scheduling off-line preemptive tasks with arbitrary
ready times and deadlines to minimize the sum of the
amounts of discarded work over all tasks. While these algorithms
allow tasks to be dependent, the possibility of error
propagation across dependent tasks was not considered. Shih
and Liu [12] has since modified this algorithm to schedule
tasks on-line so that the sum of the amounts of discarded
work of all tasks accepted by the system is minimized.
The concept of trading off result quality for timeliness
has also been independently studied by the artificial intelligence
community. Dean and Boddy [16], [17] proposed the
use of anytime algorithms in the framework of time-dependent
planning and decision-making. The execution of
an anytime algorithm may be interrupted at any point to
return a result whose quality is solely a function of the
processing time of the completed portion. Therefore, a task
based on the anytime algorithm is an optional task in the
imprecise-computation model: The mandatory processing
time of such a task is zero.
Zilberstein [18], [19], [20] extended the work of Dean and
Boddy by introducing the concept of conditional performance
profiles. Conditional performance profiles represent result
quality as a function of input quality as well as the processing
time spent to produce the result. The extended im-
precise-computation model described in the next section
resembles Zilberstein's model in this way.
Musliner [21] introduced the concept of any-dimension al-
gorithms-a general class of iterative algorithms. This concept
generalizes the anytime algorithm concept by providing
guarantees along dimensions other than time. Like an
anytime algorithm, an any-dimension algorithm is an iterative
algorithm with a termination condition which halts the
iteration when some threshold along that dimension is
reached. This aspect is not considered here.
Dey, Kurose, and Towsley [22] introduce the notion of
reward, which is analogous to error in the imprecise-
computation model or quality in anytime algorithms. They
1. In previous studies on imprecise computation, E i was called the error
in the result of task T i when the quality of the result was assumed to be a
linear function of the amount of discarded work.
FENG AND LIU: ALGORITHMS FOR SCHEDULING REAL-TIME TASKS WITH INPUT ERROR AND END-TO-END DEADLINES 3
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 3 / 14
schedule tasks so that tasks receive increasing reward with
increasing service (IRIS). However, their model ignores the
dependency of result quality on input quality.
MODEL
We extend here the imprecise-computation model to characterize
applications where inputs provided to tasks may
be imprecise. In the extended imprecise-computation
model, a workload consists of a set of independent, preemptable
composite tasks In particular,
the input of each composite task is independent of the the
output produced by other composite tasks. Each composite
task T j consists of n j component tasks T T T
K The
parameters are the processing time, mandatory
processing time, and optional processing time of the composite
task T , respectively. They are equal to the sums of
the corresponding parameters of the component tasks in T j
that is,
, , and
, , and
are the processing time, mandatory processing
time, and optional processing time of component
task
.
We focus our attention on the type of composite tasks
whose component tasks have linear precedence-constraint
graphs. The (end-to-end) ready time r j of the composite task
T j is the ready time of its first component task T i . T 1
can
begin execution at r j . T i
can begin execution only after T i
completes for
j is the (immediate) successor
of T i
, and the output of T i
is the input of T i
. The output
of the last component task T n
j is the output of the composite
task. The (end-to-end) deadline d j of T j is the deadline its
last component task T n
. The ready times and deadlines of
the intermediate component tasks T T T
are not
specified. To capture the end-to-end nature of the timing
constraints, we assign the ready times and deadlines of the
component tasks to be the same as that of the composite
task. This gives us the maximum flexibility in scheduling
the component tasks.
Most of this paper deals with the scheduling of component
tasks within a given composite task. When there is no
ambiguity, we simplify our notation by dropping the superscript
j from the component tasks T T T
K of the
composite task T and simply call them tasks
We assume that all of the component tasks are monotone.
When a component task T i-1 is terminated before it is
completed, its output contains an error E i-1 , which is the
input error e i of its successor task T i . One effect of the input
error e is that the mandatory part M i of T i may be extended
in the sense that it now takes an additional H i units of
processor time beyond m i for T i to produce an acceptable
result. We call the H i units of the mandatory
part the mandatory extension of T i , and the concatenation
of the mandatory part M i and the mandatory extension
the extended mandatory part -
. The amount of processor
time needed to execute -
M i to completion is given by
paper, we assume that the
mandatory extension H (e i ) is a monotone nondecreasing
function of the input error e i and H i every
component task is monotone, the input error e i of the task T
is a monotone nondecreasing function of the fraction of
discarded work F i-1 of the predecessor task T i-1 . Conse-
quently, the mandatory extension of T i is a monotone non-decreasing
function of F i-1 . With a slight abuse of notation,
we denote this function by H i n. The
mandatory extension of T i is zero if its predecessor task T i-1
is assigned p i units of time, i.e., F
i. We assume that the input error e 1 to the first component
task in every composite task is zero, and hence H 1
The effect on the processing time of the mandatory part
can be illustrated by Newton's root-finding method. Suppose
that the processing time of the mandatory part is the
time it takes to find a root within 10% of the actual root,
and the processing time of the optional part is the time it
takes to refine the result of the mandatory part to be within
0.1% of the actual root. Obviously, if the input to Newton's
method is poor (i.e., the predecessor component task provides
an input value which is far from the actual root), the
mandatory part must execute longer in order to meet the
10% threshold. This effect is accounted for by the mandatory
extension. The optional part stays the same.
Similar examples of extending the mandatory part occur
in image and video processing as well. Suppose that the
processing time of the mandatory part is the time it takes to
display (on a client workstation) a video frame of acceptable
quality, and the processing time of the optional part is
the time it takes to further enhance the visual quality of the
video frame. If during the transmission of a frame to the
client, some packets are lost or corrupted; the client must
do some image enhancement, and the mandatory part of
displaying the video frame is extended correspondingly in
order to bring the quality of the video frame up to acceptable
standards.
Another possible effect of input error on a task T is that
the processing time of the optional part O i is lengthened.
Based on the same argument above, the processing time of
the optional part O i of T i is extended by K i units to
offset the effects of the input error, where K i (x) is a monotone
nondecreasing function of x and K
additional time units of the optional part make up the optional
extension, and the juxtaposition of the optional part O
and the optional extension is the extended optional part -
O .
The amount of processor time needed to execute -
O i to
completion is given by -
Radar tracking is an example of an application where
extending the optional part is necessary to compensate for
input error. The mandatory part consists of processing the
returned radar signal and creating track records by a signal
processor. Each track record indicates position and direction
of movement of a possible target. The optional part
tries to associate these targets with established tracks by a
data processor. If the returned radar signal is weak and
4 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 2, FEBRUARY 1997
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 4 / 14
noisy, the amount of time required to process the signal
remains more or less the same (i.e., the processing time of
the mandatory part stays the same). However, there may be
more false returns-records associated with nonexistent
targets. As a result, the data processor must spend additional
processing time in associating tracks.
In general, both the mandatory part M and the optional
part O may be extended when a fraction F i-1 of the optional
part O i-1 is discarded and hence the input error e is nonz-
ero. Specifically, the mandatory part M i is extended by
and the optional part O by K i
of H means that the input error e i of T has a fatal effect
on never produce an acceptable result no matter
how long it executes. Similarly, if K i
finite, the effect of input error can never be erased
by executing the optional part -
O i longer and longer, although
the result produced by T i is acceptable. Hereafter,
we will refer to H i as the mandatory and
optional extension functions, respectively.
Again, we consider here composite tasks whose prece-
dence-constraint graphs are linear. For such a composite
task, its output error is equal to the output error of the last
component task, which, in turn, depends on the output errors
of its predecessor component tasks.
Let F j denote the total amount of processor time assigned
to a composite task T j by the high-level scheduler.
The heuristic algorithms for distributing the total time F j to
the component tasks attempt to keep the fraction of discarded
work F n of the last component task, and hence the
output error E n of this component task and the composite
task, as small as possible.
The algorithms presented in subsequent sections are
near optimal when the mandatory extension and optional
extension of every component task T i are linear functions of
the fraction of discarded work F i-1 of its immediate predecessor
T i-1 . In particular, they assume that the extension
functions of T i are
where h i is the mandatory error-scaling factor and k i is the optional
error-scaling factor of T i . However, the assumption on
the linearity of H i not valid in general.
We will return in Section 5 to discuss how to approximate
arbitrary functions H i linear functions.
Throughout this section, we assume that the mandatory
and optional extensions of component tasks T 2 , T 3 , -, T n
are given by (1) and (2)). The mandatory and optional extensions
of the first component task T 1 of a composite task
are zero since the input of a composite task is assumed to
be error-free. We first derive the expression for the fraction
of discarded work of the last component task, as a function
of the amounts of time assigned to the earlier component
tasks for the special case where the optional error-scaling
factors k i are zero; that is, We
then consider the special case when the mandatory error-
scaling factors h i are zero. The expressions for the fraction
of discarded work of T i in terms of that of its predecessors
will provide clues as to how to distribute the amount of
time F j that is assigned to the composite task T j to its component
tasks when the mandatory and optional extensions
of all component tasks are given by (1) and (2)).
When the mandatory error-scaling factor h i is nonzero
and the optional error-scaling factor k is zero, the amount
of time f i assigned to each component task T i must be in the
range so that its extended-
mandatory part -
M i can execute to completion. With f i constrained
to this range, the fraction of discarded work of T i is
a linearly decreasing function of f i , as illustrated by the
dotted line in Fig. 1 and stated by the following lemma.
Fig.1. An extended imprecise-computation model.
LEMMA 4.1. The fraction of discarded work F of a component task
optional error-scaling factor k i is zero is given by
f
when it is assigned
units of time and the fraction of discarded work of its
predecessor is F i-1 .
PROOF. The lemma follows directly from the property of
similar triangles.
F
As an example, if f there is only
enough time to execute the extended-mandatory part -
and the optional part O is left unexecuted. As a result, F
1. In general, the fraction of discarded work F n of a composite
task consisting of n component tasks is given by the
following theorem.
THEOREM 4. For a composite task with n component tasks whose
optional error-scaling factors are zero, the fraction of discarded
work F n of the last component task T n is given by
F C a a a
is the amount of time assigned to the component
task T i for is the constant
FENG AND LIU: ALGORITHMS FOR SCHEDULING REAL-TIME TASKS WITH INPUT ERROR AND END-TO-END DEADLINES 5
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 5 / 14
and the coefficients a are given by
a h h h
a
a h
a
PROOF. By Lemma 4.1, for a composite task consisting of
one component task, its fraction of discarded work is
given by
f
For a composite task consisting of a chain of two
component tasks, the fraction of discarded work F 2 of
is equal to
F
f
f
f
Suppose that the amount of discarded work F n-1
for a composite task consisting of a chain of n-1 component
tasks is
F C
C a a a
F
Then, the amount of discarded work F n for a composite
task with n component tasks is
C a a a
F
f
f
Similarly, when the mandatory error-scaling factor h i of
a component task T i is zero but the optional error-scaling
is nonzero, the value for f i must be in the range
is the processing time of
the extended-optional part.
LEMMA 4.2. The amount of discarded work F i for a component
task T whose mandatory part has an error-scaling factor h
of zero is given by
F
when it is assigned f i units
of time and the fraction of discarded work of its predecessor
is F i-1 .
PROOF. Using Fig. 1, the lemma follows directly from the
property of similar triangles.
F
THEOREM 4.2. For a composite task with two or more component
tasks whose mandatory error-scaling factors h i are zero, the
fraction of discarded work F i of component task T i is given by
s
s
where s i-1 and s i are the amounts of time assigned to the
optional parts of T i-1 and T i , respectively, and F i-2 is the
fraction of discarded work of T i-2 .
PROOF. From Lemma 4.2,
s
We now describe a high-level algorithm for scheduling
composite tasks and determining the total amount of time
assigned to each task. We then focus on low-level algorithms
for distributing the time assigned to each composite
task among its component tasks. These algorithms make
use of the expressions derived in the previous section to
decide how the total amount of time assigned to each composite
task should be distributed among its component
tasks so as to minimize the output error E n for the composite
task. Because the low-level algorithms compute the
amounts of time given to the component tasks based on
their error-scaling factors, we also present a method for
extracting the error-scaling factors.
5.1 High-Level Scheduling of Composite Tasks
Since the composite tasks are independent, the quality of
the result produced by a composite task is independent of
the amounts of time assigned to other composite tasks.
Therefore, the problem of scheduling a set of preemptable
composite tasks reduces to the problem of scheduling a set
of independent preemptable tasks.
Fig. 2 gives a pseudocode description of an algorithm,
called S-COMPOSITE, for scheduling composite tasks. (In
6 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 2, FEBRUARY 1997
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 6 / 14
this figure, we use h j to denote the sum i
it is the
maximum extended-mandatory processing time.) This algorithm
makes use of a modified version of the earliest-
deadline-first algorithm (M-EDF), described in [11], and
Algorithm G, described in [15]. The M-EDF algorithm treats
every composite task as if it were entirely optional and
schedules the composite tasks on an earliest-deadline-first
basis. It never schedules any composite task after its dead-
line. In other words, every composite task is terminated at
its deadline if it is not completed. It has been shown in [11]
that the M-EDF algorithm minimizes the total processing
time of the discarded portions of all tasks. Algorithm G
distributes the total available processor time as evenly as
possible among the tasks. Specifically, for a given set of
ready times and deadlines, this algorithm makes the fraction
of discarded work of the composite task (i.e., the ratio
of the processing time of the unexecuted portion of each
composite task to the total optional processing time of all
the component tasks in it) as equal as possible to that of the
other composite tasks.
Input:
(a) The ready time r j and deadline d j of every composite
task T j in T.
(b) The total processing time and the maximum
extended-mandatory processing time
(c) The parameters m j , of every component
task in every composite task in
Output:
A feasible schedule of T or a feasible schedule of a subset
of T and the list of composite tasks that cannot be feasibly
scheduled.
1. (a) For each composite task T , set the processing
time P of T j to p .
(b) Use the M-EDF algorithm to find a schedule of
If the resultant schedule is a precise schedule then
The output error of every composite task is 0.
Done.
2. (a) For
set
(b) Use the M-EDF algorithm to find a schedule of
If the resultant schedule is a precise schedule then
q. Go to Step 4.
3. Use Algorithm G to schedule T.
the total amount of time assigned to T according
the resultant schedule for each composite task in T.
4. (a) For every j, use one of the distribution algorithms to
distribute the time F assigned to T j among its component
tasks.
(b) Report all infeasible composite tasks and the processing
time distribution of all feasible composite tasks.
Fig. 2. Algorithm S-COMPOSITE.
Algorithm S-COMPOSITE has four steps. In Step 1, it
tries to schedule every composite task T j precisely. If this
step succeeds in finding a precise schedule, the output errors
of all the composite tasks are zero, and each component
task
j is assigned m
units of time. If Step 1 fails
to find a precise schedule of T, no precise schedule of T
exists [11]. Step 2 then tries to precisely schedule every
composite task whose optional processing time
compared to its maximum extended-mandatory processing
time. It does so in Step 2(a) by reducing the amounts of
time assigned to tasks which have relatively large optional
processing times. If, in Step 2(b), the M-EDF algorithm
finds a precise schedule with this reduction, the composite
tasks with small optional processing times are scheduled
precisely and have zero output errors. Each composite task
whose optional processing times larger than its maximum
extended-mandatory processing time -
assigned
a sufficient amount of time to ensure the feasible distribution
of its time among its component tasks.
On the other hand, if Step 2(b) fails, we do not know
whether we can feasibly schedule T until we distribute the
assigned to each composite task to its component
tasks. Step 3 is carried out and finds F in such a way that
the processing times of the unexecuted portions of all composite
tasks, measured in terms of fractions of their processing
times, are as equal as possible under the constraints
imposed by the ready times and deadlines of the composite
tasks. Step 4 is then invoked to distribute this time to the
component tasks.
For example, suppose that there are two composite tasks
with the following parameters:
Fig. 3 shows the three schedules of the composite tasks
produced in Steps 1, 2, and 3 of Algorithm S-COMPOSITE.
Because the schedules produced in Step 1 and Step 2 are
not precise, Step 3 is carried out, and the fractions of unexecuted
optional portions of both tasks are equal to 1/14. The
times assigned to these tasks are F 28 and F 84. The
processing times of the unexecuted portions of T 1
and T 2
are 1 and 3, respectively.
Fig. 3. An example to illustrate Algorithm S-COMPOSITE.
Later, we will expand this example and show that the
algorithm used in Step 4 can find a way to distribute the 28
units of time assigned to T 1 such that the output error is
zero and the total time used by its component tasks is less
than 28. The results produced by Step 4 include the amount
of unused time for each feasibly scheduled composite task
and the additional amount of time required for each infea-
FENG AND LIU: ALGORITHMS FOR SCHEDULING REAL-TIME TASKS WITH INPUT ERROR AND END-TO-END DEADLINES 7
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 7 / 14
sibly scheduled composite task. We can improve the chance
for Algorithm S-COMPOSITE to find a feasible schedule of
T when it fails by carrying out Step 3 and Step 4 again. In
the second iteration, the amount of time used by each composite
task that is feasibly scheduled in Step 4 in the first
iteration is considered to be mandatory. Similarly, the
amount of time required by each composite task that is not
feasibly scheduled in Step 4 is used as the mandatory processing
time of the task in the second iteration.
The time complexity of Steps 1 and 2 is O(q ln q). The
time complexity of Step 3 is O(q 3 ). The algorithms for distributing
time to the component tasks have time complexity
O(n). Hence, the time complexity of Algorithm
5.2 Low-Level Scheduling to Distribute Processor
Time
The F units of time assigned to a composite task T must be
distributed to its n component tasks in such a way that the
We present here five algorithms for this distribution. (Since
it is no longer necessary for us to keep track of different
composite tasks, we again drop the superscript to simplify
our notation.)
Algorithms
make decisions on the amount of time given to component
tasks based primarily on their mandatory error-scaling fac-
tors. They are more suited when the processing times of the
mandatory extensions of the component tasks are large compared
to the processing times of the optional extensions. In
contrast, Algorithms DIST-O and DIST-O + take into account
the effect of the optional error-scaling factors on the output
error of the composite task. They should perform better than
DIST-M, DIST-M+, and DIST-M+-ITERATIVE when the
processing times of the optional extensions are large in comparison
to the processing times of the mandatory extensions.
5.2.1 Algorithm DIST-M
Fig. 4 gives the pseudocode description of Algorithm DIST-
M, an algorithm which distributes processor time to component
tasks based solely on the mandatory error-scaling
Theorem 4.1 provides the rationale of this algorithm.
According to this theorem, when the optional error-scaling
factors of all the component tasks are zero (i.e., k
1, 2, -, n), the fraction of discarded work F n is a linear
function of the times f i s assigned to its component tasks.
Since the constraints (6) and (7) on the f i s are also linear,
the problem of finding an assignment {f i } (i.e., the set of
times assigned to component tasks) to minimize F n , and
hence the output error E n of the composite task, is a linear-programming
problem in this special case. We can use a
linear-programming package to find {f i } if the scheduling is
done off-line. However, when k i # 0, the assignment {f }
thus found is not optimal and, as we will see later, may not
even be feasible. Algorithm DIST-M and its variances offer
better alternatives with lower scheduling overhead because
its time complexity is O(n).
Input:
(a) The parameters m i , component tasks
(b) The total time F assigned to the composite task.
Output:
A feasible assignment {f i } of time to the component tasks and the
amount of unused time U, or a report on the failure to find a feasible
schedule and the additional time required.
1. If F - n
Schedule component tasks precisely by setting
Done.
2.
Report
Done.
3.
Compute a s from h i s and
according to (4).
Sort a i s in nonincreasing order and put them in the list L.
While L is not empty do
index of the largest a in L
If T x+1 is marked and x - n then
Else f
Mark T x and remove a x from L.
4. Compute the amount of unused time
If U < 0, then set
Report that the algorithm fails and that the amount of
additional time required is
Else report unused amount of time U and {f i }.
Fig. 4. Algorithm DIST-M.
More specifically, Algorithm DIST-M has four steps. The
first two steps try to find a feasible assignment in which T n is
scheduled to yield a zero output error. If these two steps fail,
Step 3 tries to find a good assignment with a small fraction of
discarded work F n . To see the rationale behind this step, we
assume for the moment that From the expression
of F n in Theorem 4.1, we see that this fraction is minimized
by choosing the values of f i in the following way: The
larger the coefficient a i in the sum given by (3), the larger the
value of f i . Unfortunately, because of constraints (6) and (7),
this choice of f i is not always possible. Because of these constraints
and the fact that the k i s are not zero, Step 3, and
hence Algorithm DIST-M, is not optimal.
Step 3 tries to find an assignment which yields a small
fraction of discarded work F n by making locally optimal or
near-optimal decisions as follows. It begins by making the
value of f x , which has the largest coefficient a x among all a i s
in (3), as large as possible. From (4), we see that a x > a x+1
means h x+1 > In other words, the processing time of the
optional part of T x is smaller than the processing time of the
maximum mandatory extension of T x+1 when the entire op-
8 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 2, FEBRUARY 1997
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 8 / 14
tional part of T x is left unexecuted. Therefore, f x is made sufficiently
large so that T x can execute to completion. Similarly,
because a x > a x-1 , and hence h x < time is required to
execute the maximum mandatory extension of T x than the
optional portion of T x-1 . Therefore, f x-1 is chosen so only the
extended-mandatory portion of T x-1 completes. This process
is repeated until the values of all f s are chosen.
Step 4 checks whether the assignment {f } produced in
Step 3 is feasible for the total time F assigned to the composite
task. If the total time required by {f i } exceeds F, then another
attempt to find a feasible assignment is made to produce
a schedule with the minimum allowable output error.
The algorithm fails if this assignment is also infeasible. As a
result of Step 4, the amount of time not used by a feasible
assignment {f i } or the additional amount of time needed for a
feasible assignment is reported. The high-level scheduler can
make use of this information to reallocate time among composite
tasks, e.g., by giving the time not required by one
composite task to one(s) that requires more time.
As an illustrative example, we consider the composite
task T 1 in Fig. 3 which consists of a chain of four component
tasks: suppress the super-
script.) The parameters of the component tasks are:
The total amount of time assigned to T 1 is 28. T 1 cannot be
precisely scheduled and executed because i
Hence, Step 1 of Algorithm DIST-M fails to find an assignment
that yields zero output error. Step 2 assigns f
units of time to T 1 , T 2 , and T 3 , respec-
tively. The remaining time F - i =1S f insufficient for
T 4 to execute to completion. Consequently, Step 3 is carried
out. Because a 44
and a a4
we have a 2 > a 1 > a 4 > a 3 . In the first
marked. The
fraction of discarded work F 1 of T 1 is 1, and the fraction of
discarded work F 2 of T 2 is 0. In the second iteration, a 1 is the
largest entry. Because T 2 is marked and F
6.4. In the third iteration, a 4 is the largest, and thus f 4 is
chosen to be m 4
the fourth iteration, the time required by T 3 is
the amount of unused
time is 0.6 units, and the fraction of discarded work F 4 of T 4 is
zero. Consequently, the output error is zero.
5.2.2 Extensions of Algorithm DIST-M
While Algorithm DIST-M strictly follows Theorem 4.1 when
making scheduling decisions, Algorithm DIST-M only uses
it as a guide. The conceptual difference between the two algorithms
is in Step 3. Unlike Algorithm DIST-M, Algorithm
does not make its scheduling decisions based solely
on the a i s. The DIST-M + algorithm goes one step further by
checking to see if the total execution time of the pair of tasks
shortened or lengthened by giving the task T
more processing time. If it is shortened, then task T i is assigned
more time; otherwise, it is only allocated enough time
to execute the extended-mandatory part. Steps 1, 2, and 4 of
this algorithm are the same as the corresponding steps of
Algorithm DIST-M; its Step 3 is described in Fig. 5. We note
that the purpose of "marking" in this algorithm is different
from that in Algorithm DIST-M. Here, a marked task is a task
whose fraction of discarded work is zero.
3. Set F
Compute a s from h s and
according to (4).
Sort a i s in nonincreasing order and put them in the
list L.
While L is not empty do
index of the largest a in L
If T x+1 is marked and x - n then
If -
Else
Mark T x
Else /* T x+1 is unmarked */
If -
Else
Mark T x
Remove a x from L.
Fig. 5. Step 3 of Algorithm DIST-M
The amounts of time required to complete the component
tasks may change during the execution of Algorithm
. If Algorithm DIST-M + is applied iteratively, it
will produce a schedule as good as or better than a schedule
produced by a single pass of Algorithm DIST-M
Therefore, Algorithm DIST-M repeatedly applies
Algorithm DIST-M + until there are no more changes to
the schedule.
5.2.3 Algorithm DIST-O
When the processing times of the mandatory extensions are
small compared to the processing times of their optional ex-
tensions, we expect that DIST-M and its variances are unlikely
to perform well. Algorithm DIST-O offers an alterna-
tive. The algorithm consists of three steps. Its first two steps
are identical to the first two steps of Algorithm DIST-M; its
Step 3 is described in Fig. 6.
FENG AND LIU: ALGORITHMS FOR SCHEDULING REAL-TIME TASKS WITH INPUT ERROR AND END-TO-END DEADLINES 9
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 9 / 14
Step 3 is carried out when Step 2 fails. In other words,
after units of time have been assigned to each of
the earlier component tasks T , the remaining time F -
insufficient for the last component task T n
to complete. The decision that must be made is whether to
assign this time to T n or an earlier component task or to
divide the time between the component tasks in some
manner.
After Step 2,
Report failure to find a feasible assignment and that
the additional time required is
Done.
Else
If y > -
Report {f }. Done.
Fig. 6. Step 3 of Algorithm DIST-O.
Algorithm DIST-O is based on the expression of output
error given by (5). Like Algorithm DIST-M, the decision
made by Algorithm DIST-O is only locally optimal. To understand
the reasoning behind the choices made by Step 3,
We suppose that the y
units of time is divided evenly between T n and T n-1 . According
to (5), the fraction of discarded work F n is given by
F
where again
We now ask
whether F n can be reduced by assigning y units of time
to T n for d > 0 at the expense of T n-1 . This question is
equivalent to whether the inequality
y
y
F
F
F
d d
is true. A simple algebraic manipulation shows that this
inequality holds if
y
In this case, it is better to give all the remaining time y to T n .
Otherwise, we give more time to the earlier component task
5.2.4 Algorithm DIST-O
The decision made in Algorithm DIST-O is good only when
the processing times of the maximum mandatory extensions
of the component tasks are fairly small. In general, we
may be able to reduce the output error by distributing
the available time to earlier component tasks. Algorithm
, an enhanced version of Algorithm DIST-O, serves
this purpose. This algorithm tries to divide the processing
time across all the component tasks; the algorithm is identical
to Algorithm DIST-M except that the heuristic guide a
in Step 3 is calculated differently.
The choice of a i is motivated by the expression in (5). According
to this equation, when the mandatory error-scaling
factors of all the component tasks are zero (i.e., h
1, 2, -, n), a component task whose optional error-scaling
factor and optional processing time are smaller than those
of the successor task should be given more time than the
successor task when the fraction of discarded work of its
predecessor is sufficiently small. Otherwise, the successor
task should be given more time. Consequently, we choose a
to be
5.3 Extracting Error-Scaling Factors
The low-level algorithms for distributing time to component
tasks require as input parameters the error-scaling
factors of the component tasks. These algorithms cannot be
applied directly to component tasks whose extension functions
are not in the linear form given by (1) and (2). We now
describe how to transform a given set of component tasks
with arbitrary mandatory and optional extensions to another
set with linear mandatory and optional extensions
and thus find the error-scaling factors.
Without loss of generality, suppose that the given mandatory
and optional extensions (denoted by H F
, respectively) of a component task T i are as shown
by the dotted curves in Fig. 7a and 7b, respectively. We approximate
each given extension function by two straight-line
segments; both segments lie entirely above each extension
function. These straight-line segments give an upper
bound of the values of the extension function at all values
of F i-1 . A valid, feasible schedule based on such straight-line
approximations of the extension functions is surely a valid,
feasible schedule for the given extension functions.
Specifically, one of the two straight lines is the vertical one
at f m (or f 1). We call
the discard threshold of task T i . The task T i can never produce a
precise result when more than f i fraction of the optional task
O i-1 of T i-1 is left unexecuted. We want to ensure that this condition
never occurs for any component task. For this reason,
increase the mandatory processing time of T i-1 by
and decrease the optional processing time of T i-1 by
denotes the given optional processing
time of T i-1 . In other words, we transform the predecessor task
T i-1 into one whose mandatory and optional processing times
are given by
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97
is the given mandatory processing time of T i-1 .
Our algorithms work with the transformed parameters m i-1
and not the corresponding given parameters.
The allowed range of the fraction of discarded work F i-1 ,
based on the computed value Adopting the
straight-line segments with finite slopes in this range, we
have the following approximate extension functions:
where X and Y are the values defined in Fig. 7. Hence, h
we assume that the characteristics
of all component tasks are first analyzed, and then the parameters
of every component task T i in
every composite task are derived from the given mandatory
and optional processing times and extension functions in
the manner described above.
Fig. 7. Extension functions.
We ran a suite of simulation experiments to evaluate the performance
of Algorithms DIST-M, DIST-M
ITERATIVE, DIST-O, and DIST-O
. For convenience, we call
the five algorithms collectively as DIST-* algorithms. In each
experiment, we randomly generated a composite task and
each of its component tasks. For each component task, the
mandatory and optional processing times (i.e., m i and
the mandatory and optional error-scaling factors (i.e., h i and
randomly chosen from their respective probability
distributions; we isolated the effect of these parameters by
keeping all other parameters fixed. (For example, the number
of component tasks in a composite task was fixed at 8.) For
each composite task, the parameters m i , h i , of each
component task T i were chosen from either uniform distributions
or bimodal distributions. We then applied the five
algorithms on each composite task and found the fractions of
discarded work of the last component task produced by
them. For a given algorithm, the lower the fraction of discarded
work, the better the performance.
6.1 Uniform Distribution

Table

1 shows the performance of the DIST-* algorithms
found in four representative experiments where the parameters
of each T i were all chosen from uniform
distributions. Each column corresponds to a composite
task whose component-task parameters are selected from
either the uniform distribution in the range [0, 10) or the uniform
distribution in the range [0, 100). We call the distribution
with the range [0, 10) to be the "small" uniform distribu-
tion. So, when the parameter h of all component tasks are
chosen from the "small" distribution and m i , and k from
the larger distribution, namely the one with range [0, 100),
we label the appropriate column with "small h" as exemplified
by the second column of each experiment in Table 1.
The numerical entries in Table 1 are either in roman or
italic font. The first two steps of all five DIST-* algorithms are
the same; these steps try to find a feasible scheduling assignment
which yields zero output error. When either Step 1
or 2 succeed, the results are listed in roman font. If either of
these steps fail, then the succeeding steps distinguish the individual
DIST-* algorithms. The results for the composite
tasks which benefit from these distinguishing steps are in
italics. If none of the steps result in a feasible schedule, then
the composite task is said to be unschedulable (uns).
When the expected values of the h i parameters are
small, the five algorithms perform almost identically.
Small h parameters imply that compensating for the input
error of a component task can be much cheaper timewise
than scheduling its predecessor tasks precisely. As a re-
sult, the best approach to schedule these types of tasks in
general is to schedule only the extended mandatory parts
of all but the last component task and then compensate
for the accumulated error by giving the last component
task as much time as possible. This approach is what Step
2 of all the DIST-* algorithms does, thus explaining the
near-identical performance.
The only instance where the algorithms do not perform
identically when h are small is when are small as
well. In this case, the approach described above takes about
as much time as scheduling the component tasks precisely
because all the optional parameters are small. In other
words, the time given to the last component task to compensate
for error in the mandatory parts (i.e., the mandatory
extensions) and for the accumulated error of its predecessors
is comparable to the amount of time it takes to simply
execute all the shorter optional parts entirely to begin
with. Because neither effect is pronounced, the heuristics in
Steps 3 or 4 of the DIST-* algorithms can come into play
and possibly produce better schedules. For instance, for
small h ,
ITERATIVE achieve the fraction of discarded work of 0.211
and perform better than the other algorithms.
FENG AND LIU: ALGORITHMS FOR SCHEDULING REAL-TIME TASKS WITH INPUT ERROR AND END-TO-END DEADLINES 11
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 11 /In general, whenever h i are small and are large, the
better approach is to schedule only the extended mandatory
parts and then compensate for the accumulated error
by giving the last component task as much time as avail-
able. On the other hand, whenever the are small,
the better approach is to schedule all the component tasks
precisely. The performance of the five heuristics seen in all
the experiments where the are small supports this
hypothesis. The heuristic steps in the DIST-* algorithms
effectively "reconcile" these opposing approaches and determine
how much of each scheduling approach to use in
finding an assignment for each set of parameter values.
In summary, Algorithms DIST-M
ITERATIVE perform better than the other algorithms in
most cases; however in some cases, they do not. For exam-
ple, in Experiment 4 when h i , are small, DIST-M
performs better than both DIST-M
ITERATIVE because the locally optimal decisions made by
were not globally op-
timal. Finally, the results of this set of experiments do not
distinguish the performance of DIST-M
ITERATIVE.
6.2 Bimodal Distribution

Table

2 shows the results obtained in four representative
experiments where the parameters m , h i ,
chosen from either uniform or bimodal distributions. Spe-
cifically, in each experiment, the parameters of each component
task were selected from either a uniform distribution
in the range [0, 100) or a bimodal distribution in the
ranges [0, 10) or [90, 100). (The bimodal probability density
function is equal to 1/20 in the ranges [0, 10) and [90, 100)
and is equal to zero elsewhere.) For example, when the h
parameters are chosen from the bimodal distribution and
are chosen from the uniform distribution, we
label the appropriate column with "bimodal h."
The results in Table 2 show that the different heuristics
used in the different DIST-* algorithms lead to a larger difference
in performance when all or some of the task parameters
are bimodally distributed. The reason is that Steps
1 and 2 do not often succeed for tasks with bimodally distributed
parameters. For instance, while column 2 of Table
1 shows that when m i , are large and h is small, all
five DIST-* algorithms achieve the same result; the corresponding
case of large m i , chosen from the same
uniform distribution but h i chosen from the bimodal distri-
FRACTION OF DISCARDED WORK-UNIFORMLY DISTRIBUTED PARAMETER
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 12 /bution (column 2 of Table 2) shows that the DIST-M + and
algorithms produce better results
than the other algorithms. The bimodal mixture of small
and large h i makes the approaches taken by Step 1 and Step
less effective, thus allowing the heuristics of the DIST-M
algorithms to be applied more
frequently and leading to better results. That Steps 1 and 2
fail more frequently for tasks with bimodally distributed
parameters is demonstrated by the larger number of italicized
entries in Table 2.
As in

Table

are small, Table 2 shows that
when are bimodally distributed, the approach of
scheduling all the component tasks precisely is still a good
one. However, it is no longer as good as in the case when
all task parameters are uniformly distributed; this is due
mainly to the fact that fewer of the parameters are
small in the bimodal distribution when compared to the
uniform distribution for a given composite task. Because
the sample of parameters is no longer uniformly
distributed, the heuristics potentially have more opportunities
to tradeoff the processing times of the mandatory and
optional extensions of the component tasks, thus producing
better results.
In summary, as in Table 1, Algorithms DIST-M + and
generally perform better than the
other algorithms when some parameters are bimodally
distributed. Furthermore, DIST-M
performed as well as or better than DIST-M


AND FUTURE WORK
In this paper, we extended the imprecise-computation
technique to account for input error and end-to-end timing
constraints and developed five heuristic scheduling algo-
-ITERATIVE, DIST-O,
-to minimize the output error of each composite
task in a real-time system. The algorithms all have
time complexity O(n). Although our initial intuition indicated
that the DIST-O and DIST-O algorithms would perform
better when the processing times of mandatory extensions
were small compared to that of the optional exten-
sions, this turned out to be false. For the suite of simulation
experiments that were run to evaluate these algorithms, the
DIST-M algorithm and its variants always performed as
well as or better than either Algorithm DIST-O or Algorithm
. This makes sense because the optional ex-
FRACTION OF DISCARDED WORK-BIMODAL AND UNIFORMLY DISTRIBUTED PARAMETERS
FENG AND LIU: ALGORITHMS FOR SCHEDULING REAL-TIME TASKS WITH INPUT ERROR AND END-TO-END DEADLINES 13
J:\PRODUCTION\TSE\2-INPROD\S95622\S95622_1.DOC regularpaper97.dot SL 19,968 02/18/97 4:56 PM 13 /tension does not have to be executed in any given schedule
whereas the mandatory extension must always be executed.
When an optional extension is "too long" (e.g., k i and/or
large), the algorithms choose not to schedule it. Further-
more, when the mandatory extensions are small (i.e., h i
and/or m i small), it is easier to compensate for the accumulated
error produced by earlier component tasks by
scheduling the last component task as much as possible.
As stated in Section 5, we could have used a linear-programming
solver to do time distribution for the special
case where the optional error-scaling factors are all zero.
However, when the linear-programming solutions are applied
to the composite tasks in the experimental suite (all of
which have nonzero optional error-scaling factors), the solution
provided by the linear-programming solver gives us
an infeasible time distribution for every composite task
generated in our experiments.
There are many natural extensions of this work including
the generation of other precedence constraint graphs and
more accurate piecewise linear approximations of the extension
functions. For example, we are evaluating the performance
of our algorithms when the extension functions of component
tasks are concave and convex. Yet another extension
would make more of a global decision in assigning time to
the component tasks of a composite task. Specifically, when
the low-level algorithm is unable to schedule the component
tasks of a composite task within its allotted time, the low-level
algorithm could provide feedback to the high-level algorithm
about its additional processing-time needs. If the
high-level algorithm finds other composite tasks that do not
require the entirety of their assigned processing times, the
unschedulable composite task could borrow time from them
in order to become schedulable.

ACKNOWLEDGMENTS

This work was supported in part by the Office of Naval
Resarch under Contract No. N00014-92-J-1146 and the Air
Force Office of Scientific Research under Contract No.
F49620-93-1-0060.



--R

"A Fault-Tolerant Scheduling Problem,"
"Minimizing Mean Weighted Execution Time Loss on Identical and Uniform Processors,"
"Concord: A System of Imprecise Computations,"
"Imprecise Results: Utilizing Partial Computations in Real-Time Systems,"
"A Position Paper for the 1987 IEEE Workshop on Real Time Operating Systems,"
"Performance Evaluation of Scheduling Algorithms for Imprecise Computer Systems,"
"Minimizing Mean Flow Time with Error Constraints,"
"Scheduling Periodic Jobs that Allow Imprecise Results,"
"Minimizing the Number of Late Tasks with Error Constraints,"
"Algorithms for Scheduling Imprecise Computations,"
"Algorithms for Scheduling Imprecise Computations to Minimize Total
"On-Line Scheduling of Imprecise Computations to Minimize
"Scheduling Imprecise Hard Real-Time Jobs with Cumulative

"Algorithms for Scheduling Imprecise Computations with Timing Constraints to Minimize Maximum
"An Analysis of Time-Dependent Plan- ning, "
"Deliberation Scheduling for Problem Solving in Time-Constrained Environments,"
"Constructing Utility-Driven Real-Time Systems Using Anytime Algorithms,"
"Operational Rationality Through Compilation of Anytime Algorithms,"

"CIRCA: The Cooperative Intelligent Real-Time Control Architecture,"

--TR

--CTR
Dong-In Kang , Richard Gerber , Manas Saksena, Parametric Design Synthesis of Distributed Embedded Systems, IEEE Transactions on Computers, v.49 n.11, p.1155-1169, November 2000
K. Subramani, An Analysis of Totally Clairvoyant Scheduling, Journal of Scheduling, v.8 n.2, p.113-133, April     2005
Hakan Aydin , Rami Melhem , Daniel Mosse , Pedro Meja-Alvarez, Optimal Reward-Based Scheduling for Periodic Real-Time Tasks, IEEE Transactions on Computers, v.50 n.2, p.111-130, February 2001
Higinio Mora-Mora , Jernimo Mora-Pascual , Juan Manuel Garca-Chamizo , Antonio Jimeno-Morenilla, Real-time arithmetic unit, Real-Time Systems, v.34 n.1, p.53-79, September 2006
Scott A. Brandt , Gary J. Nutt, Flexible Soft Real-Time Processing in Middleware, Real-Time Systems, v.22 n.1-2, p.77-118, Jan.-March 2002
Vinay Kanitkar , Alex Delis, Real-Time Processing in Client-Server Databases, IEEE Transactions on Computers, v.51 n.3, p.269-288, March 2002
real-time systems and applications;imprecise computation;end-to-end timing constraints;scheduling;error