Cross-Talk Noise Computation Using Mixed Integer Linear Program Problems And Their Solutions

Abstract

A method includes forming a mixed integer linear problem (MILP) capturing at least a plurality of timing windows over which aggressor net(s), electromagnetically coupled to a victim net in a circuit, produce computed cross-talk noise pulses potentially contributing to a maximum noise for the victim net. The MILP is solved to determine the maximum noise at the victim net. Responsive to the maximum noise meeting one or more criteria, at least an indication of the victim net is output. Forming may include forming a linear problem using overlapping timing windows for which noise pulses contribute to the maximum noise and converting the linear problem to the mixed integer linear problem by introducing into the linear problem binary variables that determine whether individual ones of overlapping or non-overlapping noise pulses from the one or more aggressor nets contribute to the maximum noise. Apparatus and program products are also disclosed.

1 . A method, comprising:
 forming a mixed integer linear problem capturing at least a plurality of timing windows over which one or more aggressor nets, electromagnetically coupled to a victim net in a circuit, produce computed cross-talk noise pulses potentially contributing to a maximum noise for the victim net;   solving the mixed integer linear problem to determine the maximum noise at the victim net; and   outputting, responsive to the maximum noise meeting one or more criteria, at least an indication of the victim net.   
     
     
         2 . The method of  claim 1 , wherein forming further comprises forming a linear problem using overlapping timing windows for which noise pulses contribute to the maximum noise and converting the linear problem to the mixed integer linear problem by introducing into the linear problem binary variables that determine whether individual ones of overlapping or non-overlapping noise pulses from the one or more aggressor nets contribute to the maximum noise. 
     
     
         3 . The method of  claim 2 , wherein forming further comprises forming the mixed integer linear program so that when a binary variable for an i-th noise pulse is a first value, the i-th pulse participates in a subset, but when the binary variable to the i-th noise pulse is a second value, the consequence is that the linear program remains feasible but the contribution of the i-th noise pulse to the subset is zero. 
     
     
         4 . The method of  claim 2 , wherein the mixed integer linear problem further captures start and end points of timing windows that are functions of a plurality of variational parameters comprising process and environmental parameters. 
     
     
         5 . The method of  claim 4 , wherein the mixed integer linear problem further captures constraints on a number of switching aggressors, the constraints allowing only a predetermined number of aggressor nets to switch simultaneously. 
     
     
         6 . The method of  claim 4 , wherein the mixed integer linear problem further captures constraints on a number of switching aggressors, the constraints resulting from logic functionality of the circuit. 
     
     
         7 . The method of  claim 4 , wherein determining the maximum noise further comprises computing active variational parameters that constrain a solution to the mixed integer linear problem. 
     
     
         8 . The method of  claim 4 , wherein determining the maximum noise further comprises computing a worst corner comprising a whole set of variational parameters that affect the maximum noise. 
     
     
         9 . The method of  claim 4 , wherein the timing windows are not rectangular. 
     
     
         10 . The method of  claim 1 , wherein:
 the method further comprises performing the forming and solving for a plurality of clusters in the circuit; and   outputting further comprises, responsive to maximum noises for certain victim nets meeting the one or more criteria, outputting indications of the certain victim nets.   
     
     
         11 . The method of  claim 1 , wherein the one or more criteria comprise a voltage over which the maximum noise may cause operational failure of the victim net. 
     
     
         12 . The method of  claim 1 , wherein the mixed integer linear problem further captures a victim sensitivity window. 
     
     
         13 . The method of  claim 1 , wherein the mixed integer linear problem further captures simulated noise pulses having a particular pulse shape. 
     
     
         14 . The method of  claim 13 , wherein the particular pulse shape comprises one of a triangle, a rectangle, a trapezoid, or an arbitrary convex piece wise linear function. 
     
     
         15 - 20 . (canceled) 
     
     
         21 - 29 . (canceled)