Stochastic bounds on execution times of parallel computations
Francesco Lo Presti, Michele Colajanni, Salvatore Tucci · 2002
We obtain stochastic bounds on execution times of parallel computations assuming ideal conditions for shared resources. A parallel computation is modelled as a task system with precedence constraints expressed as a directed acyclic graph (DAG). The task execution times are assumed independent random variables. The performance measure considered is the overall execution time of the computation. To obtain upper bounds on this measure, we apply stochastic ordering and stochastic comparison techniques.>