Guaranteeing Real-Time Requirements With Resource-Based Calibration of Periodic Processes.
This paper presents a comprehensive design methodology for guaranteeing end-to-end requirements of real-time systems. Applications are structured as a set of process components connected by asynchronous channels, in which the endpoints are the systems external inputs and outputs. Timing constraints are then postulated between these inputs and outputs; they express properties such as end-to-end propagation delay, temporal input-sampling correlation, and allowable separation times between updated output values. The automated design method works as follows: First new tasks are created to correlate related inputs, and an optimization algorithm, whose objective is to minimize CPU utilization, transforms the end-to-end requirements into a set of intermediate rate constraints on the tasks. If the algorithm fails, a restructuring tool attempts to eliminate bottlenecks by transforming the application, which is then re-submitted into the assignment algorithm. The final result is a schedulable set of fully periodic tasks, which collaboratively maintain the end-to-end constraints.
Introduction
Most real-time systems possess only a small handful of inherent timing constraints which will "make
or break" their correctness. These are called end-to-end constraints, and they are established on
the systems' external inputs and outputs. Two examples are:
(1) Temperature updates rely on pressure and temperature readings correlated within 10ms.
(2) Navigation coordinates are updated at a minimum rate of 40ms, and a maximum rate 80ms.
But while such end-to-end timing parameters may indeed be few in number, maintaining functionally
correct end-to-end values may involve a large set of interacting components. Thus, to ensure
that the end-to-end constraints are satisfied, each of these components will, in turn, be subject to
their own intermediate timing constraints. In this manner a small handful of end-to-end constraints
may - in even a modest system - yield a great many intermediate constraints.
The task of imposing timing parameters on the functional components is a complex one, and it
mandates some careful engineering. Consider example (2) above. In an avionics system, a "naviga-
tion update" may require such inputs as "current heading," airspeed, pitch, roll, etc; each sampled
within varying degrees of accuracy. Moreover, these attributes are used by other subsystems, each
of which imposes its own tolerance to delay, and possesses its own output rate. Further, the navigation
unit may itself have other outputs, which may have to be delivered at rates faster than
40ms, or perhaps slower than 80ms. And to top it off, subsystems may share limited computer
resources. A good engineer balances such factors, performs extensive trade-off analysis, simulations
and sensitivity analysis, and proceeds to assign the constraints.
These intermediate constraints are inevitably on the conservative side, and moreover, they are
conveyed to the programmers in terms of constant values. Thus a scenario like the following is
often played out: The design engineers mandate that functional units A, B and C execute with
periods 65ms, 22ms and 27ms, respectively. The programmers code up the system, and find that C
grossly over-utilizes its CPU; further, they discover that most of C's outputs are not being read by
the other subsystems. And so, they go back to the engineers and "negotiate" for new periods - for
example 60ms, 10ms and 32ms. This process may continue for many iterations, until the system
finally gets fabricated.
This scenario is due to a simple fact: the end-to-end requirements allow many possibilities for
the intermediate constraints, and engineers make what they consider to be a rational selection.
However, the basis for this selection can only include rough notions of software structuring and
scheduling policies - after all, many times the hardware is not even fabricated at this point!
Our Approach. In this paper we present an alternative strategy, which maintains the timing constraints
in their end-to-end form for as long as possible. Our design method iteratively instantiates
the intermediate constraints, all the while taking advantage of the leeway inherent in the end-to-end
constraints. If the assignment algorithm fails to produce a full set of intermediate constraints, potential
bottlenecks are identified. At this point an application analysis tool takes over, determines
potential solutions to the bottleneck, and if possible, restructures the application to avoid it. The
result is then re-submitted into the assignment algorithm.
Domain of Applicability. Due to the complexity of the general problem, in this paper we place
the following restrictions on the applications that we handle.
Restriction 1: We assume our applications possess three classes of timing constraints which we
call freshness, correlation and separation.
ffl A freshness constraint (sometimes called propagation delay) bounds the time it takes for data to
flow through the system. For example, assume that an external output Y is a function of some
system input X . Then a freshness relationship between X and Y might be: "If Y is delivered
at time t, then the X-value used to compute Y is sampled no earlier than t \Gamma 10ms." We use
the following notation to denote this constraint: "F (Y
ffl A correlation constraint limits the maximum time-skew between several inputs used to produce
an output. For example, if X 1 and X 2 are used to produce Y , then a correlation relationship
may be "if Y is delivered at time t, then the X 1 and X 2 values used to compute Y are sampled
no more than within 2ms of each other." We denote this constraint as "C(Y jX
ffl A separation constraint constrains the jitter between consecutive values on a single output
say Y . For example, "Y is delivered at a minimum rate of 3ms, and a maximum rate
of 13ms," denoted as l(Y
While this constraint classification is not complete, it is sufficiently powerful to represent many
timing properties one finds in a requirements document. (Our initial examples (1) and (2) are
correlation and separation constraints, respectively.) Note that a single output Y 1 may - either
directly or indirectly - be subject to several interdependent constraints. For example, Y 1 might
require tightly correlated inputs, but may abide with relatively lax freshness constraints. However,
perhaps Y 1 also requires data from an intermediate subsystem which is, in turn, shared with a very
high-rate output Y 2 .
Restriction 2: All subsystems execute on a single CPU. Our approach can be extended for use
in distributed systems, a topic we revisit in Section 7. For the sake of presenting the intermediate
constraint-assignment technique, in this paper we limit ourselves to uniprocessor systems.
Restriction 3: The entity-relationships within a subsystem are already specified. For example,
if a high-rate video stream passes through a monolithic, compute-intensive filter task, this situation
may easily cause a bottleneck. If our algorithm fails to find a proper intermediate timing constraint
for the filter, the restructuring tool will attempt to optimize it as much as possible. In the end,
however, it cannot redesign the system.
Finally, we stress that we are not offering a completely automatic solution. Even with a fully
periodic task model, assigning periods to the intermediate components is a complex, nonlinear
optimization problem which - at worst - can become combinatorially expensive. As for software
restructuring, the specific tactics used to remove bottlenecks will often require user interaction.
Problem and Solution Strategy. We duly note the above restrictions, and tackle the intermediate
constraint-assignment problem, as rendered by the following ingredients:
ffl A set of external inputs fX g, and the end-to-end constraints
between them.
ffl A set of intermediate component tasks f g.
ffl A task graph, denoting the communication paths from the inputs, through the tasks, and to
outputs.
Solving the problem requires setting timing constraints for the intermediate components, so that
all end-to-end constraints are met. Moreover, during any interval of time utilization may never
exceed 100%.
Our solution employs the following ingredients: (1) A periodic, preemptive tasking model (where
it is our algorithm's duty to assign the rates); (2) a buffered, asynchronous communication scheme,
allowing us to keep down IPC times; (3) the period-assignment, optimization algorithm, which
forms the heart of the approach; and (4) the software-restructuring tool, which takes over when
period-assignment fails.
Related Work. This research was, in large part, inspired by the real-time transaction model
proposed by Burns et. al. in [3]. While the model was formulated to express database applications,
it can easily incorporate variants of our freshness and correlation constraints. In the analogue to
freshness, a persistent object has "absolute consistency within t" when it corresponds to real-world
samples taken within maximum drift of t. In the analogue to correlation, a set of data objects
possesses "relative consistency within t" when all of the set's elements are sampled within an
interval of time t.
We believe that in output-driven applications of the variety we address, separation constraints
are also necessary. Without postulating a minimum rate requirement, the freshness and correlation
constraints can be vacuously satisfied - by never outputting any values! Thus the separation
constraints enforce the system's progress over time.
Burns et. al. also propose a method for deriving the intermediate constraints; as in the data
model, this approach was our departure point. Here the high-level requirements are re-written as
a set of constraints on task periods and deadlines, and the transformed constraints can hopefully
be solved. There is a big drawback, however: the correlation and freshness constraints can inordinately
tighten deadlines. E.g., if a task's inputs must be correlated within a very tight degree of
accuracy - say, several nanoseconds - the task's deadline has to be tightened accordingly. Similar
problems accrue for freshness constraints. The net result may be an over-constrained system, and
a potentially unschedulable one.
Our approach is different. With respect to tightly correlated samples, we put the emphasis on
simply getting the data into the system, and then passing through in due time. However, since
this in turn causes many different samples flowing through the system at varying rates, we perform
"traffic control" via a novel use of "virtual sequence numbering." This results in significantly looser
periods, constrained mainly by the freshness and separation requirements. We also present a period
assignment problem which is optimal - though quite expensive in the worst case.
This work was also influenced by Jeffay's ``real-time producer/consumer model'' [10], which
possesses a task-graph structure similar to ours. In this model rates are chosen so that all messages
"produced" are eventually "consumed." This semantics leads to a tight coupling between the
execution of a consumer to that of its producers; thus it seems difficult to accommodate relative
constraints such as those based on freshness.
Klein et. al. surveys the current engineering practice used in developing industrial real-time
systems [11]. As is stressed, the intermediate constraints should be primarily a function of the
end-to-end constraints, but should, if possible, take into account sound real-time scheduling tech-
niques. At this point, however, the "state-of-the-art" is the practice of trial and error, as guided
by engineering experience. And this is exactly the problem we address in this paper.
The remainder of the paper is organized as follows. In Section 2 we introduce the application
model and formally define our problem. In Section 3 we show our method of transforming
the end-to-end constraints into intermediate constraints on the tasks. In Section 4 we describe
the constraint-solver in detail, and push through a small example. In Section 5 we describe the
application transformer, and in Section 6 we show how the executable application is finally built.
Problem Description and Overview of Solution
We re-state our problem as follows:
ffl Given a task graph with end-to-end timing constraints on its inputs and outputs,
ffl Derive periods, offsets and deadlines for every task,
ffl Such that the end-to-end requirements are met.
In this section we define these terms, and present an overview of our solution strategy.
2.1 The Asynchronous Task Graph
An application is rendered in an asynchronous task graph (ATG) format, where for a given graph
i.e., the set of tasks; and g, a set of
asynchronous, buffered channels. We note that the external outputs and inputs are simply
typed nodes in D.
(D \Theta P ) is a set of directed edges, such that if  are both
in E, then  . That is, each channel has a single-writer/multi-reader restriction.
have the following attributes: a period T i , an offset O i  0 (denoting the earliest
start-time from the start-of-period), a deadline D i  T i (denoting the latest finish-time relative
to the start-of-period), and a maximum execution time e i . The interval [O constrains
the window W i of execution, where W
Note that initially the T i 's, O i 's and D i 's are open variables, and they get instantiated by the
constraint-solver.
The semantics of an ATG is as follows. Whenever a task  i executes, it reads data from all
incoming channels d j corresponding to the edges d j !  i , and writes to all channels d l corresponding
to the edges  i ! d l . The actual ordering imposed on the reads and writes is inferred by the task
All reads and writes on channels are asynchronous and non-blocking. While a writer always
inserts a value onto the end of the channel, a reader can (and many times will) read data from
any location. For example, perhaps a writer runs at a period of 20ms, with two readers running at
120ms and 40ms, respectively. The first reader may use every sixth value (and neglect the others),
whereas the second reader may use every other value.
But this scheme raises a "chicken and egg" issue, one of many that we faced in this work. One
of our objectives is to support software reuse, in which functional components may be deployed
in different systems - and have their timing parameters automatically calibrated to the physical
limitations of each. But this objective would be hindered if a designer had to employ the following
tedious method: (1) to first run the constraint-solver, which would find the T i 's, and then, based
on the results; (2) to hand-patch all of the modules with specialized IPC code, ensuring that the
intermediate tasks correctly correlate their input samples.
Luckily, the ATG semantics enables us to automatically support this process. Consider the
ATG in

Figure

1(A), whose node  4 is "blown up" in Figure 1(B). As far as the programmer is
concerned the task  4 has a (yet-to-be-determined) period T 4 , and a set of asynchronous channels,
accessible via generic operations such as "Read" and "Write." Moreover, the channels can be
treated both as unbounded, and as non-blocking.
After the constraint-assignment algorithm determines the task rates, a post-processing phase
determines the actual space required for each channel. Then they are automatically implemented
as circular, slotted buffers. This is accomplished by running an "awk" script on each module, which
instantiates each "Read" and "Write" operation to select the correct input value.
This type of scheme allows us to minimize the overhead incurred when blocking communication
is used, and to concentrate exclusively on the assignment problem. In fact - as we show in the
sequel - communication can be completely unconditional, in that we do not even require short
locking for consistency. However, we pay a price for avoiding this overhead; namely, that the
period assignments must ensure that no writer can overtake a reader currently accessing its slot.
Moreover, we note that our timing constraints define a system driven by time and output re-
quirements. This is in contrast to reactive paradigms such as ESTEREL [4], which are input-driven.
Analogous to the "conceptually infinite buffering" assumptions, the rate assignment algorithm assumes
that the external inputs are always fresh and available. The derived input-sampling rates
then determine the true requirements on input-availability. And since an input X can be connected
to another ATG's output Y , these requirements would be imposed on Y 's timing constraints.
d1 d2
6
f
Write(&Y1, res);

Figure

1: (A) A task graph and (B) code for  4 .
2.2 A Small Example
As a simple illustration, consider the system whose ATG is shown in Figure 1(A). The system
is composed of six interacting tasks with three external inputs and two external outputs. The
application's characteristics are as follows:
Freshness F (Y 1
Correlation
Separation
Max Execution e
Times: e
While the system is small, it serves to illustrate several facets of the problem: (1) There may
be many possible choices of rates for each task; (2) correlation constraints may be tight compared
to the allowable end-to-end delay; (3) data streams may be shared by several outputs (in this case
that originating at X 2 ); and (4) outputs with the tightest separation constraints may incur the
highest execution-time costs (in this case Y 1 , which exclusively requires  1 ).
2.3 Problem Components
Guaranteeing the end-to-end constraints actually poses three sub-problems, which we define as
follows.
Correctness: Let C be the set of derived, intermediate constraints and E be the set of end-to-end
constraints. Then all system behaviors that satisfy C also satisfy E .
Feasibility: The task executions inferred by C never demand an interval of time during which
utilization exceeds 100%.
Schedulability: There is a scheduling algorithm which can efficiently maintain the intermediate
constraints C, and preserve feasibility.
In the problem we address, the three issues cannot be decoupled. Correctness, for example, is often
treated as verification problem using a logic such as RTL [9]. Certainly, given the ATG we could
formulate E in RTL and query whether the constraint set is satisfiable. However, a "yes" answer
would give us little insight into finding a good choice for C - which must, after all, be simple enough
to schedule. Or, in the case of methods like model-checking ([1], etc.), we could determine whether
C)E is invariant with respect to the system. But again, this would be an a posteriori solution, and
assume that we already possess C. On the other hand, a system that is feasible may still not be
schedulable under a known algorithm; i.e., one that can be efficiently managed by a realistic kernel.
In this paper we put our emphasis on the first two issues. However, we have also imposed a task
model for which the greatest number of efficient scheduling algorithms are known: simple, periodic
dispatching with offsets and deadlines. In essence, by restricting C's free variables to the T i 's, O i 's
and D i 's, we ensure that feasible solutions to C can be easily checked for schedulability.
The problem of scheduling a set of periodic real-time tasks on a single CPU has been studied
for many years. Such a task set can be dispatched by a calendar-based, non-preemptive schedule
(e.g., [16, 17, 18]), or by a preemptive, static-priority scheme (e.g., [5, 12, 13, 15]). For the most
part our results are independent of any particular scheduling strategy, and can be used in concert
with either non-preemptive or preemptive dispatching.
However, in the sequel we frequently assume an underlying static-priority architecture. This is
for two reasons. First, a straightforward priority assignment can often capture most of the ATG's
precedence relationships, which obviates the need for superfluous offset and deadline variables.
Thus the space of feasible solutions can be simplified, which in turn reduces the constraint-solver's
work. Second, priority-based scheduling has recently been shown to support all of the ATG's
inherent timing requirements: pre-period deadlines [2], precedence constrained sub-tasks [8], and
offsets [14]. A good overview to static priority scheduling may be found in [5].
2.4 Overview of the Solution
Our solution is carried out in a four-step process, as shown in Figure 2. In Step 1, the intermediate
constraints C are derived, which postulates the periods, deadlines and offsets as free variables. The
challenge here is to balance several factors - correctness, feasibility and simplicity. That is, we
failure
Constraint
Derivation
Asynchronous
Task Graph
Constraints
Restructuring
Tool
Constraint
Satisfaction
Feasible
Task Set
Buffer
Allocation
Final
Task Set
Application Structure.
End-to-end Constraints.
Task Libraries.

Figure

2: Overview of the approach.
require that any solution to C will enforce the end-to-end constraints E , and that any solution must
also be feasible. At the same time, we want to keep C as simple as possible, and to ensure that
finding a solution is a relatively straightforward venture. This is particularly important since the
feasibility criterion - defined by CPU utilization - introduces non-linearities into the constraint
set. In balancing our goals we impose additional structure on the application; e.g., by creating new
sampler tasks to get tightly correlated inputs into the system.
In Step 2 the constraint-solver finds a solution to C, which is done in several steps. First C is
solved for the period variables, the T i 's, and then the resulting system is solved for the offsets and
deadlines. Throughout this process we use several heuristics, which exploit the ATG's structure.
If a solution to C cannot be found, the problem often lies in the original design itself. For
example, perhaps a single, stateless server handles inputs from multiple clients, all of which run at
wildly different rates. Step 3's restructuring tool helps the programmer eliminate such bottlenecks,
by automatically replicating strategic parts of the ATG.
In Step 4, the derived rates are used to reserve memory for the channels, and to instantiate
the "Read" and "Write" operations. For example, consider  4 in Figure 1(B), which reads from
Now, assume that the constraint-solver assigns  4 and  2 periods of 30ms and 10ms, respectively.
Then  4 's Read operation on d 2 would be replaced by a macro, which would read every third data
item in the buffer - and would skip over the other two.
Harmonicity. The above scheme works only if a producer can always ensure that it is not
overtaking its consumers, and if the consumers can always determine which data item is the correct
one to read. For example,  4 's job in managing d 2 is easy - since T
read every third item out of the channel.
But  4 has another input channel, d 1 ; moreover, temporally correlated samples from the two
channels have to be used to produce a result. What would happen if the solver assigned  1 a period
of 30ms, but gave  2 a period of 7ms?
If the tasks are scheduled in rate-monotonic order, then d 2 is filled five times during  4 's first
frame, four times during the second frame, etc. In fact since and 7 are relatively prime,  4 's
selection logic to correlate inputs would be rather complicated. One solution would be to time-stamp
each input X 1 and X 2 , and then pass these stamps along with all intermediate results. But
this would assume access to a precise hardware timer; moreover, time-stamps for multiple inputs
would have to be composed in some manner. Worst of all, each small data value (e.g., an integer)
would carry a large amount of reference information.
The obvious solution is the one that we adopt: to ensure that every "chain" possesses a common
base clock-rate, which is exactly the rate of the task at the head of the chain. In other words, we
impose a harmonicity constraint between (producer, consumer) pairs; (i.e., pairs
are edges  p ! d and d !  c .)
Definition 2.1 (Harmonicity) A task  2 is harmonic with respect to a task  1 if T 2 is exactly
divisible by T 1 ( represented as T 2 jT 1
Consider Figure 1(A), in which there are three chains imposing harmonic relationships. In this
tightly coupled system we have that T 4
Deriving the Constraints
In this section we show the derivation process of intermediate constraints, and how they (conser-
vatively) guarantee the end-to-end requirements. We start the process by synthesizing the intermediate
correlation constraints, and then proceed to treat freshness and separation.
3.1 Synthesizing Correlation Constraints
Recall our example task graph in Figure 3(A), where the three inputs are sampled
by three separate tasks. If we wish to guarantee that  1 's sampling of X 1 is correctly correlated
to  2 's sampling of X 2 , we must pick short periods for both  1 and  2 . Indeed, in many practical
real-time systems, the correlation requirements may very well be tight, and way out of proportion
with the freshness constraints. This typically results in periods that get tightened exclusively to
accommodate correlation, which can easily lead to gross over-utilization. Engineers often call this
problem "over-sampling," which is somewhat of a misnomer, since sampling rates may be tuned
expressly for coordinating inputs. Instead, the problem arises from poor coupling of the sampling
and computational activities.
Thus our approach is to decouple these components as much as possible, and to create specialized
samplers for related inputs. For a given ATG, the sampler derivation is performed in the following
manner.
is an integer.
d1 d2
6
s
dX1 dX2 dX3
d1 d2
6

Figure

3: (A) Original task graph and (B) transformed task graph.
foreach Correlation constraint C l (Y k jX l 1
Create the set of all input-output pairs associated with C l , i.e.,
foreach T l , foreach T k
If there's a common input X such that there exist outputs Y
with
if chains from X to Y i and X to Y j share a common task, then
foreach T l , identify all associated sampling tasks, i.e.,
If jS l j ? 1, create a periodic sampler  s l
to take samples for inputs in T l
Thus the incoming channels from inputs T l to tasks in S l are "intercepted" by the new sampler
task  s l .
Returning to our original example, which we repeat in Figure 3(A). Since both correlated inputs
share the center stream, the result is a single group of correlated inputs )g. This, in
turn, results in the formation of the single sampler  s . We assume  s has a low execution cost of 1.
The new, transformed graph is shown at the right column of Figure 3(B).
As for the deadline-offset requirements, a sampler  s l
is constrained by the following trivial
relationship
where t cor is the maximum allowable time-drift on all correlated inputs read by  s l
The sampler tasks ensure that correlated inputs are read into the system within their appropriate
time bounds. This allows us to solve for process rates as a function of both the freshness and
separation constraints, which vastly reduces the search space.
However we cannot ignore correlation altogether, since merely sampling the inputs at the same
time does not guarantee that they will remain correlated as they pass through the system. The
input samples may be processed by different streams (running at different rates), and thus they
may still reach their join points at different absolute times.
For example, refer back to Figure 3, in which F (Y 2 This disparity is the result
of an under-specified system, and may have to be tightened. The reason is simple: if  6 's period
is derived by using correlation as a dominant metric, the resulting solution may violate the tighter
freshness constraints. On the other hand, if freshness is the dominant metric, then the correlation
constraints may not be achieved.
We solve this problem by eliminating the "noise" that exists between the different set of require-
ments. Thus, whenever a fresh output is required, we ensure that there are correlated data sets to
produce it. In our example this leads to tightening the original freshness requirement F (Y 2 jX 2 ) to
Thus we invoke this technique as a general principle. For an output Y with correlated input
sets the associated freshness constraints are adjusted accordingly:
3.2 Synthesizing Freshness Constraints
Consider a freshness constraint F (Y recall its definition:
For every output of Y at some time t, the value of X used to compute Y must have
been read no earlier that time
As data flows through a task chain from X to Y , each task  adds two types of delay overhead to
the data's end-to-end response time. One type is execution time, i.e., the time required for  to
process the data, produce outputs, etc. In this paper we assume that  's maximum execution time
is fixed, and has already been optimized as much as possible by a good compiler.
The other type of delay is transmission latency, which is imposed while  waits for its correlated
inputs to arrive for processing. Transmission time is not fixed; rather, it is largely dependent on
our derived process-based constraints. Thus minimizing transmission time is our goal in achieving
tight freshness constraints.
Fortunately, the harmonicity relationship between producers and consumers allows us to accomplish
this goal. Consider a chain  is the output task, and  1 is the input
Y
O 1
O 2
O 3
1. Harmonicity: T 2
2. Precedence:  1 OE  2 OE  3
3. Chain Size: D
Constraints

Figure

4: Freshness constraints with coupled tasks.
task. From the harmonicity constraints we get T Assuming that all tasks are
started at time 0, whenever there is an invocation of the output task  n , there are simultaneous
invocations of every task in the freshness chain.
Consider Figure 4 in which there are three tasks  1 ;  2 and  3 in a freshness chain. From the
harmonicity assumption we have T 3 jT 2 and T 2 jT 1 .
The other constraints are derived for the entire chain, under the scenario that within each task's
minor frame, input data gets read in, it gets processed, and output data is produced. Under these
constraints, the worst case end-to-end delay is given by D and the freshness requirement is
guaranteed if the following holds:
Note that we also require a precedence between each producer/consumer task pair. As we show in

Figure

4, this can be accomplished via the offset and deadline variables - i.e., by mandating that
But this approach has the following obvious drawback: The end-to-end freshness t f must be
divided into fixed portions of slack at each node. On a global system-wide level, this type of rigid
flow control is not the best solution. It is not clear how to distribute the slack between intermediate
tasks, without over-constraining the system. More importantly, with a rigid slack distribution, a

Table

1: Constraints due to freshness requirements.
consumer task would not be allowed to execute before its offset, even if its input data is available. 2
Rather, we make a straightforward priority assignment for the tasks in each chain, and let
the scheduler enforce the precedence between them. In this manner, we can do away with the
intermediate deadline and offset variables. This leads to the following rule of thumb:
If the consumer task is not the head or tail of a chain, then its precedence requirement
is deferred to the scheduler. Otherwise, the precedence requirement is satisfied through
assignment of offsets.
Example. Consider the freshness constraints for our example in Figure 3(A), F (Y 1
15. The requirement F (Y 1 specifies a
chain window size of D 4 \Gamma O s  30. Since  1 is an intermediate task we now have the precedence
s OE  1 , which will be handled by the scheduler. However, according to our "rule of thumb," we
use the offset for  4 to handle the precedence  1 OE  4 . This leads to the constraints D 1  O 4 and
Similar inequalities are derived for the remaining freshness constraints, the result
of which is shown in Table 1.
3.3 Output Separation Constraints
Consider the separation constraints for an output Y , generated by some task  i . As shown in

Figure

5, the window of execution defined by O i and D i constrains the time variability within a
period. Consider two frames of  i 's execution. The widest separation for two successive Y 's can
occur when the first frame starts as early as possible, and the second starts as late as possible.
Conversely, the opposite situation leads to the smallest separation.
Thus, the separation constraints will be satisfied if the following holds true:
2 Note that corresponding issues arise in real-time rate-control in high-speed networks.
O i
O i
Y latest
Y latest
Y earliest
Y earliest

Figure

5: Separation constraints for two frames.
Example. Consider the constraints that arise from output separation requirements, which are
induced on the output tasks  4 and  6 . The derived constraints are presented below:
3.4 Execution Constraints:
Clearly, each task needs sufficient time to execute. This simple fact imposes additional constraints,
that ensure that each task's maximum execution time can fit into its window. Recall that (1) we
use offset, deadline and period variables for tasks handling external input and output; and (2) we
use period variables and precedence constraints for the intermediate constraints.
We can easily preserve these restrictions when dealing with execution time. For each external
task  i , the following inequalities ensure that window-size is sufficiently large for the CPU demand:
On the other hand, the intermediate tasks can be handled by imposing restrictions on their constituent
chains. For a single chain, let E denote the chain's execution time from the head to the
last intermediate task (i.e., excluding the outputting task, if any). Then the chain-wise execution
constraints are:
O h +E  Dm ; Dm  Tm
where O h is the head's offset, and where Dm and Tm are the last intermediate task's deadline and
period, respectively.
Example. Revisiting the example, we have the following execution-time constraints.
This completes the set of task-wise constraints C imposed on our ATG. Thus far we have shown
only one part of the problem - how C can derived from the end-to-end constraints. The end-to-
requirements will be maintained during runtime (1) if a solution to C is found, and (2) if the
scheduler dispatches the tasks according to the solution's periods, offsets and deadlines. Since
there are many existing schedulers that can handle problem (2), we now turn our attention to
problem (1).
2: Constraint Solver
The constraint solver generates instantiations for the periods, deadlines and offsets. In doing so,
it addresses the notion of feasibility by using objective functions which (1) minimize the overall
system utilization; and (2) maximize the window of execution for each task. Unfortunately, the
non-linearities in the optimization criteria - as well as the harmonicity assumptions - lead to a
very complex search problem.
We present a solution which decomposes the problem into relatively tractable parts. Our
decomposition is motivated by the fact that the non-linear constraints are confined to the period
variables, and do not involve deadlines or offsets. This suggests a straightforward approach, which
is presented in Figure 6.
1. The entire constraint set C is projected onto its subspace "
C, constraining only the T i 's.
2. The constraint set "
C is optimized for minimum utilization.
3. Since we now have values for the T i 's, we can instantiate them in the original constraint set
C. This forms a new, reduced set of constraints
C, all of whose functions are affine in the O i 's
and D i 's. Hence solutions can be found via linear optimization.
The back-edge in Figure 6 refers to the case where the nonlinear optimizer finds values for the
no corresponding solution exists for the O i 's and D i 's. Hence, a new instantiation for the
periods must be obtained - a process that continues until either a solution is found, or all possible
values for the T i 's are exhausted.
4.1 Elimination of Offset and Deadline Variables
We use an extension of Fourier variable elimination [6] to simplify our system of constraints. Intu-
itively, this step may be viewed as the projection of an n dimensional polytope (described by the
constraints) onto its lower-dimensional shadow.
Non-Linear Constraints on:
Linear Constraints on:
Non-linear Constraints on:
Eliminate O i and D i .
Optimize w.r.t. min(U ).
Optimize w.r.t. min(D
Solution

Figure

Top level algorithm to obtain task characteristics.
In our case, the n-dimensional polytope is the object described by the initial constraint set C,
and where the shadow is the subspace "
C, in which only the T i 's are free. The shadow is derived by
eliminating one offset (or deadline) variable at a time, until only period variables remain. At each
stage the new set of constraints is checked for inconsistencies (e.g., 0 ? 5). Such a situation means
that the original system was over-specified - and the method terminates with failure.
The technique can best be illustrated by a small example. Consider the following two inequalities
on W
Each constraint defines a line; when W 4 and T 4 are restricted to nonzero solutions, the result is a
2-dimensional polygon. Eliminating the variable W 4 is simple, and is carried out as follows:
Since we are searching for integral, nonzero solutions to T 4 , any integer in can be considered
a candidate.
When there are multiple constraints on W 4 - perhaps involving many other variables - the same
Y

Figure

7: Variable elimination for integer solutions - A deviant case.
process is used. Every constraint "W 4 combined with every other constraint "W 4
until W 4 has been eliminated. The correctness of the method follows simply from the polytope's
convexity, i.e., if the original set of constraints has a solution, then the solution is preserved in the
shadow.
Unfortunately, the opposite is not true; hence the the requirement for the back-edge in Figure 6.
As we have stated, the refined constraint set "
C may possess a solution for the T i 's that do not
correspond to any integral-valued O i 's and D i 's. This situation occasionally arises from our quest
for integer solutions to the T i 's - which is essential in preserving our harmonicity assumptions.
For example, consider the triangle in Figure 7. The X-axis projection of the triangle has seven
integer-solutions. On the other hand, none exist for Y , since all of the corresponding real-valued
solutions are "trapped" between 1 and 2.
If, after obtaining a full set of T i 's, we are left without integer values for the O i 's and D i 's, we
can resort to two possible alternatives:
1. Search for rational solutions to the offsets and deadlines, and reduce the clock-granularity
accordingly, or
2. Try to find new values for the T i 's, which will hopefully lead to a full integer solution.
The Example Application - From C to "
C. We illustrate the effect of variable elimination on
the example application presented earlier. The derived constraints impose lower and upper bounds
on task periods, and are shown below. Also remaining are the original harmonicity constraints.
Linear
Constraints
Harmonicity
Constraints
Utilization-Based Pruning
LCM Child Pruning
Search Solution
Harmonic Chain Merging

Figure

8: Finding the T 's - Pruning.
Here the constraints on the output tasks ( 4 and  6 ) stem from the separation constraints, which
impose upper and lower bounds on the periods.
4.2 From "
C to
C: Deriving the Periods
Once the deadlines and offsets have been eliminated, we have a set of constraints involving only
the task periods. The objective at this point is to obtain a feasible period assignment which (1)
satisfies the derived linear equations; (2) satisfies the harmonicity assumptions; and (3) is subject
to a realizable utilization, i.e.,
1.
As in the example above, the maximum separation constraints will typically mandate that the
solution-space for each T i be bounded from above. Thus we are faced with a decidable problem -
albeit a complex one. In fact there are cases which will defeat all known algorithms. In such cases
there is no alternative to traversing the entire Cartesian-space
where there are n tasks, and where each T i may range within [l
Fortunately the ATG's structure gives rise to four heuristics, each of which can aggressively
prune the search space. The strategy is pictorially rendered in Figure 8.
Let Pred(i) (Succ(i)) denote the set of tasks which are predecessors (successors) of task  i , i.e.,
those tasks from (to) which there is a directed path to (from)  i . Since the harmonicity relationship
is transitive, we have that if  j 2 Succ( i ), it follows that T j jT i . This simple fact leads to three of
our four heuristics.
Harmonic Chain Merging extends from following observation: we do not have to solve for each
it is an arbitrary variable in an arbitrary function. Rather, we can combine chains of
processes, and then solve for their base periods. This dramatically reduces the number of free
variables.
GCD Parent Pruning is used to ensure that the head of each chain forms a greatest-common-
divisor for the entire chain. All tuples which violate this property are deleted from the set of
candidate solutions.
Utilization Pruning ensures that candidate solutions maintain a CPU utilization under 100%,
a rather desirable constraint in a hard real-time system.
LCM Child Pruning takes an opposite approach to GCD Parent Pruning. It ensures that a
task's period is a multiple of its predecessors' combined LCM. Since this is the most expensive
pruning measure, it is saved for last.
Harmonic Chain Merging. The first step in the pruning process extends from a simple, but
frequently overlooked, observation: that tasks often over-sample for no discernible reason, and that
unnecessarily low T i 's can easily steal cycles from the tasks that truly need them. For our purposes,
this translates into the following rule:
If a task  i executes with period T i , and if some  j 2 has the property that
should also execute with period T i .
In other words, we will never run a task faster than it needs to be run. In designs where the
periods are ad-hoc artifacts, tuned to achieve the end-to-end constraints, such an approach would
be highly unsafe. Here the rate constraints are analytically derived directly from the end-to-end
requirements. We know "how fast" a task needs to be run, and it makes no sense to run it faster.
This allows us to simplify the ATG by merging nodes, and to limit the number of free variables
in the problem. The method is summed up in the following steps:
consequently, T i  T j . The first pruning takes place by
propagating this information to tighten the period bounds. Thus, for each task  i , the bounds are
tightened as follows:
(2) The second step in the algorithm is to simplify the task graph. Consider a task  i , which
has an outgoing edge . Then the maximum value of T i is constrained only
by harmonicity restrictions. The simplification is done by merging  i and  j , whenever it is safe
to set T i.e., the restricted solution space contains the optimal solution. The following two
rules give the condition when it safe to perform this simplification.
Rule 1: If a vertex  i has a single outgoing edge merged with  j .
Rule 2: If Succ( i merged with
Consider the graph in Figure 9. The parenthesized numbers denote the costs of corresponding
nodes. In the graph, the nodes  3 ,  5 , and  1 have a single outgoing edge. Using Rule 1, we
s (1)
1;4 (8)
6 (2)
3;5;6 (8)
1;4 (8)
s (1)
3;5;6 (8)

Figure

9: Task graph for harmonicity and its simplification.
merge  3 and  5 with  6 , and  1 with  4 . In the simplified graph, Succ( s and
g. Thus, we can invoke Rule 2 to merge  s with  2 .
This scheme manages to reduce our original seven tasks to three sets of tasks, where each set
can be represented as a pseudo-task with its own period, and an execution time equal to the sum
of its constituent tasks.
At this point we have reduced the structure of the ATG as much as possible, and we turn
to examining the search space itself. But even here, we can still use the harmonicity restrictions
and utilization bounds as aggressively as possible, with the objective of limiting our search. Let
\Phi denote the set of feasible solutions for a period T i , whose initial solution space is denoted as
g. The pruning takes place by successively refining and restricting \Phi i for
each task.
Algorithm 4.1 combines our three remaining pruning techniques - GCD Parent Pruning, Utilization
Pruning and LCM Child Pruning. In the following paragraphs, we explain these steps in
detail, and show how they are applied to our example.
GCD Parent Pruning. Consider any particular node  i in the task graph. The feasible set
of solutions for this node can be reduced by considering the harmonicity relationship with all its
successor nodes.
That is, we restrict \Phi i to values that can provide a base clock-rate for all successor tasks.
Algorithm 4.1 Prune Feasible Search Space using Harmonicity and Utilization constraints.
allowable utilization. */
Sort the graph in reverse topological order. Let the sorted list be
for to n do /* traverse the list */
/* check utilization condition for each value in \Phi i j
*/
foreach do
foreach
U min := U min \Gamma U min
U
/* Propagate restricted feasible set to all successors */
foreach

Figure

10: Pruning feasible space for period derivation.
Within our example, our three merged tasks have the following allowable ranges:
The sampler task's period is restricted to values with integral multiples in both \Phi 1;4 and \Phi 3;5;6 .
After deleting members of \Phi s;2 that fail to satisfy this property, we are left with the following
reduced set:
Utilization-Based Pruning. Let U max be the upper bound on the utilization that we wish to
achieve. At any stage, a lower bound on the utilization for task  i is given by:
U min
If the lower bound on overall utilization U min (=
then there is no solution
which satisfies the utilization bound. Now, consider a single task  ' , and consider a value "
T k for all other tasks as follows:
T ' is the period for  ' , a lower bound on the utilization is given by:
Clearly, if U ? Umax , then no feasible solution can be obtained with "
hence it may be
removed from the feasible set.
Returning to our example, at this point we have the following solution space:
Since  1;4 and  3;5;6 have no successors, and the utilization bounds are satisfied for all values, no
restriction takes place. Now we consider  s;2 , whose period comes from our original sampler task.
After testing the possible solutions for utilization, we obtain the reduced set \Phi 14g.
LCM Child-Pruning. In general, there may be several chains, each of whose tasks has been
restricted by the utilization test. (In our case we only have two chains which share a common
source.) In the general case, the reduced feasible set for each task  i may be propagated to all
successors  k . This is done by restricting T k to integer multiples of T i .
When we follow this approach in our example, we end up with the following solution space:
If our objective is to achieve optimality, then examining the remaining candidate solutions is probably
unavoidable. In this case, the optimal solution is easily found to be T
42, giving a utilization of 0:7619.
If the remaining solution-space is large, a simple a branch-and-bound heuristic can be employed
to control the search. By carefully setting the utilization bound, we can limit the search time
required, since the tighter the utilization bound, the greater is the pruning achieved. Thus, by
starting with a low utilization bound, and successively increasing it, we can reduce the amount of
search time required to achieve optimally low utilization.
However, if the objective is simply finding a solution - any solution - then any of the remaining
candidates can be selected.
4.3 Deriving Offsets and Deadlines
Once the task periods are determined, we need to revisit the constraints to find a solution to the
deadlines and offsets of the periods. This involves finding a solution which maximizes schedulability.
Variable elimination allows us to select values in the reverse order in which they are eliminated.
Suppose we eliminated in following When variable x i is eliminated, the
remaining free variables are [x are already bound to values, the
constraints immediately give a lower and an upper bound on x i .
We use this fact in assigning offsets and deadlines to the tasks. As the variables are assigned
values, each variable can be individually optimized. Recall that the feasibility of a task set requires
that the task set never demand a utilization greater than one in any time interval. We use a greedy
heuristic, which attempts to maximize the window of execution for each task. For tasks which
do not have an offset, this is straightforward, and can be achieved by maximizing the deadline.
For input/output tasks which have offsets, we also need to fix the position of the window on the
time-line. We do this by minimizing the offset for input tasks, and maximizing the deadline for
output tasks.
The order in which the variables are assigned is given by the following strategy: First, we assign
the windows for each input task, followed by the windows for each output task. Then, we assign
the offsets for each task followed by deadline for each output task. Finally, the deadlines for the
remaining tasks are assigned in a reverse topological order of the task graph. Thus, an assignment
ordering for the example application is given as fW s g. The final
parameters, derived as a result of this ordering, are shown below.
Period 14 28 14 42 28 42 42
Offset
Deadline 3
A feasible schedule for the task set is shown in Figure 11. We note that the feasible schedule can
be generated using the fixed priority ordering  s
5 Step 3: Graph Transformation
When the constraint-solver fails, replicating part of a task graph may often prove useful in reducing
the system's utilization. This benefit is realized by eliminating some of the tight harmonicity

Figure

Feasible schedule for example application.
requirements, mainly by decoupling the tasks that possess common producers. As a result, the
constraint derivation algorithm has more freedom in choosing looser periods for those tasks.
Recall the example application from Figure 3(B), and the constraints derived in Section 4. In
the resulting system, the producer/consumer pair has the largest period difference
and 42). Note that the constraint solver mandated a tight period for  2 , due to the coupled
harmonicity requirements T 4 jT 2 and T 5 jT 2 . Thus, we choose to replicate the chain including  2 from
the sampler ( s ) to data object d 2 . This decouples the data flow to Y 1 from that to Y 2 . Figure 12
shows the result of the replication.
6
d2
Figure

12: The replicated task graph.
Running the constraint derivation algorithm again with the transformed graph in Figure 12, we
obtain the following result. The transformed system has a utilization of 0.6805, which is significantly
lower than that of the original task graph (0.7619).
Periods
The subgraph replication technique begins with selecting a producer/consumer pair which requires
replication. There exist two criteria in selecting a pair, depending on the desired goal. If
the goal is reducing expected utilization, a producer/consumer pair with the maximum period difference
is chosen first. On the other hand, if the goal is achieving feasibility, then we rely on the
feedback from the constraint solver in determining the point of infeasibility.
After a producer/consumer pair is selected, the algorithm constructs a subgraph using a backward
traversal of the task graph from the consumer. In order to avoid excessive replication, the
traversal is terminated at the first confluence point. The resulting subgraph is then replicated and
attached to the original graph.
The producer task in a replication may, in turn, be further specialized for the output it serves.
For example, consider a task graph with two consumers  c1 and  c2 and a common producer  p .
If we replicate the producer, we have two independent producer/consumer pairs, namely
only serves  c2 , we can eliminate all operations that only contribute to the
output for  c1 . This is done by dead code elimination, a common compiler optimization. The same
specialization is done for  p .
6 Step 4: Buffer Allocation
Buffer allocation is the final step of our approach, and hence applied to the feasible task graph
whose timing characteristics are completely derived. During this step, the compiler tool determines
the buffer space required by each data object, and replaces its associated reads and writes with
simple macros. The macros ensure that each consumer reads temporally correlated data from
several data objects - even when these objects are produced at vastly different rates. The reads
and writes are nonblocking and asynchronous, and hence we consider each buffer to have a "virtual
sequence number."
Combining a set of correlated data at a given confluence point appears to be a nontrivial
venture. After all, (1) producers and the consumers may be running at different rates; and (2) the
flow delays from a common sampler to the distinct producers may also be different. However, due
to the harmonicity assumption the solution strategy is quite simple. Given that there are sufficient
buffers for a data object, the following rule is used:
"Whenever a consumer reads from a channel, it uses the first item that was generated
within its current period."
For example, let  p be a producer of a data object d, let  c 1
cn be the consumers that
read d. Then the communication mechanism is realized by the following techniques (where
LCM 1in (T c i ) is the least common multiple of the periods):
(1) The data object d is implemented with buffers.
(2) The producer  p circularly writes into each buffer, one at a time.
(3) The consumer  c i reads circularly from slots (0; T c i =T

Figure

13: A task graph with buffers.
Consider three tasks  2 ,  4 and  5 in our example, before we performed graph replication. The
two consumer tasks  4 and  5 run with periods 28 and 42, respectively, while the producer  2 runs
with period 14. Thus, the data object requires a 6 place buffer
from slots (0, 2, reads from slots (0, 3). Figure 13 shows the relevant part of the task
graph after the buffer allocation.
After the buffer allocation, the compiler tool expands each data object into a multiple place
buffer, and replaces each read and write operations with macros that perform proper pointer updates

Figure

14 shows the results of the macro-expansion, after it is applied to  4 's code from

Figure

1(B). Note that  1 ,  2 and  4 run at periods of 28, 14 and 28, respectively.
7 Conclusion
We have presented a four-step design methodology to help synthesize end-to-end requirements into
full-blown real-time systems. Our framework can be used as long as the following ingredients are
provided: (1) the entity-relationships, as specified by an asynchronous task graph abstraction; and
(2) end-to-end constraints imposed on freshness, input correlation and allowable output separation.
This model is sufficiently expressive to capture the temporal requirements - as well as the modular
structure - of many interesting systems from the domains of avionics, robotics, control and
multimedia computing.
However, the asynchronous, fully periodic model does have its limitations; for example, we
cannot support high-level blocking primitives such as RPCs. On the other hand this deficit yields
int
int
every 28
f
size of Buffer1;
size of Buffer2;

Figure

14: Instantiated code with copy-in/copy-out channels and memory-mapped IO.
significant gains; e.g., handling streamed, tightly correlated data solely via the "virtual sequence
afforded by the rate-assignments.
There is much work to be carried out. First, the constraint derivation algorithm can be extended
to take full advantage of a wider spectrum of timing constraints, such as those encountered in
input-driven, reactive systems. Also, we can harness finer-grained compiler transformations such
as program slicing to help transform tasks into read-compute-write-compute phases, which will even
further enhance schedulability. We have used this approach in a real-time compiler tool [7], and
there is reason to believe that its use would be even more effective here.
We are also streamlining our search algorithm, by incorporating scheduling-specific decisions
into the constraint solver. We believe that when used properly, such policy-specific strategies will
help significantly in pruning the search space.
But the greatest challenge lies in extending the technique to distributed systems. Certainly a
global optimization is impractical, since the search-space is much too large. Rather, we are taking
a compositional approach - by finding approximate solutions for each node, and then refining each
node's solution-space to accommodate the system's bound on network utilization.

Acknowledgements

The authors gratefully acknowledge Bill Pugh, who was an invaluable resource, critic, and friend
throughout the development of this paper. In particular, Bill was our best reference on the topic
on nonlinear optimization. We are also grateful for the insightful comments of the TimeWare
group members: Jeff Fischer, Ladan Gharai, Tefvik Bultan and Dong-In Kang (in addition to the
authors). In particular, discussions with Ladan and Jeff were great "sounding boards" when we
formalized the problem, and they gave valuable advice while we developed a solution.



--R


Hard real-time scheduling: The deadline-monotonic approach
Data consistency in hard real-time systems
ESTEREL: Towards a synchronous and semantically sound high level language for real time applications.
Preemptive priority based scheduling: An appropriate engineering approach.


Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority.
Safety analysis of timing properties in real-time systems
The real-time producer/consumer paradigm: A paradigm for the construction of efficient

Scheduling algorithm for multiprogramming in a hard real-time envi- ronment
Priority inheritance protocols: An approach to real-time synchronization
Using offset information to analyse static priority pre-emptively scheduled task sets
An extendible approach for analysing fixed priority hard real-time tasks
Scheduling processes with release times
A Decomposition Approach to Real-Time Scheduling
Scheduling Tasks with Resource requirements in a Hard Real-Time System
--TR

--CTR
Namyun Kim , Minsoo Ryu , Seongsoo Hong , Heonshik Shin, Experimental Assessment of the Period Calibration Method: A Case Study, Real-Time Systems, v.17 n.1, p.41-64, July 1999
Tadaaki Tanimoto , Seiji Yamaguchi , Akio Nakata , Teruo Higashino, A real time budgeting method for module-level-pipelined bus based system using bus scenarios, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
Minsoo Ryu , Seongsoo Hong, Toward Automatic Synthesis of Schedulable Real-Time Controllers, Integrated Computer-Aided Engineering, v.5 n.3, p.261-277, August 1998
Luigi Palopoli , Giuseppe Lipari , Gerardo Lamastra , Luca Abeni , Gabriele Bolognini , Paolo Ancilotti, An object-oriented tool for simulating distributed real-time control systems, SoftwarePractice & Experience, v.32 n.9, p.907-932, July 2002
Victor A. Braberman, Automatic verification of real-time designs, Proceedings of the 21st international conference on Software engineering, p.716-717, May 16-22, 1999, Los Angeles, California, United States
D.-I. Kang , R. Gerber , L. Golubchik , J. K. Hollingsworth , M. Saksena, A software synthesis tool for distributed embedded system design, ACM SIGPLAN Notices, v.34 n.7, p.87-95, July 1999
Dinesh Ramanathan , Ali Dasdan , Rajesh Gupta, Timing-driven HW/SW codesign based on task structuring and process timing simulation, Proceedings of the seventh international workshop on Hardware/software codesign, p.203-207, March 1999, Rome, Italy
Ali Dasdan , Dinesh Ramanathan , Rajesh K. Gupta, Rate derivation and its applications to reactive, real-time embedded systems, Proceedings of the 35th annual conference on Design automation, p.263-268, June 15-19, 1998, San Francisco, California, United States
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
Huan Li , Krithi Ramamritham , Prashant Shenoy , Roderic A. Grupen , John D. Sweeney, Resource management for real-time tasks in mobile robotics, Journal of Systems and Software, v.80 n.7, p.962-971, July, 2007
Ali Dasdan , Dinesh Ramanathan , Rajesh K. Gupta, A timing-driven design and validation methodology for embedded real-time systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.4, p.533-553, Oct. 1998
Richard Gerber , Seongsoo Hong, Slicing real-time programs for enhanced schedulability, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.525-555, May 1997
Victor A. Braberman , Miguel Felder, Verification of real-time designs: combining scheduling theory with automatic formal verification, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.494-510, Nov. 1999
Dinesh Ramanathan , Ravindra Jejurikar , Rajesh K. Gupta, Timing driven co-design of networked embedded systems, Proceedings of the 2000 conference on Asia South Pacific design automation, p.117-122, January 2000, Yokohama, Japan
design methodology;non-linear optimization;end-to-end timing constraints;real-time;static priority scheduling;constraint solving