Random Walk Guided Decap Embedding for Power/Ground Network Optimization

The reliability of power/ground networks is becoming significantly important in modern integrated circuits, while decap insertion is a main approach to enhance the power grid safety. In this brief, we propose a fast and efficient decap allocation algorithm, and adequately consider the leakage effect of decap. This approach borrows the idea of random walks to perform circuit partitioning and does subsequent decap insertion based on locality property of partitioned area, which avoids solving a large nonlinear programming problem in traditional decap optimization process. The optimization flow also integrates a refined leakage current model for decaps which makes it more practical. Experimental results show that our proposed method can achieve approximate 15 X speed up over the optimal budget method within the acceptable error tolerance. Also this algorithm only causes a few penalty area to compensate the leakage effect.     

Incorporation of Multiport Lumped Networks Into the Hybrid Time-Domain Finite-Element Analysis

A systematic and efficient algorithm is presented for incorporating multiport lumped networks in terms of admittance matrices into a hybrid field-circuit solver based on the extended time-domain finite-element method. The Laplace-domain admittance matrices are cast into the time-domain stepping equations for port voltages and currents to form a lumped-network subsystem, which is then interfaced with the finite-element and circuit subsystems through shared ports. While the port voltages of the lumped-network subsystem are determined by the finite-element and circuit subsystems, its port currents are treated as external current excitations for the finite-element and circuit subsystems. All the lumped-network port variables are then eliminated from the final expressions to form a global system for only the finite-element and circuit unknowns. The proposed algorithm further extends the capability of the existing field-circuit solver to model more complex and mixed-scale hybrid circuits, and the algorithm is validated and demonstrated through numerical examples.      

Blind time-domain equalizer for doubly-selective channel with reduced time averaging and computational complexity

This study presents a blind time-domain equalizer for a CP-free multiuser/MIMO-OFDM system over a doubly selective fast-fading channel, which enables a pertinent trade-off in error performance and complexity. A high-velocity outdoor system is considered, such as a vehicular user in which the channel varies too rapidly to be tracked. The proposed method applies the computationally efficient modified recursive Cholesky (RChol) algorithm incorporating a linear predictor and the LMMSE criteria, which scales down the correlation matrix time averaging and hence results in a significantly computationally efficient algorithm for the multiuser/MIMO-OFDM time-domain equalizer. The method reduces the effect of any perturbation introduced by the linear prediction, noise, and multipath. The performance of the proposed method is analyzed and compared with those of the existing pilot-based, semi-blind, and blind methods. The results show that the proposed RChol algorithm is computationally efficient compared with the existing subspace-based and linear prediction-based methods.     

An optimal algorithm for cycle breaking in directed graphs

This paper describes an exact algorithm for the identification of a minimal feedback vertex set in digital circuits. The proposed algorithm makes use of graph reduction and efficient graph partitioning methods based on local properties of digital circuits. It has been implemented and applied to ISCAS-89 benchmark circuits. Previously, non-optimum solutions were found. In other cases, the optimality of the solution could not be established for all circuits. By using the proposed algorithm we obtained the optimum results for all the circuits in a relatively short CPU time.Supported in part by the Technion fund for the promotion of research.     

Efficient finite-element-based time-domain beam propagation analysis of optical integrated circuits

In this paper, a novel numerically efficient time-domain beam propagation method based on the versatile finite element method (FETDBPM) is presented for the analysis of arbitrarily shaped optical integrated circuits. Lumping the global mass matrix into a diagonal matrix, an explicit full band finite-element time-domain propagation algorithm that needs only matrix-vector multiplication at each time step is derived. The accuracy and efficiency of the proposed FETDBPM is demonstrated through the analysis of propagation in different photonic integrated structures.     

Circuit analysis of electromagnetic radiation and field couplingeffects for networks with embedded full-wave modules

With continually increasing operating frequencies, the analysis of electromagnetic interference (EMI)-related effects is becoming an important issue for high-speed designs. An algorithm is presented for fast analysis of radiation and incident field coupling effects in high-speed circuits. The proposed technique provides an efficient means for combining the solutions from full-wave field solvers such as the finite-difference time-domain (FDTD) method with circuit level simulators such as SPICE for calculating radiated/coupled fields in arbitrarily shaped interconnect structures. The technique speeds up the whole simulation process by employing a model-reduction-based approach, and also overcomes the numerical stability problems associated with the FDTD, in the presence of nonlinear terminations. In addition, the proposed algorithm provides a direct access to existing vast device libraries of SPICE in EMI analysis     

Compact Macromodeling of High-Speed Circuits via Delayed Rational Functions

This letter introduces a new method for compact macromodeling of high-speed circuits with long delays, characterized by tabulated time-domain data. The algorithm is based on partitioning the response and subsequently approximating each partition with a low-order sum-of-exponentials, delayed in time-domain. This results in a compact low-order macromodel in the form of delayed-differential equations, which can be efficiently analyzed using SPICE like simulators.     

A Kernel‐Based Partitioning Algorithm for Low‐Power,Low‐Area Overhead Circuit Design Using Don't‐Care Sets

This letter proposes an efficient kernel‐based partitioning algorithm for reducing area and power dissipation in combinational circuit designs using don't‐care sets. The proposed algorithm decreases power dissipation by partitioning a given circuit using a kernel extracted from the logic. The proposed algorithm also reduces the area overhead by minimizing duplicated gates in the partitioned sub‐circuits. The partitioned subcircuits are further optimized utilizing observability don't‐care sets. Experimental results for the MCNC benchmarks show that the proposed algorithm synthesizes circuits that on the average consume 22.5% less power and have 12.7% less area than circuits generated by previous algorithms based on a precomputation scheme.     

Efficient sensitivity analysis of transmission-line networks usingmodel-reduction techniques

An efficient algorithm, based on congruent transformation and model reduction, is proposed for evaluation of frequency- and time-domain sensitivity of large linear networks containing lossy coupled transmission lines. The sensitivity of the voltage and current waveforms can be calculated with respect to lumped components and parameters of transmission lines. The algorithm is based on projecting the adjoint network equations on a reduced-order subspace that preserves the circuit moments. The proposed algorithm provides a significant decrease in the computational expense for sensitivity analysis     

Time-domain modeling of high-speed interconnects by modified methodof characteristics

In this paper, a new model of lossy transmission lines is presented for the time-domain simulation of high-speed interconnects. This model is based on the modified method of characteristics (MMC). The characteristic functions are first approximated by applying lower order Taylor series in the frequency domain, and then a set of simple recursive formulas are obtained in the time domain. The formulas, which involve tracking performances between two ends of a transmission line, are similar to those derived by the method of characteristics for lossless and undistorted lossy transmission lines. The algorithm, based on the proposed MMC model, can efficiently evaluate transient responses of high-speed interconnects. It only uses the quantities at two ends of the lines, requiring less computation time and less memory space than required by other methods. Examples indicate that the new method has high accuracy and is very efficient for the time-domain simulation of interconnects in high-speed integrated circuits     

An efficient heuristic force directed placement algorithm based on partitioning

An efficient heuristic force directed placement algorithm based on partitioning is proposed for very large-scale circuits. Our heuristic force directed approach provides a more efficient cell location adjustment scheme for iterative placement optimization than the force directed relaxation (FDR) method. We apply hierarchical partitioning based on a new parallel clustering technique to decompose circuit into several level sub-circuits. During the partitioning phase, a similar technique to ‘terminal propagation’ was introduced so as to maintain the external connections that affect cell adjustment in sub-circuit. In these lowest level sub-circuits, the heuristic force directed algorithm is used to perform iterative placement optimization. Then each pair of sub-circuits resulted from bisection combine into a larger one, in which cells are located as the best placement state of either sub-circuits. The bottom-up combination is done successively until back to the original circuit, and at each combination level the heuristic force directed placement algorithm is used to further improve the placement quality. A set of MCNC (Microelectronics Centre of North-Carolina) standard cell benchmarks is experimented and results show that our placement algorithm produces on average of 12% lower total wire length than that of Feng Shui with a little longer CPU time.     

A Time-Domain Approach for Extracting Broadband Macro- π Models of Differential Via Holes

A novel time-domain approach is proposed to synthesize the broadband macro-pi model of the differential vias based on time-domain reflected/transmitted waveforms either measured by time-domain reflectometry (TDR) or simulated by finite-difference time-domain (FDTD) method. The step responses of the differential via are solved in terms of rational functions by the generalized pencil-of-matrix (GPOM) method. The macro-pi model in terms of the rational functions pairs is obtained through an ABCD matrix transformation. The order of the macro-pi model can be reduced without losing the accuracy according to a residue criterion. The equivalent lumped circuits of the macro-pi model is synthesized by a lumped circuit extraction method (LCEM). The stability and passivity of the extracted models can be preserved based on this time-domain approach and the macro-pi topology. Two examples, one is an asymmentric via and the other is an differential via in four-layer PCB, are used to demonstrate the broadband accuracy of the proposed approach both in time-domain and frequency-domain     

Analysis of Heuristic Graph Partitioning Methods for the Assignment of Packet Control Units in GERAN

Over the last few years, graph partitioning has been recognized as a suitable technique for optimizing cellular network structure. For example, in a recent paper, the authors proposed a classical graph partitioning algorithm to optimize the assignment of cells to Packet Control Units (PCUs) in GSM-EDGE Radio Access Network. Based on this approach, the quality of packet data services in a live environment was increased by reducing the number of cell re-selections between different PCUs. To learn more about the potential of graph partitioning in cellular networks, in this paper, a more sophisticated, yet computationally efficient, partitioning algorithm is proposed for the same problem. The new method combines multi-level refinement and adaptive multi-start techniques with algorithms to ensure the connectivity between cells under the same PCU. Performance assessment is based on an extensive set of graphs constructed with data taken from a live network. During the tests, the new method is compared with classical graph partitioning approaches. Results show that the proposed method outperforms classical approaches in terms of solution quality at the expense of a slight increase in computing time, while providing solutions that are easier to check by the network operator.     

VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.     

A Multiple-Line Double Multirate Shooting Technique for the Simulation of Heterogeneous RF Circuits

This paper describes a computer-aided design tool especially conceived for the efficient time-domain simulation of strongly nonlinear mixed digital, baseband, and RF circuits operating in multiple time scales. The proposed numerical method is based on a 3-D envelope oriented technique over an innovative multiple-line double multirate shooting strategy, and is tested with an illustrative circuit example. Significant gains in computation speed over previous methods recently proposed for the simulation of this category of circuits are reported, as the technique was tailored to take advantage of the circuits' heterogeneity and stimulus time-rate disparity.      

Design and Implementation of Active Decoupling Capacitor Circuits for Power Supply Regulation in Digital ICs

Control of on-chip power supply noise has become a major challenge for continuous scaling of CMOS technology. Conventional passive decoupling capacitors (decaps) exhibit significant area and leakage penalties. To improve the efficiency of power supply regulation, this paper proposes a distributed active decap circuit for use in digital integrated circuits (ICs). The proposed design uses an operational amplifier to boost the performance of conventional decaps. Simulations proved its enhanced decoupling effect in comparison with passive decaps. The proposed active decap also shows advantages in providing additional damping to the on-chip resonant noise. To verify the performance from the proposed circuit, a 0.18-$mu$ m test chip with on-chip noise generators and sensors has been fabricated. Measurements show a 4-11$times$ boost in decap value over conventional passive decaps for frequencies up to 1 GHz with a total area saving of 40%. Local supply noise distribution and decap gating capability were also examined from the test chip.      

Diagnostics of Analog Circuits Based on LS-SVM Using Time-Domain Features

Most researchers use wavelet transforms to extract features from a time-domain transient response from analog circuits to train classifiers such as neural networks (NNs) and support vector machines (SVMs) for analog circuit diagnostics. In this paper, we have proposed some new feature selection methods from a time-domain transient response, and compared the diagnostic results based on a least squares SVM (LS-SVM) using different time-domain feature vectors. First, we have improved two traditional feature selection methods: (a) using the mean and standard deviation in wavelet transform features, and (b) using the mean, standard deviation, skewness, kurtosis, and entropy in statistical property features. Then, a conventional time-domain feature vector based on the impulse response properties of a control system has been proposed. The simulation experiments for a leapfrog filter and a nonlinear rectifier show that: (1) the two improved methods have better accuracy than the traditional methods; (2) the proposed conventional time-domain feature vector is effective in the diagnostics of analog circuits—over 99 % for both of the two example circuits; (3) the proposed diagnostic method can diagnose soft faults, hard faults, and multi-faults, regardless of component tolerances and nonlinearity effects.     

OFDM电力线通信系统的时域信道估计方法

针对G3-PLC协议,提出了两种改进的时域信道估计方法。为达到时域降噪效果,采用了预置电力线信道最大时延的方法,但这使得相关的时频变换矩阵不满秩,无法直接采用最小二乘准则估计其时域特性。因此,文中提出一种基于修正变换矩阵的时域LS算法,解决了矩阵不可逆问题。同时进一步提出了一种无需信道统计特性的时域线性最小均方误差算法,大幅降低了复杂度。仿真结果表明,修正的时域LS算法和简化的时域LMMSE算法均性能良好。     

Simulation of coupled interconnects using waveform relaxation and transverse partitioning

The large number of coupled lines in an interconnect structure is a serious limiting factor in simulating high-speed circuits. A new method is presented for efficient simulation of large interconnects based on transverse partitioning and waveform relaxation techniques. The computational cost of the proposed algorithm grows linearly with the number of coupled lines. In addition, the algorithm is highly suitable for parallel implementation leading to further significant reduction in the computational complexity.     

微波非线性电路稳态响应分析的理论与算法

本文建立了适于非线性微波电路ＣＡＡ与ＣＡＤ的谐波平衡算法，通过增广谐波平衡方程，微分线性化网络，非线性伴随网络等概念的引入，使得谐波平衡方程的求解和电路灵敏度的计算简捷，高效，概念清晰，且易于和已有的线性微波电路频域分析软件结合。提出了多级网络分析的松驰谐波平衡法，使得在一般的微机上可进行中等以下规模非线性微波电路的分析与设计。