On the Execution Time of Programs in Stochastic Scheduling

Abstract

Scheduling appears frequently in distributed, cloud and high-performance computing, as well as in embedded systems. Here, the execution time of subtasks is the major factor influencing decision-making, and despite being random variables they are majorly treated in the literature as being deterministic. Our project intends to shed more light on the underlying distribution of execution times, attempting to verify: 1) if the usual assumption of normal distribution is reasonable; 2) if there exist more suitable distribution families; and 3) if anything can be inferred a priori by analyzing general aspects of the program. We have modeled the problem and experimentally assessed distributions, showing that they are often not normal. We suggest alternative distributions, which we released as R packages, and propose estimators that ease parameter inference. With this we hope to promote usage of stochastic scheduling by making it easier for users to define distributions when requested.