A quantum algorithm toward a practical evaluation of Worst-Case Execution Times (WCETs) for real-time tasks

Published : 10 January 2019

Schedulability analysis is an old research field related to both real-time systems and performance of systems.

An important requirement of the schedulability analysis is the availability of upper bounds of execution times.

As a consequence, the research field of Worst Case Execution Times (WCETs) started to flourish in the 90s.

For safety critical real-time systems, missing a deadline can lead to catastrophic results, with important damages or even loss of human lives. As such event must be avoided, the schedulability analysis must provide a safe result.

So if exact WCETs cannot be expressed, which is usually the case because they depends on too many parameters including a perfect model of inner-work of the target microprocessor, then a safe upper bound of the WCETs must be provided instead.

However, if it is indeed easy to show overly pessimistic WCETs, e.g. by disabling caches, and serializing instructions in the pipeline, the usefulness of a given WCET estimation decreases as its accuracy is reduced. So a useful WCET should be both safe and as accurate as possible, which is a tricky problem because execution times in modern systems are heavily context dependent, and the mathematical models of WCETs are NP-hard problems.

Within this PhD work we aim at two target objectives: The first si to find a way of modeling the evaluation of WCETs with a quantum algorithm, and the second is to open up another field of application of quantum computing outside of the usual fields of reseach.

More information