Artem Burmyakov

Towards a Tractable Exact Test for Global Multiprocessor Fixed Priority Scheduling
Assistant Professor at the Innopolis University, Russia
28, Jul, 2023 14:30
CISTER, Porto, Portugal

An exact schedulability analysis of a system of sporadic tasks to be executed upon a multiprocessor platform is proved to be a weakly NP-hard computational problem. The available exact tests suffer from a high computation time and memory requirement, which make them intractable for large realistic real-time systems. On the other hand, the available approximate sufficient tests, which are faster and consume less memory, are very pessimistic in provisioning the execution requirements of a given system. Motivated by these observations, we propose an exact schedulability test for constrained-deadline sporadic tasks under global multiprocessor fixed-priority scheduler (GFP), which is significantly faster and consumes less memory, compared to any other available exact test. To derive a faster test, we exploit the idea of a state-space pruning, aiming at reducing the number of feasible system states to be examined by the test. The resulted test is multiple orders of magnitude faster with respect to other state-of-the-art exact tests. The C++ implementation of our test is publicly available.

Artem Burmyakov is an assistant professor at the Innopolis University, Russia. He received the PhD degree in Computer Science from the University of Porto in 2016, and the Master's degree in Applied Mathematics and Informatics from Moscow Engineering Physics Institute in 2007. In 2006-2010 he worked as a software developer at CERN, and in 2016-2017 he was a postdoctoral researcher at Seoul National University. Artem was also a member of CISTER between 2010 and 2016. His research interests are related to mathematics and algorithms, real-time multiprocessor scheduling, parallel computations, software development.

Event photos can be found HERE.

CISTER's participants:
Artem Burmyakov

S101 Auditorium/Seminar Room
1st Floor