A hierarchical approach for bounding the completion time distribution of stochastic task graphs

The analytical evaluation of the completion time distribution of a general directed acyclic graph (DAG) is known to bean NP-complete problem. In this paper we present a new algorithm, named Tree Bound , for the evaluation of bounds onthe completion time of stochastic graphs assuming ideal conditions for shared resources and independent random variablesas task execution times. The Tree Bound method uses a hierarchical approach that first gives a tree-like representation ofthe graph, and then evaluates lower and upper bounds through a single visit of the tree. As lower bound the method takesthe distribution of an embedded series–parallel graph which is evaluated by means of a simple recursion. The upper boundis based on a hierarchical application of other bounding techniques. In this paper, we use the Shogan algorithm because itsdeterminism allows us to demonstrate some interesting properties of the Tree Bound method.Indeed, through stochastic ordering and stochastic comparison techniques, we demonstrate analytically that our approachprovides tighter bounds than Shogan’s and Yazici-Pekergin’s bounds. On the other hand, we cannot compare formally theTree Bound accuracy to that of other important methods, such as Kleinöder and Dodin, because of their non-determinism.Various empiric comparisons show that the Tree Bound algorithm provides analogous or superior results than heuristicsderived from main non-deterministic methods. Moreover, the Tree Bound algorithm keeps linear complexity and avoidsnon-determinism. Finally, it represents a useful basis for the combination of different bounding techniques which seems theonly way to achieve even tighter bounds on the completion time distribution of stochastic graphs.