Title :
Unfolding probabilistic data-flow graphs under different timing models
Author :
Tongsima, Sissades ; O´Neil, Timothy W. ; Sha, Edwin H M
Author_Institution :
Dept. of Comput. Sci. & Eng., Notre Dame Univ., IN, USA
Abstract :
It is known that in many applications, because of selection statements, e.g., if-statement, the computation time of a node can be represented by a random variable. This paper focuses on any iterative application (containing loops) reflecting those uncertainties. Such an application can then be transformed to a probabilistic data-flow graph. A challenging problem is to derive graph transformation 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 guarantees the best schedule length. We also propose a good estimation for choosing an unfolding factor for a graph under the time-variant model
Keywords :
data flow graphs; iterative methods; parameter estimation; probability; timing; computation time; graph transformation techniques; if-statement; iterative application; loops; minimum rate-optimal unfolding factor; node; probabilistic data-flow graph; probabilistic data-flow graphs; random variable; schedule length; selection statements; time-invariant model; time-variant model; timing models; uncertainties; unfolding factor estimation; Application software; Artificial intelligence; Bandwidth; Computer science; Modems; Processor scheduling; Random variables; TV; Throughput; Timing;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1999. Proceedings., 1999 IEEE International Conference on
Conference_Location :
Phoenix, AZ
Print_ISBN :
0-7803-5041-3
DOI :
10.1109/ICASSP.1999.758292