UNFOLDING PROBABILISTIC DATA-FLOW GRAPHS UNDER DIFFERENT TIMING MODELS

It is known that in many applications, because of selection state-ments, e.g., if-statement, the computation time of a node can be represented by a random variable. This paper focuses on any it-erative application (containing loops) reflecting those uncertain-ties. Such an application can then be transformed to a probabilistic data-flow graph. A challenging problem is to derive graph trans-formation techniques which can produce a good schedule. This paper introduces two timing models, the time-invariant and time-variant models, to characterize the nature of these applications. Furthermore, for the time-invariant model, we propose a means of selecting a minimum rate-optimal unfolding factor which guaran-tees the best schedule length. We also propose a good estimation for choosing an unfolding factor for a graph under the time-variant model. 1