Alan Mishchenko
email: alanmi@eecs.berkeley.edu

Robert K Brayton
email: brayton@eecs.berkeley.edu

SAT-Based Complete Don't-Care Computation for Network Optimization

This paper describes an improved approach to Boolean network optimization using internal don't-cares. The improvements concern the type of don't-cares computed, their scope, and the computation method. Instead of the traditionally used compatible observability don't-cares (CODCs), we introduce and justify the use of complete don't-cares (CDC). To ensure the robustness of the don't-care computation for very large industrial networks, a optional windowing scheme is implemented that computes substantial subsets of the CDCs in reasonable time. Finally, we give a SAT-based don'tcare computation algorithm that is more efficient than BDD-based algorithms. Experimental results confirm that these improvements work well in practice. Complete don't-cares allow for a reduction in the number of literals compared to the CODCs. Windowing guarantees robustness, even for very large benchmarks on which previous methods could not be applied. SAT reduces the runtime and enhances robustness, making don't-cares affordable for a variety of other Boolean methods applied to the network.

Introduction

Optimization of Boolean networks using don't-cares plays an important role in technology-independent logic synthesis and incremental re-synthesis of mapped netlists. Traditionally, only satisfiability don't-cares (SDCs) and compatible observability don'tcares (CODCs) have been used [START_REF] Savoj | The use of observability and external don't-cares for the simplification of multi-level networks[END_REF]. The classical algorithm to compute CODCs [START_REF] Savoj | Don't cares in multi-level network optimization[END_REF] implemented in SIS [START_REF] Sentovich | SIS: A system for sequential circuit synthesis[END_REF] is used for many industrial tools. Later improvements dealt with (a) a more robust implementation [START_REF] Savoj | Improvements in technology independent optimization of logic circuits[END_REF], (b) independence from the local function representation [START_REF] Brayton | Compatible observability don't-cares revisited[END_REF], (c) generalization to multi-valued networks [START_REF] Jiang | Don't-cares and multi-valued logic network optimization[END_REF], and (d) approximations [START_REF] Saluja | A robust algorithm for approximate compatible observability don't care computation[END_REF].

CODCs form a subset of the complete don't-cares (or complete flexibility) [START_REF] Mishchenko | A theory of non-deterministic networks[END_REF] projected onto a node by its context in the multilevel network. It was shown experimentally [START_REF] Mishchenko | Simplification of nondeterministic multi-valued networks[END_REF] that the computation of CDCs is comparable in runtime and memory requirements while, as expected, the amount of don't-cares computed is larger than for CODCs. The presentation in [START_REF] Mishchenko | Simplification of nondeterministic multi-valued networks[END_REF] [START_REF] Mishchenko | A theory of non-deterministic networks[END_REF] considers the most general case of non-deterministic multi-valued networks, leaving open questions about efficiency when applied to binary deterministic networks.

The first contribution of this paper is in developing a specialized efficient version of the multi-valued don't-care computation algorithm [START_REF] Mishchenko | Simplification of nondeterministic multi-valued networks[END_REF] [START_REF] Mishchenko | A theory of non-deterministic networks[END_REF], to work on binary networks, and in showing that, compared to CODCs, this algorithm leads to an increase in optimization quality, due to the additional freedom provided by the CDCs.

The second contribution concerns the computation of don't-cares in large industrial designs. The traditional don't-care optimization in SIS is performed using the whole network as the context for each node. This restricts the use of don't-cares to small or medium-sized networks. To apply the same method to larger networks, the network can be partitioned with the scope of computation limited to one partition at a time. Although not published, such methods are probably part of some industrial tools. However, we suspect that partitioning for don't care computation is difficult, ad hoc, and implementation dependent. We propose a non-partitioning scheme, called windowing, which efficiently trades quality for runtime in network optimization. Windowing captures the maximal flexibility within a context limited by a fixed number of logic levels surrounding the node in question. The reconvergent paths surrounding the node are included into the window and excluded as in [START_REF] Saluja | A robust algorithm for approximate compatible observability don't care computation[END_REF]. Windowing is fast because construction of a window for a node involves a limited number of surrounding nodes visited without traversing the whole network. Windowing is not a partitioning scheme because each node has its own window that may overlap with windows computed for other nodes. Finally, windowing is dynamic and can be performed "on the fly", without duplicating or otherwise modifying the network or its parts. The latter quality makes windowing useful for applications that frequently update the network, e.g. decomposition-mapping [START_REF] Mishchenko | A new enhanced constructive decomposition and mapping algorithm[END_REF].

The third contribution concerns the use of Boolean satisfiability [9][16] rather than BDDs or SOPs, for the computation of don'tcares. We show that SAT is responsible for a speed-up making CDCs easy to compute and affordable enough. As a result, many procedures that previously relied on algebraic methods can now be extended to use Boolean methods based on CDCs.

In combination, these contributions provide improved efficiency, quality, and ruggedness for technology-independent logic synthesis.

The paper is structured as follows: Section 2 establishes the background. Section 3 defines CDCs and compares them with CODCs. Section 4 presents windowing. Section 5 describes and compares BDD-based and SAT-based approaches to CDC computation. Section 6 gives experimental results, and Section 7 concludes the paper.

Background

Definition. A completely specified Boolean function (CSF) is a mapping from n-dimensional (n 0) Boolean space into a singledimensional one: {0,1} n {0,1}.

A don't-care for a logic function allows it to have either 0 or 1 as a possible value. If for at least one input combination, the output of a function is a don't-care, this function is called an incompletely specified Boolean function (ISF).

An assignment of n Boolean variables to particular values is called a minterm. A CSF has negative (positive) minterms that correspond to the assignments, for which it takes values 0 (1). The positive and negative minterms are called the care minterms. An ISF has don'tcare minterms, which correspond to the assignments where the function can be either 0 or 1.

A CSF is compatible with an ISF (implements the ISF), if the CSF can be derived from the ISF by assigning either 0 or 1 to each don'tcare minterm. One ISF is said to be larger than another if it has more don't-care minterms.

Definition. A Boolean network is a directed acyclic graph (DAG) with nodes represented by Boolean functions. The sources of the graph are the primary inputs (PIs) of the network; the sinks are the primary outputs (POs).

The same name is used for a node and its output signal. The output of a node may be an input to other nodes called its fanouts. The inputs of a node are called its fanins. If there is a path from node A to B, then A is in the transitive fanin of B and B in the transitive fanout of A. The transitive fanin of B, TFI(B), includes node B and the nodes in its transitive fanin, including the PIs. The transitive fanout of B, TFO(B), includes node B and the nodes in its transitive fanout, including the POs.

The functionality of a node in terms of its immediate fanins is its local function. Its functionality in terms of the primary inputs of the network is its global function.

Complete don't-cares

Consider an individual node represented by a local CSF. It is not possible to change the node's function without changing the node's behavior. However, the situation is different when the node is considered in its context in the network. Then, often the node's function can be substantially modified without changing the behavior of the network. This is because other nodes prevent some combinations of inputs from reaching the node (non justification) as well as hiding the node's output from the POs under some conditions (non propagation).

The flexibility allowed in the implementation of a node can be represented as an ISF. A don't-care minterm of the ISF represents a combination of the node's input variables, for which the value of the node's output is not required for the POs of the network to produce the correct values.

Definition. The complete don't-cares (CDCs), or complete flexibility (CF), of a node in the binary network, is the largest ISF, whose don't-care minterms represent conditions when the output of the node does not influence the values produced by the POs of the network.

CDCs are important for network optimization because replacing a node's function by any CSF compatible with its CDC, does not change the network's output.

A key observation is that CDCs are not compatible, unlike CODCs [START_REF] Savoj | Don't cares in multi-level network optimization[END_REF]. That is, some POs of the network may produce incorrect values if CDCs are derived for several nodes and used independently. However, if a CDC is computed for a node and used immediately to optimize and replace that node before computing the CDC of another node, compatibility is not required. In this case, whenever a CDC is computed and used for a node, all prior changes to the other nodes are reflected in the computation. Heuristically, we found that visiting the nodes in topological order from the POs to the PIs gives the best literal reduction in a CDC-based optimization scheme.

CDCs have two major parts, the satisfiability don't-cares (SDCs) arising because some combinations are not produced as the inputs of the node, and the observability don't-cares (ODCs) arising because under some conditions the output value of the node does not matter. In Figure 1, node F has SDCs in the local space (x = 0, y = 1) due to limited controllability, while node G has ODCs in the global space (a = 1, b = 1) due to limited observability.

Figure 1. Example of SDCs and ODCs.

Don't-care computations are traditionally performed in the context of the entire Boolean network, as exemplified by SIS [START_REF] Sentovich | SIS: A system for sequential circuit synthesis[END_REF]. In the case of CDCs, this approach guarantees that the don't-cares computed are the largest set of don't-cares possible for a node. Since these computations can be expensive, we developed an optional windowing method that limits the scope of the don't-care computation to only a few logic levels on the fanin/fanout side of the node. A key observation is that re-convergence is a prime reason for don't cares. Therefore, along with the near TFI and TFO of a node, a window should contain all re-convergent paths that begin and terminate in these nodes. Previous approaches to windowing for don't-care computation [START_REF] Saluja | A robust algorithm for approximate compatible observability don't care computation[END_REF] considers only the TFI and TFO of the node without considering re-convergence.

For the special case when the inputs to the window have disjoint supports in terms of the PIs and all outputs of the window are POs, the CDC computed for the window is equal to the CDC when the whole network is considered.

Windowing

This section contains a detailed discussion of the windowing algorithm introduced in [START_REF] Mishchenko | A new enhanced constructive decomposition and mapping algorithm[END_REF].

Definition. Given a DAG and two non-overlapping subsets of nodes, one set is called the leaf set and the other the root set, if every path from the sources of the DAG to any node in the root set passes through some node in the leaf set.

Definition. Given two subsets in the leaf/root relationship, its window is the subset of nodes of the DAG that contains the roots plus all nodes on paths between the leaf set and the root set. The nodes in the leaf set are not included in the window.

Definition. A path between a pair of nodes is distance-k if it spans exactly k edges between the pair.

Definition. Two nodes are distance-k from each other if the shortest path between them is distance-k.

The pseudo-code in Figure 2 and the example in Figure 3 Procedures CollectLeaves and CollectRoots take the set of the window's internal nodes and determine the leaves and roots of this window. The leaves are the nodes that do not belong to the given set but are fanins of at least one of the nodes in the set. The roots are the nodes that belong to the given set and are also fanins of at least one node not in the set. Note that some of the roots thus computed are not in the TFO cone of the original node(s), for which the window is being computed, and therefore can be dropped without violating the definition of the window and undermining the usefulness of the window for the don't-care computation.

We typically refer to the window constructed for a node by including n TFI logic levels and m TFO logic levels as an n m window.

Example: Figure 3 shows a 1 1 window for node N in a DAG. The nodes labeled I 1 , O 1 , S, L, and R are in correspondence with the pseudo-code in Figure 2. The window's roots (top) and leaves (bottom) are shaded. Note that the nodes labeled by P do not belong to the TFI and TFO cones of node N, but represent the reconvergent paths in the vicinity of node N. The left-most root and right-most root are not in the TFO of N and can be dropped, as explained above.

Don't-care computation

The network optimization discussed in this paper iterates through all the nodes of the network. For each node, a CDC is computed and used to simplify and replace the node before optimizing the next node. The computation of the CDC for a node can be performed in the context of the whole network, if the network is small; otherwise, a window is used. Without limiting the generality of the CDC computation, we discuss these methods as applied to a node in the whole network. If a window is used, the network is the sub-network defined by the window used for the node.

The general approach to computing the CDC of a node in a nondeterministic multi-valued network [START_REF] Mishchenko | Simplification of nondeterministic multi-valued networks[END_REF] [START_REF] Mishchenko | A theory of non-deterministic networks[END_REF] relies on the use of an additional variable z for the output of the node, and the computation of a Boolean relation in terms of z and the PI and PO variables.

For a Boolean (binary deterministic) network, this approach can be simplified. The computation can be performed without using z or Boolean relations. In both BDD-based and SAT-based implementations, we consider two instances of the same network that differ only in an inverter at the output of the given node in the second copy (Figure 4). This duplication is an imaginary construction, done for the sake of the presentation and not actually implemented in software.

The first network isthe original one, while the second has an invertor inserted at the node's output. The functionalities of these networks are compared to detect when the change in the node's behavior influences the values at the POs. To this end, the two networks are transformed into a "miter" [START_REF] Brand | Verification of large synthesized designs[END_REF] derived by combining the pairs of PIs with the same names and feeding the pairs of POs with the same names into EXOR gates ORed to produce the only output of the miter (Figure 4).

Computation using BDDs

We use x to represent the PIs of the network and y to represent the immediate fanins of the node to be minimized. The BDD-based CDC computation begins by deriving the global functions of the POs of the two networks, {f i (x)} and {f i '(x)}. Next, the output function of the miter, C(x), is derived, which represents the care set in the global space:

C(x) = i [f i (x) f i '(x)
]. The ODC of the node in the global space is the complement of the care set:

ODC(x) = ( ) x C = i [f i (x) f i '(x)],
Next, the local CDC is computed by imaging the global ODC into the local space using the mapping M(x,y) (inferred from the network) that relates the global and local spaces:

( ) [ ( , ) ( )] [ ( , ) ( )] x x CDC y M x y ODC x M x y ODC x .
This computation adds the SDC, ( , ) M x y , to the already computed ODC. Thus a don't-care minterm y is, for all assignments of the PI variables x, either an SDC or an ODC. If external don't-cares are available, they are simply added to the ODC.

Computation using SAT

The use of SAT [START_REF] Marques-Silva | GRASP: A search algorithm for propositional satisfiability[END_REF][16] in the CDC computation is similar to the use of SAT in combinational equivalence checking [START_REF] Goldberg | Using SAT for combinational equivalence checking[END_REF]. A solution of the SAT problem corresponding to the miter in Figure 4 gives a satisfying assignment for all network signals when a 1 is the output of the miter. The values of variables y (the fanins of the node) in this All the care set minterms in terms of variables y are collected by enumerating through the satisfying assignments of the SAT problem and adding breaking clauses for each of them. A similar method of generating the satisfying assignments is described in [START_REF] Mcmillan | Applying SAT methods in unbounded symbolic model checking[END_REF], except that we do not undo the implication graph when a new satisfying assignment is found. We treat satisfying assignments similar to conflicts. In both cases, non-chronological backtracking is performed to the highest level determined using the new clause.

The SAT-based CDC computation is summarized in Figure 5. The top-level procedure CompleteDC takes node N and its context S given by the network, or by a window constructed for node N. Procedure ConstructMiter applies structural hashing [START_REF] Kuehlmann | Robust Boolean reasoning for equivalence checking and functional property verification[END_REF] to the miter of the two copies of S shown in Figure 4. The resulting compact AND-INV graph G is constructed in one DFS traversal of the nodes in S, without actual duplication.

For efficiency, random simulation is used to derive part of the care set, F 1 . The CNF P is the conjunction of clauses derived from G and the complement of F 1 . The CNF of G is derived using a technique that adds three CNF clauses for each AND gates. For example, the clauses added for the gate ab = c are: c + a, c + b, a + b + c. The only other clause added to the CNF is the clause asserting that the PO of the miter is equal to 1.

The SAT solver enumerates through the satisfying solutions, F 2 , of the resulting problem representing the remaining part of the care set. In practice, it often happens that the SAT problem has no solutions (F 2 = 0). In such cases, SAT is only useful to prove the completeness of the care set derived by random simulation. This approach solves the SAT problem by enumerating through the satisfying assignments that represent local minterms of the care set of the given node. Therefore, it should be limited to nodes with roughly 10 inputs or less, which is typically the case for most Boolean networks. It could also be enforced by decomposing large nodes first. To make the approach appropriate for networks nodes with a larger number of inputs, the implementation of the SAT solver should be further modified to return incomplete satisfying assignments corresponding to cubes rather than minterms of the local care set.

Experimental results

The methods for computing CDCs of a node in the context of both a window and the whole network have been implemented in the MVSIS environment [START_REF]UC Berkeley[END_REF].

The SAT-based part was implemented using MiniSat [START_REF] Eén | An extensible SAT-solver[END_REF], an "extensible SAT solver". Despite its small size (600 lines of C++ code written without STL), MiniSat is very efficient. In our experiments, it outperformed several popular SAT solvers. Moreover, the implementation of MiniSat is easy to understand and modify, which was the original intention of its developers.

Two experiments were performed. In both cases, the measurements were done on a Windows XP computer with a 1.6GHz CPU and 1Gb RAM, although less than 256Mb of RAM are needed for the largest benchmarks in Table 2.

The resulting networks were verified using a SAT-based verifier in MVSIS designed along the lines of [START_REF] Goldberg | Using SAT for combinational equivalence checking[END_REF][6].

Experiment 1: Comparing CODCs vs. CDCs

We compared the optimization potential of CODCs and CDCs. The BDD-based don't-care computation flow was used in both cases. We considered the largest MCNC benchmarks [START_REF] Yang | Logic synthesis and optimization benchmarks[END_REF], for which BDDs could be constructed. Table 1 compares the runtime and number of literals produced by the CODC-based command full_simplify of SIS, and the new CDC-based command mfs implemented in MVSIS and later ported to SIS. The SIS version was used in this experiment. Both full_simplify and mfs perform Boolean resubstitution followed by SOP minimization as part of a don't-carebased optimization. Network sweep in SIS is performed before and after both commands.

The first column in Table 1 lists the benchmark names, followed by five columns containing the number of literals: (1) after initial sweeping only ("sweep") (which is the starting point of the other columns), (2) after full_simplify ("fs"), (3) after mfs without the "advanced features" ("mfs"), (4) after mfs with 2 x 2 windowing without the "advanced features" ("mfsw"), and (5) after mfs with the advanced features enabled ("MFS"). The advanced features include on-the-fly merging of nodes with functionality equivalence up to complementation and phase-assignment, performed as part of optimization. In columns ( 2) and (3) these features are disabled to have a fair comparison with full_simplify. Some benchmarks could not be processed by full_simplify because of the large BDD sizes (indicated by the dash in the table).

The last three columns give the runtimes in seconds. The bottom line shows the average of the ratios of the improvements in the number of literals, achieved by each command, compared to the number of literals in the original (swept) benchmarks. The asterisk in Table 1 indicates that, to compare against fs, the averages of the ratios are taken only over the 11 examples where fs could complete. Although full_simplify was expected to be faster than mfs, this was not the case possibly because of the differences in the implementation and use of different BDD variable ordering heuristics in SIS and MVSIS. Comparing literals, Table 1 shows that the CDCs outperform CODCs in the context of the whole network (columns "fs" vs. "mfs"). In those rare cases when CODCs give better literal counts, the improvement is attributed to finding a better ordering of nodes. Our experiments have shown that, on average over all considered benchmarks, CDCs typically contain 20% more don't-care minterms in the local spaces of the nodes, compared to the CODCs.

f i (x) f i '(x) x x y y C(x)
For CDCs with windowing (column "mfsw"), Table 1 shows that the literal count is close to that of CODCs in the context of the whole network (column "fs"), but the runtime is only 7% of that of "fs". Thus, the improvement due to the CDCs is only marginally outweighed by the degradation due to using a window instead of the whole network in the case of CODCs. Additionally, window-based optimization (mfsw) is applicable to very large circuits, well beyond the scope of full_simplify in SIS or mfs without windowing.

Experiment 2: Cumulative effect of improvements

Table 2 shows the results of network optimization using the SATbased flow for ITC'99 [START_REF]ITC '99 Benchmarks[END_REF], ISCAS, and PicoJava benchmarks [START_REF]PicoJava Microprocessor Cores[END_REF]. These benchmarks are relatively large. As a result, BDD-based methods, full_simplify in SIS and mfs in MVSIS without windowing, cannot be applied.

The first column of Table 2 lists the benchmark names. The second column shows the number of inputs, outputs, and latches. The next three columns contain the number of literals in the factored forms in (1) the original benchmark after sweeping ("sweep"), (2) after applying mfs with 2x2 windowing ("mfsw"), and (3) as part of a script ("script"). The last two columns show the runtime in seconds for mfsw and script. The script used in this experiment was mvsis.rugged which is similar to script.rugged of SIS, except that mvsis.rugged is implemented in MVSIS and the CODC-based SIS command full_simplify is replaced by the CDC-based MVSIS command mfs, using 2x2 windows (mfs -w 22) and SAT instead of BDDs. Table 2 shows that the proposed don't-care-based optimization flow can be applied to quite large circuits. This is because the don'tcare computation is performed in a window, and therefore is local and does not depend on the circuit size. The overall runtimes scale well with the problem size and are predictable; a rule of the thumb is for mfs -w 22, the computation takes about 1 second per 3000 literals.

The reader can refer to a workshop version of the paper [START_REF] Mishchenko | SAT-based complete don't-care computation for network optimization[END_REF] for the detailed comparison of the performance of SAT and BDDs with windows of different sizes. In summary, the SAT-based computations are faster and scale better than the BDD-based ones. Thus, for 1 1 windows, SAT is on average 20% faster; for 2 2 windows, it is over two times faster while for 4 4 windows, it is over 7 times faster. This ratio increases further with the window size.

Conclusions

This paper contributes several improvements to the optimization of logic networks using don't-cares:

Complete don't-cares are used instead of compatible don'tcares. Abandoning compatibility does not lead to any problems in runtime but does increase the amount of don't-cares computed.

To ensure robust computation of don't-cares, windowing is used. This technique noticeably reduces the runtime while computing a substantial subset of the complete don't-cares for each node.

A new implementation of the don't-care computation using Boolean satisfiability is used, taking advantage of the recent improvements in the performance of SAT solvers [START_REF] Moskewicz | Chaff: engineering an efficient SAT solver[END_REF]. The same set of don't-cares is computed as in the corresponding BDD-based algorithm, but several times faster. The experiments described in the paper show that the proposed improvements enhance the optimization quality reduce the runtime and provide robustness. The overall effect is that the computation of internal don't-cares becomes very affordable, even for very large industrial networks.

Since such ideas make CDC computations quite affordable and robust, we believe that they can be applied to other Boolean logic optimization methods, reducing computational cost and improving optimality. As a result, these Boolean methods become more affordable and should eventually replace some sub-optimal algebraic methods for a variety of tasks in logic synthesis.

  describe the flow of a window construction algorithm. Procedure Window takes a node and two integers that define the number of logic levels on the fanin/fanout sides of the node to be included in the window. It returns the leaf set and the root set of the window. With modifications, this procedure can compute a window for a set of

Figure 2 .

 2 Figure 2. Computation of a window for a node.The procedure CollectNodesTFI takes a set S of nodes and an integer m 0, and returns a set of nodes on the fanin side that are distance-m or less from the nodes in S. An efficient implementation of this procedure for small m (for most applications, m 10) iterates through the nodes that are distance-k (0 k m) from the given set. The distance-0 nodes are the original nodes. The distance-(k+1) nodes are found by collecting the fanins of the distance-k nodes not visited before. The procedure CollectNodesTFO is similar.

Figure 3 .

 3 Figure 3. Example of a 1 x 1 window.Procedures CollectLeaves and CollectRoots take the set of the window's internal nodes and determine the leaves and roots of this window. The leaves are the nodes that do not belong to the given set but are fanins of at least one of the nodes in the set. The roots are the nodes that belong to the given set and are also fanins of at least one node not in the set. Note that some of the roots thus computed are not in the TFO cone of the original node(s), for which the window is being computed, and therefore can be dropped without violating the definition of the window and undermining the usefulness of the window for the don't-care computation.We typically refer to the window constructed for a node by including n TFI logic levels and m TFO logic levels as an n m window.Example: Figure3shows a 1 1 window for node N in a DAG. The nodes labeled I 1 , O 1 , S, L, and R are in correspondence with the pseudo-code in Figure2. The window's roots (top) and leaves (bottom) are shaded. Note that the nodes labeled by P do not belong to the TFI and TFO cones of node N, but represent the reconvergent paths in the vicinity of node N. The left-most root and right-most root are not in the TFO of N and can be dropped, as explained above.

  care set minterm in the local space of the node. This is because, for them, we know there exist values of the PI variables x, such that at least one pair of POs produces different values.

Figure 4 .

 4 Figure 4. Illustration of a miter used in CDC computation.

function 1 FFigure 5 .

 15 Figure 5. Pseudo-code of SAT-based CDC computation.

Table 1 . Comparing CODCs vs. CDCs.

 1

	Name		Literals in factored forms		Runtime, sec
		sweep	fs	mfs mfsw MFS	fs	mfs mfsw
	dalu	2976 2140 1741 2250 1747 64.8	2.1	0.8
	des	6101 5677 5616 5920 5334	8.1	3.7	3.7
	frg2	2010 1454 1440 1477 1409	5.1	0.6	0.5
	i10	4355	-3809 3853 3694	-82.2	1.2
	k2	2928 2889 2663 2878 2641	6.2	3.9	3.3
	pair	2420 2179 2143 2151 2139	3.5	2.9	0.4
	c1355	992	984	992	992	992 22.8 86.7	0.2
	c1908 1058	869	870	869	754 12.4 10.9	0.3
	c2670 1570 1189 1215 1411 1195	4.9	2.8	0.3
	c432	335	298	288	299	288	2.2	0.9	0.3
	c499	576	568	576	576	576	1.0 13.0	0.1
	c5315 3531 3184 3168 3176 2951 31.5	7.3	0.9
	c7552 4750	-4057 4079 3594	-50.0	1.4
	c880	648	625	624	625	624	1.2	7.2	0.1
	Ave	1.00 0.88 * 0.86 0.90 0.83 1.00 0.87 0.07

Table 2 . Network optimization using CDCs, windowing and SAT.

 2

	Name In/Out/Latch	Literals in factored forms Runtime, s
			sweep	mfsw script mfsw script
	b14	32 / 54 / 245	17388 10664	7911 3.9 18.0
	b15	36 / 70 / 449	16244 15056 10948 6.1 22.9
	b17	37 / 97 / 1415	57311 49067 37877 35.7 104.8
	b20	32 / 22 / 490	35149 21826 16813 7.6 55.0
	b21	32 / 22 / 490	35908 22312 16932 9.3 51.1
	b22	32 / 22 / 735	52276 33017 25174 13.5 59.8
	s15850	14 / 87 / 597	7303	6350	4033 1.2	4.0
	s35932	35 / 320	24408 20248 10986 4.2 16.7
	s38417	28 / 106	18699 17327 13640 4.5 15.5
	pj1	1769 / 1063/0	34828 30547 18076 9.5 37.0
	pj2	690 / 429/0	7422	6464	3457 1.1	4.0
	Ave		1.00	0.79	0.54 1.00 4.36

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgements

The authors gratefully acknowledge the support of the California MICRO program and our industrial sponsors, Intel, Fujitsu, Magma, and Synplicity.


Haisang Wu

Binoy Ravindran

E Douglas Jensen

Energy-Efficient, Utility Accrual Real-Time Scheduling Under the Unimodal Arbitrary Arrival Model *

We present an energy-efficient real-time scheduling algorithm called EUA * , for the unimodal arbitrary arrival model (or UAM). UAM embodies a "stronger" adversary than most arrival models. The algorithm considers application activities that are subject to time/utility function time constraints, UAM, and the multi-criteria scheduling objective of probabilistically satisfying utility lower bounds, and maximizing system-level energy efficiency. Since the scheduling problem is intractable, EUA * allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands, in polynomial-time. We establish that EUA * achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate EUA * 's superiority.

Introduction

Mobile and embedded devices are becoming increasingly popular at the workplace and at home. As batteries are the primary energy source of such devices, increasing the energy-efficiency of computing and communications is of critical importance. In many embedded systems, the CPU consumes a substantial fraction of the total energy, making it a prime target for energy saving in past efforts. Besides the CPU, other components also consume energy.

The characteristics of the power/performance tradeoffs of CMOS circuits dictate that the power consumption changes linearly with frequency and quadratically with voltage, yielding potential energy savings for reduced speed/voltage. Dynamic Voltage Scaling (DVS) is the technique for exploiting this tradeoff-an appropriate clock rate and voltage is determined in response to dynamic application behaviors (see [START_REF] Aydin | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Kim | Dynamic Voltage Scaling Algorithm for Fixed-Priority Real-Time Systems Using Work-Demand Analysis[END_REF][START_REF] Pillai | Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems[END_REF] and the references therein).

In this paper, we focus on dynamic, adaptive, embedded real-time control systems that occur in many domains including robotics, space, defense, consumer electronics, and financial markets. Such systems are fundamentally timecritical and energy-critical, as they must produce timely control responses, while running on batteries. Further, they operate in environments with dynamically uncertain properties. These uncertainties include transient and sustained overloads on the CPU (due to context dependent execution times) and arbitrary arrival patterns for application activities. Nevertheless, such systems desire assurances on activity timeliness behaviors, whenever possible. Consequently, the non-deterministic operating situations must be characterized with stochastic or extensional (rule-based) models.

The most distinguishing property of such systems, however, is that they are subject to time constraints that are "soft" (besides hard) in the sense that completing an activity at any time will result in some (positive or negative) utility to the system, and that utility depends on the activity's completion time. These soft time constraints are subject to optimality criteria such as completing all time-constrained activities as close as possible to their optimal completion times-so as to yield maximal collective utility. The optimality of the soft time constraints is generally as missionand safety-critical as that of the hard ones.

Jensen's time/utility functions [START_REF] Jensen | A Time-Driven Scheduling Model for Real-Time Systems[END_REF] (or TUFs) allow the semantics of soft time constraints to be precisely specified. A TUF, which generalizes the deadline constraint, specifies the utility to the system resulting from the completion of an activity as a function of its completion time. A TUF's utility values are derived from application-level quality of service metrics. Figure 1 shows example time constraints from real applications specified using TUFs. Figures 1(a)-1(c) show time constraints of two applications in the defense domain [START_REF] Clark | An Adaptive, Distributed Airborne Tracking System[END_REF][START_REF] Maynard | An Example Real-Time Command, Control, and Battle Management Application for Alpha[END_REF]. The classical deadline is a binary-valued, downward "step" shaped TUF; 1(d) shows an example.

When activity time constraints are expressed with TUFs, the timeliness optimality criteria are typically based on accrued activity utility-e.g., maximizing sum of the activities' attained utilities or assuring satisfaction of lower bounds on activities' maximal utilities. Such criteria are called Utility Accrual (or UA) criteria, and sequencing (scheduling, dispatching) algorithms that consider UA criteria are called UA sequencing algorithms. UA criteria facilitate adaptivity during overloads, when completing activities that are more important than those which are more urgent is often desirable. During overloads, UA algorithms that maximize summed utility typically favor activities that are more important (since more utility can be attained from them) than those which are more urgent.

Most past efforts on energy-efficient, real-time scheduling consider activity arrival models that are either periodic, or frame-based (where all periods are equal), or sporadic. These include past works that consider deadline-based timeliness optimality criteria (e.g., meeting all or some percentage of deadlines) [START_REF] Aydin | Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems[END_REF][START_REF] Kim | Dynamic Voltage Scaling Algorithm for Fixed-Priority Real-Time Systems Using Work-Demand Analysis[END_REF][START_REF] Pillai | Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems[END_REF][START_REF] Yuan | Energy-Efficient Soft Real-Time CPU Scheduling for Mobile Multimedia Systems[END_REF], and those that consider UA criteria (e.g., maximizing summed utility) [START_REF] Rusu | Multi-Version Scheduling in Rechargeable Energy-aware Real-time Systems[END_REF][START_REF] Wang | A Power Aware Best-Effort Real-Time Task Scheduling Algorithm[END_REF][START_REF] Wu | CPU Scheduling for Statistically-Assured Real-Time Performance and Improved Energy Efficiency[END_REF][START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF]. As far as we know, the only exception is [START_REF] Wang | A Power Aware Best-Effort Real-Time Task Scheduling Algorithm[END_REF], which allows aperiodic arrivals. However, [START_REF] Wang | A Power Aware Best-Effort Real-Time Task Scheduling Algorithm[END_REF] provides no timeliness assurances. Thus, prior efforts are concentrated on two extremes: (1) those that provide timeliness assurances, but under highly restrictive periodic, frame-based, or sporadic arrivals; or (2) those that allow aperiodic arrivals, but provide no timeliness assurances. Both these extremes are inappropriate for the applications/domains of interest to us.

In this paper, we bridge these extremes by considering the unimodal arbitrary arrival model (or UAM) [START_REF] Hermant | A Protocol and Correctness Proofs for Real-Time High-Performance Broadcast Networks[END_REF]. UAM embodies a "stronger" adversary than many traditional arrival models, and subsumes traditional models as special cases. We consider activities subject to TUF time constraints, arriving according to UAM. To better account for uncertainties in execution behaviors, we stochastically describe activity execution demands. We adopt Martin's system-level energy consumption model [START_REF] Martin | Balancing Batteries, Power and Performance: System Issues in CPU Speed-Setting for Mobile Computing[END_REF] that accounts for each system component's energy consumption and aggregates them to obtain the system's energy consumption.

For such a model, our objective is to: (1) probabilistically satisfy lower bounds on individual activity's maximal utility; and (2) maximize system-level energy efficiency.

This problem is N P-hard. We present a polynomialtime, heuristic algorithm for the problem called Energyefficient Utility Accrual Algorithm * (or EUA * ). We establish that EUA * 's timeliness behavior subsumes the optimal timeliness behavior of deadline scheduling as a special case. Further, we identify the conditions under which EUA * provides timeliness assurances. Our simulation studies confirm the effectiveness and superior performance of EUA * .

Thus, the paper's contribution is the EUA * algorithm. We are not aware of any other efforts that consider the problem of TUF/UA scheduling under UAM, solved by EUA * .

The rest of the paper is organized as follows: Section 2 describes our models and states the scheduling objective. Section 3 presents EUA * , and Section 4 establishes EUA * 's timeliness properties. Section 5 discusses the simulation studies. We conclude the paper in Section 6.

Models and Objective

System and Task Model

We consider a preemptive system which consists of a set of independent tasks, denoted as

T = {T 1 , T 2 , • • • , T n }.
The target variable voltage processor can be operated at m (jobs). With the UAM model, we associate a tuple a i , P i with a task T i , meaning the maximal number of its instance arrivals during any sliding time window of P i is a i . Instances may arrive simultaneously. Note that the periodic model is a special case of UAM model with 1, P i , 1 being both the upper and lower bound. We refer to the j th job (or invocation) of task T i as J i,j . The basic scheduling entity that we consider is the job abstraction. Thus, we use J to denote a job without being task specific, as seen by the scheduler at any scheduling event.

frequencies {f 1 , • • • , f m f 1 < • • • < f m }. Each task T i has a number of instances

Timeliness Model and Statistical Requirement

A job's time constraint is specified using a TUF. Jobs of a task have the same TUF. We use U i (•) to denote task T i 's TUF, and use U i,j (•) to denote the TUF of T i 's jth job. Without being task specific, U J k means the TUF of a job J k ; completion of J k at a time t will yield a utility U J k (t). In this paper, we restrict our focus to non-increasing, unimodal TUFs i.e., those TUFs for which utility never increases as time advances. Figures 1(a Each TUF U i,j , i ∈ {1, • • • , n} has an initial time I i,j and a termination time X i,j . Initial and termination times are the earliest and the latest times for which the TUF is defined, respectively. We assume that I i,j is equal to the arrival time of J i,j , and X i,j -I i,j is equal to the sliding time window P i of the task T i . If a job's termination time is reached and its execution has not been completed, an exception is raised. Normally, this exception will cause the job's abortion and execution of exception handlers.

Similar to that in [START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF], the statistical timeliness requirement of a task T i is denoted as {ν i , ρ i }, which implies that task T i should accrue at least ν i percentage of its maximum possible utility with a probability of at least ρ i . For step TUFs, ν can only take the value 0 or 1.

During some situations, it is possible that such statistical assurances cannot be provided; then the objective is to maximize the total utility per unit energy consumption.

Activity Cycle Demands

Both UA scheduling and DVS depend on the prediction of task cycle demands. Similar to [START_REF] Wu | CPU Scheduling for Statistically-Assured Real-Time Performance and Improved Energy Efficiency[END_REF] and [START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF], we estimate the statistical properties (e.g., mean and variance) of the demand rather than the worst-case demand.

Let Y i be the random variable representing T i 's cycle demand i.e., the number of processor cycles required by T i . We assume that the mean and variance of Y i , denoted as E(Y i ) and V ar(Y i ) respectively, are finite and determined through either online or off-line profiling. Under a frequency f (given in cycles per second), the expected execution time of a task T i is given by e i = E(Y i ) f .

Energy Consumption Model

We consider Martin's system-level energy consumption model to derive the energy consumption per cycle (detailed model descriptions can be found in [START_REF] Martin | Balancing Batteries, Power and Performance: System Issues in CPU Speed-Setting for Mobile Computing[END_REF][START_REF] Wang | A Power Aware Best-Effort Real-Time Task Scheduling Algorithm[END_REF][START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF]). In this model, when operating at a frequency f , a component's dynamic power consumption is denoted as P d . P d of CPU is given by S 3 × f 3 , where S 3 is constant.

Besides the CPU, other system components also consume energy. P d of those that must operate at a fixed voltage (e.g., main memory) is given by S 1 × f , while P d of those that consume constant power with respect to the frequency (e.g., display devices) can be represented as an constant S 0 . In practice, the quadratic term S 2 ×f 2 is also included to account for the appearance of variations in DC-DC regulator efficiency across the range of output power, CMOS leakage currents, and other second order effects [START_REF] Martin | Balancing Batteries, Power and Performance: System Issues in CPU Speed-Setting for Mobile Computing[END_REF].

Summing the power consumption of all components, we obtain the system-level energy consumption of a task as:

E i = e i × S 3 × f 3 + S 2 × f 2 + S 1 × f + S 0 .
Thus, the expected energy consumption per cycle is given by:

E(f ) = S 3 × f 2 + S 2 × f + S 1 + S 0 f (1)

Scheduling Objective

We consider a two-fold scheduling criterion: (1) assure that each task T i accrues the specified percentage ν i of its maximum possible utility with at least probability ρ i ; and

(2) maximize the system's "energy efficiency." When it is not possible to satisfy {ν i , ρ i } for each task, our objective is to maximize the system-level energy efficiency.

Intuitively, when the system is overloaded, DVS tends to select the highest frequency f m for the processor execution. Therefore, during overloads, with the constant energy consumption at f m , the scheduling objective becomes utility maximization under energy constraints. During underloads, the algorithm delivers the performance assurances. Thus, the objective becomes the dual criterion problem of utility maximization, that is, minimizing energy while achieving the given utility within the given time constraint.

The EUA * Algorithm

Determining Task Critical Time and Demand

For non-increasing TUFs, to satisfy the designated ν i on accrued utility, we should bound task T i 's sojourn time to less than its "critical time" (D i ). With E(Y i ) and V ar(Y i ), by the Chebyshev's inequality, we can derive the minimal required cycles c i to allocate to each job of T i , so that P r[Y i < c i ] ≥ ρ i . These are addressed in our prior work [START_REF] Wu | CPU Scheduling for Statistically-Assured Real-Time Performance and Improved Energy Efficiency[END_REF][START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF], where D i is calculated from

ν i = U i (D i ) U max i , and c i = E(Y i ) + ρi×V ar(Yi) 1-ρ i .

Utility Accrual Scheduling

We define a performance metric, Utility and Energy Ratio (UER) to integrate timeliness and energy consumption. A job's UER measures the utility that can be accrued per unit energy consumption by executing the job. The UER of T i under frequency f at time t is calculated as Ui(t+ci/f ) (c i ×E(f )) , where E(f ) is derived using Equation 1. Equation 1 indicates that there is an optimal value (not necessarily the lowest one) for clock frequency that maximizes T i 's UER.

The scheduling events of EUA * include the arrival and completion of a job, and the expiration of a time constraint such as the arrival of a TUF's termination time. We define the following variables and auxiliary functions for EUA * : • During a time window P i , D a i is task T i 's earliest invocation's absolute critical time; c r i is its earliest job's remaining computation cycles.

• J r = {J 1 , J 2 , • • • , J n } is the current unscheduled job set; σ is the ordered schedule. J k ∈ J r is a job. • J k .D is job J k 's critical time; J k .
X is its termination time; J k .c is its remaining cycles. T (J k ) returns the corresponding task of job J k .

• headOf(σ) returns the first job in σ; sortByUER(σ) sorts σ by each job's UER, in a non-increasing order. selectFreq(x) returns the lowest frequency

f i ∈ {f 1 < • • • < f m } such that x ≤ f i .
• offlineComputing() is computed at t = 0. For task T i , it computes c i and D i as described in Section 3.1, and determines its optimal frequency f o T i ∈ {f 1 , • • • , f m }, which maximizes the task's UER.

• insert(T ,σ,I) inserts T in the ordered list σ at the position indicated by index I; if there are already entries in σ at the index I, T is inserted after them.

• feasible(σ) returns a boolean value denoting schedule σ's feasibility. For σ to be feasible, the predicted completion time of each job in σ, calculated at the highest frequency f m , must not exceed its termination time. Algorithm 1: EUA * : High Level Description A high level description of EUA * is shown in Algorithm 1. When EUA * is invoked at time t cur , the algorithm first updates each task's remaining cycles (the switch starting from line 5). The algorithm then checks the feasibility of the jobs. If a job is infeasible, then it can be safely aborted (line 10). Otherwise, its UER is calculated (line 11).

input : T = {T1, • • • , Tn}, Jr = {J1, • • • , J
The jobs are then sorted by their UERs (line 12). In each step of the for loop from line 13 to 18, the job with the largest UER is inserted into σ, if it can produce a positive UER and keep the schedule after insertion feasible. Thus, σ is a feasible schedule sorted by the jobs' critical times, in an non-decreasing order.

Finally, EUA * analyzes the demands of the task set and applies DVS to decide the frequency f exe with algorithm decideFreq(). The selected job J exe at the head of σ is executed with the frequency f exe (line 19-21).

DVS with the UAM model

We consider the "processor demand approach" [START_REF] Baruah | Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic, Real-Time Tasks on One Processor[END_REF] to analyze the feasibility of tasks with stochastic parameters.

Theorem 1 For a task T i with a UAM pattern a i , P i and critical time D i , all its jobs can meet their D i , if T i is executed at a frequency no lower than C i D i , where C i is the total cycles of a i jobs in the time window P i , i,e., C i = a i c i .

Proof The necessary and sufficient condition for satisfying job critical times is fL ≥ C i (0, L), ∀L > 0, where f is the processor frequency allocated to T i , and

C i (0, L) is the cycle demand on the time interval [0, L], i.e., C i (0, L) = (L-D i ) P i + 1 C i . Thus, we need f ≥ 1 L L-D i Pi + 1 C i ≥ C i Pi 1 + P i -D i L
, ∀L > 0. Since P i ≥ D i , f monotonically decreases with L. Furthermore, notice that if L ≤ D i , C i (0, L) = 0 because no job has a critical time earlier than D i . Thus, it is sufficient to consider the case of L = D i , where f ≥ C i D i . input: T, Jexe, tcur; output: fexe ; 1:

U til := C 1 /D 1 + • • • + C n /D n ; 2: s := 0; 3: for i = 1 to n, T i ∈ {T 1 , • • • , T n D a 1 ≥ • • • ≥ D a n } do 4:
/* reverse EDF order of tasks */ U til := U til -C i /D i ; 5:

x

:=max(0, C r i -(fm -U til) × (D a i -D a n )); 6: U til := ( 1, if D a i -D a n = 0 U til + C r i -x D a i -D a n
, otherwise ; 7: s := s + x; 8:

f :=min(f m , s/(D a n -t cur )); 9:
f exe :=selectFreq (f ); 10:

f exe :=max(f exe , f o T (J exe ) ); 11:
Algorithm 2: decideFreq() Algorithm 2 shows decideFreq(), the stochastic DVS technique of EUA * . Based on Theorem 1, we use C i for utilization analysis. For the current time window P i with a i instances, EUA * keeps track of the remaining computation cycles C r i , which is calculated as

C r i = min((a i -1)c i + c r i , (a i -1)c i + c r i ).
Note that the actual number of jobs a i can be larger than the maximum job arrivals a i , because there may be unfinished jobs from the previous time window. But we only need to consider at most a i instances of them. In line 2-9, EUA * considers the interval until the next task critical time and tries to "push" as much work as possible beyond the critical time. Similar to LaEDF [START_REF] Pillai | Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems[END_REF], the algorithm considers the tasks in the latest-critical-time-first order in line 4. If task T i has more than one jobs in P i , D a i is set to be its earliest invocation's absolute critical time.

x counts the minimum number of cycles that a task must execute before the closest critical time, D a n , in order for it to complete by its own critical time (line 6), assuming worstcase aggregate CPU demand U til by tasks with earlier critical times. In line 7, U til is adjusted to reflect the actual demand of the task for the time after D a n , with the consideration of the case that jobs of different tasks have the same termination times, which can occur, especially during overloads. s is simply the sum of the x values calculated for all of the tasks, and therefore reflects the minimum number of cycles that must be executed by D a n in order for all tasks to meet their critical times (line 8).

Thus, decideFreq() capitalizes on early task completion by deferring work for future tasks in favor of scaling the current task. Also, during overloads, the required frequency may be higher than f m , and selectFreq() would fail to return a value. In line 9, we solve this by setting the upper limit of the required frequency to be the highest frequency f m . Finally, f exe is compared with f o T (J exe ) . The higher frequency is selected-to provide performance assurances, we cannot decrease f exe , but may increase it to maximize the system-level energy efficiency.

EUA * 's Timeliness Properties

The periodic model is a special case of UAM. Thus, under the conditions: (1) a set of periodic tasks with 1, P i subject to downward step TUFs; and (2) absence of CPU overloads (i.e., the conditions in [START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment[END_REF]), we establish: Theorem 2 Under conditions ( 1) and ( 2), a schedule produced by EDF [START_REF] Horn | Some Simple Scheduling Algorithms[END_REF] is also produced by EUA * , yielding equal total utilities. This is a critical time ordered schedule. 1) and ( 2), EUA * always meets all task critical times. 1) and ( 2), EUA * minimizes the maximum lateness.

Corollary 3 Under conditions (

Corollary 4 Under conditions (

Theorem 5 Under conditions ( 1) and ( 2), EUA * meets the statistical performance requirements.

The proofs can be found in [START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF]. In Theorem 6, we also derive the above theorems' counterparts for non-step and non-increasing TUFs, with which critical times are less than termination times. The proof for it can be found in [START_REF] Baruah | Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic, Real-Time Tasks on One Processor[END_REF]. Theorem 6 For a set of independent periodic tasks, where each task has a single computational thread with a nonincreasing TUF, the task set is schedulable and can meet all statistical performance requirements under the condition of Baruah,Rosier,and Howell [3].

Experimental Results

We simulate EUA * on the AMD k6 processor with PowerNow! mechanism [START_REF]Mobile AMD-K6-2+ Processor Data Sheet[END_REF], which operates at seven frequencies, {360, 550, 640, 730, 820, 910, 1000 MHz}. For comparison, we consider StaticEDF, LaEDF [START_REF] Pillai | Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems[END_REF], and LaEDF-NA. While StaticEDF and LaEDF abort infeasible tasks during overloads, LaEDF-NA is LaEDF without abortion. We normalize the results to BaseEDF, which is EDF that always uses the highest frequency.

We select task sets with 10 to 50 tasks in three applications, whose parameters are summarized in Table 1 The energy consumption per cycle at a particular frequency is calculated using Equation 1. In practice, the S 3 , S 2 , S 1 , and S 0 terms depend on the power management state of the system and its subsystems [START_REF] Martin | Balancing Batteries, Power and Performance: System Issues in CPU Speed-Setting for Mobile Computing[END_REF][START_REF] Wang | A Power Aware Best-Effort Real-Time Task Scheduling Algorithm[END_REF]. We test three energy settings similar to those in [START_REF] Wu | Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems[END_REF], as shown in Table 2.

Note that E 1 is the same as the conventional energy model, which only considers the CPU's energy consumption.

Performance with Step TUFs

We first focus on step TUFs, for which EUA * can be compared with the other strategies. We set {ν i = 1, ρ i = 0.96}, and apply different schemes on periodic task sets under different energy settings. The other strategies, e.g., LaEDF, are based on the worst case workload; here we use cycles allocated by EUA * as their inputs.

Figure 2 shows the normalized utility and energy under energy setting E 1 and E 3 , as Load varies from 0.2 to 1.8. From Figure 2(b) and 2(d), we observe that EUA * saves more energy than others during under-loads. LaEDF-NA's energy consumption increases linearly with Load, because it does not abort jobs and executes all jobs that arrive. During overloads, the results of all schemes except LaEDF-NA converge to 1, because they select the highest frequency.

As Figure 2(a) and 2(c) show, during under-loaded situations, all schemes accrue the same (optimal) utility because of EDF's optimality in such cases [START_REF] Horn | Some Simple Scheduling Algorithms[END_REF]. But during overloads, LaEDF-NA suffers domino effects [START_REF] Locke | Best-Effort Decision Making for Real-Time Scheduling[END_REF] and accrues almost no utility. On the other hand, EUA * schedules jobs with higher UERs, and thus accrues remarkably higher utility than others. Results under E 2 are similar.

Thus, the performance gap demonstrates that EUA * accrues higher utility during overloads, and handles the dual criterion problem during under-loads-saving energy while achieving the given utility within the given time constraint.

Performance with Non-Increasing TUFs

We now consider non-step and non-increasing TUFs with EUA * , and study the impact of UAM model on the energy consumption. We allocate a linear TUF to each task, and its slope is calculated as -U max P , where P is the time window. We set {ν i = 0.3, ρ i = 0.9} to each task, and use the energy model E 1 in the experiments of this section.

We change the parameter a i in the UAM model a i , P i for each task from 1 to 3, and run EUA * on the task set. We observe that, during overloads, the energy consumption does not change with a i , because EUA * tends to select the highest frequency. However, during under-loads, as a i increases, EUA * 's energy consumption increases, even under the same Load. For example, when Load = 0.5, the normalized energy consumption of 1, P is 0.26; that of 2, P is 0.41, and with 3, P , this number increases to 0.61. This is because DVS is dependent on the prediction of future workload and slack time estimation. When a i increases, more complicated job arrivals negatively affect the accurate estimation of slack times.

Conclusions, Future Work

We present an energy-efficient, UA scheduling algorithm called EUA * , which allows activities to arrive according to the UAM model. UAM embodies a "stronger" adversary than most arrival models. The algorithm considers TUF time constraints and the scheduling objective of probabilistically satisfying utility lower bounds, and minimizing system-level energy consumption (during under-loads). During overloads, EUA * considers the dual criterion problem, utility maximization under energy constraints. EUA * allocates cycles, scales CPU frequency, and computes schedules using statistical estimates of cycle demands. We establish the conditions under which EUA * 's timeliness assurances hold. Our simulation experiments confirm EUA * 's timeliness behavior and improvement on system-level energy efficiency.

Future work includes scheduling under finite energy budgets, and considering activity models where activities accrue utility as a function of their progress.

Figure 1 .

 1 Figure 1. Example TUF Time Constraints from AWACS [4] (a) and Coastal Air Defense [12] (b-c), and a Step TUF (d).

  ), 1(b), and 1(d) show examples.

Figure 2 .

 2 Figure 2. Normalized Energy and Utility vs. Load under E 1 and E 3

Figure 3 .

 3 Figure 3. Energy Consumption of Different UAM Settings

  . Within each range, the time window P is uniformly distributed. The synthesized task sets simulate the varied mix of short and long time windows. For each task cycle demand Y i , we keep V ar(Y i ) ≈ E(Y i ), and generate normally-distributed demands. Finally, according to the calculation of c i in Section 3.1, E(Y i )s are scaled by a constant k, and V ar(Y i )s are scaled by k 2 ; k is chosen such that the system load (Load = 1 D i ) reaches a desired value. The U max of the TUFs in A 1 , A 2 , and A 3 are uniformly generated in the range [50, 70], [300, 400], and [1, 10], respectively.

	f m	n i=1	C i

Table 1 :

 1 Task Settings

	App.	tasks	UAM a, P
	A1	4	5, 22-28
	A 2	18	8, 50-70
	A 3	8	3, 2.4-9.6

Table 2 :

 2 Energy Settings

	Energy Model	S3	S2 S1	S0
	E1	1.0	0	0	0
	E 2 E3	0.75 0.5	0 0	0 0	0.25f 3 m 0.5f 3 m

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work was supported by the US Office of Naval Research under Grant N00014-00-1-0549 and The MITRE Corporation under Grant 52917.


Rafik Henia
email: henia@ida.ing.tu-bs.de

Rolf Ernst
email: ernst@ida.ing.tu-bs.de

Context-Aware Scheduling Analysis of Distributed Systems with Tree-shaped Task-Dependencies

In this paper we present a new technique which exploits timing-correlation between tasks for scheduling analysis in multiprocessor and distributed systems with tree-shaped task-dependencies. Previously developed techniques also allow capturing and exploiting timing-correlation in distributed systems. However, they are only suitable for linear systems, where tasks cannot trigger more than one succeeding task. The new technique presented in this paper, allows capturing timing-correlation between tasks in parallel paths in a more accurate way, enabling its exploitation to calculate tighter bounds for the worst-case response time analysis for tasks scheduled under a static priority preemptive scheduler.

Introduction

For simplicity, most formal scheduling analysis techniques ignore correlations between task execution times or communication timing. This avoids the growing analysis complexity, in particular when it comes to heterogeneous multiprocessor systems. However, such correlations can have a large influence on system timing as has been shown for special system topologies [6] [4]. This paper extends the analysis to more general structures.

Observe the system in figure 1. The system consists of five tasks mapped on three resources. Due to the datadependency between the tasks, their activating events are time-correlated. We call the information about such correlation inter event stream context [START_REF] Jersak | Context-aware performance analysis for efficient embedded system design[END_REF]. However, a typical scheduling analysis would ignore the available inter event stream context and would assume that all tasks are independent and that in the worst-case they are activated simultaneously [START_REF] Tindell | An extendible approach for analysing fixed priority hard real-time systems[END_REF]. This may lead to a greater calculated maximum number of interrupts of a lower-priority task by higherpriority tasks, resulting in a longer calculated worst-case response time of the lower priority task.

Methods exploiting inter event stream contexts for the worst-case response time calculation already exist. However, they are either limited to linear systems and tasks in Figure 1. Distributed system with timingcorrelation between tasks in parallel paths single paths [START_REF] Tindell | Adding time-offsets to schedulability analysis[END_REF] [4], e. g. the correlation between T 2 and T 5 on R 2 , or enable to capture the complete timing-correlation between tasks in parallel paths [START_REF] Redell | Accounting for precedence constraints in the analysis fo fixed priority scheduled tasks[END_REF] [3], e. g. the correlation between T 3 and T 4 on R 3 , in an accurate way. All this methods only consider the external events (produces by source) as references to capture timing-correlation between tasks.

In this paper, we present a new technique to capture the inter event stream context information for tasks in parallel paths and exploit it for the worst-case static priority scheduling analysis to calculate tighter response time bounds.

In the following section, we will more deeply review the existing approaches from literature to exploit inter event stream contexts for worst-case response time calculation in distributed systems. In Section 3, we introduce our computational model, then we present some inter event stream context preliminaries in section 4. In section 5, we show the limits of existing techniques in exploiting inter event stream contexts for tasks in parallel paths and introduce the idea of relative offset and relative jitter. An algorithm for the worstcase response time calculation considering relative offset and jitter information is presented in section 6. Experiments are carried out in section 7. We interpret the experimental results, before we draw our conclusions.

Related Work

Inter event stream contexts capture the timing correlation between events in a way that can be exploited by schedul-ing analysis. Tindell introduced this idea for tasks scheduled by a static priority preemptive scheduler [START_REF] Tindell | Adding time-offsets to schedulability analysis[END_REF]. In his paper, each set of time-correlated tasks is grouped into a so called transaction. Each transaction is activated by a periodic sequence of external events. Each task belonging to a transaction is activated when a relative time, called offset, elapses after the arrival of the external event. An activation of a task releases the execution of one instantiation of that task, called job. However, Tindell's technique did not allow offsets to be larger than the transaction period.

Tindell's work was later generalized by Palencia and Harbour [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF]. They presented the WCDO (Worst Case Dynamic Offsets) algorithm which extends the analysis presented by Tindell, by allowing the task offsets to be larger than the transaction period and extending the technique for distributed systems to dynamic offsets, which vary from one job to another. In [START_REF] Palencia | Exploiting precedence relations in the schedulablilty analysis of distributed real-time systems[END_REF], Palencia and Harbour presented a new analysis technique for tasks with precedence relations in distributed systems. The presented technique called WCDOPS (Worst Case Dynamic Offsets with Priority Schemes) extended the WCDO algorithm by exploiting precedence relations among tasks during analysis. However, the WCDOPS algorithms only took into account tasks in linear transactions, where each task is allowed to have at most one successor.

In recent works, Redell extended the WCDOPS algorithm by considering precedence relations between tasks in so called tree-shaped transactions [START_REF] Redell | Accounting for precedence constraints in the analysis fo fixed priority scheduled tasks[END_REF] [3], by allowing tasks to have more than one successor. However even though the algorithm he proposed (the WCDOPS+ algorithm) allows exploiting the inter context information for tasks in parallel paths, it was based on the inter context capturing technique presented by Palencia and Harbour, which was developed for linear systems. Therefore, as we will show, not all available timing-correlation was exploited.

Computational Model

The model that we consider is composed of tasks executing in a distributed system consisting of computation and communication resources. Tasks are allowed to have more than one immediate successor. Each task is assumed to have exactly one input and is activated due to one activating event. After finishing its execution, a task produces exactly one event at each of its outputs. The possible timing of events is described using event models. Event models are described using two parameters: the period and the jitter, noted P and J. These parameters state that each event generally occurs periodically with a period P , but that it can jitter around its exact position within a jitter interval J. If the jitter is larger than the period, then two or more events can occur at the same time, leading to bursts. Tasks are also assigned priorities. An execution of a lower priority task can be interrupted by the execution of a higher priority task mapped on the same resource. The response time R of a task is defined as the difference between its completion and its activation time.

Transactions

In this section, we review preliminaries about capturing the inter event stream context information and exploiting it for the worst-case response time calculation, as presented in [START_REF] Tindell | Adding time-offsets to schedulability analysis[END_REF] and [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF]. Each set of time-correlated tasks in the distributed system is grouped into one transaction. In addition, each task belonging to a transaction is identified by an offset parameter which indicates the earliest activation time after the arrival of the associated external event activating the transaction. In the following, we call this offset global offset.

To calculate the worst-case response time of a lower priority task T l , we must calculate the maximum contribution from all the transactions to its busy period. The busy period of T l is a time-interval during which the resource is busy processing T l or another task from hp(T l ), where hp(T l ) is the set of higher or equal priority tasks sharing a same resource with T l . The instant that starts the busy period is called critical instant and is noted t c . In [START_REF] Tindell | Adding time-offsets to schedulability analysis[END_REF] and [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF], it was shown that the maximum contribution of a transaction Γ to the busy period is obtained when the critical instant t c coincides with the activation time of some task T c ∈ hp Γ (T l ) (hp Γ (T l ) is the set of tasks belonging to hp(T l ) and Γ) when T c is delayed by its maximum jitter. In order to perform an exact analysis, it is necessary to check all possible critical instants created by all tasks from hp Γ (T l ) and choose the one that leads to the worst-case response time of T l .

Figure 2 shows execution timing of a task T i which belongs to hp Γ (T l ). The downward arrows indicate the external events activating the transaction. The upward arrows indicate the offset Φ i of T i . Assuming that T i is activated by the event model (P i , J i ), its activation can occur between the instants t 0 + Φ i and t 0 + Φ i + J i , where t 0 is the instant at which the associated external event arrived.

Figure 2. Transaction with executions of T l and jobs of T i

The maximum contribution of T i to the worst-case busyperiod of T l is obtained, as shown in figure 2, when T i is activated if possible at, or as soon as possible after t c .

Relative Offset And Relative Jitter

Problem Formulation

Observe the system modeled in figure 1. We assume static priority scheduling on R 2 and R 3 . The priorities are assigned as follows: T 2 > T 5 and T 3 > T 4 . The core execution times, i.e. assuming no interrupts, are assumed to be [START_REF] Redell | Accounting for precedence constraints in the analysis fo fixed priority scheduled tasks[END_REF]8] for T 1 and [2,2] for all other tasks. T 1 is assumed to be activated periodically by events sent by the source task source. Let the activating event model of T 1 be (P 1 = 10, J 1 = 0). At the end of each execution, T 1 produces exactly one event at each of its outputs. Due to the data-dependency between T 1 , T 2 , T 3 , T 4 and T 5 , we group all tasks in one transaction. Without loss of generality, we assume that T 1 has a global offset Φ 1 = 0. In the following, we will focus on the worst-case response time of task T 4 .

Table 1 shows the input event models and offsets of T 3 and T 4 after having analyzed the resources R 1 and R 2 . Note that the jitter is due to the response time variation of T 1 . task input event model offset

T 3 (P 3 = 10, J 3 = 6) Φ 3 = 4 T 4 (P 4 = 10, J 4 = 6) Φ 4 = 2

Table 1. Offsets and input event models of T 3 and T 4

The worst-case response time of the lower priority task T 4 calculated by the WCDO [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF] and WCDOPS+ [START_REF] Redell | Accounting for precedence constraints in the analysis fo fixed priority scheduled tasks[END_REF] [3] algorithms is R w 4 = 4. This worst case response time, as shown in the gantt-chart in figure 3, is obtained when T 4 starts the critical instant, i.e. that T 4 is activated after having arrived as late as possible. The maximum contribution of T 3 is obtained by delaying its activation by 4 time units which causes it to coincide with the critical instant. Therefore, one interrupt of T 4 by T 3 is calculated.

Figure 3. worst-case response time calculation of T 4 using WCDO and WCDOPS+

Now, let us take a closer look on our system. Since T 1 produces one event at each output after each execution, T 2 and T 4 are always activated simultaneously. As both tasks share different resources, there is no conflict between their execution requests. Therefore, since T 3 is activated after T 2 finishes its execution (which takes 2 time units), an activation of T 3 always occurs 2 time units after an activation of T 4 . As no former activation of T 3 can be delayed by an amount of jitter that cause it to delay or interrupt the execution of T 4 , the true worst-case response time of T 4 is R w 4 = 2. The pessimistic worst-case response time calculation of the WCDO and WCDOPS+ is due to the fact that these algorithms only consider the external events (here events produced by source) as references to capture timing correlations between tasks in the system. I.e. they ignore that, other references in the system could lead to an exacter calculation. In the example above, since events at both outputs of T 1 are produced simultaneously, it would be more accurate to consider the completion time of T 1 as a reference to cap-ture the timing correlation between the tasks in the parallel paths starting at T 1 .

Relative Offset and Relative Jitter Concept

To capture the timing correlation between tasks in parallel paths, we introduce the concept of relative offset and relative jitter.

Definition 1 (relative offset).

A task T i is said to be activated after an offset Φ i (T r ) relative to a reference task T r , if T i is activated at the earliest when a relative time Φ i (T r ) elapses after the completion time of T r . Φ i (T r ) is called offset of T i relative to T r .

Definition 2 (relative jitter). The activation of a task T i relative to the completion time of a reference task T r can vary within a jitter interval of length

J i (T r ). J i (T r ) is called jitter of T i relative to T r .
The offset and jitter information of a task T i relative to task T r shall be denoted: (T r , Φ i (r), J i (r)).

The relative offset and relative jitter calculation extends the global offset and jitter calculation by allowing any reference task not just external sources. I.e. the relative offset corresponds to the minimum path latency starting from the reference task and the relative jitter corresponds to the difference between the maximum and the minimum path latency starting from the reference task.

In the example in figure 1, since T 2 and T 4 are activated immediately after the execution completion of T 1 , the offset and jitter information of T 2 and T 4 relative to T 1 is: (T 1 , 0, 0). Since T 3 is activated immediately after T 2 finishes its execution, which takes 2 time units in both best-and worstcase, the offset and jitter information of T 3 relative to T 1 is: (T 1 , 2, 0). Depending on the system topology a task may have an offset and jitter relative to several reference tasks. This is shown in figure 4

Worst Case Response Time Analysis

In this section, we derive the worst-case response time calculation for a lower priority task T l considering the relative offset and jitter information for higher or equal priority tasks belonging to the same transaction Γ.

The worst-case scenario for the task under analysis is obtained by constructing a critical instant t c that leads to the worst-case busy period. Let us assume that t c is started by some task T c ∈ hp Γ (T l ). Without loss of generality, we set the origin of time at t c . We will first show the maximum contribution of tasks belonging to hp Γ (T l ) to the busy-period, by considering global offsets only. Then we will additionally consider the relative offset and jitter.

We assign indexes to each external event, e, activating the transaction Γ as shown in figure 2. The first external event that occurs before or at t c is denoted e 0 . Previous external events are assigned negative indexes. Following external events are assigned positive indexes. For each task T i belonging to hp Γ (T l ), each job is assigned the index of the associated external event. A job of T i with an index k is denoted T i,k . The activation instant of T i,k is denoted t i,k .

The earliest job of T i that can be delayed enough to be activated at the critical instant is denoted n i . In Figure 2, n i is -2. In [START_REF] Tindell | Adding time-offsets to schedulability analysis[END_REF] and [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF], it was proven that the maximum contribution of a job T i,k , with k ≥ n i , to the busy period is obtained by delaying its activation by a certain amount of jitter to coincide with t c , or to activate it without any delay if its earliest activation time occurs after t c : e.g. in figure 2, the maximum contribution of T i to the busy period is obtained by activating T i,-1 and T i,-2 at t c and all the following jobs without any delay. Note that jobs with an index smaller than n i are not considered since they cannot be delayed enough to be activated at t c .

So far, to calculate the maximum contribution of a job T i,k to the worst-case busy period, we determined its activation instant depending on its global offset and jitter only. However, if a relative offset and jitter information is available, an other dependency could exist between T i,k and jobs triggered by the associated external event e k , i.e. jobs having the same index k, and belonging to other tasks from hp Γ (T l ). Recall the example in section 5.1. By exploiting the available offset and jitter information relative to T 1 , we found out that an activation of T 4 precedes the activation of T 3 triggered by the same associated external event, by 2 time units. I.e. although each job can be delayed to coincide with t c , it is impossible to activate them simultaneously at t c .

Let T j be a task which also belongs to hp Γ (T l ). We assume that both T i and T j have an offset and jitter information relative to a reference task T r . Let (T r , Φ i (T r ), J i (T r )) be this information for T i and (T r , Φ j (T r ), J j (T r )) for T j . Consider the jobs T i,k and T j,k , with k ≥ n i , k ≥ n j and k ≤ 0. Without loss of generality, let us assume that due to the available relative offset and jitter information, the activation of T i,k always precedes the activation of T j,k . If we assume a maximum contribution of T i,k to the busy period by activating it at t c , T j,k will be activated after t c , and thus its activation may occur outside the busy period. On the other hand, if we assume a maximum contribution of T j,k to the busy period by activating it at t c , T i,k must be activated before t c and thus, is not considered for the busy period. Figure 5 shows both activation scenarios for T i,k and T j,k . In general, when considering the available relative offset and jitter information, and in order to obtain the maximum contribution to the busy period of jobs belonging to different tasks and having the same index, we have to consider all activation scenarios. In each scenario, a maximum contribution to the busy period is assumed for one job by activating it at t c . Depending on the activation instant of this job and all available relative offset and jitter information, activation instants for the other jobs are calculated. Note that this is very similar to the global offset exploitation concept, where it is necessary to check all possible critical instant construction scenarios and choose the one that leads to the worst-case response time [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF]. In the following, the activation scenario of jobs triggered by the external event e k is denoted A k . When a maximum contribution to the busy period is assumed for a job with index k, we say that this job determines the activation scenario A k .

Figure 5. Activation scenarios for T i,k and T j,k

In section 5, we stated that each task may have an offset and jitter relative to several reference tasks. When constructing an activation scenario, we choose a reference task which is common to all tasks on the same resource and having relative offset and jitter information. If there are several common reference tasks, we choose the most "recent" task as reference. In the example in figure 4, assuming that we are constructing an activation scenario for T 9 and T 10 only, we choose the task T 4 as reference task among the set of common reference tasks T 1 , T 4 . When constructing an activation scenario for T 9 , T 10 and T 11 , the only common reference task is T 1 .

After having constructed all activation scenarios for jobs having the same index, we still need to combine them with activation scenarios for jobs having other indexes. Assume that k -1 ≥ n i and k -1 ≥ n j , i.e. the activations of T i,k-1 and T j,k-1 can also be delayed to coincide with t c . Figure 6 shows the activation scenarios A k-1 and A k involving jobs of T i and T j , assuming a higher priority for T i . Note that since an activation of a job cannot precede the activation of an anterior job belonging to the same task, T i,k-1 and T j,k cannot respectively determine the activation scenarios A k-1 and A k at the same time. In general, if a job of some task T s determines an activation scenario, all activation scenarios having higher indexes can only be determined by jobs either belonging to T s or belonging to tasks that precede T s . This allows a reduction of the number of activation scenarios combinations we need to check. Note that the process of combining activation scenarios is also very similar to the process of combining critical instant candidates belonging to different transactions, when exploiting global offsets [START_REF] Palencia | Schedulablilty analysis for tasks with static and dynamic offsets[END_REF].

Figure 6. Activation scenarios A k-1 and A k involving jobs of T i and T j

In the following, we drop the assumption that an activation of T i always precedes the activation of T j . Let us now assume that T i,k determines the activation scenario A k by activating T i,k at the instant t i,k = t c . Let δ i,k be the delay needed by the activation of T i,k to occur at t c (see δ i,k in figure 5). The earliest occurrence of t j,k , t min j,k , can be expressed by the following equation:

t min j,k = t c + Φ j (T r ) -Φ i (T r ) -min(δ i,k , J i (T r )) (1) Proof.
Let us first calculate the earliest completion time of T r,k as a function of t i,k . The activation of T i,k occurs after an offset Φ i (T r ) after the completion time of T r,k and can experience a maximum delay of J i (T r ). On the other hand, this delay cannot exceed δ i,k . Therefore, the maximum delay experienced by T i,k , relative to T r,k , corresponds to min(δ i,k , J i (T r )). The earliest completion time of T r,k occurs consequently at the instant t i,k -Φ i (T r )min(δ i,k , J i (T r )). Now we can calculate the earliest occurrence of t j,k as a function of t i,k . T j,k is activated at the earliest after an offset Φ j (T r ) after the completion time of T r,k . Therefore, the earliest activation instant of T j,k is t i,k +Φ j (T r ) -Φ i (T r )min(δ i,k , J i (T r )). Since t i,k = t c , equation 1 holds.

The latest occurrence of t j,k , t max j,k , can be expressed by the following equation:

t max j,k = t c + Φ j (T r ) -Φ i (T r ) + J j (T r ) -max(0, δ i,k + J i (T r ) -J i ) (2)
Proof. Let us first calculate the latest completion time of T r,k as a function of t i,k . The activation of T i,k occurs at the earliest after an offset Φ i (r) after the completion time of T r,k , i.e. without experiencing any delay. The delay δ i,k is thus, assumed to be generated only due execution time variations of T r,k and jobs of tasks preceding T r and having the index k. However, since this delay can not exceed J i -J i (T r ), the minimum delay experienced by T i,k relative to T r,k corresponds to max(0, δ i,k + J i (T r ) -J i ). Therefore, the latest completion time of T r,k occurs at the instant t i,k -Φ i (T r )max(0, δ i,k + J i (T r ) -J i ). Now we can calculate the latest occurrence of t j,k as a function of t i,k . T j,k is activated at the latest after an offset Φ j (T r ) and a maximum delay J i (T r ) after the completion time of T r,k . Therefore, the latest activation instant of t j,k is

t i,k +Φ j (T r )-Φ i (T r )+J j (T r )-max(0, δ i,k +J i (T r )-J i ).
Since t i,k = t c , equation 2 holds. Now we can calculate the instant t j,k which leads to a maximum contribution of T j,k to the busy period, under the assumption that T i,k determines A k . Since the activation of T j,k cannot precede the activation of T j,k-1 , the maximum contribution of T j,k to the busy period is obtained when t j,k = max(t c , t j,k-1 ). In addition, t j,k belongs to the interval [t min j,k , t max j,k ]. Therefore, we have to distinguish following cases:

• max(t c , t j,k-1 ) < t min j,k : in this case, the maximum contribution of T j,k to the busy period is obtained when it is activated as soon as possible after the instant max(t c , t j,k-1 ). I.e. t j,k = t min j,k . In the example in section 5.1, the maximum contribution of T 3,0 to the busy period is obtained when t 3,0 = t c = 0. However, since t min 3,0 = 2 under the condition that T 4,0 determines the activation scenario A 0 , t 3,0 = t min 3,0 = 2. • max(t c , t j,k-1 ) > t max j,k : We know that t max j,k is greater or equal t j,k-1 . Consequently, max(t c , t j,k-1 ) = t c . Therefore, the instant t j,k occurs before t c . I.e. T j,k does not contribute to the busy period. In the example in section 5.1, the maximum contribution of T 4,0 to the busy period is obtained when t 4,0 = t c = 0. However, since t max 4,0 = -2 under the condition that T 3,0 determines the activation scenario A 0 , t 4,0 occurs before t c .

• max(t c , t j,k-1 ) ∈ [t min j,k , t max j,k ]: in this case, the maximum contribution of T j,k to the busy period is obtained when t j,k = max(t c , t j,k-1 ). Now after having considered jobs with indexes lower or equal 0, we will calculate the activation instants of jobs with indexes greater than 0. In the following, we show that the activation of T j,1 cannot be delayed by the activation of previous jobs and thus, the maximum contribution to the busy period of jobs with indexes greater than 0 is obtained when they are activated, as before, without experiencing any delay.

The activation of T j,1 cannot occur before the instant t c + Φ j . I.e. t min j,1 ≥ t c + Φ j . On the other hand, as stated above, depending on the relative offset and jitter information, t j,k , with n j ≤ k ≤ 0, occurs either before t c , at t c , at t j,k-1 or at t min j,k . We show that t j,k ≤ t c + Φ j :

• t j,k ≤ t c : it is obvious that t j,k ≤ t c + Φ j

• t j,k = t min j,k : using equation 1, we can state that t min j,k ≤ t c + Φ j (T r ). Therefore, since Φ j ≥ Φ j (T r ), t min j,k ≤ t c + Φ j .

• t j,k = t j,k-1 : since t j,k-1 also occurs either before t c , at t c , at t j,k-2 or at t min j,k-1 , we can replace k -1 by k and repeat the same process described above.

Since no job having an index lower or equal 0 can delay the activation of T j,1 , jobs with indexes greater than 0 can be considered activated as before, without any delay. Therefore, there is no need to exploit the potential relative offset and jitter information for these jobs.

As explained above, to exploit relative offset and jitter for the worst-case response time calculation we need to consider all combinations of activation scenarios with indexes lower or equal 0. Since for each task, the number of jobs that can be delayed to coincide with t c is bounded, the relative offset and jitter exploitation only adds a polynomial number of cases to check to the global offset exploitation algorithm WCDO.

Experiments

We have performed a large number of experiments using randomly generated systems with tree-shaped taskdependencies. Tasks mapping, event models, core execution times and priorities were also assigned randomly. We have compared the results obtained using our technique considering relative offset an jitter with the results obtained by the inter event stream context blind analysis (i.e. without considering timing-correlation between tasks), WCDO, and WCDOPS+.

Figure 7 shows the response time average ratios R blind /R relative , R W CDO /R relative and R W CDOP S+ /R relative as function of the system utilization. The results show that a large improvement can be obtained due to the relative offset and jitter exploitation: up to 66% compared to the inter event stream context blind analysis, up to 57% compared to the WCDO and up to 41% compared to WCDOPS+. It is also interesting to note that in general, a larger improvement is obtained for large system utilization. This is due to the fact that a large system utilization leads to higher calculated worst-case response times. This in turn leads to larger task global jitters on which, the response times themselves depend. When

Conclusion

In this paper we presented a new technique to capture timing-correlation between tasks in distributed systems with tree-shaped task-dependencies. We have seen that considering the external system events activating tasks as unique timing reference does not allow to capture the complete existing timing-correlation between tasks in parallel paths. Our solution consists in considering tasks with several successors as additional timing-references. We also developed an algorithm to exploit this approach for the worst-case response time analysis under a static priority scheduler. Through our experiments, we showed that our technique allows to calculate considerably tighter bounds compared to other techniques. We consider that our approach is an important extension of the collection of analysis techniques exploiting timing-correlation between tasks in distributed systems.

  which represents an extension of the system in figure 1. T 5 , T 6 and T 8 have an offset and jitter relative to T 1 and T 3 while T 7 , T 9 and T 10 have an offset and jitter relative to T 1 and T 4 .

Figure 4 .

 4 Figure 4. System showing tasks having offset and jitter relative to several references

Figure 7 .

 7 Figure 7. Response time average ratios as a function of utilization considering relative jitters, the effect of global jitters on response times calculation can be reduced and thus, lower response-times are calculated.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE