# Control-Scheduling Codesign Exploiting Trade-Off between Task Periods and Deadlines

Authors: Hyun-Jun Cha; Woo-Hyuk Jeong; Jong-Chan Kim
Journal: Mobile Information Systems
 (2016)

---

## Abstract

A control task’s performance heavily depends on its sampling frequency and sensing-to-actuation delay. More frequent sampling, that is, shorter period, improves the control performance. Similarly, shorter delay also has a positive effect. Moreover, schedulability is also a function of periods and deadlines. By taking into account the control performance and schedulability at the same time, this paper defines a period and deadline selection problem for fixed-priority systems. Our problem is to find the optimal periods and deadlines for given tasks that maximize the overall system performance. As our solution, this paper presents a novel heuristic algorithm that finds a high-quality suboptimal solution with very low complexity, which makes the algorithm practically applicable to large size task sets.


---

## Body

## 1. Introduction

In a cyberphysical system (CPS), real-time control systems monitor and control physical systems (i.e., target plants) with precise control performance requirements and tight resource constraints. When designing such a system, two different approaches can be applied. First, the traditional approach separates thecontrol design phase andimplementation phase such that scheduling parameters such as sampling rates are determined in the control design phase without considering the scheduling issue. The second approach, known ascontrol-scheduling codesign, takes into account both the control performance and task scheduling simultaneously for the purpose of enhancing control performance with limited resources [1–4]. This paper advocates the second approach when designing a CPS.Performance of a real-time control system in a CPS depends on not only its functional correctness but also its scheduling parameters such assampling frequency. With more frequent sensing and actuation, more accurate control results can be obtained [5]. Certainly, this performance enhancement is at the cost of increased computing demands. Another important but often ignored timing property is the delay between sensing and actuation, that is,input-output delay. Since a shorter delay means more recent sensing data has been used to produce the actuation value, it can provide higher control performance [5]. Then, one interesting observation is that a task’s period, that is, inverse of sampling frequency, can be lengthened without hurting the control performance if we can somehow reduce the delay. To maintain a task’s delay within a certain range, the desired maximum delay should be used as the relative deadline in the schedulability check. If the schedulability check passes, the task’s input-output delay is guaranteed less than the relative deadline. One more timing attribute we have to discuss isjitter, which is the amount of uncertain variation of sampling time or input-output delay, calledsampling jitter andinput-output jitter, respectively. Generally, large jitter has negative effects on the control performance even though the effect is not that significant as the input-output delay [6]. Even regarding jitters, a shorter relative deadline also gives tighter upper bounds of the sampling jitter and input-output jitter such that a better control result can be produced [6]. As a result, the control performance can be enhanced by either way of shorter periods or shorter deadlines, and periods and deadlines have atrade-off relation in terms of control performance.Besides control performance, schedulability is also heavily affected by periods and deadlines of the tasks. Generally speaking, longer periods and longer deadlines both make the system more schedulable, however, at the cost of a reduced control performance. In other words, a better control performance can be obtained with a lower chance of being schedulable. Moreover, similar to the control performance case, periods and deadlines are mutually tradable to maintain schedulability. Therefore, it is important to select proper periods and deadlines which satisfy both the control performance and the schedulability. For this control-scheduling codesign issue, an optimization problem can be formulated which finds the best feasible periods and deadlines for given tasks that maximize the overall system performance.In the literature, with a similar motivation,period selection problem has been extensively studied [7–10] for both dynamic and fixed-priority scheduling algorithms. However,period and deadline selection problem, which this paper is dealing with, has gathered relatively little attention and only the dynamic-priority case has been studied [6, 11]. With this motivation, targeting fixed-priority systems, this paper proposes a novel task set synthesis algorithm that finds the proper periods and deadlines which maximize the overall system performance while guaranteeing the system schedulability. Since, even with a small number of tasks, finding the optimal solution is intractable due to the huge solution space to be searched, our algorithm is basically structured as a search-based heuristic algorithm. As will be shown in Section 6, our algorithm has a linear complexity and finds a high-quality suboptimal solution even with a large task set.For the quantitative analysis of control performance with varying periods and deadlines, we also conduct a measurement study with an automotive control application. The measured control performance of the task is defined as a nonlinear and nonconvex function of period and deadline. This function is used as an input to our heuristic algorithm.This paper’s contribution can be summarized as follows:(i)
We identify and demonstrate the trade-off relation between period and deadline in terms of control performance through actual experimental studies with an automotive control application.
(ii)
Exploiting the above trade-off relation, a novel task set synthesis algorithm is proposed, which heuristically finds near-optimal feasible (period and delay) combinations maximizing the overall control performance.The rest of our paper is organized as follows. The next section briefly explains related work. Section3 presents brief background knowledge and formally describes our problem. In Section 4, the trade-off relation of control performance is formally described. Section 5 presents our heuristic algorithm for the period and deadline selection problem. The experimental results are presented in Section 6. Finally, Section 7 concludes this paper.


## 2. Related Work

Control-scheduling codesign problem has been extensively studied in the literature. Seto et al. [7] first defined the period selection problem assuming that the control performance can be expressed as an exponential decay function of the sampling period and the tasks are scheduled using dynamic-priority methods. The problem is extended to fixed-priority systems by Seto et al. [8] by finding the finite set of feasible period ranges using a branch and bound-based integer programming method. In their work, the cost function is assumed to be a monotonically increasing function of task period. Later, Bini and Di Natale [9] proposed a faster algorithm that finds a suboptimal period assignment, which can be used for a task set of practical size that was intractable by previous methods due to its high computing demands. Recently, Du et al. [12] proposed an analytical solution using the method of Lagrange multipliers and an online algorithm for the overloaded situation.The common assumption of the above researches regarding the period selection problem is that the control performance is only affected by the sampling rate, that is, task period, of the controller. However, the delay between sensing and actuation also has a significant effect on the control performance. With this motivation, Bini and Cervin [10] incorporated each task’s sensing to actuation delay into the cost function. In their work, in order to find the optimal period assignment, cost functions are approximated as linear functions of period and delay, and the delay is also approximated assuming the fluid model scheduler. Through these approximations, they proposed an analytical solution.Wu et al. [6] further enhanced the algorithm by finding task periods and deadlines altogether for EDF scheduled systems. As a result, the problem had become a period and deadline selection problem. They showed that, by regulating relative deadlines of tasks, we can upper-limit the amount of delays and jitter each task can experience. In their work, the cost function is assumed to be a nonlinear function which increases in both period and deadline of tasks. A two-step approach was presented which first fixes periods and tries to minimize deadlines using unused resources. Recently, Tan et al. [11] proposed a new algorithm which simultaneously adjusts periods and deadlines assuming EDF scheduling and LGQ controller tasks. They showed that the new algorithm is more robust with different workloads than the previous method.Despite the above researches, however, compared to the period selection problem, the period and deadline selection problem has gained less attention even though it has more flexibility to enhance control performance with scarce resources. Moreover, only EDF scheduling is considered in the period and deadline selection problem due to its ease of schedulability analysis, though the fixed-priority scheduling is more commonly used in the practice. On the contrary, this paper is dealing with the period and deadline selection problem under the fixed-priority scheduling.


## 3. Background and Problem Description

### 3.1. System Model

This paper considers a system withn independent periodic real-time tasks {
τ
1
,
τ
2
,
…
,
τ
n
}, which control n different plants, respectively. The tasks are scheduled by the fixed-priority scheduler and the priorities are assigned according to the Deadline Monotonic (DM) order. Each τ
i is characterized by the following scheduling parameters:(i)
C
i: the worst-case execution time (WCET).
(ii)
T
i: the sampling period.
(iii)
D
i: the relative deadline. From the above, C
i is a known parameter decided by the control code, whereas T
i and D
i are operational parameters which can be controlled by system designers. Regarding deadlines, this paper considers onlyconstrained deadlines where D
i is always less than or equal to T
i. During system execution, each τ
i generates infinite sequence of periodic jobs τ
i
,
1
,
τ
i
,
2
,
… with its period T
i, which controls its corresponding target plant by (i) sensing the state of the plant, (ii) calculating the actuation values, and (iii) actuating the plant.


### 3.2. Control Performance as a Function of Period and Deadline

When defining the performance of a controller, various metrics can be used, such as transient response time and steady-state accuracy [6, 13]. In some cases, even the energy consumption can be a control performance metric [7]. Among the various control performance metrics, this paper chooses the system error as our optimization target. System error is defined as the difference between the desired state and the actual state of the plant [6]. This can be thought of as how well the plant is acting following the controller’s intention.More specifically, let us take the lane keeping assist system (LKAS) as an example. In a modern vehicle, LKAS controls the steering angle such that the vehicle is able to follow the center of its lane. Then, the system error can be defined as the lateral error between the center of the vehicle and the center of the lane, which is illustrated in Figure1. Since this system error also varies along with time t, we further define the worst-case system error as the largest lateral error the vehicle can experience during its driving. More interested readers are referred to [14].Figure 1
Lane keeping assist system. Its system error is defined as the lateral distance between the vehicle center point and the lane center line.Following the notation in [6], each task’s control performance is defined as a function of its period and deadline, which is denoted by(1)
J
i
T
i
,
D
i
. Generally, J
i
(
T
i
,
D
i
) is defined as a nonlinear cost function which increases in both T
i and D
i; that is, if period or deadline increases, system error always increases. The intuition behind this assumption will be discussed in Section 4. We assume that J
i
(
T
i
,
D
i
) is not continuous but discrete in both T
i and D
i, which are also constrained within [
T
i
m
i
n
,
T
i
m
a
x
] and [
D
i
m
i
n
,
D
i
m
a
x
], respectively.Besides each task’s system error, the overall system error is denoted by(2)
J
T
,
D
, where T is the vector of T
i’s and D is the vector of D
i’s. For the notational simplicity, J
(
T
,
D
) is shortened to J as in the following:(3)
J
=
∑
1
≤
i
≤
n
w
i
J
i
T
i
,
D
i
, where J is defined as a weighted sum of J
i
(
T
i
,
D
i
)’s and w
i is a user-defined weight constant for the purpose of normalizing each J
i
(
T
i
,
D
i
) to a desired range. Now, the system’s overall system error can be obtained by giving every task’s period and deadline.


### 3.3. Problem Description

Assuming the above concepts and notations, this subsection describes our period and deadline selection problem, which can be formally defined as follows.Problem Description. For a given task set {
τ
1
,
τ
2
,
…
,
τ
n
}, each τ
i’s C
i and J
i
(
T
i
,
D
i
) are given a priority. Then, our problem is to find the optimal T
=
(
T
1
,
T
2
,
…
,
T
n
) and D
=
(
D
1
,
D
2
,
…
,
D
n
) such that the overall system error J
(
T
,
D
) is minimized while guaranteeing every τ
i’s schedulability.Since it is assumed thatJ
i
(
T
i
,
D
i
) is not continuous, we do not try to make an analytical solution for our optimization problem. Instead, we formulate our problem as a combinatorial optimization problem. Figure 2 shows a graphical representation of an example J
i
(
T
i
,
D
i
) with 10 discrete (
T
i
,
D
i
) combinations. Note that since we only consider constrained deadlines, the left upper triangular matrix is not considered at all.Figure 2
A graphical representation of an exampleJ
i
(
T
i
,
D
i
) function with its period varying from 0 ms to 30 ms and its deadline also varying from 0 ms to 30 ms. The granularity of periods and deadlines is 10 ms.


## 3.1. System Model

This paper considers a system withn independent periodic real-time tasks {
τ
1
,
τ
2
,
…
,
τ
n
}, which control n different plants, respectively. The tasks are scheduled by the fixed-priority scheduler and the priorities are assigned according to the Deadline Monotonic (DM) order. Each τ
i is characterized by the following scheduling parameters:(i)
C
i: the worst-case execution time (WCET).
(ii)
T
i: the sampling period.
(iii)
D
i: the relative deadline. From the above, C
i is a known parameter decided by the control code, whereas T
i and D
i are operational parameters which can be controlled by system designers. Regarding deadlines, this paper considers onlyconstrained deadlines where D
i is always less than or equal to T
i. During system execution, each τ
i generates infinite sequence of periodic jobs τ
i
,
1
,
τ
i
,
2
,
… with its period T
i, which controls its corresponding target plant by (i) sensing the state of the plant, (ii) calculating the actuation values, and (iii) actuating the plant.


## 3.2. Control Performance as a Function of Period and Deadline

When defining the performance of a controller, various metrics can be used, such as transient response time and steady-state accuracy [6, 13]. In some cases, even the energy consumption can be a control performance metric [7]. Among the various control performance metrics, this paper chooses the system error as our optimization target. System error is defined as the difference between the desired state and the actual state of the plant [6]. This can be thought of as how well the plant is acting following the controller’s intention.More specifically, let us take the lane keeping assist system (LKAS) as an example. In a modern vehicle, LKAS controls the steering angle such that the vehicle is able to follow the center of its lane. Then, the system error can be defined as the lateral error between the center of the vehicle and the center of the lane, which is illustrated in Figure1. Since this system error also varies along with time t, we further define the worst-case system error as the largest lateral error the vehicle can experience during its driving. More interested readers are referred to [14].Figure 1
Lane keeping assist system. Its system error is defined as the lateral distance between the vehicle center point and the lane center line.Following the notation in [6], each task’s control performance is defined as a function of its period and deadline, which is denoted by(1)
J
i
T
i
,
D
i
. Generally, J
i
(
T
i
,
D
i
) is defined as a nonlinear cost function which increases in both T
i and D
i; that is, if period or deadline increases, system error always increases. The intuition behind this assumption will be discussed in Section 4. We assume that J
i
(
T
i
,
D
i
) is not continuous but discrete in both T
i and D
i, which are also constrained within [
T
i
m
i
n
,
T
i
m
a
x
] and [
D
i
m
i
n
,
D
i
m
a
x
], respectively.Besides each task’s system error, the overall system error is denoted by(2)
J
T
,
D
, where T is the vector of T
i’s and D is the vector of D
i’s. For the notational simplicity, J
(
T
,
D
) is shortened to J as in the following:(3)
J
=
∑
1
≤
i
≤
n
w
i
J
i
T
i
,
D
i
, where J is defined as a weighted sum of J
i
(
T
i
,
D
i
)’s and w
i is a user-defined weight constant for the purpose of normalizing each J
i
(
T
i
,
D
i
) to a desired range. Now, the system’s overall system error can be obtained by giving every task’s period and deadline.


## 3.3. Problem Description

Assuming the above concepts and notations, this subsection describes our period and deadline selection problem, which can be formally defined as follows.Problem Description. For a given task set {
τ
1
,
τ
2
,
…
,
τ
n
}, each τ
i’s C
i and J
i
(
T
i
,
D
i
) are given a priority. Then, our problem is to find the optimal T
=
(
T
1
,
T
2
,
…
,
T
n
) and D
=
(
D
1
,
D
2
,
…
,
D
n
) such that the overall system error J
(
T
,
D
) is minimized while guaranteeing every τ
i’s schedulability.Since it is assumed thatJ
i
(
T
i
,
D
i
) is not continuous, we do not try to make an analytical solution for our optimization problem. Instead, we formulate our problem as a combinatorial optimization problem. Figure 2 shows a graphical representation of an example J
i
(
T
i
,
D
i
) with 10 discrete (
T
i
,
D
i
) combinations. Note that since we only consider constrained deadlines, the left upper triangular matrix is not considered at all.Figure 2
A graphical representation of an exampleJ
i
(
T
i
,
D
i
) function with its period varying from 0 ms to 30 ms and its deadline also varying from 0 ms to 30 ms. The granularity of periods and deadlines is 10 ms.


## 4. How Scheduling Affects Control Performance

This section deals with the rationale behind the definition ofJ
i
(
T
i
,
D
i
), which is introduced in Section 3.2. It is claimed in many literatures that the control performance of a task can be defined as a function of the task period and deadline [6, 10, 11]. If the control system is composed of only a single periodic task, it should be strictly periodic and the input-output delay is simply bounded by C
i. Thus, the control performance should be defined as a function of T
i and C
i. However, when multiple control tasks are implemented and scheduled on a shared processor, their execution is also subject to the following scheduling effects [6]:(i)
Sampling Delay. Although a job is released at a certain time point, the actual beginning of the job can be delayed due to the execution of higher-priority jobs. The time distance between the release time and the actual beginning of a job is defined as a sampling delay.
(ii)
Input-Output Delay. The time distance between the beginning and the completion of a job is defined as an input-output delay, which is composed of the actual execution time of the job which is bounded by C
i and the blocking time by higher-priority jobs.
(iii)
Sampling Jitter. As a task produces consecutive jobs, its sampling delay is not constant but varies according to the scheduling pattern each job experiences. The difference between the minimum and maximum sampling delay is defined as the sampling jitter of the task.
(iv)
Input-Output Jitter. The difference between the minimum and maximum input-output delay of a task is defined as the input-output jitter of the task.By the above scheduling effects, the actual execution of a control task is not strictly periodic and the input-output delay significantly varies due to different scheduling scenarios. Thus, the above scheduling effects as well as the control period collectively affect the control performance. Note that, for each task, the only tunable scheduling parameters areT
i and D
i in our system model. The control period T
i itself has a significant effect on the control performance since it determines the control frequency. Besides, for the above four scheduling effects, Wu et al. [6] analyzed the worst-case scenarios as in the following under the condition that every task is schedulable:(i)
Sampling delay is bounded byD
i
-
C
i, which happens when the beginning of a job is delayed as long as possible without hurting the schedulability, and the job executes without any interference by higher-priority jobs once it begins.
(ii)
Input-output delay is bounded byD
i, which happens when a job begins right after it is released and finishes right before the job’s deadline.
(iii)
Sampling jitter is bounded byD
i
-
C
i. The minimum possible sampling delay is 0 and the maximum possible sampling delay is D
i
-
C
i. Thus, the difference between the maximum and minimum sampling delay is D
i
-
C
i.
(iv)
Input-output jitter is bounded byD
i
-
C
i
b, where C
i
b is the best-case execution time which can be simply assumed to be zero when not available. The minimum possible input-output delay is C
i
b and the maximum possible input-output delay is D
i. Thus, the difference between the maximum and minimum input-output delay is D
i
-
C
i
b.The analysis above shows that a shorter deadline makes shorter sampling delay and shorter input-output delay. Even the jitters can be controlled by a shorter deadline. The implication of the above analysis is that a better control performance can be obtained by shorteningD
i as well as T
i [6]. From the above observation, we can conclude that the control performance generally increases as T
i or D
i decreases. In other words, J
i
(
T
i
,
D
i
), the system error, is a monotonically increasing function in both T
i and D
i. Note that J
i
(
T
i
,
D
i
) also reflects the effect of jitters as well as delays and sampling frequency. In order to account for the above scheduling effects when estimating the control performance, Jitterbug [15], which is a MATLAB toolbox, can be used to analyze the cost of delay and jitter in terms of control performance. Besides, TrueTime [16] provides a simulation environment which facilitates cosimulation of controller task execution and real-time scheduling.Although analysis and simulation methods are useful when estimating control performance, this paper proposes a different approach when findingJ
i
(
T
i
,
D
i
). As will be further explained in Section 6.1, a measurement environment is developed for an automotive control application. In practice, T
i and D
i cannot be an arbitrary number but should be chosen from a number of predefined candidate parameters the software platform provides. Thus, it is practically feasible to measure the system errors for each T
i and D
i combination for each control task by arbitrarily making the worst-case scenarios. Using these discrete functions J
i
(
T
i
,
D
i
)’s, the optimization algorithm in Section 5 can be used to find optimal T and D that minimize J
(
T
,
D
).


## 5. Task Set Synthesis Algorithm

In order to findT and D with the minimum J
(
T
,
D
), the simplest solution is to explore the entire solution space for every (
T
i
,
D
i
) combination checking the schedulability and calculating the overall system error. This exhaustive search method, however, has a too high complexity such that it is not applicable to a task set even with a small number of tasks like five or six tasks. The computational feasibility of the exhaustive search algorithm will be further discussed in Section 6.2. Instead, this section proposes an alternative heuristic algorithm that finds a suboptimal result, however, with a very low computational complexity. Even with this low complexity, our solution can find a very-high-quality solution for very large task sets, which will be shown later in Section 6.2.For the ease of explanation, let us define the following function:(4)
Schedulability
T
,
D
,
C
, where T and D are vectors of chosen periods and deadlines. C is a vector of each task’s C
i’s. It is assumed that C is a constant vector. Inside this function, tasks are sorted according to the DM order where the task with the shortest D
i gets index 1 and the task with the longest D
i gets index n. Then, following Audsley et al. [17], the exact schedulability check is performed. For that, the following recursive equation computes the worst-case response time R
i of each τ
i:(5)
R
i
k
+
1
=
C
i
+
∑
1
≤
m
<
i
R
i
k
T
m
·
C
m
, where R
i
0
=
C
i. The recursive equation continues until R
i
k
=
R
i
k
+
1 and the converged value is taken as the final R
i. Then, since we know every R
i, we can simply check each τ
i’s schedulability by comparing R
i with D
i. If every R
i is less than D
i for 1
≤
i
≤
n, the system is schedulable and every τ
i’s input-output delay is guaranteed under D
i. From the result of the schedulability check, S
c
h
e
d
u
l
a
b
i
l
i
t
y
(
T
,
D
,
C
) returns either of the following values: (i)
T
r
u
e: if the system is schedulable.
(ii)
F
a
l
s
e: if the system is not schedulable. This schedulability check function is used inside the outer loop of our heuristic search algorithm to check the feasibility of the chosen T and D.In the beginning of our heuristic algorithm, the initial solution is set to(6)
τ
1
0,0
,
τ
2
0,0
,
…
,
τ
n
0,0
; that is, all the periods and deadlines are equal to zero. Certainly, this initial solution has the lowest possible J
(
T
,
D
) but is definitely not schedulable. Then, our heuristic algorithm iteratively selects (i) the task and (ii) the direction to move the chosen task until S
c
h
e
d
u
l
a
b
i
l
i
t
y
(
T
,
D
,
C
)
=
T
r
u
e. Our rule of thumb for selecting the proper task is to choose the task with the lowest J
i
(
T
i
,
D
i
) for the purpose of preventing a certain task from moving too quickly to the higher J
i
(
T
i
,
D
i
). For choosing the moving direction for each iteration, the basic idea is to choose the direction with the lower slope in order to minimize the resulting J
i
(
T
i
,
D
i
) after the move.When applying the above basic idea, however, it can suffer from the following worst-case scenario. Starting a new iteration, the algorithm choosesτ
i as the task to be moved. By looking at τ
i’s current position in J
(
T
i
,
D
i
), the right direction has the lower slope compared to the upper direction. Naturally, our algorithm moves τ
i to the right direction. However, imagine that even though the upper direction requires higher slope, the task set can be schedulable immediately after moving τ
i to the upper direction. If this case happens repeatedly, τ
i will move to the right direction too many times, but still making the system unschedulable.To prevent such scenarios, we slightly tune the algorithm by looking at the system schedulability as well asJ
(
T
i
,
D
i
)’s slope when determining the moving direction. Figure 3 shows the four cases our algorithm should consider when the current location of the task is τ
i
(
10,0
):(i)
Figure3(a) shows a case where both directions make the system schedulable. In that case, it is desirable to choose the direction with the lower slope.
(ii)
Figure3(b) shows another case where both directions are not schedulable. Then, our choice is also to choose the direction with the lower slope.
(iii)
Figure3(c) shows a case where the lower slope direction is schedulable, but the higher slope direction is not schedulable. Then, the choice is to take the lower slope direction, which makes the system schedulable immediately.
(iv)
Figure3(d) shows a case where the lower slope is not schedulable, but the higher slope is schedulable. In this case, it is not possible to decide the correct direction from the current information available. If we take the upper direction, the system will be immediately schedulable with J
i
(
T
i
,
D
i
)
=
0.07. However, if we move to the right direction two times, it will also make the system schedulable with even lower J
i
(
T
i
,
D
i
)
=
0.06. One interesting observation is that the cells in the right-hand side of τ
i
(
10,10
) make J
i
(
T
i
,
D
i
) always larger than 0.07. Thus, if there is a better solution compared to τ
i
(
10,10
), it must be among the cells in the right-hand side of the current location, that is, τ
(
10,0
). Then, our quick fix is that, upon meeting this condition, every cell in the lower slope direction is quickly visited to compare the resulting J
i
(
T
i
,
D
i
) with J
i
(
T
i
,
D
i
) when taking the high slope direction to choose the better direction.Figure 3
The four cases to be considered by our heuristic algorithm. S and N mean schedulable and not schedulable, respectively. H and L mean higher slope and lower slope, respectively.
(a)
Both directions are schedulable
(b)
Both directions are not schedulable
(c)
Lower slope is schedulable, but higher slope is not schedulable
(d)
Lower slope is not schedulable, but higher slope is schedulableProcedure1 shows the pseudocode of our heuristic iterative search algorithm. After positioning each τ
i at the initial solution, the while loop iteratively chooses the next moving τ
i and the direction to move considering the four cases in Figure 3 until the system becomes schedulable. Then, using break, the while loop is terminated and the output is finally decided.Procedure 1:Procedure for finding optimal T and D.
FindOptimalPhases:
Input: τ
1
,
τ
2
,
…
,
τ
n, τ
i
=
(
C
i
,
J
i
(
T
i
,
D
i
)
)
Output: T and D
begin procedure
(1) Set each τ
i at (
0,0
)
(2)  while (1) do
(3)  Choose τ
i with the lowest J
i
(
T
i
,
D
i
)
(4)  Check the schedulability for upper and right directions
(5)
if Case in Figure 3(a)
then
(6)   Move τ
i to the lower slope direction
(7)
end if
(8)
if Case in Figure 3(b)
then
(9)   Move τ
i to the lower slope direction
(10)
end if
(11)
if Case in Figure 3(c)
then
(12) Move τ
i to the lower slope direction
(13)
end if
(14)
if Case in Figure 3(d)
then
(15) Visit every cell in the lower slope direction and compare J
i
(16) Move τ
i to the lower J
i direction
(17)
end if
(18)
if the system is schedulable then
(19) break
(20)
end if
(21)
end while
end procedure


## 6. Experiments

### 6.1. Control Performance Measurement Study

In this subsection, the experimental results for the control performance measurement study are presented. First, we explain how the measurement environment is designed and implemented. Then, the actual measurement data is presented for an example control application. For the measurement study, as the target control application, we use LKAS, in which the system error is defined as the maximum lateral error the vehicle experiences during the measurement.Figure4 shows the measurement environment, which consists of a vehicle dynamics simulator and two automotive electronic control units (ECUs) connected by a controller area network (CAN) bus. Inside the ECUs, control application codes are deployed upon our specially tuned real-time operating system (RTOS), which is a modified version of Erika Enterprise [18]. We specifically tuned the RTOS such that the worst-case job release and delay pattern always happens to simulate the worst-case scenario the vehicle can experience. Among the two ECUs, the first one contains the LKAS code and the second one has the cruise control (CC) code. The CC algorithm controls the throttle and brake to make the vehicle run at a predefined constant speed. In the following, each component is explained in more detail:(i)
Vehicle Simulator. For simulating the real-time dynamics of a vehicle, we use a modified version of the open source TORCS [19] simulator on a PC with Ubuntu-14.04. TORCS has a precise vehicle dynamics engine and 3D visualization features.
(ii)
ECU (LKAS). This ECU contains the LKAS code, which receives sensing data (e.g., vehicle speed, steering angle, yaw, and lateral distance) from the vehicle simulator and sends out the steering actuation values. Infineon TC1797 MCU [20] is used with 180 MHz CPU, 4 MB Flash, and 1 MB RAM.
(iii)
ECU (Cruise Control). This ECU actuates the throttle and brake of the vehicle simulator to keep the vehicle at a constant speed. Since we are only interested in the LKAS performance, we just set this ECU to maintain 100 km/h speed throughout the experiment with 1 ms period. Infineon TC1796 MCU [21] with 150 MHz CPU, 2 MB Flash, and 512 KB RAM is used.
(iv)
Operation and Measurement Console. We made a control panel using LabVIEW [22], which can control the period and deadline of the ECUs by the operator person. Also, it can gather the resulting system error and visualize it using a real-time plotting screen.
(v)
CAN Bus Interfaces. For the real-time communication between the vehicle simulator, ECUs, and the operation and measurement console, a 500 kbps CAN bus is used. For PCs, UBS-CAN interfaces [23] are used. For ECUs, its onboard controller is used.
(iv)
Human-Vehicle Interface. Driving wheel, throttle, and brake are installed for manual driving. Logitech G25 model [24] is used for the interface.Figure 4
Measurement environment with vehicle dynamics simulator and automotive control ECUs.Using the measurement environment, we actually measure the maximum system error as varying periods and delays. Period ranges within[0 ms, 120 ms] and deadline ranges from 0 ms to its period. The timing granularity is 10 ms for both period and delay. Figure 5 shows the system errors as varying periods with a fixed deadline at 20 ms. As shown in the figure, the system error monotonically increases as period increases, which means that larger periods have a negative impact on the control performance. Comparing the shortest period (20 ms) and the longest period (120 ms), the system error is almost doubled. Figure 6 shows a different configuration where the period is fixed at 100 ms and the delay is varying from 0 ms to its period, that is, 100 ms. By looking at the trends, we can conclude that larger deadlines have also a negative impact. Comparing Figures 5 and 6, the measured data shows that deadlines have a more significant effect on the performance than periods. Figure 7 shows the system errors as varying periods and deadlines in a 3D graph. The two axes on the floor are period and delay, respectively. The vertical axis is the measured system error. From the figure, it is clearly shown that the system error is monotonically increasing in both period and delay and the delay has a more significant impact on the control performance compared to the period.Figure 5
System error as varying periods with a fixed deadline.Figure 6
System error as varying deadlines with a fixed period.Figure 7
System error as varying periods and deadlines.


### 6.2. Evaluation of Our Proposed Algorithm

This subsection evaluates our heuristic algorithm in terms of optimality and computational feasibility with synthesized task sets. When generating task sets, for each task, the following were considered:(i)
C
i is an integer value which is randomly selected from the uniform distribution in the interval from 1 ms to 10 ms.
(ii)
J
(
T
i
,
D
i
) is generated as a monotonically increasing function in T
i and D
i. The minimum and maximum of both T
i and D
i are 0 ms and 100 ms, respectively, with a granularity of 10 ms. Since we only assume the cases with D
i
≤
T
i, a total of 66 values should be generated for each T
i and D
i pair, which are randomly chosen real values uniformly distributed in the interval from 0 to 1.Figure8 is an example task set {
τ
1
,
τ
2
,
τ
3
} with n = 3. For each of them, C
i is simply set to 10 ms. In the figure, note that the cells with D
i
>
T
i are not generated since we only consider constrained deadlines. The figure also depicts how our heuristic algorithm iteratively finds the solution with an example. The initial solution is set to(7)
τ
1
0,0
,
τ
2
0,0
,
τ
3
0,0
, where each tuple is (
T
i
,
D
i
) pair. Then, for each iteration, the task with the lowest J
i
(
T
i
,
D
i
) is chosen and the task is moved to the proper direction as explained in Section 5. Each circled number means the movement of the consecutive search iterations. The move continues until the system becomes schedulable. In this example, after 16 moves, the final solution is found, that is,(8)
τ
1
30,30
,
τ
2
30,20
,
τ
3
30,20
. At the final solution, J
(
T
,
D
)
=
0.55
=
0.203
+
0.173
+
0.174. Note that when deciding the overall system error, the weights w
i’s are simply given 1 in the entire experiment.Figure 8
The process of heuristic algorithm.
(a)
τ
1
(b)
τ
2
(c)
τ
3With the above exemplified task set generation method and heuristic algorithm, we compare the following three approaches:(i)
Searching every possible combination of periods and deadlines checking the schedulability and overall system error. The result is optimal for the entire solution space. This approach is denoted byExhaustive.
(ii)
Searching only the combinations withP
i
=
D
i, which significantly reduces the solution space compared toExhaustive. The result is only optimal for the solution space with implicit deadlines. This approach is denoted byImplicit.
(iii)
Search guided by our heuristic algorithm as explained in Section5. The result may not be optimal compared toExhaustive. This approach is denoted byOurs.Figure9 shows the overall system error with the above three approaches. The number of tasks is varied from 1 to 6. For each experiment, 100 task sets are generated and the result is the average of 100 task sets. As shown in the figure,Exhaustive shows the best result even though the algorithm almost never ends when the number of tasks exceeds 4. The results for 5 and 6 are approximated using a curve fitting method with quadratic equations. ComparingImplicit andOurs,Ours wins for every six experiments. Though the difference is marginal when the number of tasks is small, note that the difference is increasing as the number of tasks increases.Figure 9
Comparison of our approach with optimal results.Table1 shows the required computing time for the three approaches when the number of tasks varies from 1 to 10. The numbers in parenthesis are estimated values whereas the other numbers are actually measured. From the table,Exhaustive requires more than a year when the number of tasks is only 7. Even forImplicit, when the number of tasks is 10, which is relatively small in practice, the required computing time exceeds 2 days. Therefore, we can conclude that bothExhaustive andImplicit cannot be used as practical size task sets whereasOurs finds solutions even with larger task sets.Table 1
The required computing times for the three approaches with varying number of tasks.
Number of tasks
Exhaustive
Implicit
Ours
1
0.6835 ms
0.7885 ms
0.69 ms
2
13.684 ms
0.926 ms
0.88 ms
3
1305 ms
6 ms
0.75 ms
4
2 min
72 ms
0.74 ms
5
(3 hours)
986 ms
1.65 ms
6
(12 days)
1100 ms
2.44 ms
7
(1228 days)
(2 min)
16.19 ms
8
(3 years)
(26 min)
121 ms
9
(30577 years)
(5 hours)
609 ms
10
(290635 years)
(2 days)
1121 msIn order to prove that our heuristic algorithm produces a high-quality solution compared to other methods, we also compareOurs with the following two other heuristic algorithms:(i)
At each iteration, the approach chooses the moving direction with the higher slope ofJ
(
T
i
,
D
i
). This approach is denoted byHigher.
(ii)
At each iteration, the approach chooses the moving direction with the lower slope ofJ
(
T
i
,
D
i
). This approach is denoted byLower. Note thatOurs is an extension ofLower, which additionally considers the resulting schedulability as well as the slope when deciding the moving direction.Figure10 compares the performance ofOurs withHigher andLower. The result is the average of 100 synthesized task sets for each number of tasks from 1 to 6. As shown in the figure,Ours shows the best result compared toHigher andLower. By comparingHigher andLower,Lower shows a better result compared toHigher. The result first explains that taking the lower slope produces a better result than taking the higher slope. Meanwhile,Ours further enhances the performance by taking the schedulability into consideration as well as the slope at each iteration.Figure 10
Comparison of our approach with other heuristic methods.


## 6.1. Control Performance Measurement Study

In this subsection, the experimental results for the control performance measurement study are presented. First, we explain how the measurement environment is designed and implemented. Then, the actual measurement data is presented for an example control application. For the measurement study, as the target control application, we use LKAS, in which the system error is defined as the maximum lateral error the vehicle experiences during the measurement.Figure4 shows the measurement environment, which consists of a vehicle dynamics simulator and two automotive electronic control units (ECUs) connected by a controller area network (CAN) bus. Inside the ECUs, control application codes are deployed upon our specially tuned real-time operating system (RTOS), which is a modified version of Erika Enterprise [18]. We specifically tuned the RTOS such that the worst-case job release and delay pattern always happens to simulate the worst-case scenario the vehicle can experience. Among the two ECUs, the first one contains the LKAS code and the second one has the cruise control (CC) code. The CC algorithm controls the throttle and brake to make the vehicle run at a predefined constant speed. In the following, each component is explained in more detail:(i)
Vehicle Simulator. For simulating the real-time dynamics of a vehicle, we use a modified version of the open source TORCS [19] simulator on a PC with Ubuntu-14.04. TORCS has a precise vehicle dynamics engine and 3D visualization features.
(ii)
ECU (LKAS). This ECU contains the LKAS code, which receives sensing data (e.g., vehicle speed, steering angle, yaw, and lateral distance) from the vehicle simulator and sends out the steering actuation values. Infineon TC1797 MCU [20] is used with 180 MHz CPU, 4 MB Flash, and 1 MB RAM.
(iii)
ECU (Cruise Control). This ECU actuates the throttle and brake of the vehicle simulator to keep the vehicle at a constant speed. Since we are only interested in the LKAS performance, we just set this ECU to maintain 100 km/h speed throughout the experiment with 1 ms period. Infineon TC1796 MCU [21] with 150 MHz CPU, 2 MB Flash, and 512 KB RAM is used.
(iv)
Operation and Measurement Console. We made a control panel using LabVIEW [22], which can control the period and deadline of the ECUs by the operator person. Also, it can gather the resulting system error and visualize it using a real-time plotting screen.
(v)
CAN Bus Interfaces. For the real-time communication between the vehicle simulator, ECUs, and the operation and measurement console, a 500 kbps CAN bus is used. For PCs, UBS-CAN interfaces [23] are used. For ECUs, its onboard controller is used.
(iv)
Human-Vehicle Interface. Driving wheel, throttle, and brake are installed for manual driving. Logitech G25 model [24] is used for the interface.Figure 4
Measurement environment with vehicle dynamics simulator and automotive control ECUs.Using the measurement environment, we actually measure the maximum system error as varying periods and delays. Period ranges within[0 ms, 120 ms] and deadline ranges from 0 ms to its period. The timing granularity is 10 ms for both period and delay. Figure 5 shows the system errors as varying periods with a fixed deadline at 20 ms. As shown in the figure, the system error monotonically increases as period increases, which means that larger periods have a negative impact on the control performance. Comparing the shortest period (20 ms) and the longest period (120 ms), the system error is almost doubled. Figure 6 shows a different configuration where the period is fixed at 100 ms and the delay is varying from 0 ms to its period, that is, 100 ms. By looking at the trends, we can conclude that larger deadlines have also a negative impact. Comparing Figures 5 and 6, the measured data shows that deadlines have a more significant effect on the performance than periods. Figure 7 shows the system errors as varying periods and deadlines in a 3D graph. The two axes on the floor are period and delay, respectively. The vertical axis is the measured system error. From the figure, it is clearly shown that the system error is monotonically increasing in both period and delay and the delay has a more significant impact on the control performance compared to the period.Figure 5
System error as varying periods with a fixed deadline.Figure 6
System error as varying deadlines with a fixed period.Figure 7
System error as varying periods and deadlines.


## 6.2. Evaluation of Our Proposed Algorithm

This subsection evaluates our heuristic algorithm in terms of optimality and computational feasibility with synthesized task sets. When generating task sets, for each task, the following were considered:(i)
C
i is an integer value which is randomly selected from the uniform distribution in the interval from 1 ms to 10 ms.
(ii)
J
(
T
i
,
D
i
) is generated as a monotonically increasing function in T
i and D
i. The minimum and maximum of both T
i and D
i are 0 ms and 100 ms, respectively, with a granularity of 10 ms. Since we only assume the cases with D
i
≤
T
i, a total of 66 values should be generated for each T
i and D
i pair, which are randomly chosen real values uniformly distributed in the interval from 0 to 1.Figure8 is an example task set {
τ
1
,
τ
2
,
τ
3
} with n = 3. For each of them, C
i is simply set to 10 ms. In the figure, note that the cells with D
i
>
T
i are not generated since we only consider constrained deadlines. The figure also depicts how our heuristic algorithm iteratively finds the solution with an example. The initial solution is set to(7)
τ
1
0,0
,
τ
2
0,0
,
τ
3
0,0
, where each tuple is (
T
i
,
D
i
) pair. Then, for each iteration, the task with the lowest J
i
(
T
i
,
D
i
) is chosen and the task is moved to the proper direction as explained in Section 5. Each circled number means the movement of the consecutive search iterations. The move continues until the system becomes schedulable. In this example, after 16 moves, the final solution is found, that is,(8)
τ
1
30,30
,
τ
2
30,20
,
τ
3
30,20
. At the final solution, J
(
T
,
D
)
=
0.55
=
0.203
+
0.173
+
0.174. Note that when deciding the overall system error, the weights w
i’s are simply given 1 in the entire experiment.Figure 8
The process of heuristic algorithm.
(a)
τ
1
(b)
τ
2
(c)
τ
3With the above exemplified task set generation method and heuristic algorithm, we compare the following three approaches:(i)
Searching every possible combination of periods and deadlines checking the schedulability and overall system error. The result is optimal for the entire solution space. This approach is denoted byExhaustive.
(ii)
Searching only the combinations withP
i
=
D
i, which significantly reduces the solution space compared toExhaustive. The result is only optimal for the solution space with implicit deadlines. This approach is denoted byImplicit.
(iii)
Search guided by our heuristic algorithm as explained in Section5. The result may not be optimal compared toExhaustive. This approach is denoted byOurs.Figure9 shows the overall system error with the above three approaches. The number of tasks is varied from 1 to 6. For each experiment, 100 task sets are generated and the result is the average of 100 task sets. As shown in the figure,Exhaustive shows the best result even though the algorithm almost never ends when the number of tasks exceeds 4. The results for 5 and 6 are approximated using a curve fitting method with quadratic equations. ComparingImplicit andOurs,Ours wins for every six experiments. Though the difference is marginal when the number of tasks is small, note that the difference is increasing as the number of tasks increases.Figure 9
Comparison of our approach with optimal results.Table1 shows the required computing time for the three approaches when the number of tasks varies from 1 to 10. The numbers in parenthesis are estimated values whereas the other numbers are actually measured. From the table,Exhaustive requires more than a year when the number of tasks is only 7. Even forImplicit, when the number of tasks is 10, which is relatively small in practice, the required computing time exceeds 2 days. Therefore, we can conclude that bothExhaustive andImplicit cannot be used as practical size task sets whereasOurs finds solutions even with larger task sets.Table 1
The required computing times for the three approaches with varying number of tasks.
Number of tasks
Exhaustive
Implicit
Ours
1
0.6835 ms
0.7885 ms
0.69 ms
2
13.684 ms
0.926 ms
0.88 ms
3
1305 ms
6 ms
0.75 ms
4
2 min
72 ms
0.74 ms
5
(3 hours)
986 ms
1.65 ms
6
(12 days)
1100 ms
2.44 ms
7
(1228 days)
(2 min)
16.19 ms
8
(3 years)
(26 min)
121 ms
9
(30577 years)
(5 hours)
609 ms
10
(290635 years)
(2 days)
1121 msIn order to prove that our heuristic algorithm produces a high-quality solution compared to other methods, we also compareOurs with the following two other heuristic algorithms:(i)
At each iteration, the approach chooses the moving direction with the higher slope ofJ
(
T
i
,
D
i
). This approach is denoted byHigher.
(ii)
At each iteration, the approach chooses the moving direction with the lower slope ofJ
(
T
i
,
D
i
). This approach is denoted byLower. Note thatOurs is an extension ofLower, which additionally considers the resulting schedulability as well as the slope when deciding the moving direction.Figure10 compares the performance ofOurs withHigher andLower. The result is the average of 100 synthesized task sets for each number of tasks from 1 to 6. As shown in the figure,Ours shows the best result compared toHigher andLower. By comparingHigher andLower,Lower shows a better result compared toHigher. The result first explains that taking the lower slope produces a better result than taking the higher slope. Meanwhile,Ours further enhances the performance by taking the schedulability into consideration as well as the slope at each iteration.Figure 10
Comparison of our approach with other heuristic methods.


## 7. Conclusion

By exploiting the trade-off relation of task periods and deadlines, this paper proposes a novel task set synthesis algorithm for maximizing the overall system performance. For conducting a measurement study regarding the control performance, a simulation environment is developed, which can easily gather the performance variations of automotive control applications while applying various task periods and deadlines. Starting from the measured data, which confirms the trade-off relation, our problem is formally defined as a period and deadline selection problem. The input to our problem is each task’s WCET and its measured control performance matrix with various periods and deadlines. For the scheduling, DM fixed-priority scheduling is assumed. Since it becomes quickly intractable to find the optimal solution with even relatively small number of tasks, this paper proposes a heuristic algorithm with a linear complexity that finds a high-quality suboptimal solution. Our heuristic algorithm is based on a gradient descent method with its initial solution at the smallest period and deadline for each task. Starting from the initial solution, our algorithm iteratively increases period or deadline one at a time until the task set is schedulable. For each iteration, the task and its moving direction are chosen comparing the control performance reductions.In our future work, we consider a new system configuration where multiple implicit deadline periodic tasks collectively control a single plant. For such systems, a chain of tasks actually controls a plant from sensing to actuation. By controlling each task’s sampling period, we have to indirectly control the sampling frequency and input-output delay the plant actually experiences.



---

*Source: 3414816-2016-04-24.xml*