Determining the Probability Distribution of Execution Times
Matheus Henrique Junqueira Saldanha, Adriano Kamimura Suzuki · 2021 IEEE Symposium on Computers and Communications (ISCC) · 2021
In the fields of stochastic scheduling (for cloud workflows) and hard real-time systems, execution times of programs and subroutines are modeled as random variables. Most often, the normal, uniform and exponential families of distributions are used to perform simulation studies. In many other cases, users and practitioners are expected to provide the probability distributions within their workflows, which is not simple. We demonstrate that execution times might have none of the aforementioned distributions, and discuss general features of programs that might lead to normality. In particular, a general central limit theorem can raise a priori evidence that a certain program will display normality, depending on its control flow graph. We analyze a particular program and perform a simulation study to give further insight into this phenomenon. We expect this to ease usage of methods proposed in the literature, and be used as basis for stating that normality can be expected.