We propose an electrostatics-based placement algorithm for large-scale mixed-size circuits (ePlace-MS). ePlace-MS is generalized, flat, analytic and nonlinear. The density modeling method eDensity is extended to handle the mixed-size placement. We conduct detailed analysis on the correctness of the gradient formulation and the numerical solution, as well as the rationale of dc removal and the advantages over prior density functions. Nesterov's method is used as the nonlinear solver, which shows high yet stable performance over mixed-size circuits. The steplength is set as the inverse of Lipschitz constant of the gradient function, while we develop a backtracking method to prevent overestimation. An approximated nonlinear preconditioner is developed to minimize the topological and physical differences between large macros and standard cells. Besides, we devise a simulated annealer to legalize the layout of macros and use a second-phase global placement to reoptimize the standard cell layout. All the above innovations are integrated into our mixed-size placement prototype ePlace-MS, which outperforms all the related works in literature with better quality and efficiency. Compared to the leading-edge mixed-size placer NTUplace3, ePlace-MS produces up to 22.98% and on average 8.22% shorter wirelength over all the 16 modern mixed-size benchmark circuits with the same runtime.

We develop a flat, analytic, and nonlinear placement algorithm, ePlace , which is more effective, generalized, simpler, and faster than previous works. Based on the analogy between placement instance and electrostatic system, we develop a novel placement density function eDensity , which models every object as positive charge and the density cost as the potential energy of the electrostatic system. The electric potential and field distribution are coupled with density using a well-defined Poisson's equation, which is numerically solved by spectral methods based on fast Fourier transform (FFT). Instead of using the conjugate gradient (CG) nonlinear solver in previous placers, we propose to use Nesterov's method which achieves faster convergence. The efficiency bottleneck on line search is resolved by predicting the steplength using a closed-form equation of Lipschitz constant. The placement performance is validated through experiments on the ISPD 2005 and ISPD 2006 benchmark suites, where ePlace outperforms all state-of-the-art placers (Capo10.5, FastPlace3.0, RQL, MAPLE, ComPLx, BonnPlace, POLAR, APlace3, NTUPlace3, mPL6) with much shorter wirelength and shorter or comparable runtime. On average, of all the ISPD 2005 benchmarks, ePlace outperforms the leading placer BonnPlace with 2.83% shorter wirelength and runs 3.05× faster; and on average, of all the ISPD 2006 benchmarks, ePlace outperforms the leading placer MAPLE with 4.59% shorter wirelength and runs 2.84× faster.

ePlace is a generalized analytic algorithm to handle large-scale standard-cell and mixed-size placement. We use a novel density function based on electrostatics to remove overlap and Nesterov's method to minimize the nonlinear cost. Steplength is estimated as the inverse of Lipschitz constant, which is determined by our dynamic prediction and backtracking method. An approximated preconditioner is proposed to resolve the difference between large macros and standard cells, while an annealing engine is devised to handle macro legalization followed by placement of standard cells. The above innovations are integrated into our placement prototype ePlace, which outperforms the leading-edge placers on respective standard-cell and mixed-size benchmark suites. Specifically, ePlace produces 2.83%, 4.59% and 7.13% shorter wirelength while runs 3.05×, 2.84× and 1.05× faster than BonnPlace, MAPLE and NTUplace3-unified in average of ISPD 2005, ISPD 2006 and MMS circuits, respectively.

Detecting overlapping of switching windows between coupling nets is a major static technique to accurately locate crosstalk noise. However, due to the mutual dependency between switching windows, the computation requires iterations to converge. In this paper, we discuss the issues and provide answers to the important questions involved in convergence and numerical properties, including the effect of coupling models, multiple convergence points, convergence rate, computational complexity, non-monotonicity, continuity and the effectiveness of bounds. Numerical fixed point computation results are used to explain these properties. Our contribution here builds a theoretical foundation for static crosstalk noise analysis.

In this paper, we present a new chip-level electrothermal timing simulator for CMOS VLSI circuits. Given the chip layout, the packaging specification, and the periodic input signal pattern, it finds the on-chip steady-state temperature profile and the resulting circuit performance. A tester chip has been designed for verification of ILLIADS-T, and very good agreement between simulation and experiment was found. Using this electrothermal simulator, temperature-dependent reliability and timing problems of VLSI circuits can be accurately identified.

In this paper, we present a new statistical technique for estimation of average power dissipation in digital circuits. The present parametric statistical technique estimates the average power based on the assumption that the power distribution can be characterized by a preassumed function. Large error can incur when the assumption is not met. On the other hand, the existing nonparametric technique, although accurate, is too conservative and requires a large sample size in order to achieve convergence. For a good tradeoff between simulation accuracy and computational efficiency, we propose a new nonparametric technique using the properties of the order statistics. It is generally applicable to any type of circuit irrespective of its power distribution function. Compared to the existing nonparametric technique, it is much more computationally efficient since it requires a much smaller sample size to achieve the same accuracy specification. This new technique is implemented in the distribution-independent power estimation tool (DIPE). DIPE is empirically demonstrated to be more robust and accurate than the parametric technique.

In this paper, we present a new statistical techniquefor estimating average power dissipation in sequential circuits.Due to the feedback mechanism, in sequential circuitspower dissipation in consecutive clock cycles are temporallycorrelated, which violates the basic requirement ofstatistical mean inference procedures. We overcome thisproblem by using a randomness test and a sequential procedureto select a proper independence interval, which in turnis used to generate random power samples. A distribution-independentstopping criterion is applied to analyze thesample data and terminate the simulation upon achievementof the accuracy specification. The technique is successfullyapplied to a set of benchmark circuits.

In this paper, we present a new electromigration reliability diagnosis tool (iTEM) for CMOS VLSI circuits. Unlike previous electromigration reliability tools, iTEM can estimate the interconnect temperature rise due to joule heating and heat conduction from the substrate using a newly developed lumped thermal model. By including the temperature effect, iTEM provides much more accurate electromigration reliability diagnosis. Moreover, it is computationally efficient, and can analyze circuit layouts containing tens of thousands of transistors on a desktop workstation.

In this paper, we present the first chip-level electrothermal simulator, iCET. For a given chip layout, packaging material, user-specified input signal patterns, and thermal boundary conditions, it automatically finds the CMOS on-chip steady-state temperature profile and the resulting circuit performance. iCET has been tested on several circuits and it can efficiently analyze layouts containing tens of thousands of transistors on a desktop workstation.

In this paper, we present a hierarchical reliability-driven CAD system for the design of electromigration resistant circuits.The top of the hierarchy aims at quickly identifying those critical interconnects with potential electromigration reliability problems.Then the detailed electromigration analysis of critical interconnects is carried out by an accurate and computationally ecient simulation tool (iTEM).This top-down approach provides a feasible solution to the complicated electromigration diagnosis problem.

We present a new statistical technique for estimation of average power dissipation in digital circuits. Present statistical techniques estimate the average power based on the assumption that the power distribution can be characterized by a preassumed function. A large error can result if the assumption is not met. To overcome this problem, we propose a nonparametric technique in which no distribution function needs to be assumed. A set of distribution-independent upper and lower bounds of the average power are developed using the properties derived from the order statistics. A stopping criterion is designed based on the bounds for a desired percentage error with a specified confidence level. Since it does not resort to assuming any particular distribution function, the technique can be applied to all circuits irrespective of their power distributions. Comparison is made against the present statistical technique based on the central limit theorem. Experimental results show that the proposed technique is much more accurate and robust, yet the efficiency characteristic of statistical techniques is still preserved.

In this paper, we present two learning mechanisms for artificial neural networks (ANN's) that can be applied to solve classification problems with binary outputs. These mechanisms are used to reduce the number of hidden units of an ANN when trained by the cascade-correlation learning algorithm (CAS). Since CAS adds hidden units incrementally as learning proceeds, it is difficult to predict the number of hidden units required when convergence is reached. Further, learning must be restarted when the number of hidden units is larger than expected. Our key idea in this paper is to provide alternatives in the learning process and to select the best alternative dynamically based on run-time information obtained. Mixed-mode learning (MM), our first algorithm, provides alternative output matrices so that learning is extended to find one of the many one-to-many mappings instead of finding a unique one-to-one mapping. Since the objective of learning is relaxed by this transformation, the number of learning epochs can be reduced. This in turn leads to a smaller number of hidden units required for convergence. Population-based learning for ANN's (PLAN), our second algorithm, maintains alternative network configurations to select at run time promising networks to train based on error information obtained and time remaining. This dynamic scheduling avoids training possibly unpromising ANNs to completion before exploring new ones. We show the performance of these two mechanisms by applying them to solve the two-spiral problem, a two-region classification problem, and the Pima Indian diabetes diagnosis problem.

In combinational logic circuits, a single switching event on the primary inputs may give rise to multiple switchings at the internal nodes. This glitching effect is caused primarily by unequal delay paths and results in increased power consumption and decreased device reliability. In this paper, we present a new algorithm to estimate the maximum number of transitions at internal nodes in combinational CMOS VLSI circuits. Unlike exhaustive simulation, our algorithm is based on the technique of propagating uncertainty waveforms throughout the circuit and using these waveforms to count the maximum switching activity at every node. Our approach guarantees a tight upper bound on the number of transitions which is necessary to assess the minimum circuit reliability lifetime and maximum power dissipation.

This paper presents a study of cache hashing functions for micro-parallel processors (e.g., superpipeline and super-scalar processors). Several novel cache hashing functions are experimented. Our simulation results show that an unconventional cache hashing function applied on a direct-mapped cache results in hit rates as good as a two-way set associative cache with traditional mapping, while the cache hit times are as fast as a direct-mapped cache with traditional mapping.