Southern Illinois University Carbondale

In this paper, we propose an algorithm to compute the occurrence probability for a given path precisely in an acyclic synthesizable VHDL or software code. This can be useful for the ranking of critical paths and in a variety of problems that include compiler-level architectural optimization and static timing analysis for improved performance. Functions that represent condition statements at the basic blocks are manipulated using Binary Decision Diagrams (BDDs). Experimental results show that the proposed method outperforms the traditional Monte Carlo simulation approach. The later is shown to be non-scalable as the number of inputs increases.