  We propose the first method that determines the exact worst-case execution
time (WCET) for implicit linear model predictive control (MPC). Such WCET
bounds are imperative when MPC is used in real time to control safety-critical
systems. The proposed method applies when the quadratic programming solver in
the MPC controller belongs to a family of well-established active-set solvers.
For such solvers, we leverage a previously proposed complexity certification
framework to generate a finite set of archetypal optimization problems; we
prove that these archetypal problems form an execution-time equivalent cover of
all possible problems; that is, that they capture the execution time for
solving any possible optimization problem that can be encountered online.
Hence, by solving just these archetypal problems on the hardware on which the
MPC is to be deployed, and by recording the execution times, we obtain the
exact WCET. In addition to providing formal proofs of the methods efficacy, we
validate the method on an MPC example where an inverted pendulum on a cart is
stabilized. The experiments highlight the following advantages compared with
classical WCET methods: (i) in contrast to classical static methods, our method
gives the exact WCET; (ii) in contrast to classical measurement-based methods,
our method guarantees a correct WCET estimate and requires fewer measurements
on the hardware.
