Scheduling of Real-tIme Heterogeneous Mulitprocesor Platform – SHRIMP

MultiProcessor Systems on Chips (MPSoCs) embedded in real-time systems are made of increasingly specialised computing (CPUs, GPUs, NPU's, etc.). This heterogeneity offers a better use of the resources (processing units, power consumption, etc.) but systems may be harder to predict. Critical real-time systems must provide logical but also timing guarantees.


The application part of these systems is represented by tasks with temporal constraints, such as a deadline, the date before which the execution of a task must be completed. For the hardware part, these heterogeneous systems are often described in the literature as "unrelated" platforms. In this classification, it is possible to assign a different execution speed to each task/processor pair. This generalizes the so-called "homogeneous" category, where processors can have different but constant speeds for all tasks.


The SHRIMP project aims at designing an efficient, real-time scheduler for such heterogeneous platforms. In particular, the scheduler must be global (allowing migration between processors) and dynamic. It must be able to handle (sporadic) tasks without pre-defined arrivals and to react online to events. Existing state-of-the-art solutions are constructed offline which produces an unsatisfactory use of the resources. For example, they cannot take advantage of the early completion (before the end of its worst-case execution time) of a task. Moreover, the task models considered in this work are not adapted to the characteristics of modern applications (dependencies) and realistic (monolithic worst-case execution time for a task possibly running on different processors). Also, their task model can not capture modern applications features (e.g. dependencies) and realistic (monolithic worst-case execution time for a task possibly running on different processors).

The project aims at considering first a particular case of "unrelated" platforms called "consistent" for which there is a comparison order between the processors but where the speed of the processors are not necessarily constant (as for the homogeneous platforms). This category allows for representing ARM big.LITTLE type architectures with slow and fast processors, of different architectures but with the same instruction set. Then, it will be necessary to be critical towards the classically used task model and to propose a scheduling algorithm able to schedule dependent tasks. This last model would allow representing more accurately tasks with code sections whose execution time could vary according to the processor used.



The developed solutions will have to be formally validated through proofs and theoretical tools for comparing schedulers. Through simulations, attention will be paid to the performance of the scheduler, e.g. on the utilisation workload supported or on the number of context changes (preemptions, migrations) which have a strong impact on the applicability of the results. In this respect, the project also focuses on the practical evaluation of the solution. The scheduling algorithms will have to be implemented on a realistic testbed.