Probabilistic transitive-closure ordering and its application on variational buffer insertion

We propose a provably transitive-closure ordering rule with theoretical foundations to prune suboptimal design solutions in the presence of process variations. As an example, this probabilistic ordering rule is applied to develop an efficient variational buffering algorithm. Compared to the conventional deterministic approach, variational buffering improves the parametric timing yield by 15.7% on average. This transitive-closure ordering rule may be leveraged to solve other computer-aided-design problems considering process variation effects. © 2007 IEEE.