Publication details

T. Cucinotta, A. Amory, G. Ara, F. Paladino, M. Di Natale. "Multi-Criteria Optimization of Real-Time DAGs on Heterogeneous Platforms under P-EDF," ACM Transactions on Embedded Computing Systems, April 2023

Abstract

This paper tackles the problem of optimal placement of complex real-time embedded applications on hetero- geneous platforms. Applications are composed of directed acyclic graphs of tasks, with each DAG having a minimum inter-arrival period for its activation requests, and an end-to-end deadline within which all of the computations need to terminate since each activation. The platforms of interest are heterogeneous power-aware multi-core platforms with DVFS capabilities, including big.LITTLE Arm architectures, and platforms with GPU or FPGA hardware accelerators with Dynamic Partial Reconfiguration capabilities. Tasks can be deployed on CPUs using partitioned EDF-based scheduling. Additionally, some of the tasks may have an alternate implementation available for one of the accelerators on the target platform, which are assumed to serve requests in non-preemptive FIFO order. The system can be optimized by: minimizing power consumption, respecting precise timing constraints; maximizing the applications’ slack, respecting given power consumption constraints; or even a combination of these, in a multi-objective formulation.
We propose an off-line optimization of the mentioned problem based on mixed-integer quadratic constraint programming (MIQCP). The optimization provides the DVFS configuration of all the CPUs (or accelerators) capable of frequency switching and the placement to be followed by each task in the DAGs, including the software-vs-hardware implementation choice for tasks that can be hardware-accelerated. For relatively big problems, we developed heuristic solvers capable of providing suboptimal solutions in a significantly reduced time compared to the MIQCP strategy, thus widening the applicability of the proposed framework.
We validate the approach by running a set of randomly generated DAGs on Linux under SCHED_DEADLINE, deployed onto two real boards, one with Arm big.LITTLE architecture, the other with FPGA acceleration, verifying that the experimental runs meet the theoretical expectations in terms of timing and power optimization goals.

Download paper

See paper on publisher website

Accompanying open-source material to reproduce the paper experiments

FRED Framework: used to support hardware acceleration for the experiments on the UltraScale+ ZCU102 board;
Power-Aware RT Profiling and Simulation: used to perform a systematic simulation of the timing of all optimized real-time DAGs, to verify there were no deadline misses with the optimized configurations;
Patches to the Linux kernel (v5.4), used for the experiments made in the paper:
- Patch #1 for disabling run-time scaling in SCHED_DEADLINE, to ensure consistency among scaled run-times in user-space and kernel-space;
- Patch #2 for inverting the real-time and deadline scheduling classes, needed for the experiments on the UltraScale+ board.
MIQCP Optimizer: used to perform the MIQCP-based optimization of the system, as described in the paper.

DOI: 10.1145/3592609

BibTeX entry:

@article{Cucinotta2023,
	doi = {10.1145/3592609},
	url = {https://doi.org/10.1145%2F3592609},
	year = 2023,
	month = apr,
	publisher = {Association for Computing Machinery ({ACM})},
	author = {Tommaso Cucinotta and Alexandre Amory and Gabriele Ara and Francesco Paladino and Marco Di Natale},
	title = {Multi-Criteria Optimization of Real-Time {DAGs} on Heterogeneous Platforms under P-{EDF}},
	journal = {{ACM} Transactions on Embedded Computing Systems}
}

Last updated on
18 March 2024