Clock meshes possess inherent low clock skews and excellent immunity to process-voltage-temperature variations, and have increasingly found their way to high-performance integrated circuit designs. However, analysis of such massively coupled networks is significantly hindered by the sheer size of the network and tight coupling between non-tree interconnects and large numbers of clock drivers. While the SPICE simulation of large clock meshes is often intractable, standard interconnect model order reduction algorithms also fail due to the large number of input/output ports introduced by clock drivers. The presented approach is motivated by the key observation of the steady-state operation of the clock networks while its efficiency is facilitated by exploringnewclock-mesh specific harmonic-weighted model order reduction algorithm and locality analysis via port sliding. The scalability of the analysis is significantly improved by eliminating the need for computing infeasible multi-port passive reduced order interconnect models with large port count and decomposing the overall task into very tractable and naturally parallelizable model generation and fast Fourier transform/inverse-fast Fourier transform operations, all on a per driver or per sink basis. We demonstrate the application of our approach by feasibly analyzing large clock meshes with excellent accuracy.

This paper presents a class of power grid analysis and optimization techniques, all of which are based on the algebraic-multigrid (AMG) method. First, a new AMG-based reduction scheme is proposed to improve the efficiency of reducing the problem size for power grid analysis and optimization. Next, with the proposed reduction technique, a fast transient-analysis method is developed and extended to an accurate solver with error control mechanism. After that, the scope of this method is further broadened for handling the analysis of the modified grid. Finally, a fast decap-allocation (DA) scheme based on AMG is suggested. Experimental results show that these techniques not only achieve a significant speedup over reported industrial methods but also enhance the quality of solutions. By using the proposed techniques, transient analysis with 200 time steps on a 1.6-M-node power grid can be completed in less than 5 min; dc analysis on the same circuit can reach an accuracy of in about 141 s. Our DA can process a circuit with up to one million nodes in about 11 min.

Decap allocation are the primary methods for addressing the dynamic voltage noise problem of on-chip power networks. When space in the immediate proximity of a hot spot is constrained, simply adding decoupling capacitance without improving the local wiring is ineffective. Based on this key observation we proposed an effecient co-optimization of decap allocation and local wiring enhancement. The method solves a linear program (LP) iteratively and is based on the decap budgeting algorithm [10]. Experimental results on two actual chip designs demonstrate the area and run-time efficiency of the co-optimization algorithm. Moreover, it provides excellent solutions even in cases where decap allocation alone fails to provide a feasible solution.

We propose a novel and efficient incremental analysis technique for 'what-if analysis of on-chip power distribution networks (PDN). Effect of local modifications to a PDN, including local topology changes, can be quickly analyzed without need for very expensive re-analysis of the entire modified network. We borrow ideas from a fictitious domain method that has been successfully used in solving partial differential equations arising from inhomogeneous problems in mechanics. The effect of local wiring modifications in several PDN regions is mimicked by applying fictitious currents at the boundaries of these regions in the original unmodified network. The fictitious currents are calculated from component sub-problems in a low-computation iterative procedure. The practicality of this method for use in what-if analysis is demonstrated with several large power networks from actual industrial designs. It analyzes a modified network with few million changes in a fraction of time it would take for a complete re-analysis.

Clock meshes posses inherent low clock skews and excellent immunity to PVT variations, and have increasingly found their way to high-performance IC designs. However, analysis of such massively coupled networks is significantly hindered by the sheer size of the network and tight coupling between non-tree interconnects and large numbers of clock drivers. The presented Harmonic-weighted model order reduction algorithm is motivated by the key observation of the steady-state operation of the clock networks, and its efficiency is facilitated by the locality analysis via port sliding. The scalability of the analysis is significantly improved by eliminating the need of computing infeasible multi-port passive reduced order interconnect models with large port count. And the overall task is decomposed into tractable and naturally parallelizable model generation and FFT/Inverse-FFT operations, all on a per driver or per sink basis.

We propose a novel and efficient charge-based decoupling capacitance budgeting algorithm. Our method uses the macromodeling technique and effective radius of decoupling capacitance to reduce the size of the problem. We formulate the nonlinear optimization into a linear program (LP) by integrating the nodal equations across a time period of interest and through certain approximations. To reduce the error caused by linearization, we do multiple iterations of the linear program. Experimental results demonstrate that, with the proposed algorithm, even very large power networks (eg. 5 million nodes) can be optimized in a couple of hours with 1-2 transient analyses. Comparison of our algorithm with another heuristic method shows area efficiency and run time advantage of our method.

Decap (decoupling capacitor) is an effective technique for suppressing power supply noise. Nevertheless, over-usage of decap usually causes excessive power dissipation. Therefore, the total decap area needs to be minimized subject to power supply noise constraints. This is a complicated nonlinear optimization problem that may have as many as millions of variables. We propose an algebraic multigrid (AMG) based method to handle the high complexity. An error compensation scheme is developed to compensate the accuracy loss during the AMG reduction. A charge based back-mapping method and a few other techniques are suggested to further improve the computation efficiency. Our method is flexible to use and can be easily integrated with other existing decap allocation works. When compared to several previous works, the results from our method are usually the closest to the optimum. Our method also runs fast and can solve circuits with up to 1 million nodes in about 11 minutes. In addition, it has better scalability than the previous works.

Power-distribution networks of very large-scale integrated (VLSI) chips should be designed carefully to ensure reliable performance. A sound power network requires an adequate number of power-supply input connections (pads and pins). Placing them at the best vantage locations helps to reduce the number of supply connections necessary for obtaining quality power distribution. This paper addresses the problem of finding an optimum set of pads, pins, and on-chip voltage regulators, and their placement in a given power-supply network, subject to constraints on the voltage drops in the network and maximum currents through the pads, pins, and regulators. The problem is modeled as a mixed-integer linear program (MILP) with the help of macromodeling techniques. Two new heuristics, in addition to the commonly used branch-and-bound technique, are proposed to make the problem tractable. The effectiveness of the proposed technique is demonstrated on several real chips and memories used in low-power and high-performance applications.

As VLSI technology enters the ultra-deep submicron era, wire coupling capacitance starts to dominate self capacitance and can no longer be neglected in timing driven routing. In this paper, a coupling aware timing driven track routing heuristic is proposed. Given a global routing solution and timing constraint for each net, major trunks of wire segments are assigned to routing tracks such that the minimum timing slack among all nets is maximized. Delay penalties from both coupling capacitance and wire detour are considered in a unified graph model. The core problem is formulated and solved as a Sequential Ordering Problem (SOP). Routing blockages are handled in a post processing procedure. The experimental results on benchmark circuits show that the effect of coupling capacitance on timing is significant and the proposed heuristic results in greater improvement on coupling aware timing compared with other approaches.

Power delivery networks of VLSI chips require adequate input supply connections to ensure reliable performance. This paper addresses the problem of finding an optimum set of pads, pins, and on-chip voltage regulators, and their placement in a given power supply network, subject to constraints on the voltage drops in the network and maximum currents through the pads, pins and regulators. The problem is modeled as a mixed integer linear program using macromodeling techniques and several heuristic techniques are proposed to make the problem tractable. The effectiveness of the proposed techniques is demonstrated on several real chips and memories used in low-power and high-performance applications.

The present research presents procedures for exploitation of level sensitive latches in wire pipelining. The user gives a Steiner tree, having a signal source and set of destination or sinks, and the location in rectangular plane, capacitive load and required arrival time at each of the destinations. The user also defines a library of non-clocked (buffer) elements and clocked elements (flip-flop and latch), also known as synchronous elements. The first procedure performs concurrent repeater and synchronous element insertion in a bottom-up manner to find the minimum latency that may be achieved between the source and the destinations. The second procedure takes additional input (required latency) for each destination, derived from previous procedure, and finds the repeater and synchronous element assignments for all internal nodes of the Steiner tree, which minimize overall area used. These procedures utilize the latency and area advantages of latch based pipelining over flip-flop based pipelining. The second procedure suggests two methods to tackle the challenges that exist in a latch based design. The deferred delay padding technique is introduced, which removes the short path violations for latches with minimal extra cost.

Process variation has become a significant concern for static timing analysis. In this paper, we present a new method for path-based statistical timing analysis. We first propose a method for modeling inter- and intra-die device length variations. Based on this model, we then present an efficient method for computing the total path delay probability distribution using a combination of device length enumeration for inter-die variation and an analytical approach for intra-die variation. We also propose a simple and effective model of spatial correlation of intra-die device length variation. The analysis is then extended to include spatial correlation. We test the proposed methods on paths from an industrial high-performance microprocessor and present comparisons with traditional path analysis which does not distinguish between inter- and intra-die variations. The characteristics of the device length distributions were obtained from measured data of 8 test chips with a total of 17688 device length measurements. Spatial correlation data was also obtained from these measurements. We demonstrate the accuracy of the proposed approach by comparing our results with Monte-Carlo simulation.

In this paper, a precorrected-fast-Fourier-transform (FFT) approach for fast and highly accurate simulation of circuits with on-chip inductance is proposed. This work is motivated by the fact that circuit analysis and optimization methods based on the partial element equivalent circuit model require the solution of a subproblem in which a dense inductance matrix must be multiplied by a given vector, an operation with a high computational cost. The grid representation enables the use of the discrete FFT for fast magnetic vector potential calculation. The precorrected-FFT method has been applied to accurately simulate large industrial circuits with up to 121 000 inductors and over 7 billion mutual inductive couplings in about 20 min. Techniques for trading off CPU time with accuracy using different approximation orders and grid constructions are also illustrated. Comparisons with a block-diagonal sparsification method are used to illustrate the accuracy and effectiveness of this method. In terms of accuracy, memory, and speed, it is shown that the precorrected-FFT method is an excellent approach for simulating on-chip inductance in a large circuit.

The simulation of on-chip inductance using PEEC-based circuit analysis methods often requires the solution of a subproblem where an extracted inductance matrix must be multiplied by a current vector, an operation with a high computational cost. This paper presents a highly accurate technique, based on a precorrected-FFT approach, that speeds up this calculation. Instead of computing the inductance matrix explicitly, the method exploits the properties of the inductance calculation procedure while implicitly considering the effects of all of the inductors in the layout. An optimized implementation of the method has been applied to accurately simulate large industrial circuits with up to 121,000 inductors and nearly 7 billion mutual inductive couplings in about 20 minutes. Techniques for trading off the CPU time with the accuracy using different approximation orders and grid constructions are also illustrated. Comparisons with a block diagonal sparsification method in terms of accuracy, memory and speed demonstrate that our method is an excellent approach for simulating on-chip inductance in a large circuit.

Careful design and verification of the power distribution network of a chip are of critical importance to ensure its reliable performance. With the increasing number of transistors on a chip, the size of the power network has grown so large as to make the verification task very challenging. The available computational power and memory resources impose limitations on the size of networks that can be analyzed using currently known techniques. Many of today's designs have power networks that are too large to be analyzed in the traditional way as flat networks. In this paper, we propose a hierarchical analysis technique to overcome the aforesaid capacity limitation. We present a new technique for analyzing a power grid using macromodels that are created for a set of partitions of the grid. Efficient numerical techniques for the computation and sparsification of the port admittance matrices of the macromodels are presented. A novel sparsification technique using a 0-1 integer linear programming formulation is proposed to achieve superior sparsification for a specified error. The run-time and memory efficiency of the proposed method are illustrated on industrial designs. It is shown that even for a 60 million-node power grid, our approach allows for an efficient analysis, whereas previous approaches have been unable to handle power grids of such size.

We present an efficient algorithm for technology mapping of domino logic to a parameterized library. The algorithm is optimal for mapping trees consisting of two-input AND/OR nodes, and has a computation time that is polynomial in terms of constraint size. The mapping method is then extended to DAG covering that permits the implicit duplication of logic nodes. Our synthesis procedure maps the complementary logic cones independently when AND/OR logic is to be implemented, and together using dual-monotonic gates in the case of XOR/XNOR logic. The mapping procedure solves the output phase assignment problem as a preprocessing step. Based on a key observation that the output phase assignment could reduce the implementation cost due to the possible large cost difference between two polarities, a 0--1 integer linear programming formulation was designed to minimize the implementation cost. Our experimental results show the effectiveness of the proposed techniques.

With operating frequencies approaching the gigahertz range, inductance is becoming an increasingly important consideration in the design and analysis of on-chip interconnect. In this paper, we give a tutorial overview of the analysis and design issues related to on-chip inductance effects.We explain the complexity of the current flow in VLSI circuits. We discuss the applicability of the PEEC approach in a detailed circuit model of the signal and power grid interconnect, switching devices, power pads and the package. Fur-ther, we explain techniques that can be used to speed-up simulation of the large PEEC model. We then discuss a simplified model that uses the so-called loop inductance approach, and compare it with the detailed model.We present experimental results, obtained from simulations of industrial circuits, for both the PEEC and loop models. We also cover design techniques that can help tackle the on-chip inductance issues.

In this paper, a new structural matching algorithm for technology mapping is proposed. The algorithm is based on a key observation that the matches for a node in a subject Boolean network are related to the matches for its children. The structural relationships between the library cells are modeled using a lookup table. The proposed method is fast, has low memory usage, and is easy to implement. Experimental results show speedups of 20x over Matsunaga's fast mapping approach, and orders of magnitude over SIS, with the same or slightly better results, and much lower memory utilization.

Careful design and verification of the power distribution network of a chip are of critical importance to ensure its reliable performance. With the increasing number of transistors on a chip, the size of the power network has grown so large as to make the verification task very challenging. The available computational power and memory resources impose limitations on the size of networks that can be analyzed using currently known techniques. Many of today's designs have power networks that are too large to be analyzed in the traditional way as flat networks. In this paper, we propose a hierarchical analysis technique to overcome the aforesaid capacity limitation. We present a new technique for analyzing a power grid using macromodels that are created for a set of partitions of the grid. Efficient numerical techniques for the computation and sparsification of the port admittance matrices of the macromodels are presented. A novel sparsification technique using a 0-1 integer linear programming formulation is proposed to achieve superior sparsification for a specified error. The run-time and memory efficiency of the proposed method are illustrated through the analysis of case studies of several multi-million node power grids, extracted from real microprocessor and DSP designs.

In this paper two problems on domino logic synthesis are addressed. A mapping method that maps the complementary logic cones independently when AND/OR logic is to be implemented and together using dual-monotonic gates in the case of XOR/XNOR logic, is proposed. The results show up to 28.9% improvement in area and always show the same or better performance in delay over existing approaches. Then a 0-1 integer programming formulation is provided for the output phase assignment problem for domino logic. It considers the cost difference between two polarities and enables a standard linear programming package to be used to solve the problem. The results show up to 41.0% improvement in area.

Domino logic is a circuit family that is well-suited to implementing high-speed circuits. Synthesis of domino circuits is more complex than static logic synthesis due to the noninverting nature of the logic and the complex timing relationships associated with the clock scheme. In this paper, we address several problems along a domino synthesis flow. We mainly consider the problem of partitioning a circuit into static and domino regions under timing constraints. The algorithm is extended to develop a method for partitioning domino logic into two phases, with inverters permitted between the two phases, and then to a flow for general two-phase static-domino partitioning. We also address a timing verification and sizing optimization tool for circuits containing mixed domino and static logic.

Domino logic is a high-performance circuit configuration that is usually embedded in a static logic environment and tightly coupled with the clocking scheme. In this paper the timing-driven partitioning algorithms that partition a logic network between (1) static and domino implementations, and (2) the phases of a two-phase clock, are provided In addition, an efficient static mapping algorithm is described.

Domino logic is a popular con#guration for implementing high-speed circuits. An algorithm for domino logic mapping, under a parameterized library style, is presented here. Practical design methods, such as the use of multioutput domino and wide domino gates, are incorporated within the technology mapping framework. The technique can handle large circuits with small computational overheads, and shows improvements of up to about 37# over existing methods.