Optimal Priority Assignment to Control Tasks

A Optimal Priority Assignment to Control Tasks GIULIO M. MANCUSO, Scuola Superiore Sant’Anna ENRICO BINI, Lund University GABRIELE PANNOCCHIA, University of Pisa

In embedded real-time systems, task priorities are often assigned to meet deadlines. However, in control tasks, a late completion of a task has no catastrophic consequence. Rather, it has a quantifiable impact in the control performance achieved by the task. In this paper, we address the problem of determining the optimal assignment of priorities and periods of sampled-data control tasks that run over shared computation unit. We show that the minimization of the overall cost can be performed efficiently using a branch and bound algorithm, which can be further speeded up by allowing for a small degree of sub-optimality. Detailed numerical simulations are presented to show the advantages of various branching alternatives, the overall algorithm effectiveness, and its scalability with the number of tasks.

1. INTRODUCTION

In embedded systems, it is of crucial importance to make a careful usage of any available resource. One of the most critical resources is certainly the CPU. Modern RealTime Operating Systems (RTOS) provide several mechanisms to allocate the CPU resource to all the demanding tasks. While RTOS implements the mechanism for reserving the resources, the actual CPU allocation must be performed by the application designer. However, the determination of the most appropriate CPU allocation is a very delicate task since it can affect significantly the performance. In addition, as it typically happens in cyber-physical systems, choosing the best possible CPU allocation requires the knowledge of a wide spectrum of disciplines from the application domain to the RTOS internal structure. Hence, any method which can support this stage is certainly helpful. The most popular way to assign the CPU to tasks is by setting priorities. Priorities exist in any modern RTOS (such as LynxOS1 , Enea OSE2 , QNX Neutrino RTOS3 , ERIKA Enterprise4 ). However, the problem of assigning the “best” priority is generally open and application-dependent. First of all, it is necessary to understand the effect of priorities on tasks. It is well understood that tasks running at lower priority will 1 http://www.lynuxworks.com/rtos/ 2 http://www.enea.com/software/solutions/rtos/ose/ 3 http://www.qnx.com/products/neutrino-rtos/ 4 http://www.evidence.eu.com/products/erika-enterprise.html

The research leading to these results was supported by the Linneaus Center LCCC, the ELLIIT Excellence Center, and the Marie Curie Intra European Fellowship within the 7th European Community Framework Programme. Author’s addresses: G. M. Mancuso, Scuola Superiore Sant’Anna; E. Bini, Lund University; G. Pannocchia, University of Pisa. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or [email protected]. c YYYY ACM 1539-9087/YYYY/01-ARTA $15.00

DOI:http://dx.doi.org/10.1145/0000000.0000000 ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:2

G. M. Mancuso et al.

suffer a higher interference and hence their execution will be delayed more. We can understand this simple principle, for example, by studying the classical response time analysis [Joseph and Pandya 1986]. In control systems, it is possible to relate the task delay to the associated control cost which can be quantified, e.g., in a classical Linear Quadratic Regulation (LQR) ˚ om and Wittenmark 1997; Franklin et al. 1994; Kondo and Furuta 1985]. scheme [Astr¨ By exploiting this relationship, it is possible, in principle, to determine the effect of the priority assignment on the control performance, and then to design a scheme that optimally assigns priorities. Following this intuition, in this paper we propose the following contributions: — we describe a branch and bound algorithm for finding the optimal priority assignment of a control task; — we propose an approximation scheme, which can trade the computational complexity of the search with the proximity to the minimal control cost. 1.1. Related works

“Optimal” priority assignments were investigated in the literature for several different interpretations of optimality. In real-time systems a priority assignment P is defined optimal if any task set which does not miss a deadline with any other priority assignment P 0 will never miss a deadline with P too. Liu and Layland [1973] proved the optimality of Rate Monotonic (RM), when the task deadline is assumed equal to the task period. Later, Leung and Whitehead [1982] proved the if deadlines are constrained to be not larger than periods, then Deadline Monotonic (DM) is optimal. Audsley [1991] provided an algorithm for Optimal Priority Assignment (OPA) in the case of arbitrary deadline. Finally, Shin and Sunwoo [2007] formulated a genetic algorithm to assign periods and priorities to a distributed real-time application, minimizing a weighted response time. When scheduling jobs over machines, there may be several definitions of optimality: (i) makespan minimization, (ii) maximum lateness minimization, (iii) weighted flow time minimization. Tzafestas and Triantafyllakis [1993] provide a good overview of sequencing methods. In queuing systems, it is often investigated the effect of priorities over the average waiting time of jobs. Nain and Ross [1986] found the priority that minimizes a linear combination of the average queue lengths for all service classes in the queueing system. Altman and Shwartz [1989] addressed the same problem with a time sharing policy. Chipalkatti et al. [1989] investigated the effect of several priority assignments in statistical multiplexer. Contributions that are more closely related to the topic of this paper, investigate the relationship between the amount of allocated resource and the control cost. Seto et al. [1996] investigated the assignments of task periods when the resource constrain is expressed as a utilization upper bound. The influence of task delay and jitter in Linear Quadratic Gaussian (LQG) control has been investigated by Nillson et al. [1998]. Kao and Rantzer [2007] established the bounds on the magnitude and the derivative of the control action, which guarantee the stability of a linear plant, in continuous-time systems. Bini and Cervin [2008] determined an analytic solution of the optimal task periods in the case of a cost function linear in both task period and delay. When tasks are scheduled by Earliest Deadline First (EDF), Wu et al. [2010] described a method, although non-optimal, to assign jointly task periods and deadline to control tasks, so that a control cost is minimized. In a recent work, we addressed the computation of the optimal period of each task in order to minimize the worst-case task cost when the priority among tasks is fixed a-priori [Mancuso et al. 2011]. By exploiting the idea ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:3

that a task does not affect any other task with higher priority [Audsley 1991], Aminifar et al. [2012] did investigate the period and priority assignment, which preserve, by construction, system stability. However, the optimality of the priority assignment is not proven. Aminifar et al. [2014] proposed a co-design technique to design both the controller and the bandwidth server isolating the controller, such that the overall consumed resource is minimized and the plant is stable. Finally, it was recently proposed to design the controller by using the distribution of the job response time as controller delay [Xu et al. 2014]. 2. BACKGROUND 2.1. System model

We assume there are N control tasks denoted by τ1 , . . . , τN . Also, we denote the set of the first N strictly positive integers by N := {1, . . . , N } ⊂ N. Every period Ti , each task releases a job with computation time Ci . The frequency of the task activations i is denoted by fi := T1i , whereas its utilization is denoted by Ui := C Ti = Ci fi . Notice that, although more advanced task models have been proposed to capture complex task structures [Stigge et al. 2011], the assumption of a constant computation time is realistic for control tasks, since they typically have no conditional statements as they perform only a matrix multiplication (by the feedback gain), in a large number of cases. We represent a priority assignment by the vector π := [i1 |i2 | . . . |iN ] of the indices of tasks sorted in decreasing priority order. For a given priority assignment vector π, we also define its inverse permutation by the vector pri pri(i) = p

⇔

π(p) = i.

In accordance to this definition, pri(i) is the priority of task τi (a lower value of pri(i) indicates a higher priority). For example, the priority assignment vector π = [3|1|2] indicates that τ3 is the highest priority task, τ1 is the second highest priority task, and τ2 is the lowest priority task. Consequently, the vector pri is [2|3|1]. Given a priority assignment vector π, for any task τi we define the set of higher priority tasks as: hpi := {j ∈ N | pri(j) < pri(i)}.

(1)

We denote a partial priority assignment by π = [S1 |S2 | . . . |S` ], with S1 , S2 , . . . , S` beS` ing disjoint subsets of N , such that k=1 Sk = N . Any τj with j ∈ Sk has higher priority than any τi with i ∈ Sr and r > k. However, the priority ordering among any pair τi , τj with i, j belonging to the same Sk , is not specified (this explains why the priority ordering is referred to as partial). The definition of partial priority assignments is necessary for the branch and bound algorithm, which assigns only one task priority per depth level of the search tree (more details will follow in Section 3). Notice that, by generalizing the definition of pri(i) as pri(i) = p

⇔

i ∈ Sp ,

given a partial priority assignment π = [S1 |S2 | . . . |S` ], for any task τi we can still define the set hpi of tasks having higher priority than τi as in (1). We define the set P as the set of all possible complete priority assignments. We also denote as |P| the cardinality of P. The set P is the set of all possible permutations of N elements of N , and then it follows that |P| = N !. A generic subset of P is denoted by Pi . Notice that Pi corresponds to a partial or a complete priority assignment, depending on |Pi |. In particular, Pi represents a partial priority assignment when |Pi | > 1. Notice that a given partial priority assignment πi corresponds to a particular set Pi whose elements are complete priority assignments. For example, if the partial priorACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:4

G. M. Mancuso et al.

ity assignment vector is πi = [2|4 1|3] = [S1 |S2 |S3 ], then: hp2 = ∅, hp1 = hp4 = {2}, hp3 = {1, 2, 4}, and it follows that Pi = {[2|4|1|3], [2|1|4|3]}. 2.2. Cost model in control systems

In this section we recall some basics of control systems and we formulate the cost of a control action. We assume that each task is controlling a continuous-time system, with a state x evolving according to the following ordinary differential equation (ODE)5 : x(t) ˙ = Ax(t) + Bu(t),

x(0) = x0

(2)

with A ∈ Rn×n , and B ∈ Rn×m . We assume that (A, B) is controllable and that the state is measurable by the control task. We formulate the cost minimization problem as a Linear Quadratic Regulator (LQR) problem. In this context, the control input signal u must be found so that the following cost Z ∞
0 0 x(t) Q x(t) + u(t) R u(t) dt, (3) J= 0

is minimized, subject to the constraint (2) of the system dynamics. In (3), Q and R are positive definite matrices of appropriate dimensions, representing the weights of the state and of the input, respectively. Also, we adopt the Matlab-like notation x0 to denote the transpose of the vector x. The minimization of the cost J of (3) has the following physical interpretation: the aim of the design is to determine a control strategy such that x tends to zero quickly (stability), without requiring a too large effort with the control signal u. The relative importance of the speed of convergence to zero of the state x, and the cost of applying a control signal u, is determined by the weights Q and R. This problem is extremely well studied in control systems, and the optimal control input is given by [Kwakernaak and Sivan 1972, Sec. 3.4.2] u∗ (t) = −R−1 B 0 S x(t),

(4)

where S is the unique positive definite solution of the Algebraic Riccati Equation (ARE) A0 S + SA + Q − SBR−1 B 0 S = 0. ∗

(5)

x00

and, the optimal cost is J = S x0 . In embedded systems, however, controllers are not capable of applying a continuous signal. Rather, they are implemented by software tasks with period T and a delay ∆ from the sensing to the actuation, due to the computation of the control law and to the preemption of higher priority tasks. In Figure 1, we represent how the task schedule affects the control input for a vehicle active suspension control systems [Gao et al. 2010] . At the bottom we represent the schedule of task τ3 . It can be noticed that its schedule is delayed by the execution of the higher priority tasks τ1 and τ2 . The delay pattern ∆3,1 , ∆3,2 , ∆3,3 , . . . varies over time and then, the control signal u3 changes at instants which are not strictly periodic. At the top of the figure, we also represent the evolution of the system state x3 in accordance to the given control signal u3 . In this case, the determination of the optimal solution becomes more complex. If the delay from sensing to actuation is constantly equal to ∆, the minimization of the cost (3) can still be performed [Mancuso et al. 2011]. A discussion of the limits of the assumption of a constant delay is given in Section 2.3. Without entering into many details (which can be found in [Mancuso et al. 2011]), the cost of the optimal control 5 For

simplicity of notation, we avoid using subscripts (e.g., Ai , Bi , etc.) to denote parameters and variables of the system controlled by τi .

ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:5

Fig. 1. Example of control signal for task τ3 , with period T3 and time-varying delay.

˜ ∆). action of a controller with period T and delay ∆ can be written as a function J(T, Such a cost function can also be normalized, so that ˜ 0) = 1, J(0,

˜ ∆) ≥ 1. J(T,

For example, in Figure 2 we show the cost J˜ as function of T for ∆ ∈ {0, 0.025, 0.05} for vehicle active suspension systems [Gao et al. 2010]. Moreover, for the purpose of solving the cost minimization problem, it is often convenient to use the following linearization of the control cost ˜ ∆) ≈ J (T, ∆) = αT + β∆ + γ. J(T,

(6)

Next we assume that α and β are strictly positive, since we expect that the cost J˜ increases with both the period T and the delay ∆. 2.3. Model of task delay

The concept of job delay is quite intuitive: it is the time that elapses from the sampling instant (which can be assumed coincident with the job activation) to the actuation instant (which can be assumed equal to the job completion time) of a job. However, the job delay has several characteristics which make it unfit for the controller design problem: (1) the job delay is a discontinuous function of the task parameters: for example, there may be an infinitesimal variation of a task period which produces a sensible variation of the response time, due, for example, to the interference of another higher priority job. Analytically, this phenomenon is a consequence of the discontinuity of the ceiling operator in the response time analysis [Joseph and Pandya 1986]; (2) while the impact of a constant delay in the control cost can be determined [Mancuso et al. 2011], the presence of time-varying delay, as shown in Figure 1, challenges ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:6

G. M. Mancuso et al.

Fig. 2. Example of cost J˜ function.

significantly the analysis of the impact of the delay pattern on the control cost. In addition, the relationship between the task periods and the pattern of job delay is provided only through the iterative procedure of the response time analysis [Joseph and Pandya 1986]. Such a relationship cannot be differentiated, as required by optimization procedures. It is then necessary to find a suitable model for task delay, which can then be used for solving the optimal design problem. One option is to use an approximation of the response time that has some smoothness properties that allows us to solve the problem of minimizing the control cost. Bini et al. [2009] proposed a continuous and differentiable upper bound of the response time. They proved that

Ri ≤

Riub

:=

Ci +

P

j∈hpi

1−

P

Cj (1 − Uj )

j∈hpi

Uj

.

(7)

Thanks to the smoothness of this upper bound, optimization methods can be better performed if this expression of the delay is used. However, this approach presents two drawbacks: (1) Since Riub is not convex w.r.t. task periods, numerical solvers are not guaranteed to find a period assignment that guarantees a global minimum cost; (2) Since the response time Ri is the maximum response time of all the jobs activated by τi and Riub ≥ Ri , if we set ∆i = Riub we would certainly overestimate the impact of the delay in the controller. Rather, we prefer to approximate the task delay by possibly convex quantity that is smaller than Riub . By lower bounding the ceiling operator in response time analysis, ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:7

we find

Ri = Ci +

X  Ri  X Ri Cj ≥ Ci + Cj Tj Tj

j∈hpi

Ri ≥

1−

j∈hpi

C P i

j∈hpi Uj

=: Riapprox .

(8)

Let’s now examine some properties of Riapprox , defined as the RHS of the inequality above. First, its convexity makes it suitable for optimization. Second, Riapprox is a closer approximation of the average task delay, since it is a lower bound to the longest job delay, as shown in (8). Finally, it is possible to determine an analytic solution to the optimal period assignment problem, when the controller cost is linearized w.r.t. the period and the delay [Bini and Cervin 2008]. Intuitively, Riapprox is the response time that the task τi would experience in a procesPi−1 sor that provides a fluid share of 1 − j=1 Uj of the available bandwidth. This would be the exact response time if the higher priority tasks τ1 , . . . , τi−1 received a constant share of the processor equal to their utilization. Moreover, if we use the task frequency fi and the inverse of the delay δi = 1/∆i as independent variables, setting the delay as

∆i =

1−

C P i

j∈hpi

(9)

Uj

can be rewritten as the following linear relation:

Ci δi =

X X Ci =1− Uj = 1 − Cj fj . ∆i j∈hpi

(10)

j∈hpi

In this way the solvers can take advantage of the linearity of the constraint.

2.4. Optimal Periods for a Complete Priority Assignment

In this section we briefly recall the results of [Bini and Cervin 2008]. Given a priority assignment π, Bini and Cervin [2008] addressed the problem of finding the periods Ti (or analogously the frequencies fi ) for control tasks such that the aggregate cost function X Ji (Ti , ∆i ), (11) i∈N

is minimized, where Ji := αi Ti + βi ∆i represents the linearized cost each task (notice that we drop the constant term γi from (6) because it does not alter the optimum). The cost (11) takes into account the overall performance of the systems. Let f := [f1 f2 . . . fN ] and δ := [δ1 δ2 . . . δN ] be the vectors of task frequencies and inACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:8

G. M. Mancuso et al.

verse delays, respectively. The mathematical formulation of the problem is   N X 1 1 min V(f , δ , π) := Ji , f ,δδ fi δ i i=1 N X

s.t.

Ci fi ≤ 1,

(12a) (12b)

i=1

X

Cj fj + Ci δi = 1 ∀i ∈ N ,

(12c)

j∈hpi

(12d) (12e)

f > 0, δ > 0.

In [Bini and Cervin 2008] the authors show how the optimization problem (12) can be solved in closed form by replacing each task frequency with the corresponding utilizai tion. Recalling that Ui := C Ti = Ci fi , (12c) can be exploited to remove δi from problem (12). Let U := [U1 U2 . . . UN ] be the vector of utilizations. Then, the problem (12) can be rewritten as follows: X 1 1 ˜ P min V(U, π) := ai + bi (13a) U Ui 1 − j∈hpi Uj i∈N X s.t. Ui ≤ 1, (13b) i∈N

where ai := αi Ci , bi := βi Ci . As shown in [Bini and Cervin 2008], the optimal utilizations are:  µ1  Uπ(1) = λ1 +µ1 λk−1 k Uπ(k) = λkµ+µ Uπ(k−1) k = 2, . . . , N − 1 (14) k µk−1  P  Uπ(N ) = 1 − j6=N Uj , with λk and µk defined as follows  √ µk = ap π(k) λN −1 = aπ(N ) + bπ(N ) p  λk−1 = bπ(k) + (λk + µk )2

k = 1, . . . , N − 1 k = 2, . . . , N − 1.

We remind that, in the above expressions, π(k) denotes the index of the task with priority k. 3. OPTIMAL PRIORITY ASSIGNMENT 3.1. Problem definition

Now we focus on the problem of finding the minimizer of the aggregate cost function where both periods and priorities are decision variables. The mathematical formulation of the optimal period and priority simultaneous assignment can be defined as: min

π∈P

min f ,δδ

V(f , δ , π)

s.t. (12b), (12c), (12d), (12e),

(15a) (15b)

Notice that the inner minimization is an instance of (12) and hence (for a given π ∈ P) it can be solved analytically as discussed in Section 2.4. ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:9

One way to solve the problem (15) could be by brute-force enumeration of all possible feasible priority assignments. This approach, however, is suitable only for a small number of tasks since the cardinality of the set of all possible priority assignment P is N !. Different combinatorial methods can be used to solve the above problem [Parker and Rardin 1988; Horst and Tuy 1990]. In the following section we explore a branch and bound technique to efficiently solve the optimization problem. It performs a partial enumeration of the feasible solutions by excluding from the search some subsets of the feasible space because it is proved that they cannot provide any better solution than the current best solution. 3.2. Branch and Bound Algorithm: Definitions

Before exploring the Branch and Bound algorithm, it is convenient introduce some basic concepts. If we consider a subset Pi ⊆ P of all priority assignment, we can define Φmin (Pi ) := min

π∈Pi

min V(f , δ , π) f ,δδ

s.t. (12b), (12c), (12d), (12e) . Consequently, the solution of the optimization problem (15) is (formally) given by: V ∗ := Φmin (P). Now we define a lower-bounding function Φlb : P → R>0 that satisfies the following properties. (1) For any p disjoint subsets of P such that p [ P= Pi , i=1

p \

Pi = ∅,

i=1

the following condition holds true: Φlb (Pi ) ≤ Φmin (Pi ), (16) meaning that the function Φlb must actually be a lower bound over any subset Pi ; (2) Given any complete priority assignment Pi , that |Pi | = 1, the following condition holds true: Φlb (Pi ) = Φmin (Pi ),

(17)

meaning that when the subset Pi has only one priority assignment, then the lower bound coincides with the exact solution. We discuss a suitable choice of Φlb (·) later in the Section 3.4. With all these ingredients, we can build a branch and bound policy to solve the combinatorial problem, according to the following rationale. (1) We build the search tree starting from P (root). (2) We branch the tree building a list of candidate subsets (nodes). (3) For each node we compute the lower bound Φlb (·) and compare it with the current best solution (an initial feasible solution has to be computed) (4) If the lower bound at a node is higher than the current best solution, that node and the sub-tree originating from it is pruned. In Sections 3.3 and 3.4 we explore the branching and bounding rules. A generic set Pi is referred to as a node of the search tree. Two special nodes are the root, when |Pi | = N !, and a leaf, when |Pi | = 1. It can be shown that a branch and bound algorithm based on the above rationale converges to the solution in a finite number of iterations if [Parker and Rardin 1988, Theorem 5.1]: ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:10

G. M. Mancuso et al.

(1) There are only finitely many subsets Pi that can be created at any step. (2) At any step we never explore a subset Pi that has been explored before. (3) At any step there holds: [ [ P= Pk ∪ Pj k∈candidate list

(18)

j∈pruned list

3.3. Branching rules

The branching rule allows one to recursively partition the generic working set P¯ (initially P¯ = P) into p disjoint subsets Pi such that P¯ =

p [

Pi

p \

and

j=1

Pi = ∅,

(19)

j=1

building a list of new possible candidates sets. Different branching rules could be applied. We examine two options. The first one (called “Top”) is to recursively partition the set P¯ by assigning the highest priority tasks first. Specifically, starting from P¯ = P = [S] we branch into N smaller subsets Pi = [i|S 0 ] where S 0 = S \ {i}. Hence, the set Pi denotes all possible priority assignments in which the task τi has the highest priority. Then, we proceed analogously branching again each Pi into N − 1 subsets assigning the second priority task, i.e. Pij = [i|j|S 00 ] where S 00 = S 0 \ {j}. And so forth. The second one (called “Bottom”) is to recursively partition the set P¯ by assigning the lowest priority tasks first. Specifically, starting from P¯ = P = [S] we branch into N smaller subsets Pi = [S 0 |i] where S 0 = S \ {i}. Hence, the set Pi denotes all possible priority assignments in which the task τi has the lowest priority. Then, we proceed analogously branching again each Pi into N − 1 subsets assigning the second last priority task, i.e. Pij = [S 00 |j|i] where S 00 = S 0 \ {j}. And so forth. 3.4. Bounding rule

As we said before the second key ingredient of the branch and bound algorithm is the lower bound function Φlb (·). In this section we provide the lower bound by suitably solving the optimization (13) when a partial priority assignment is provided. Let us assume that priorities are partially assigned by πi = [S1 | . . . |S` ]. Let us intro¯i , i = 1, . . . `, each corresponding to sum of the utilizations duce ` additional variables U of the tasks in Si : X ¯i = U Uj . j∈Si

Given this partial priority assignment, it is possible to find a lower bound to the aggregate cost, by optimistically assuming the following task delay model: ∆k =

1−

C Pk

j∈hpi

¯j , U

k ∈ Si ,

i = 1, . . . , `.

(20)

Compared to (9) this expression of delay is optimistic, since it assumes that all tasks k ∈ Si have at the same time the highest possible priority in the partition Si . Let ¯1 U ¯2 . . . U ¯` . We can then find a lower bound to the optimal cost associated ¯ := U U ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:11

with a (partial) priority assignment π = [S1 | . . . |S` ], by solving the following problem: P ` X X 1 k∈Si bk P min ak + (21a) ¯j ¯ Uk 1− U U,U s.t.

` X

j∈hpi

i=1

k∈N

¯i ≤ 1 U

(21b)

i=1

X

¯i Uk = U

(21c)

i = 1, . . . , `.

k∈Si

Let νi denote the Lagrange multiplier of the i-th equality constraint in (21c). By differentiating the Lagrangian function associated with (21) w.r.t. any Uk , k ∈ Si , and setting this partial derivative to zero (for optimality), we find r ak 1 . (22) −ak 2 + νi = 0 ⇒ Uk = Uk νi Then, from the i-th equality constraint in (21c) we find 1 X√ ¯i , ak = U √ νi k∈Si

and from (22) we obtain:

√ ¯i P Uk = U

ak √

j∈Si

aj

k ∈ Si .

,

(23)

By replacing (23) in (21a), we find that the problem (21) is equivalent to the following one P `  X ` X X √ 2 1 k∈Si bk P min ak ¯ + (24a) ¯j ¯ Ui 1− U U i=1

s.t.

` X

i=1

k∈Si

j∈hpi

¯i ≤ 1. U

(24b)

i=1

We observe that problem (24) is an instance of the problem as (13) with a suitable redefinition of task set with coefficients and delays as follows:  X √ 2 X Ci P ¯ . a ¯i = ak , ¯bi = bk , ∆i = 1− Ui k∈S k∈S i

i

j∈hpi

¯∗

Thus, we can obtain the optimal vector U (π) analytically as discussed in Section 2.4 ˆ (and optionally recover the optimal vector U∗ (π) using (23)). Finally, we denote by V(π) the optimal value function, i.e.: ˆ V(π) :=

` X i=1

` X ¯bi a ¯i P + ¯ ∗ (π) ¯ ∗ (π) . U 1 − j∈hpi U i j i=1

(25)

The following result holds. T HEOREM 1. Given P 0 , P 00 ⊆ P, corresponding to the priority assignments π 0 and π , respectively, if P 00 ⊂ P 0 then ˆ 0 ) < V(π ˆ 00 ). V(π (26) 00

ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:12

G. M. Mancuso et al.

P ROOF. Let π 0 = [S1 | . . . |Sk | . . . |Sl ] be the partial priority assignment which defines the set P 0 . By definition P 00 ⊂ P 0 means that some (at least one) of the subsets Sk defining π 0 are split into two or more subsets in π 00 . Without loss of generality (as the following argument can be repeated if necessary), we can assume that π 00 = [S1 | . . . |Sk1 |Sk2 | . . . |S` ], i.e. π 00 is identical to π 0 except for Sk which is divided into Sk1 , Sk2 , where Sk = Sk1 ∪ Sk2 and Sk1 ∩ Sk2 = ∅. For any i ∈ Sk , let Ci 00 ∆i (π 0 ) := 1−P Ci U ¯ ∗ (π 0 ) and ∆i (π ) := 1−P ¯ ∗ (π 00 ) be, respectively, the delay of U j∈hpi

j∈hpi

j

j

task i as given in (20) for π 0 and π 00 and associated optimal utilizations. Recalling that all tasks in Sk1 have higher priority than any task in Sk2 , from the delay model (20) it follows that:  ∆i (π 0 ) = ∆i (π 00 ) i ∈ Sk1 , ∆i (π 0 ) > ∆i (π 00 ) i ∈ Sk2 . Thus, (26) follows from strict monotonicity of the tasks cost w.r.t. to the associated delay. p S Pi , it follows C OROLLARY 1. Given a set P¯ and p disjoint subsets such that P¯ = i=1

that ˆ π ) < V(π ˆ i ) ∀i = 1, . . . , p. V(¯ Given the previous results, for any subset Pi ⊂ P and its associated partial assignment vector πi , we can define a suitable lower bound on the optimal cost associated to any complete priority assignment drawn from Pi as: ˆ i ). Φlb (Pi ) := V(π

(27)

3.5. Overall algorithm and approximate solution

The generic pseudo-code of the overall algorithm used in this work is represented by Algorithm 1. Using Algorithm 1, we can either find the global minimum or an approximated solution with a prescribed relative accuracy  > 0. At each iteration of ¯ in order to achieve an approximate the algorithm, given the current best solution V, solution we can prune when ¯ Φlb (Pi ) ≥ (1 − )V. Clearly, at each iteration more branches will be pruned compared to the case of optimal solution (corresponding to  = 0), and this will speed up completion of the algorithm. It also follows that the achieved solution has a cost V ∗ () that satisfies: (1 − )V ∗ () ≤ V ∗ ≤ V ∗ ().

(28)

where V ∗ is the true optimal cost. 4. EXPERIMENTAL RESULTS

The optimal algorithm has been tested with a set of randomly generated optimal control problems with N = 5, . . . , 10. The optimization parameters have been generated within a range of respectively Ci ∈ [1, 100], αi ∈ [1, 1000] and βi ∈ [1, 10000]. This choice is supported by the observation that, in general, the cost functions Ji are more sensitive to the delay than to the sampling time. We evaluated the number of visited nodes as well as the run time of both exact ( = 0) and approximated search algorithm ( > 0). For a given N we run the solver 30 times starting from different random initial priority assignments. When the branch and bound algorithm is run using  = 0, it is clear that the achieved minimum does not depend on the initial guess. However, ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:13

ALGORITHM 1: Branch and bound algorithm ¯ = min V(·), approximation parameter  > 0 Input: Initial feasible solution π ¯, V δ ,π=¯ f ,δ π

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Set P¯ = P; ¯ > 1) then if (|P| Partition P¯ into p disjoint subsets Pi , as described in Section 3.3; for i = 1 : p do Evaluate Φlb (Pi ), as described in Section 3.4; ¯ then if Φlb (Pi ) ≥ (1 − )V ¯ Prune Pi from P; else Go (recursively) to Line 2 with P¯ temporarily redefined as Pi end end else ¯ 0, especially as the number of tasks increases. Furthermore, in Figure 5, we plot the run-time of the optimization routine using the Top and Bottom branching rules to achieve the global optimum. For the Bottom rule, we also report the run-time of required to achieve a sub-optimal solution using  = 0.01 or  = 0.1. These experiments were performed on a machine with an AMD Opteron running at 1.9 GHz and 64GB of RAM. The execution time of the optimal algorithm is still exponential. However, tolerating a small deviation to the optimum does reduce the run-time dramatically. For example, by linearly interpolating the algorithm run-time, we claim the approximated algorithm can find a solution of 20 tasks within a tolerance ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:14

G. M. Mancuso et al.

Fig. 3. Comparing Bottom and Top branching rules.

Fig. 4. Comparison of the Bottom approach against the worst case path in the tree for different values of .

of  = 0.1 to the optimum, in one second. Given the superior performance of the Bottom branching rule, from now on we only focus on this in the subsequent studies. Motivated by the observation that the more similar are tasks the less relevant is going to be the priority assignment, we investigated the effect of the variance of the task parameters over the number of visited nodes. To this purpose, the task computation times Ci are randomly generated within the interval [Cavg − φL, Cavg + φL], with φ ∈ [0, 1]. The average computation time Cavg and maximum length of the interval 2L are such that the interval is again [1, 100] with φ = 1. Hence, by changing φ, we can control how the computation times are similar (with small φ) or diverse (φ close to 1). ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:15

Fig. 5. Execution Time.

The task cost coefficients αi and βi are generated according to the same principle with the same φ. In Figure 6, we report the normalized number of visited nodes for varying φ, with N = 8 tasks. When parameters are identical for all tasks (φ = 0), it is clear that the

Fig. 6. Effect of the variability of the task parameters.

optimal algorithm ( = 0) needs to visit all nodes since all possible priority assignments lead to the same overall cost. At the same time, allowing some distance to the optimum ( > 0) can lead to huge pruning, since all different branches are the same. Conversely, as soon as the task parameters are different (φ → 1) the number of nodes visited by ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

A:16

G. M. Mancuso et al.

the optimal algorithm decreases and tolerating some  > 0 does not produce the same drastic reduction. 5. CONCLUSIONS

The assignment of priorities can indeed affect significantly the performance of control tasks. Rather than using some meta-heuristic to assign task priorities (genetic algorithm, simulated annealing, etc.), we propose a branch and bound algorithm which is capable to find either the optimum or an approximation with an arbitrary small error . The key ingredient that enables an efficient implementation is a tight bounding rule. Future directions of further research include: — the extension to the case with a more realistic cost model; — the search for a more adherent delay model, which allows an efficient solution of the optimization problem as well as a tighter characterization of the realistic task delay; — the exploitation of richer information on the task delay for determining a tighter impact on the control LQG cost. REFERENCES ˚ om and B. Wittenmark. 1997. Computer-controlled systems: theory and design (third ed.). Prentice K. J. Astr¨ Hall. Eitan Altman and Adam Shwartz. 1989. Optimal priority assignment: a time sharing approach. IEEE Trans. Automat. Control 34, 10 (Oct. 1989), 1098–1102. DOI:http://dx.doi.org/10.1109/9.35286 Amir Aminifar, Enrico Bini, Petru Eles, and Zebo Peng. 2014. Bandwidth-Efficient Controller — Server Co-Design with Stability Guarantees. In 2014 Design, Automation and Test in Europe Conference. Amir Aminifar, Soheil Samii, Petru Eles, Zebo Peng, and Anton Cervin. 2012. Designing High-Quality Embedded Control Systems with Guaranteed Stability. In Proceedings of the 33rd IEEE Real-Time Systems Symposium. San Juan, Puerto Rico. Neil Audsley. 1991. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report YCS 164. Dept. Computer Science, University of York. Enrico Bini and Anton Cervin. 2008. Delay-Aware Period Assignment in Control Systems. In Proceedings of the 29th IEEE Real-Time Systems Symposium. Barcelona, Spain, 291–300. ˆ Nguyen, Pascal Richard, and Sanjoy K. Baruah. 2009. A Response-Time Bound Enrico Bini, Thi Huyen Chau in Fixed-Priority Scheduling with Arbitrary Deadlines. IEEE Trans. Comput. 58, 2 (Feb. 2009), 279–286. DOI:http://dx.doi.org/10.1109/TC.2008.167 Renu Chipalkatti, James F. Kurose, and Don Towsley. 1989. Scheduling policies for realtime and non-real-time traffic in a statistical multiplexer. In Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies. 774–783. DOI:http://dx.doi.org/10.1109/INFCOM.1989.101526 G. Franklin, A. Emami-Naeini, and J. D. Powell. 1994. Feedback Control of Dynamic Systems (third ed.). Addison-Wesley Longman Publishing Co. Huijun Gao, Weichao Sun, and Peng Shi. 2010. Robust Sampled-Data Control for Vehicle Active Suspension Systems. Control Systems Technology, IEEE Transactions on 18 (2010), 238–245. Reiner Horst and Hoang Tuy. 1990. Global optimization : deterministic approaches. New york : SpringerVerlag. M. Joseph and P. K. Pandya. 1986. Finding Response Times in a Real-Time System. Comput. J. 29, 5 (1986), 390–395. Chung-Yao Kao and Anders Rantzer. 2007. Stability analysis of systems with uncertain time-varying delays. Automatica 43, 6 (2007), 959–970. R. Kondo and K. Furuta. 1985. Sampled-data optimal control of continuous systems for quadratic criterion function taking account of delayed control action. Internat. J. Control 41 (1985), 1051–1060. H. Kwakernaak and R. Sivan. 1972. Linear Optimal Control Systems. John Wiley & Sons. J. P. Lehoczky, L. Sha, and K. G. Shin. 1996. On task schedulability in real-time control systems. In Proceeedings of IEEE Real-Time Systems Symposium. 13–21. Joseph Y.-T. Leung and J. Whitehead. 1982. On the Complexity of Fixed-priority Scheduling of Periodic Real-time Tasks. Performance Evaluation 2, 4 (Dec. 1982), 237–250.

ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

Optimal Priority Assignment to Control Tasks

A:17

C. L. Liu and J. W. Layland. 1973. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the Association for Computing Machinery 20, 1 (1973), 46–61. G.M. Mancuso, E. Bini, and G. Pannocchia. 2011. Optimal Computational Resource Allocation for Control Task under Fixed Priority Scheduling. In Procedings of the 18th IFAC World Congress, Vol. 18. 12599– 12604. Philippe Nain and Keith W. Ross. 1986. Optimal priority assignment with hard constraint. IEEE Trans. Automat. Control 31, 10 (Oct. 1986), 883–888. DOI:http://dx.doi.org/10.1109/TAC.1986.1104127 Johan Nilsson, Bo Bernhardsson, and Bj¨orn Wittenmark. 1998. Stochastic analysis and control of real-time systems with random time delays. Automatica 34, 1 (1998), 57–64. DOI:http://dx.doi.org/10.1016/S0005-1098(97)00170-2 R. Gary Parker and Ronald L. Rardin. 1988. Discrete optimization. Academic Press, Inc. M. Shin and Sunwoo. 2007. Optimal Period and Priority Assignment for a Networked Control System Scheduled by a Fixed Priority Scheduling System. International Journal of Automotive Technology 8, 1 (2007), 39–48. Martin Stigge, Pontus Ekberg, Nan Guan, and Wang Yi. 2011. The Digraph Real-Time Task Model. In Proceeding of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium. Chicago, IL, USA, 71–80. Spyros Tzafestas and Alekos Triantafyllakis. 1993. Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms. Mathematics and Computers in Simulation 35, 5 (1993), 397–434. DOI:http://dx.doi.org/10.1016/0378-4754(93)90041-R Yifan Wu, Giorgio Buttazzo, Enrico Bini, and Anton Cervin. 2010. Parameter Selection for Real-Time Controllers in Resource-Constrained Systems. IEEE Transactions on Industrial Informatics 6, 4 (Nov. 2010), 610–620. DOI:http://dx.doi.org/10.1109/TII.2010.2053378 ˚ rz´en, Enrico Bini, and Anton Cervin. 2014. Response Time Driven Design of Control Yang Xu, Karl-Erik A Systems. In Procedings of the 19th IFAC World Congress.

ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.