1 Introduction
2 Motivating case study
3 Problem description
4 Related Work
Properties | OPAM | RMPO | DMPO | OPA | OPA-MLD | RPA | FNR-PA | PRPA | OPTA | EPAF |
---|---|---|---|---|---|---|---|---|---|---|
Periodic task | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ |
Aperiodic task | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ | ||||
Resource dependency | ∘ | |||||||||
Triggering relationship | ∘ | |||||||||
Multi-core system | ∘ | ∘ | ∘ | ∘ | ∘ | ∘ | ||||
Safety margin | ∘ | ∘ | ∘ | ∘ | ||||||
Engineering constraint | ∘ | ∘ |
5 Approach Overview
6 Competitive Coevolution
6.1 Representations
6.2 Simulation
6.3 Fitness functions
6.4 Evolution: Worst-case task arrivals
6.5 Evolution: Best-case priority assignments
6.6 External fitness evaluation
7 Evaluation
7.1 Research questions
7.2 Industrial study subjects
-
HPSS is a satellite system for two satellites, named Herschel and Planck (Mikučionis et al. 2010). The two satellites share the same computational architecture, although they have different scientific missions. Herschel aims at studying the origin and evolution of stars and galaxies. Planck’s primary mission is the study of the relic radiation from the Big Bang. ESA5 carried out the HPSS project.
-
ESAIL is a microsatellite for tracking ships worldwide by detecting messages that ships radio-broadcast (see Section 2). Luxspace, our industry partner, developed ESAIL in an ESA project.
Task types | Relationships | Platform | |||
---|---|---|---|---|---|
System | Periodic | Aperiodic | Dependencies | Triggering | Cores |
ICS | 3 | 3 | 3 | 0 | 3 |
CCS | 8 | 3 | 3 | 6 | 2 |
UAV | 12 | 4 | 4 | 0 | 3 |
GAP | 15 | 8 | 6 | 5 | 2 |
HPSS | 23 | 9 | 5 | 0 | 1 |
ESAIL | 11 | 14 | 0 | 0 | 1 |
7.3 Synthetic study subjects
7.4 Experimental Design
-
\(\mathbf {T}_{a}^{10}\): A set of task-arrival sequences generated by using an adaptive random search technique (Chen et al. 2010) that aims at maximizing the diversity of task-arrival sequences. The \(\mathbf {T}_{a}^{10}\) set contains 10 sequences of task arrivals.
-
\(\mathbf {T}_{w}^{10}\): A set of task-arrival sequences generated by using a stress test case generation method that aims at maximizing the chances of deadline misses in task executions. The stress test case generation method extends prior work (Briand et al. 2005). The extended method uses the fitness function regarding deadline misses and genetic operators that OPAM introduces for evolving worst-case task-arrival sequences (see Section 6). The \(\mathbf {T}_{w}^{10}\) set contains 10 sequences of task arrivals.
-
\(\mathbf {T}_{r}^{10}\): A set of task-arrival sequences generated randomly. The \(\mathbf {T}_{r}^{10}\) set has 10 sequences of task arrivals.
-
\(\mathbf {T}_{a}^{500}\): A set of task-arrival sequences generated by using the adaptive random search technique. The \(\mathbf {T}_{a}^{500}\) set contains 500 sequences of task arrivals.
-
\(\mathbf {T}_{w}^{500}\): A set of task-arrival sequences generated by using the stress test case generation method. The \(\mathbf {T}_{w}^{500}\) set contains 500 sequences of task arrivals.
-
\(\mathbf {T}_{r}^{500}\): A set of task-arrival sequences generated randomly. The \(\mathbf {T}_{r}^{500}\) set has 500 sequences of task arrivals.
7.5 Evaluation metrics
-
HV is defined to measure the volume in the objective space that is covered by members of a Pareto front generated by a search algorithm (Zitzler and Thiele 1999). The higher the HV values, the more optimal the search outputs.
-
GD+ is defined to measure the distance between the points on a Pareto front obtained from a search algorithm and the nearest points on a reference Pareto front (Ishibuchi et al. 2015). GD+ modifies General Distance (GD) (Veldhuizen and Lamont 1998) to account for the dominance relations when computing the distances. The lower the GD+ values, the more optimal the search outputs.
-
Δ is defined to measure the extent of spread among the points on a Pareto front computed by a search algorithm (Deb et al. 2002). We note that OPAM aims at obtaining a wide variety of equally-viable priority assignments on a Pareto front (see Section 6). The lower the Spread values, the more spread out the search outputs.
7.6 Parameter tuning and implementation
7.7 Results
Subject | Execution time (s) | Memory usage (MB) |
---|---|---|
ICS | 104.34 | 89.97 |
CCS | 165.50 | 111.85 |
UAV | 1455.35 | 312.85 |
GAP | 2819.03 | 730.29 |
HPSS | 226.98 | 127.77 |
ESAIL | 55844.23 | 2879.79 |
Periodic tasks | Aperiodic tasks | All tasks | ||
---|---|---|---|---|
Engineer | Min | -44.5 | 9.4 | -44.5 |
Max | 1879.7 | 59710.3 | 59710.3 | |
Avg. | 126.6 | 52.6 | 78.1 | |
Median | 82.1 | 9.4 | 48.1 | |
OPAM | Min | 48.1 | 9.4 | 9.4 |
Max | 1879.7 | 59707.2 | 59707.2 | |
Avg. | 129.8 | 57.2 | 82.3 | |
Median | 85.7 | 9.4 | 48.1 | |
% Difference | Min | 208.09% | 0.00% | 121.12% |
Max | 0.00% | -0.01% | -0.01% | |
Avg. | 2.53% | 8.89% | 5.33% | |
Median | 4.38% | 0.00% | 0.00% |