Design Optimization and Scheduling of Real-Time Embedded Systems under End-To-End Latency Constraints

Modern cyber-physical systems offer tons of different functionalities, spanning from careful control activities to infotainment. All these features have different timing properties and requirements: periodicity and deadline may substantially vary in the set of all functionalities, and necessarily guide the design of the application. System designers are required to make some decisions to deploy the application on a hardware platform. First, the features have to be wrapped into OS tasks; then, each task needs to be assigned a priority value to be scheduled by the OS. Moreover, the hardware platform is generally heterogeneous: the available processing units may run at different frequency; besides the CPUs, there may be hardware accelerators like GPUs and FPGAs; the memory banks may be of NUMA type. Placing a functionality on a CPU running at a specific frequency or on a hardware accelerator changes the execution time of that functionality. In addition, depending on the number of tasks running on the same processing unit and their priority, the functionality may suffer from interference. Finally, allocating a variable the functionality uses in a specific memory location affects the access time of that variable. To complicate the picture even more, the functionalities are not isolated, but exchange data. These features can be organized in cause-effect chains where each feature reads data from its producer and writes data to its consumer. Timing requirements can be specified for the end-to-end latency of these chains, i.e., end-to-end deadlines, and finding a way to meet them is a challenging problem. All these design choices cannot be handled manually by system designers; hence, automated design strategies based on optimization techniques are needed. The first part of this thesis proposes a placement method for AUTOSAR classic systems on a NUMA platform with homogeneous processing units. The strategy is based on an MILP formulation and some heuristic algorithms to scale down the complexity of the problem. The second part introduces a design strategy for a more complex scenario, where DAG-based applications with end-to-end deadlines need to be placed on heterogeneous platforms made of CPUs and hardware accelerators like GPUs and FPGAs. An optimal strategy to minimize the energy consumption is proposed based on an MIQCP formulation, while two heuristic algorithms provide suboptimal solutions. The third part describes a mapping strategy for parallel applications developed with the OpenMP library that are modeled as DAGs with end-to-end deadlines. An optimal solution for the deployment problem on platforms with heterogeneous cores is given in the form of an MIQCP formulation that minimizes the power consumption, along with a heuristic algorithm for faster suboptimal configurations. The fourth part of the thesis manages the design of systems where the functionalities are organized in cause-effect chains of periodic LET tasks, and their end-to-end latencies need to be minimized. The proposed strategy assigns priorities to tasks following a branch-and-bound algorithm and, alternatively, heuristic rules for scalability. Finally, the thesis explores the design and development of systems using Lingua Franca, a coordination language that guarantees time determinism and checks at runtime that task deadlines are met. In particular, a layered scheduler was developed to obtain earliest deadline first (EDF) scheduling of reactions in Lingua Franca.