Statistical timing analysis has been widely applied to predict the timing yield of VLSI circuits when process variations become significant. Existing statistical latch timing methods are either having exponential complexity or unable to treat the random variable's self-dependence caused by the coexistence of level-sensitive latches and feedback loops. In this paper, an efficient iterative statistical timing algorithm with provable convergence is proposed for latch-based circuits with feedback loops. Based on a new notion of iteration mean, we prove that the algorithm converges unconditionally. Moreover, we show that the converged value of iteration mean ca be used to predict the circuit yield during design time. Tested by ISCAS'89 benchmark circuits, the proposed algorithm shows a error of 1.1% and speedup of 303 /spl times/ on average when compared with the Monte Carlo simulation.

The soaring clocking frequency and integration density demand robust and stable power delivery to support tens of millions of transistor switching. In this paper, we consider the problem of minimizing the area of wires and decoupling capacitors (decaps) for a power delivery network, subject to the limit on integral of voltage drops. First, we derive the gradients of constraint function without Tellegen's theorem. This greatly simplifies the discuss of adjoint sensitivity analysis. Then, we apply the IEKS method to speed up the sensitivity analysis over 3 times. Finally, this efficient analyzer is incorporated with the state-of-the-art nonlinear programming package, SNOPT, to perform the optimization. Extensive experimental results show that the proposed method can work efficiently for large power delivery networks.

Dramatic rises in the power consumption and integration density of contemporary systems-on-chip (SoCs) have led to the need for careful attention to chip-level thermal integrity. High temperatures or uneven temperature distributions may result not only in reliability issues, but also timing failures, due to the temperature-dependent nature of chip time-to-failure and delay, respectively. To resolve these issues, high-quality, accurate thermal modeling and analysis, and thermally oriented placement optimizations, are essential prior to tapeout. This paper first presents an overview of thermal modeling and simulation methods, such as finite-difference time domain, finite element, model reduction, random walk, and Green-function based algorithms, that are appropriate for use in placement algorithms. Next, two-dimensional and three-dimensional thermal-aware placement algorithms such as matrix-synthesis, simulated annealing, partition-driven, and force directed are presented. Finally, future trends and challenges are described

Zero-skew clock-tree with minimum clock-delay is preferable due to its low unintentional and process-variation induced skews. We propose a zero-skew buffered clock-tree synthesis flow and a novel algorithm that enables clock-tree optimization throughout the full zero-skew design-space by considering simultaneous buffer-insertion, buffer-sizing, and wire-sizing. For an industrial clock-tree with 3101 sink nodes, our algorithm achieves up to 45X clock-delay improvement and up to 23% power reduction compared with its initial routing.

Process variations cause significant timing uncertainty and yield degradation in deep sub-micron technologies. A solution to counter timing uncertainty is post-silicon clock tuning. Existing design approaches for post-silicon-tunable (PST) clock-tree synthesis usually insert a PST clock buffer for each flip-flop or put PST clock buffers across an entire level of a clock-tree. This can cause significant over-design and long tuning time. In this paper, we propose to insert PST clock buffers at both internal and leaf nodes of a clock-tree and use a bottom-up algorithm to reduce the number of candidate PST clock buffer locations. We then provide two statistical-timing-driven optimization algorithms to reduce the hardware cost of a PST clock-tree. Experimental results on ISCAS89 benchmark circuits show that our algorithms achieve up to a 90% area or a 90% number of tunable clock buffer reductions compared to existing design methods.

With the increasing power density and heat-dissipation cost of modern VLSI designs, thermal and power integrity has become serious concern. Although the impacts of thermal effects on transistor and interconnect performance are well-studied, the interactions between power-delivery and thermal effects are not clear. As a result, power-delivery design without thermal consideration may cause soft-error, reliability degradation, and even premature chip failures. In this paper, we propose a thermal-aware power-delivery optimization algorithm. By simultaneously considering thermal and power integrity, we are able to achieve high power supply quality and thermal reliability. For a 58/spl times/72 mesh as shown in the experimental results, our algorithm shows that the lifetime of the optimized ground network is 9.5 years. Whereas the lifetime of the ground network generated by a traditional method is only 2 years without thermal concern.

To ensure the power and signal integrity of modern VLSI circuits, it is crucial to analyze huge amount of nonlinear devices together with enormous interconnect and even substrate parasitics to achieve the required accuracy. Neither traditional circuit simulation engines such as SPICE nor switch-level timing analysis algorithms are equipped to handle such a tremendous challenge in both efficiency and accuracy. We establish a solid framework that simultaneously takes advantage of a hierarchical nonlinear circuit simulation algorithm and an advanced large-scale linear circuit simulation method using a new predictor-corrector algorithm. Under solid convergence and stability guarantees, our simulator, HiSIM, a hierarchical interconnect-centric circuit simulator, is capable of handling the post-layout RLKC power and signal integrity analysis task efficiently and accurately. Experimental results demonstrate over 180X speed up over the conventional flat simulation method with SPICE-level accuracy.

In deep sub-micron technologies, process variations can cause significant path delay and clock skew uncertainties thereby lead to timing failure and yield loss. In this paper, we propose a comprehensive clock scheduling methodology that improves timing and yield through both pre-silicon clock scheduling and post-silicon clock tuning. First, an optimal clock scheduling algorithm has been developed to allocate the slack for each path according to its timing uncertainty. To balance the skew that can be caused by process variations, programmable delay elements are inserted at the clock inputs of a small set of flip-flops on the timing critical paths. A delay-fault testing scheme combined with linear programming is used to identify and eliminate timing violations in the manufactured chips. Experimental results show that our methodology achieves substantial yield improvement over a traditional clock scheduling algorithm in many of the ISCAS89 benchmark circuits, and obtain an average yield improvement of 13.6%.

Net weighting is a key technique in large scale timing driven placement, which plays a crucial role for deep submicron physical synthesis and timing closure. A popular way to assign net weight is based on the slack of the nets, trying to minimize the worst negative slack (WNS) for the entire circuit. While WNS is an important optimization metric, another figure of merit (FOM), defined as the total slack difference compared to a certain slack threshold for all timing end points, is of equivalent importance to measure the overall timing closure result for highly complex modern ASIC and microprocessor designs. In this paper, we perform a comprehensive analysis of the slack and FOM sensitivities to the net weight, and propose a new net weighting scheme based on the slack and FOM sensitivities. Such sensitivity analysis implicitly takes potential physical synthesis effect into consideration. Experiment results on a set of industrial circuits are promising for both stand-alone timing driven placement and physical synthesis afterwards.

Clock distribution is crucial for timing and design convergence in high-performance very large scale integration designs. Minimum-delay/power zero skew buffer insertion/sizing and wire-sizing problems have long been considered intractable. In this paper, we present ClockTune , a simultaneous buffer insertion/sizing and wire-sizing algorithm which guarantees zero skew and minimizes delay and power in polynomial time. Extensive experimental results show that our algorithm executes very efficiently. For example, ClockTune achieves 45/spl times/ delay improvement for buffering and sizing an industrial clock tree with 3101 sink nodes on a 1.2-GHz Pentium IV PC in 16 min, compared with the initial routing. Our algorithm can also be used to achieve useful clock skew to facilitate timing convergence and to incrementally adjust the clock tree for design convergence and explore delay-power tradeoffs during design cycles. ClockTune is available on the web (http://vlsi.ece.wisc.edu/Tools.htm).

In 21st-Century VLSI design, clocking plays crucial roles for both performance and timing convergence. Due to their non-convex nature, optimal minimum-delay/area zero-skew wire-sizing problems have long been considered intractable. None of the existing approaches can guarantee optimality for general clock trees to the authors' best knowledge. In this paper, we present an ε-optimal zero-skew wire-sizing algorithm, ClockTune, which guarantees zero-skew with delay and area within ε distance to the optimal solutions in pseudo-polynomial time. Extensive experimental results show that our algorithm executes very efficiently in both runtime and memory usage. For example, ClockTune takes less than two minutes and 35MB memory to size an industrial clock tree with 3101 sink nodes within 2% to the optimal solution on a 533MHz Pentium III PC. Our algorithm can also be used to achieve useful clock skew to facilitate timing convergence and to incrementally adjust clock tree for design convergence and explore delay/power tradeoffs during design cycles. ClockTune is available on the web [13].