Incorporating logic exclusivity (LE) constraints in noise analysis using gain guided backtracking method

Crosstalk noise becomes one of the critical issues gating design closure for nano-meter designs. Pessimism in noise analysis can lead to significant additional time spent addressing false violations. Taking logic correlation into consideration, noise analysis can reduce pessimism significantly by eliminating false noise signals [1]-[3][5]-[7][10]-[13]. Eliminating the aggressors from the aggressor candidate set that can not switch simultaneously restricted by the logic exclusivity (LE) relationship among them can save simulation time as well. The LE problem, being proved as NP-complete, is basically to determine the subset (possibly multiple equivalent subsets) of a given aggressor candidate set which has the largest combined weight out of all possible subsets governed by logic exclusivity constraints. This paper presents a new approach in resolving the LE problem, which employs a gain guided backtrack search technique that does not require exhaustive search of all the binary paths to reach an optimal solution. We first prove that under certain conditions, if the gain at each level is non-negative, then the result will be optimal. Based on this theorem, a new algorithm is developed. The experimental results demonstrate the efficiency and accuracy of this approach. The algorithm can quickly find the optimal solutions for most cases from industry designs and outperforms other methods.