Peter Poplavko, Lefteris Angelis, Ayoub Nouri, Alexandros Zerzelidis, Saddek Bensalem, Panagiotis Katsaros
Regression-based Statistical Bounds on Software Execution Time (2016)
Regression-based Statistical Bounds on Software Execution Time (2016)
TR-2016-7.pdf
Keywords: worst-case execution time, linear regression, statistical methods
Abstract: This work can serve to analyze schedulability of non-critical systems, in particular those that have soft real-time constraints, where one can rely on conventional statistical techniques to obtain a maximal probabilistic execution time (MET) bound. Even for hard real-time systems for certain platforms it is considered eligible to use statistics for WCET estimates, calculated as MET at extremely high probability levels; such levels are ensured by a technique called extreme value theory. Whatever technique is used, a major challenge is dealing with the dependency on input data values, which makes the execution times non-random. We propose methods to obtain adequate data-dependency models with random errors and to take advantage of the rich set of model-fitting tools offered by conventional statistical techniques associated with linear regression. These methods can compensate for non-random input data dependency and do not only provide average expectations, but also probabilistic bounds. We demonstrate our methods on a JPEG decoder running on an industrial SPARC V8 processor.
