Feasible aggressor-set identification under constraints for maximum coupling noise

In this paper, we consider the problem of identifying a feasible set of aggressor nets that would induce maximum crosstalk noise or delay pushout on a coupled victim net, under given logical constraints.We present a novel mathematical formulation of this problem and propose a Lagrangian relaxation-based approach for solving it efficiently and optimally. Experimental results show that the proposed approach is run-time efficient by a factor of up to 800 times in comparison to an exhaustive search approach and reduces timing pessimism by up to 36%. We also formulate and solve this problem while considering the noise susceptibility of the victim's receiving gate. © 2009 IEEE.