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 $hbox{C}^{2}hbox{MOS}$ latch/register structures, obtaining speedups of $2.5{-}10 ti-mes$ , 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 $hbox{C}^{2} hbox{MOS}$ , obtaining speedups of more than 10 $times$ 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.