Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2022 Jan 4:8:762227.
doi: 10.3389/frobt.2021.762227. eCollection 2021.

Configuring ADAS Platforms for Automotive Applications Using Metaheuristics

Shane D McLean  1 , Emil Alexander Juul Hansen  1 , Paul Pop  1 , Silviu S Craciunas  2
Affiliations

Configuring ADAS Platforms for Automotive Applications Using Metaheuristics

Shane D McLean et al. Front Robot AI. .

Abstract

Modern Advanced Driver-Assistance Systems (ADAS) combine critical real-time and non-critical best-effort tasks and messages onto an integrated multi-core multi-SoC hardware platform. The real-time safety-critical software tasks have complex interdependencies in the form of end-to-end latency chains featuring, e.g., sensing, processing/sensor fusion, and actuating. The underlying real-time operating systems running on top of the multi-core platform use static cyclic scheduling for the software tasks, while the communication backbone is either realized through PCIe or Time-Sensitive Networking (TSN). In this paper, we address the problem of configuring ADAS platforms for automotive applications, which means deciding the mapping of tasks to processing cores and the scheduling of tasks and messages. Time-critical messages are transmitted in a scheduled manner via the timed-gate mechanism described in IEEE 802.1Qbv according to the pre-computed Gate Control List (GCL) schedule. We study the computation of the assignment of tasks to the available platform CPUs/cores, the static schedule tables for the real-time tasks, as well as the GCLs, such that task and message deadlines, as well as end-to-end task chain latencies, are satisfied. This is an intractable combinatorial optimization problem. As the ADAS platforms and applications become increasingly complex, such problems cannot be optimally solved and require problem-specific heuristics or metaheuristics to determine good quality feasible solutions in a reasonable time. We propose two metaheuristic solutions, a Genetic Algorithm (GA) and one based on Simulated Annealing (SA), both creating static schedule tables for tasks by simulating Earliest Deadline First (EDF) dispatching with different task deadlines and offsets. Furthermore, we use a List Scheduling-based heuristic to create the GCLs in platforms featuring a TSN backbone. We evaluate the proposed solution with real-world and synthetic test cases scaled to fit the future requirements of ADAS systems. The results show that our heuristic strategy can find correct solutions that meet the complex timing and dependency constraints at a higher rate than the related work approaches, i.e., the jitter constraints are satisfied in over 6 times more cases, and the task chain constraints are satisfied in 41% more cases on average. Our method scales well with the growing trend of ADAS platforms.

Keywords: IEEE 802.1Qbv; TSN; automotive applications; task preemption; task scheduling; time-sensitive networking.

PubMed Disclaimer

Conflict of interest statement

Author SC was employed by the company TTTech Computertechnik AG. The remaining authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

Figures

FIGURE 1
FIGURE 1
High-level platform model.
FIGURE 2
FIGURE 2
Task chain example with TSN communication.
FIGURE 3
FIGURE 3
Solution overview.
FIGURE 4
FIGURE 4
Schedule optimization. (A) End-to-end task chain latencies not satisfied. (B) End-to-end task chains latencies satisfied.
FIGURE 5
FIGURE 5
Scheduling approaches, (A) is a schedule where flows 1 and 2 are scheduled before taking tasks into account, (B) is the optimized scenario where task and flows are scheduled concurrently.
FIGURE 6
FIGURE 6
Blocking times of a frame with a period of 15 ms considering another frame with a period of 10 ms over their hyperperiod.
FIGURE 7
FIGURE 7
How tasks and flow frames are scheduled together. The order is indicated by the number in parenthesis.
FIGURE 8
FIGURE 8
Visualization of lower bound and upper bounds. The hatched areas are already filled by other frames, such that the non-hatched areas form the feasible region. (A) Case where the next frame can be scheduled in the feasible region. (B) Case where there is not enough space is available to schedule the frame and backtracking will be used to move the frame forward.
FIGURE 9
FIGURE 9
Topologies used for experiments. In each topology, a switch has 3 end systems attached (for tree: Leaf nodes only). (A) Mesh topology. (B) Ring topology. (C) Tree topology with depth = 2.
FIGURE 10
FIGURE 10
Comparison of SA and GA in terms of percentage of solved solutions, i.e., all the tasks and flows are successfully scheduled and the constraints, e.g., chain latencies, are satisfied.
FIGURE 11
FIGURE 11
Comparison of SA and GA runtimes when searching for the first feasible solution.
See this image and copyright information in PMC

References

    1. Abdelzaher T. F., Shin K. G. (1999). Combined Task and Message Scheduling in Distributed Real-Time Systems. IEEE Trans. Parallel Distrib. Syst. 10, 1179–1191. 10.1109/71.809575 - DOI
    1. Aichouch M., Prévotet J.-C., Nouvel F. (2013). “Evaluation of the Overheads and Latencies of a Virtualized RTOS,” in 2013 8th IEEE International Symposium on Industrial Embedded Systems (IEEE; ), 81–84. 10.1109/sies.2013.6601475 - DOI
    1. Barzegaran M., Cervin A., Pop P. (2020). Performance Optimization of Control Applications on Fog Computing Platforms Using Scheduling and Isolation. IEEE Access 8, 104085–104098. 10.1109/access.2020.2999322 - DOI
    1. Becker M., Dasari D., Mubeen S., Behnam M., Nolte T. (2017). End-to-end Timing Analysis of Cause-Effect Chains in Automotive Embedded Systems. J. Syst. Architecture 80, 1. 10.1016/j.sysarc.2017.09.004 - DOI
    1. Becker M., Dasari D., Mubeen S., Behnam M., Nolte T. (2016a). “Synthesizing Job-Level Dependencies for Automotive Multi-Rate Effect Chains,” in 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (IEEE; ), 159–169. 10.1109/rtcsa.2016.41 - DOI