Tesi etd-09252024-135925
Link copiato negli appunti
Tipo di tesi
Dottorato
Autore
PALADINO, FRANCESCO
URN
etd-09252024-135925
Titolo
Design Optimization and Scheduling of Real-Time Embedded Systems under End-To-End Latency Constraints
Settore scientifico disciplinare
ING-INF/05
Corso di studi
Istituto di Tecnologie della Comunicazione, dell'Informazione e della Percezione - PHD IN EMERGING DIGITAL TECHNOLOGIES
Commissione
relatore Prof. BIONDI, ALESSANDRO
Membro Prof. ZHENG, HAIBO
Presidente Prof. NELISSEN, GEOFFREY
Membro Dott. CASINI, DANIEL
Membro Prof. ZHENG, HAIBO
Presidente Prof. NELISSEN, GEOFFREY
Membro Dott. CASINI, DANIEL
Parole chiave
- real-time systems
- end-to-end latency
- system design
- optimization
- real-time scheduling
Data inizio appello
15/03/2025;
Disponibilità
parziale
Riassunto analitico
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.
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.
File
| Nome file | Dimensione |
|---|---|
Ci sono 1 file riservati su richiesta dell'autore. |
|