This paper proposes a fast decoupling capacitance (decap) allocation and budgeting algorithm for both early stage decap estimation and later stage decap minimization in today's very large scale integration physical design. The new method is based on a sensitivity-based conjugate gradient (CG) approach. But several new techniques that significantly improve the efficiency of the optimization process were adopted. First, an efficient search step scheme to replace the time-consuming line search phase in the conventional CG method for decap budget optimization was proposed. Second, instead of optimizing an entire large circuit, the circuit is partitioned into a number of smaller subcircuits and optimized separately by exploiting the locality of adding decaps. Third, the time-domain merged adjoint method was applied to compute the sensitivity information and show that the partitioning-based merged adjoint method leads to better results than the flat merged adjoint method with the improved search scheme. Experimental results show that the proposed algorithm achieves at least ten times speed-up over similar decap allocation methods reported so far with similar budget quality, and a power grid circuit with about one million nodes can be optimized using the new method in half an hour on the latest Linux workstations

This paper presents a novel compact passive modeling technique for high-performance RF passive and interconnect circuits modeled as high-order resistor-inductor-capacitor-mutual inductance circuits. The new method is based on a recently proposed general s-domain hierarchical modeling and analysis method and vector potential equivalent circuit model for self and mutual inductances. Theoretically, this paper shows that s-domain hierarchical reduction is equivalent to implicit moment matching at around s=0 and that the existing hierarchical reduction method by one-point expansion is numerically stable for general tree-structured circuits. It is also shown that hierarchical reduction preserves the reciprocity of passive circuit matrices. Practically, a hierarchical multipoint reduction scheme to obtain accurate-order reduced admittance matrices of general passive circuits is proposed. A novel explicit waveform-matching algorithm is proposed for searching dominant poles and residues from different expansion points based on the unique hierarchical reduction framework. To enforce passivity, state-space-based optimization is applied to the model order reduced admittance matrix. Then, a general multiport network realization method to realize the passivity-enforced reduced admittance based on the relaxed one-port network synthesis technique using Foster's canonical form is proposed. The resulting modeling algorithm can generate the multiport passive SPICE-compatible model for any linear passive network with easily controlled model accuracy and complexity. Experimental results on an RF spiral inductor and a number of high-speed transmission line circuits are presented. In comparison with other approaches, the proposed reduction is as accurate as passive reduced-order interconnect macromodeling algorithm in the high-frequency domain due to the enhanced multipoint expansion, but leads to smaller realized circuit models. In addition, under the same reduction ratio, realized models by the new method have less error compared with reduced circuits by time-constant-based reduction techniques in time domain.

This paper proposes a novel wideband modeling technique for high-performance RF passives and linear(ized) analog circuits. The new method is based on a recently proposed sdomain hierarchical modeling and analysis method [27]. Theoretically, we show that the s-domain hierarchical reduction is equivalent to implicit moment matching around s = 0, and that the existing hierarchical reduction method by one-point expansion is numerically stable for general tree-structured circuits. Practically, we propose a hierarchical multi-point reduction scheme for high-fidelity, wideband modeling of general passive or active linear circuits. A novel explicit waveform matching algorithm is proposed for searching the dominant poles and residues from different expansion points based on the unique hierarchical reduction framework. Experimental results with large analog circuits, on-chip spiral inductors are presented to validate the proposed method.

We develop a realizable circuit reduction to generate the interconnect macro-model for parasitic estimation in wideband applications. The inductance is represented by VPEC (vector potential equivalent circuit) model, which not only enables the passive sparsification but also gives correct low-frequency response, whereas the recent circuit reduction intrinsically has inaccurate value and low-frequency response due to nodal-susceptance formulation. Applying hierarchical circuit-reduction enhanced by multi-point expansions, we can obtain an accurate high-order impedance function to capture the high-frequency response. The impedance function is further enforced passivity by convex programming, and realized by a Foster's synthesis. Experiments show that our method is as accurate as PRIMA in high frequency range, but leads to a realized circuit model with up to 10X times less complexity and up to 8X smaller simulation time. In addition, under the same reduction ratio, its error margin is less than that for the time-constant based reduction in both time-domain and frequency-domain simulations.

This paper proposes a fast decoupling capacitance (decap) allocation and budgeting algorithm for both early stage decap estimation and later stage decap minimization in today's VLSI physical design. The new method is based on a sensitivity-based conjugate gradient (CG) approach. But it adopts several new techniques, which significantly improve the efficiency of the optimization process. First, the new approach applies the time-domain merged adjoint network method for fast sensitivity calculation. Second, an efficient search step scheme is proposed to replace the timeconsuming line search phase in conventional conjugate gradient method for decap budget optimization. Third, instead of optimizing an entire large circuit, we partition the circuit into a number of smaller sub-circuits and optimize them separately by exploiting the locality of adding decaps. Experimental results show that the proposed algorithm achieves at least 10X speed-up over the fastest decap allocation method reported so far with similar or even better budget quality and a power grid circuit with about one million nodes can be optimized using the new method in half an hour on the latest Linux workstations.

As power density increases exponentially, runtime regulation of operating temperature by dynamic thermal managements becomes necessary. This paper proposes a novel approach to the thermal analysis at chip architecture level for efficient dynamic thermal management. Our new approach is based on the observation that the power consumption of architecture level modules in microprocessors running typical workloads presents strong nature of periodicity. Such a feature can be exploited by fast spectrum analysis in frequency domain for computing steady state response. To obtain the transient temperature changes due to initial condition and constant power inputs, numerically stable moment matching approach is carried out. The total transient responses is the addition of the two simulation results. The resulting fast thermal analysis algorithm leads to at least 10/spl times/-100/spl times/ speedup over traditional integration-based transient analysis with small accuracy loss.

This paper proposes a novel method to efficiently reduce the terminal number of general linear interconnect circuits with a large number of input and/or output terminals considering delay variations. Our new algorithm is motivated by the fact that VLSI interconnect circuits have many similar terminals in terms of their timing and delay metrics due to their closeness in structure or due to mathematic approximation using meshing in finite difference or finite element scheme during the extraction process. By allowing some delay tolerance or variations, we can reduce many similar terminals and keep a small number of representative terminals. After terminal reduction, traditional model order reduction methods can achieve more compact models and improve simulation efficiency. The new method, TermMerg, is based on the moments of the circuits as the metrics for the timing or delay. It then employs singular value decomposition (SVD) method to determine the optimum number of clusters based on the low-rank approximation. After this, the K-means clustering algorithm is used to cluster the moments of the terminals into different clusters. Experimental results on a number of real industry interconnect circuits demonstrate the effectiveness of the proposed method.

As power density increases exponentially, run-time regulation of operating temperature by dynamic thermal management becomes imperative. This paper proposes a novel approach to real-time thermal estimation at chip level for efficient dynamic thermal management in lieu of the thermal sensors, which are erroneous and having longer delays. Our new approach is based on the observation that the average power consumption of architecture level modules in microprocessors running typical workloads determines the trend of temperature variations. Such a feature can be exploited by applying fast moment matching technique in frequency domain. To obtain the transient temperature changes due to initial condition and constant power input pattern, numerically stable moment matching approach is carried out to speed up on-line temperature tracking with high accuracy and low overhead. The resulting fast thermal analysis algorithm has linear time complexity in run-time setting and leads to about two orders of magnitude speed-up over traditional integration-based transient analysis. The average maximum error under running typical benchmarks is only about 0.37/spl deg/C as compared to other well-accepted simulation tools.

This paper proposes a novel approach to the exact symbolic analysis of very large analog circuits. The new method is based on determinant decision diagrams (DDDs) representing symbolic product terms. But instead of constructing DDD graphs directly from a flat circuit matrix, the new method constructs DDD graphs in a hierarchical way based on hierarchically defined circuit structures. The resulting algorithm can analyze much larger analog circuits exactly than before. The authors show that exact symbolic expressions of a circuit are cancellation-free expressions when the circuit is analyzed hierarchically. With this, the authors propose a novel symbolic decancellation process, which essentially leads to the hierarchical DDD graph constructions. The new algorithm partially avoids the exponential DDD construction time by employing more efficient DDD graph operations during the hierarchical construction. The experimental results show that very large analog circuits, which cannot be analyzed exactly before like /spl mu/A725 and other unstructured circuits up to 100 nodes, can be analyzed by the new approach for the first time. The new approach significantly improves the exact symbolic capacity and promises huge potentials for the applications of exact symbolic analysis.

This paper provides a novel approach to exact symbolic analysis of very large analog circuits. The new method is based on determinant decision diagrams (DDDs) to represent symbolic product terms. But instead of constructing DDD graphs directly from a flat circuit matrix, the new method constructs DDD graphs in a hierarchical way based on hierarchically defined circuit structures. The resulting algorithm can analyze much larger analog circuits exactly than before. Theoretically, we show that exact symbolic expressions of a circuit are cancellation-free expressions when the circuit is analyzed hierarchically. Practically we propose a novel hierarchical DDD graph construction algorithm. Our experimental results show that very large analog circuits, which can't be analyzed exactly before like μA725 and other unstructured circuits up to 100 nodes, can be analyzed by the new approach for the first time. The new approach significantly improves the exact symbolic capacity and promises huge potentials for the new applications of symbolic analysis in analog circuit design automation.

This paper proposes a new hierarchical circuit modeling and simulation technique in s-domain for linear analog circuits. The new algorithm can perform circuit complexity reduction by deriving the exact or approximate admittances in rational form in the reduced circuit matrix and deriving the circuit characteristics for very large linear analog and interconnect circuits. We characterize some theoretical results regarding the conditions on the generations of canceling terms during the general hierarchical circuit analysis and propose an explicit de-cancellation scheme to remove canceling terms based on a new hierarchical symbolic analysis framework. The resulting algorithm can be used for modeling and simulation of linear analog and interconnect circuits in both frequency and time domain.