Independent and interdependent latch setup/hold time characterization via Newton-Raphson solution and Euler curve tracking of state-transition equations
Characterizing setup/hold times of latches and registers, which is a task crucial for achieving timing closure of large digital designs, typically occupies months of computation in semiconductor industries. We present a novel approach to speed up latch characterization by formulating the setup/hold time problem as a scalar nonlinear equation h (tau(s), tau(h)) = 0; this nonlinear algebraic formulation is derived from, and embeds within it, the state-transition function of the latch. We first present a technique to characterize setup and hold times independently of each other: by decoupling h(tau(s), tau(h)) = 0 into two equations h(tau(s)) = 0 and h(tau(h)) = 0 and solving each equation using the Newton-Raphson method. Next, we also present a method for interdependent characterization of latch setup/hold times-a core component of techniques for pessimism reduction in timing analysis. We achieve this by solving the underdetermined nonlinear equation h(tau(s), tau(h)) = 0 using a Moore-Penrose pseudoinverse-based Newton method. Furthermore, we use null-space information from the Newton's Jacobian matrix to efficiently find constant-clock-to-q contours (in the setup/hold time plane) via an Euler-Newton curve-tracing procedure. We validate fast convergence and computational advantage for independent characterization on transmission gate and (CMOS)-M-2 latch/register structures, obtaining speedups of 2.5-10X, at high levels of accuracy, over the current standard of binary search. We validate the method for interdependent characterization on true single-phased clock and C2MOS, obtaining speedups of more than 10x for tracing 17-24 points, over prior approaches while achieving superior accuracy; this speedup linearly increases with the precision with which curve tracing is desired. We also apply our method for interdependent characterization on a transmission gate register to illustrate limitations of our method.
interdependence hold time characterization newton-raphson euler-newton setup time