Probabilistic Parameters of Conditional Task Graphs

This paper deals with the problem of determination of probabilistic parameters for tasks in a series-parallel conditional task graph. Such problematic is encountered in the context of parallel computing when dealing with conditional precedence constrained parallel tasks on a multi-core machine. The conditional task graph was introduced in order to express conditional precedence constraints and thus to model conditional execution in an application, which is not possible with a conventional task graph. We focus here in the calculation of two probabilistic parameters: the heads (release dates) and the tails (delivery times). An algorithm for computing these parameters is proposed. Although it has a pseudo-polynomial time complexity, the execution time of the algorithm can be further reduced at the price of less precision in the results.